753 - A Plug for UNIX

[frk_styc]

There can be more than 300 plug names in the input - each of the 100 adapters may introduce up to two new plug names. Increase your MAX constant to something like a 500.

Also, your program does not print a blank line between test cases.

Oh I see! Now it's been accepted. Thank you very very much!

[mrbobguy]

I can't figure out what would be wrong with this one.

I basically build a graph of the different types of plug/outlet, there being an edge from A to B if A can be plugged into B. I then run a transitive closure algorithm to account for plugging adapters into adapters. Then I run bipartite matching algorithm.

Code follows:

Code: Select all

#include <iostream>
#include <map>
#include <string>
using namespace std;

    map<string, int> types;
    bool g[450][450];
    int to[100];
    int tpl[100];
    int adap[100][2];
    bool vis[100];
    int match[100];
    int npl;
    int nout;
    bool dfs(int i);

    int main() {
        int n; cin >> n;
        for (int cn = 0; cn < n; cn++) {
            types.clear();
            cin >> nout;
            int ctr = 0;

            // Read in outlets
            for (int i = 0; i < nout; i++) {
                string s; cin >> s;
                if (types.find(s)==types.end()) types[s]=ctr++;
                to[i] = types[s];
            }

            cin >> npl;
            // Read in plugs
            for (int i = 0; i < npl; i++) {
                string s; cin >> s >> s;
                if (types.find(s)==types.end()) types[s]=ctr++;
                tpl[i] = types[s];
            }

            int nad; cin >> nad;
            //Read in adapters
            for (int i = 0; i < nad; i++) {
                string s1,s2; cin >> s1 >> s2;
                if (types.find(s1)==types.end()) types[s1]=ctr++;
                if (types.find(s2)==types.end()) types[s2]=ctr++;
                adap[i][0] = types[s1]; adap[i][1] = types[s2];
            }

            for (int i = 0; i < ctr; i++) for (int j = 0; j < ctr; j++) g[i][j] = false;

            //Build graph
            for (int i = 0; i < ctr; i++) g[i][i] = true;
            for (int i = 0; i < nad; i++) {
                g[adap[i][0]][adap[i][1]] = true;
            }


            // Transitive closure
            for (int k = 0; k < ctr; k++) {
                for (int i = 0; i < ctr; i++) {
                    for (int j = 0; j < ctr; j++) {
                        if (g[i][k] && g[k][j]) g[i][j] = true;
                    }
                }
            }


            // transitive closure is done.
            // bipartite matching
            for (int i = 0; i < nout; i++) match[i]=-1;
            for (int i = 0; i < npl; i++) {
                for (int j = 0; j < npl; j++) vis[j]=false;
                dfs(i);
            }

            int count = 0;
            for (int i = 0; i < nout; i++) if (match[i]!=-1) count++;
            int ret = npl-count;
            cout << ret << endl;
            if (cn+1!=n) cout << endl;
        }

    }
    bool dfs(int i) {
        vis[i] = true;
        for (int j = 0; j < nout; j++) {
            if (g[tpl[i]][to[j]]) {
                if (match[j] == -1) {
                    match[j] = i; return true;
                }
                else if (!vis[match[j]] && dfs(match[j])) {
                    match[j] = i; return true;

                }
            }
        }
        return false;
    }

[kamiloj]

Ok, here are some test cases for this problem.

Input

Code: Select all

10

4
A
B
C
D
6
a 0
b 1
c 2
d 3
e 4
f 5
9
0 A
0 D
1 A
1 B
2 B
2 C
3 C
4 A
5 A

4
A
B
C
D
5
laptop B
phone C
pager B
clock B
comb X
3
B X
X A
X D

5
A
B
C
D
E
5
a 0
b 1
c 2
d 3
e 4
9
0 A
0 D
1 A
1 B
2 B
2 C
2 E
3 C
4 B

5
A
B
C
D
E
6
a C
b C
c C
d C
e A
f A
4
C E
E D
E B
B A

5
A
B
C
D
E
4
a W
b X
c Y
d Z
4
W X
X Y
Y Z
Z Q

30
r0
r1
r2
r3
r4
r5
r6
r7
r8
r9
r10
r11
r12
r13
r14
r15
r16
r17
r18
r19
r20
r21
r22
r23
r24
r25
r26
r27
r28
r29
30
d0 p0
d1 p1
d2 p2
d3 p3
d4 p4
d5 p5
d6 p6
d7 p7
d8 p8
d9 p9
d10 p10
d11 p11
d12 p12
d13 p13
d14 p14
d15 p15
d16 p16
d17 p17
d18 p18
d19 p19
d20 p20
d21 p21
d22 p22
d23 p23
d24 p24
d25 p25
d26 p26
d27 p27
d28 p28
d29 p29
100
p15 r19
p12 r21
p12 r11
p7 r2
p10 r16
p29 r4
p3 r17
p23 r28
p27 r1
p18 r2
p3 r29
p5 r8
p14 r9
p23 r0
p29 r0
p18 r14
p19 r22
p27 r24
p3 r5
p18 r5
p21 r10
p10 r17
p27 r25
p15 r16
p27 r4
p18 r22
p25 r15
p0 r9
p25 r23
p1 r16
p16 r11
p0 r27
p3 r19
p13 r29
p24 r2
p4 r8
p4 r6
p2 r2
p9 r21
p28 r19
p13 r24
p4 r14
p3 r21
p29 r27
p7 r15
p8 r29
p13 r12
p19 r18
p20 r7
p5 r16
p6 r22
p9 r8
p25 r18
p29 r15
p9 r4
p18 r13
p2 r25
p25 r10
p24 r0
p14 r5
p19 r17
p3 r1
p17 r8
p18 r15
p23 r27
p23 r10
p8 r14
p25 r7
p10 r21
p17 r12
p16 r4
p14 r10
p5 r21
p8 r24
p0 r11
p17 r17
p11 r5
p2 r26
p25 r17
p6 r25
p23 r24
p24 r12
p29 r28
p11 r1
p19 r20
p5 r5
p24 r19
p7 r21
p10 r7
p7 r11
p10 r25
p20 r22
p22 r15
p18 r17
p24 r17
p4 r18
p11 r29
p22 r2
p3 r8
p15 r0

100
r0
r1
r2
r3
r4
r5
r6
r7
r8
r9
r10
r11
r12
r13
r14
r15
r16
r17
r18
r19
r20
r21
r22
r23
r24
r25
r26
r27
r28
r29
r30
r31
r32
r33
r34
r35
r36
r37
r38
r39
r40
r41
r42
r43
r44
r45
r46
r47
r48
r49
r50
r51
r52
r53
r54
r55
r56
r57
r58
r59
r60
r61
r62
r63
r64
r65
r66
r67
r68
r69
r70
r71
r72
r73
r74
r75
r76
r77
r78
r79
r80
r81
r82
r83
r84
r85
r86
r87
r88
r89
r90
r91
r92
r93
r94
r95
r96
r97
r98
r99
100
d0 p0
d1 p1
d2 p2
d3 p3
d4 p4
d5 p5
d6 p6
d7 p7
d8 p8
d9 p9
d10 p10
d11 p11
d12 p12
d13 p13
d14 p14
d15 p15
d16 p16
d17 p17
d18 p18
d19 p19
d20 p20
d21 p21
d22 p22
d23 p23
d24 p24
d25 p25
d26 p26
d27 p27
d28 p28
d29 p29
d30 p30
d31 p31
d32 p32
d33 p33
d34 p34
d35 p35
d36 p36
d37 p37
d38 p38
d39 p39
d40 p40
d41 p41
d42 p42
d43 p43
d44 p44
d45 p45
d46 p46
d47 p47
d48 p48
d49 p49
d50 p50
d51 p51
d52 p52
d53 p53
d54 p54
d55 p55
d56 p56
d57 p57
d58 p58
d59 p59
d60 p60
d61 p61
d62 p62
d63 p63
d64 p64
d65 p65
d66 p66
d67 p67
d68 p68
d69 p69
d70 p70
d71 p71
d72 p72
d73 p73
d74 p74
d75 p75
d76 p76
d77 p77
d78 p78
d79 p79
d80 p80
d81 p81
d82 p82
d83 p83
d84 p84
d85 p85
d86 p86
d87 p87
d88 p88
d89 p89
d90 p90
d91 p91
d92 p92
d93 p93
d94 p94
d95 p95
d96 p96
d97 p97
d98 p98
d99 p99
100
p95 r21
p44 r99
p52 r5
p53 r24
p92 r32
p89 r20
p85 r45
p33 r32
p89 r45
p14 r38
p27 r77
p47 r32
p8 r99
p3 r50
p77 r78
p0 r72
p99 r96
p23 r4
p1 r29
p80 r45
p61 r70
p66 r99
p67 r99
p83 r8
p97 r98
p46 r76
p75 r93
p8 r35
p93 r11
p85 r70
p90 r37
p94 r41
p33 r69
p45 r87
p98 r26
p32 r12
p96 r98
p63 r15
p50 r46
p23 r99
p44 r69
p75 r20
p14 r84
p7 r7
p47 r45
p29 r37
p82 r23
p31 r68
p45 r76
p55 r43
p54 r87
p7 r2
p38 r22
p17 r40
p69 r40
p39 r65
p61 r66
p37 r76
p2 r45
p83 r50
p90 r65
p39 r24
p88 r70
p92 r33
p99 r47
p29 r53
p35 r88
p56 r25
p11 r73
p65 r32
p66 r56
p97 r27
p22 r87
p55 r25
p32 r91
p27 r74
p56 r66
p98 r96
p89 r91
p82 r88
p38 r11
p93 r25
p51 r49
p50 r14
p75 r67
p98 r41
p23 r48
p20 r98
p35 r28
p23 r67
p19 r2
p41 r75
p68 r91
p71 r9
p82 r53
p97 r73
p16 r91
p98 r20
p92 r1
p86 r67

20
r0
r1
r2
r3
r4
r5
r6
r7
r8
r9
r10
r11
r12
r13
r14
r15
r16
r17
r18
r19
20
d0 p0
d1 p1
d2 p2
d3 p3
d4 p4
d5 p5
d6 p6
d7 p7
d8 p8
d9 p9
d10 p10
d11 p11
d12 p12
d13 p13
d14 p14
d15 p15
d16 p16
d17 p17
d18 p18
d19 p19
20
p10 r7
p5 r1
p6 r10
p15 r2
p17 r9
p10 r3
p6 r3
p6 r14
p4 r16
p3 r5
p6 r17
p9 r4
p2 r19
p19 r0
p3 r1
p7 r0
p2 r6
p10 r10
p8 r19
p19 r19

3
A
B
C
5
a a
b b
c c
x p99
d d
100
p1 p0
p2 p1
p3 p2
p4 p3
p5 p4
p6 p5
p7 p6
p8 p7
p9 p8
p10 p9
p11 p10
p12 p11
p13 p12
p14 p13
p15 p14
p16 p15
p17 p16
p18 p17
p19 p18
p20 p19
p21 p20
p22 p21
p23 p22
p24 p23
p25 p24
p26 p25
p27 p26
p28 p27
p29 p28
p30 p29
p31 p30
p32 p31
p33 p32
p34 p33
p35 p34
p36 p35
p37 p36
p38 p37
p39 p38
p40 p39
p41 p40
p42 p41
p43 p42
p44 p43
p45 p44
p46 p45
p47 p46
p48 p47
p49 p48
p50 p49
p51 p50
p52 p51
p53 p52
p54 p53
p55 p54
p56 p55
p57 p56
p58 p57
p59 p58
p60 p59
p61 p60
p62 p61
p63 p62
p64 p63
p65 p64
p66 p65
p67 p66
p68 p67
p69 p68
p70 p69
p71 p70
p72 p71
p73 p72
p74 p73
p75 p74
p76 p75
p77 p76
p78 p77
p79 p78
p80 p79
p81 p80
p82 p81
p83 p82
p84 p83
p85 p84
p86 p85
p87 p86
p88 p87
p89 p88
p90 p89
p91 p90
p92 p91
p93 p92
p94 p93
p95 p94
p96 p95
p97 p96
p98 p97
p99 p98
p0 A

100
a0
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
a12
a13
a14
a15
a16
a17
a18
a19
a20
a21
a22
a23
a24
a25
a26
a27
a28
a29
a30
a31
a32
a33
a34
a35
a36
a37
a38
a39
a40
a41
a42
a43
a44
a45
a46
a47
a48
a49
a50
a51
a52
a53
a54
a55
a56
a57
a58
a59
a60
a61
a62
a63
a64
a65
a66
a67
a68
a69
a70
a71
a72
a73
a74
a75
a76
a77
a78
a79
a80
a81
a82
a83
a84
a85
a86
a87
a88
a89
a90
a91
a92
a93
a94
a95
a96
a97
a98
a99
100
b0 c0
b1 c1
b2 c2
b3 c3
b4 c4
b5 c5
b6 c6
b7 c7
b8 c8
b9 c9
b10 c10
b11 c11
b12 c12
b13 c13
b14 c14
b15 c15
b16 c16
b17 c17
b18 c18
b19 c19
b20 c20
b21 c21
b22 c22
b23 c23
b24 c24
b25 c25
b26 c26
b27 c27
b28 c28
b29 c29
b30 c30
b31 c31
b32 c32
b33 c33
b34 c34
b35 c35
b36 c36
b37 c37
b38 c38
b39 c39
b40 c40
b41 c41
b42 c42
b43 c43
b44 c44
b45 c45
b46 c46
b47 c47
b48 c48
b49 c49
b50 c50
b51 c51
b52 c52
b53 c53
b54 c54
b55 c55
b56 c56
b57 c57
b58 c58
b59 c59
b60 c60
b61 c61
b62 c62
b63 c63
b64 c64
b65 c65
b66 c66
b67 c67
b68 c68
b69 c69
b70 c70
b71 c71
b72 c72
b73 c73
b74 c74
b75 c75
b76 c76
b77 c77
b78 c78
b79 c79
b80 c80
b81 c81
b82 c82
b83 c83
b84 c84
b85 c85
b86 c86
b87 c87
b88 c88
b89 c89
b90 c90
b91 c91
b92 c92
b93 c93
b94 c94
b95 c95
b96 c96
b97 c97
b98 c98
b99 c99
100
d0 e0
d1 e1
d2 e2
d3 e3
d4 e4
d5 e5
d6 e6
d7 e7
d8 e8
d9 e9
d10 e10
d11 e11
d12 e12
d13 e13
d14 e14
d15 e15
d16 e16
d17 e17
d18 e18
d19 e19
d20 e20
d21 e21
d22 e22
d23 e23
d24 e24
d25 e25
d26 e26
d27 e27
d28 e28
d29 e29
d30 e30
d31 e31
d32 e32
d33 e33
d34 e34
d35 e35
d36 e36
d37 e37
d38 e38
d39 e39
d40 e40
d41 e41
d42 e42
d43 e43
d44 e44
d45 e45
d46 e46
d47 e47
d48 e48
d49 e49
d50 e50
d51 e51
d52 e52
d53 e53
d54 e54
d55 e55
d56 e56
d57 e57
d58 e58
d59 e59
d60 e60
d61 e61
d62 e62
d63 e63
d64 e64
d65 e65
d66 e66
d67 e67
d68 e68
d69 e69
d70 e70
d71 e71
d72 e72
d73 e73
d74 e74
d75 e75
d76 e76
d77 e77
d78 e78
d79 e79
d80 e80
d81 e81
d82 e82
d83 e83
d84 e84
d85 e85
d86 e86
d87 e87
d88 e88
d89 e89
d90 e90
d91 e91
d92 e92
d93 e93
d94 e94
d95 e95
d96 e96
d97 e97
d98 e98
d99 e99

Output

Code: Select all

2

1

0

1

4

2

49

9

4

100

[@li_kuet]

Who r getting WA can try this
Input :

Code: Select all

1

4
A
B
C
D
4
Laptop B
Mobile B
Camera B
Clock C
3
B A
B C
B D

Output :

Code: Select all

0

[vsha041]

Here is some input - output for those getting WA. Also note that you don't need to use edmonds-karp/ford-fulkerson algorithm to solve this problem. It's a bipartite graph and can be solved by an n^3 algorithm explained here.

http://www.geeksforgeeks.org/maximum-bi ... -matching/

Output for this input is verified through here -> http://www.uvatoolkit.com/problemssolve.php
Also my AC program runs in around 0.016 seconds for this input.

Also note that receptor names and device names are unique for the judge data. Although problem description doesn't specifies that for receptor names specifically.

To solve it, you can construct the general graph first and then run BFS from every device. If a device say laptop connects to B, then don't run BFS again for pager because both laptop and pager will have same adjacency list as they connect to B. Once you do that you will get a bipartite graph like this:

laptop -> A,B,D
phone -> C
pager -> A,B,D
clock -> A,B,D
comb -> A,D

Now just run the MCBM algorithm and subtract the result from number of devices.

Sample Input

Code: Select all

10

4
_44_
_yty_
C
_ze_yty_r_44__
5
l_44__h_to_h_ _yty_
_h_hone C
_h__44_ge_cow_ _yty_
clock _yty_
com_yty_ X
3
_yty_ X
X _44_
X _ze_yty_r_44__

5
_44_
_yty_
C
_ze_yty_r_44__
E
5
_44_ 0
_yty_ 1
c 2
_ze_yty_r_44__ 3
e 4
9
0 _44_
0 _ze_yty_r_44__
1 _44_
1 _yty_
2 _yty_
2 C
2 E
3 C
4 _yty_

5
_44_
_yty_
C
_ze_yty_r_44__
E
6
_44_ C
_yty_ C
c C
_ze_yty_r_44__ C
e _44_
f _44_
4
C E
E _ze_yty_r_44__
E _yty_
_yty_ _44_

5
_44_
_yty_
C
_ze_yty_r_44__
E
4
_44_ W
_yty_ X
c Y
_ze_yty_r_44__ Z
4
W X
X Y
Y Z
Z Q

30
_cow_0
_cow_1
_cow_2
_cow_3
_cow_4
_cow_5
_cow_6
_cow_7
_cow_8
_cow_9
_cow_10
_cow_11
_cow_12
_cow_13
_cow_14
_cow_15
_cow_16
_cow_17
_cow_18
_cow_19
_cow_20
_cow_21
_cow_22
_cow_23
_cow_24
_cow_25
_cow_26
_cow_27
_cow_28
_cow_29
30
_ze_yty_r_44__0 _h_0
_ze_yty_r_44__1 _h_1
_ze_yty_r_44__2 _h_2
_ze_yty_r_44__3 _h_3
_ze_yty_r_44__4 _h_4
_ze_yty_r_44__5 _h_5
_ze_yty_r_44__6 _h_6
_ze_yty_r_44__7 _h_7
_ze_yty_r_44__8 _h_8
_ze_yty_r_44__9 _h_9
_ze_yty_r_44__10 _h_10
_ze_yty_r_44__11 _h_11
_ze_yty_r_44__12 _h_12
_ze_yty_r_44__13 _h_13
_ze_yty_r_44__14 _h_14
_ze_yty_r_44__15 _h_15
_ze_yty_r_44__16 _h_16
_ze_yty_r_44__17 _h_17
_ze_yty_r_44__18 _h_18
_ze_yty_r_44__19 _h_19
_ze_yty_r_44__20 _h_20
_ze_yty_r_44__21 _h_21
_ze_yty_r_44__22 _h_22
_ze_yty_r_44__23 _h_23
_ze_yty_r_44__24 _h_24
_ze_yty_r_44__25 _h_25
_ze_yty_r_44__26 _h_26
_ze_yty_r_44__27 _h_27
_ze_yty_r_44__28 _h_28
_ze_yty_r_44__29 _h_29
100
_h_15 _cow_19
_h_12 _cow_21
_h_12 _cow_11
_h_7 _cow_2
_h_10 _cow_16
_h_29 _cow_4
_h_3 _cow_17
_h_23 _cow_28
_h_27 _cow_1
_h_18 _cow_2
_h_3 _cow_29
_h_5 _cow_8
_h_14 _cow_9
_h_23 _cow_0
_h_29 _cow_0
_h_18 _cow_14
_h_19 _cow_22
_h_27 _cow_24
_h_3 _cow_5
_h_18 _cow_5
_h_21 _cow_10
_h_10 _cow_17
_h_27 _cow_25
_h_15 _cow_16
_h_27 _cow_4
_h_18 _cow_22
_h_25 _cow_15
_h_0 _cow_9
_h_25 _cow_23
_h_1 _cow_16
_h_16 _cow_11
_h_0 _cow_27
_h_3 _cow_19
_h_13 _cow_29
_h_24 _cow_2
_h_4 _cow_8
_h_4 _cow_6
_h_2 _cow_2
_h_9 _cow_21
_h_28 _cow_19
_h_13 _cow_24
_h_4 _cow_14
_h_3 _cow_21
_h_29 _cow_27
_h_7 _cow_15
_h_8 _cow_29
_h_13 _cow_12
_h_19 _cow_18
_h_20 _cow_7
_h_5 _cow_16
_h_6 _cow_22
_h_9 _cow_8
_h_25 _cow_18
_h_29 _cow_15
_h_9 _cow_4
_h_18 _cow_13
_h_2 _cow_25
_h_25 _cow_10
_h_24 _cow_0
_h_14 _cow_5
_h_19 _cow_17
_h_3 _cow_1
_h_17 _cow_8
_h_18 _cow_15
_h_23 _cow_27
_h_23 _cow_10
_h_8 _cow_14
_h_25 _cow_7
_h_10 _cow_21
_h_17 _cow_12
_h_16 _cow_4
_h_14 _cow_10
_h_5 _cow_21
_h_8 _cow_24
_h_0 _cow_11
_h_17 _cow_17
_h_11 _cow_5
_h_2 _cow_26
_h_25 _cow_17
_h_6 _cow_25
_h_23 _cow_24
_h_24 _cow_12
_h_29 _cow_28
_h_11 _cow_1
_h_19 _cow_20
_h_5 _cow_5
_h_24 _cow_19
_h_7 _cow_21
_h_10 _cow_7
_h_7 _cow_11
_h_10 _cow_25
_h_20 _cow_22
_h_22 _cow_15
_h_18 _cow_17
_h_24 _cow_17
_h_4 _cow_18
_h_11 _cow_29
_h_22 _cow_2
_h_3 _cow_8
_h_15 _cow_0

100
_cow_0
_cow_1
_cow_2
_cow_3
_cow_4
_cow_5
_cow_6
_cow_7
_cow_8
_cow_9
_cow_10
_cow_11
_cow_12
_cow_13
_cow_14
_cow_15
_cow_16
_cow_17
_cow_18
_cow_19
_cow_20
_cow_21
_cow_22
_cow_23
_cow_24
_cow_25
_cow_26
_cow_27
_cow_28
_cow_29
_cow_30
_cow_31
_cow_32
_cow_33
_cow_34
_cow_35
_cow_36
_cow_37
_cow_38
_cow_39
_cow_40
_cow_41
_cow_42
_cow_43
_cow_44
_cow_45
_cow_46
_cow_47
_cow_48
_cow_49
_cow_50
_cow_51
_cow_52
_cow_53
_cow_54
_cow_55
_cow_56
_cow_57
_cow_58
_cow_59
_cow_60
_cow_61
_cow_62
_cow_63
_cow_64
_cow_65
_cow_66
_cow_67
_cow_68
_cow_69
_cow_70
_cow_71
_cow_72
_cow_73
_cow_74
_cow_75
_cow_76
_cow_77
_cow_78
_cow_79
_cow_80
_cow_81
_cow_82
_cow_83
_cow_84
_cow_85
_cow_86
_cow_87
_cow_88
_cow_89
_cow_90
_cow_91
_cow_92
_cow_93
_cow_94
_cow_95
_cow_96
_cow_97
_cow_98
_cow_99
100
_ze_yty_r_44__0 _h_0
_ze_yty_r_44__1 _h_1
_ze_yty_r_44__2 _h_2
_ze_yty_r_44__3 _h_3
_ze_yty_r_44__4 _h_4
_ze_yty_r_44__5 _h_5
_ze_yty_r_44__6 _h_6
_ze_yty_r_44__7 _h_7
_ze_yty_r_44__8 _h_8
_ze_yty_r_44__9 _h_9
_ze_yty_r_44__10 _h_10
_ze_yty_r_44__11 _h_11
_ze_yty_r_44__12 _h_12
_ze_yty_r_44__13 _h_13
_ze_yty_r_44__14 _h_14
_ze_yty_r_44__15 _h_15
_ze_yty_r_44__16 _h_16
_ze_yty_r_44__17 _h_17
_ze_yty_r_44__18 _h_18
_ze_yty_r_44__19 _h_19
_ze_yty_r_44__20 _h_20
_ze_yty_r_44__21 _h_21
_ze_yty_r_44__22 _h_22
_ze_yty_r_44__23 _h_23
_ze_yty_r_44__24 _h_24
_ze_yty_r_44__25 _h_25
_ze_yty_r_44__26 _h_26
_ze_yty_r_44__27 _h_27
_ze_yty_r_44__28 _h_28
_ze_yty_r_44__29 _h_29
_ze_yty_r_44__30 _h_30
_ze_yty_r_44__31 _h_31
_ze_yty_r_44__32 _h_32
_ze_yty_r_44__33 _h_33
_ze_yty_r_44__34 _h_34
_ze_yty_r_44__35 _h_35
_ze_yty_r_44__36 _h_36
_ze_yty_r_44__37 _h_37
_ze_yty_r_44__38 _h_38
_ze_yty_r_44__39 _h_39
_ze_yty_r_44__40 _h_40
_ze_yty_r_44__41 _h_41
_ze_yty_r_44__42 _h_42
_ze_yty_r_44__43 _h_43
_ze_yty_r_44__44 _h_44
_ze_yty_r_44__45 _h_45
_ze_yty_r_44__46 _h_46
_ze_yty_r_44__47 _h_47
_ze_yty_r_44__48 _h_48
_ze_yty_r_44__49 _h_49
_ze_yty_r_44__50 _h_50
_ze_yty_r_44__51 _h_51
_ze_yty_r_44__52 _h_52
_ze_yty_r_44__53 _h_53
_ze_yty_r_44__54 _h_54
_ze_yty_r_44__55 _h_55
_ze_yty_r_44__56 _h_56
_ze_yty_r_44__57 _h_57
_ze_yty_r_44__58 _h_58
_ze_yty_r_44__59 _h_59
_ze_yty_r_44__60 _h_60
_ze_yty_r_44__61 _h_61
_ze_yty_r_44__62 _h_62
_ze_yty_r_44__63 _h_63
_ze_yty_r_44__64 _h_64
_ze_yty_r_44__65 _h_65
_ze_yty_r_44__66 _h_66
_ze_yty_r_44__67 _h_67
_ze_yty_r_44__68 _h_68
_ze_yty_r_44__69 _h_69
_ze_yty_r_44__70 _h_70
_ze_yty_r_44__71 _h_71
_ze_yty_r_44__72 _h_72
_ze_yty_r_44__73 _h_73
_ze_yty_r_44__74 _h_74
_ze_yty_r_44__75 _h_75
_ze_yty_r_44__76 _h_76
_ze_yty_r_44__77 _h_77
_ze_yty_r_44__78 _h_78
_ze_yty_r_44__79 _h_79
_ze_yty_r_44__80 _h_80
_ze_yty_r_44__81 _h_81
_ze_yty_r_44__82 _h_82
_ze_yty_r_44__83 _h_83
_ze_yty_r_44__84 _h_84
_ze_yty_r_44__85 _h_85
_ze_yty_r_44__86 _h_86
_ze_yty_r_44__87 _h_87
_ze_yty_r_44__88 _h_88
_ze_yty_r_44__89 _h_89
_ze_yty_r_44__90 _h_90
_ze_yty_r_44__91 _h_91
_ze_yty_r_44__92 _h_92
_ze_yty_r_44__93 _h_93
_ze_yty_r_44__94 _h_94
_ze_yty_r_44__95 _h_95
_ze_yty_r_44__96 _h_96
_ze_yty_r_44__97 _h_97
_ze_yty_r_44__98 _h_98
_ze_yty_r_44__99 _h_99
100
_h_95 _cow_21
_h_44 _cow_99
_h_52 _cow_5
_h_53 _cow_24
_h_92 _cow_32
_h_89 _cow_20
_h_85 _cow_45
_h_33 _cow_32
_h_89 _cow_45
_h_14 _cow_38
_h_27 _cow_77
_h_47 _cow_32
_h_8 _cow_99
_h_3 _cow_50
_h_77 _cow_78
_h_0 _cow_72
_h_99 _cow_96
_h_23 _cow_4
_h_1 _cow_29
_h_80 _cow_45
_h_61 _cow_70
_h_66 _cow_99
_h_67 _cow_99
_h_83 _cow_8
_h_97 _cow_98
_h_46 _cow_76
_h_75 _cow_93
_h_8 _cow_35
_h_93 _cow_11
_h_85 _cow_70
_h_90 _cow_37
_h_94 _cow_41
_h_33 _cow_69
_h_45 _cow_87
_h_98 _cow_26
_h_32 _cow_12
_h_96 _cow_98
_h_63 _cow_15
_h_50 _cow_46
_h_23 _cow_99
_h_44 _cow_69
_h_75 _cow_20
_h_14 _cow_84
_h_7 _cow_7
_h_47 _cow_45
_h_29 _cow_37
_h_82 _cow_23
_h_31 _cow_68
_h_45 _cow_76
_h_55 _cow_43
_h_54 _cow_87
_h_7 _cow_2
_h_38 _cow_22
_h_17 _cow_40
_h_69 _cow_40
_h_39 _cow_65
_h_61 _cow_66
_h_37 _cow_76
_h_2 _cow_45
_h_83 _cow_50
_h_90 _cow_65
_h_39 _cow_24
_h_88 _cow_70
_h_92 _cow_33
_h_99 _cow_47
_h_29 _cow_53
_h_35 _cow_88
_h_56 _cow_25
_h_11 _cow_73
_h_65 _cow_32
_h_66 _cow_56
_h_97 _cow_27
_h_22 _cow_87
_h_55 _cow_25
_h_32 _cow_91
_h_27 _cow_74
_h_56 _cow_66
_h_98 _cow_96
_h_89 _cow_91
_h_82 _cow_88
_h_38 _cow_11
_h_93 _cow_25
_h_51 _cow_49
_h_50 _cow_14
_h_75 _cow_67
_h_98 _cow_41
_h_23 _cow_48
_h_20 _cow_98
_h_35 _cow_28
_h_23 _cow_67
_h_19 _cow_2
_h_41 _cow_75
_h_68 _cow_91
_h_71 _cow_9
_h_82 _cow_53
_h_97 _cow_73
_h_16 _cow_91
_h_98 _cow_20
_h_92 _cow_1
_h_86 _cow_67

20
_cow_0
_cow_1
_cow_2
_cow_3
_cow_4
_cow_5
_cow_6
_cow_7
_cow_8
_cow_9
_cow_10
_cow_11
_cow_12
_cow_13
_cow_14
_cow_15
_cow_16
_cow_17
_cow_18
_cow_19
20
_ze_yty_r_44__0 _h_0
_ze_yty_r_44__1 _h_1
_ze_yty_r_44__2 _h_2
_ze_yty_r_44__3 _h_3
_ze_yty_r_44__4 _h_4
_ze_yty_r_44__5 _h_5
_ze_yty_r_44__6 _h_6
_ze_yty_r_44__7 _h_7
_ze_yty_r_44__8 _h_8
_ze_yty_r_44__9 _h_9
_ze_yty_r_44__10 _h_10
_ze_yty_r_44__11 _h_11
_ze_yty_r_44__12 _h_12
_ze_yty_r_44__13 _h_13
_ze_yty_r_44__14 _h_14
_ze_yty_r_44__15 _h_15
_ze_yty_r_44__16 _h_16
_ze_yty_r_44__17 _h_17
_ze_yty_r_44__18 _h_18
_ze_yty_r_44__19 _h_19
20
_h_10 _cow_7
_h_5 _cow_1
_h_6 _cow_10
_h_15 _cow_2
_h_17 _cow_9
_h_10 _cow_3
_h_6 _cow_3
_h_6 _cow_14
_h_4 _cow_16
_h_3 _cow_5
_h_6 _cow_17
_h_9 _cow_4
_h_2 _cow_19
_h_19 _cow_0
_h_3 _cow_1
_h_7 _cow_0
_h_2 _cow_6
_h_10 _cow_10
_h_8 _cow_19
_h_19 _cow_19

3
_44_
_yty_
C
5
_44_ _44_
_yty_ _yty_
c c
x _h_99
_ze_yty_r_44__ _ze_yty_r_44__
100
_h_1 _h_0
_h_2 _h_1
_h_3 _h_2
_h_4 _h_3
_h_5 _h_4
_h_6 _h_5
_h_7 _h_6
_h_8 _h_7
_h_9 _h_8
_h_10 _h_9
_h_11 _h_10
_h_12 _h_11
_h_13 _h_12
_h_14 _h_13
_h_15 _h_14
_h_16 _h_15
_h_17 _h_16
_h_18 _h_17
_h_19 _h_18
_h_20 _h_19
_h_21 _h_20
_h_22 _h_21
_h_23 _h_22
_h_24 _h_23
_h_25 _h_24
_h_26 _h_25
_h_27 _h_26
_h_28 _h_27
_h_29 _h_28
_h_30 _h_29
_h_31 _h_30
_h_32 _h_31
_h_33 _h_32
_h_34 _h_33
_h_35 _h_34
_h_36 _h_35
_h_37 _h_36
_h_38 _h_37
_h_39 _h_38
_h_40 _h_39
_h_41 _h_40
_h_42 _h_41
_h_43 _h_42
_h_44 _h_43
_h_45 _h_44
_h_46 _h_45
_h_47 _h_46
_h_48 _h_47
_h_49 _h_48
_h_50 _h_49
_h_51 _h_50
_h_52 _h_51
_h_53 _h_52
_h_54 _h_53
_h_55 _h_54
_h_56 _h_55
_h_57 _h_56
_h_58 _h_57
_h_59 _h_58
_h_60 _h_59
_h_61 _h_60
_h_62 _h_61
_h_63 _h_62
_h_64 _h_63
_h_65 _h_64
_h_66 _h_65
_h_67 _h_66
_h_68 _h_67
_h_69 _h_68
_h_70 _h_69
_h_71 _h_70
_h_72 _h_71
_h_73 _h_72
_h_74 _h_73
_h_75 _h_74
_h_76 _h_75
_h_77 _h_76
_h_78 _h_77
_h_79 _h_78
_h_80 _h_79
_h_81 _h_80
_h_82 _h_81
_h_83 _h_82
_h_84 _h_83
_h_85 _h_84
_h_86 _h_85
_h_87 _h_86
_h_88 _h_87
_h_89 _h_88
_h_90 _h_89
_h_91 _h_90
_h_92 _h_91
_h_93 _h_92
_h_94 _h_93
_h_95 _h_94
_h_96 _h_95
_h_97 _h_96
_h_98 _h_97
_h_99 _h_98
_h_0 _44_

100
_44_0
_44_1
_44_2
_44_3
_44_4
_44_5
_44_6
_44_7
_44_8
_44_9
_44_10
_44_11
_44_12
_44_13
_44_14
_44_15
_44_16
_44_17
_44_18
_44_19
_44_20
_44_21
_44_22
_44_23
_44_24
_44_25
_44_26
_44_27
_44_28
_44_29
_44_30
_44_31
_44_32
_44_33
_44_34
_44_35
_44_36
_44_37
_44_38
_44_39
_44_40
_44_41
_44_42
_44_43
_44_44
_44_45
_44_46
_44_47
_44_48
_44_49
_44_50
_44_51
_44_52
_44_53
_44_54
_44_55
_44_56
_44_57
_44_58
_44_59
_44_60
_44_61
_44_62
_44_63
_44_64
_44_65
_44_66
_44_67
_44_68
_44_69
_44_70
_44_71
_44_72
_44_73
_44_74
_44_75
_44_76
_44_77
_44_78
_44_79
_44_80
_44_81
_44_82
_44_83
_44_84
_44_85
_44_86
_44_87
_44_88
_44_89
_44_90
_44_91
_44_92
_44_93
_44_94
_44_95
_44_96
_44_97
_44_98
_44_99
100
_yty_0 c0
_yty_1 c1
_yty_2 c2
_yty_3 c3
_yty_4 c4
_yty_5 c5
_yty_6 c6
_yty_7 c7
_yty_8 c8
_yty_9 c9
_yty_10 c10
_yty_11 c11
_yty_12 c12
_yty_13 c13
_yty_14 c14
_yty_15 c15
_yty_16 c16
_yty_17 c17
_yty_18 c18
_yty_19 c19
_yty_20 c20
_yty_21 c21
_yty_22 c22
_yty_23 c23
_yty_24 c24
_yty_25 c25
_yty_26 c26
_yty_27 c27
_yty_28 c28
_yty_29 c29
_yty_30 c30
_yty_31 c31
_yty_32 c32
_yty_33 c33
_yty_34 c34
_yty_35 c35
_yty_36 c36
_yty_37 c37
_yty_38 c38
_yty_39 c39
_yty_40 c40
_yty_41 c41
_yty_42 c42
_yty_43 c43
_yty_44 c44
_yty_45 c45
_yty_46 c46
_yty_47 c47
_yty_48 c48
_yty_49 c49
_yty_50 c50
_yty_51 c51
_yty_52 c52
_yty_53 c53
_yty_54 c54
_yty_55 c55
_yty_56 c56
_yty_57 c57
_yty_58 c58
_yty_59 c59
_yty_60 c60
_yty_61 c61
_yty_62 c62
_yty_63 c63
_yty_64 c64
_yty_65 c65
_yty_66 c66
_yty_67 c67
_yty_68 c68
_yty_69 c69
_yty_70 c70
_yty_71 c71
_yty_72 c72
_yty_73 c73
_yty_74 c74
_yty_75 c75
_yty_76 c76
_yty_77 c77
_yty_78 c78
_yty_79 c79
_yty_80 c80
_yty_81 c81
_yty_82 c82
_yty_83 c83
_yty_84 c84
_yty_85 c85
_yty_86 c86
_yty_87 c87
_yty_88 c88
_yty_89 c89
_yty_90 c90
_yty_91 c91
_yty_92 c92
_yty_93 c93
_yty_94 c94
_yty_95 c95
_yty_96 c96
_yty_97 c97
_yty_98 c98
_yty_99 c99
100
_ze_yty_r_44__0 e0
_ze_yty_r_44__1 e1
_ze_yty_r_44__2 e2
_ze_yty_r_44__3 e3
_ze_yty_r_44__4 e4
_ze_yty_r_44__5 e5
_ze_yty_r_44__6 e6
_ze_yty_r_44__7 e7
_ze_yty_r_44__8 e8
_ze_yty_r_44__9 e9
_ze_yty_r_44__10 e10
_ze_yty_r_44__11 e11
_ze_yty_r_44__12 e12
_ze_yty_r_44__13 e13
_ze_yty_r_44__14 e14
_ze_yty_r_44__15 e15
_ze_yty_r_44__16 e16
_ze_yty_r_44__17 e17
_ze_yty_r_44__18 e18
_ze_yty_r_44__19 e19
_ze_yty_r_44__20 e20
_ze_yty_r_44__21 e21
_ze_yty_r_44__22 e22
_ze_yty_r_44__23 e23
_ze_yty_r_44__24 e24
_ze_yty_r_44__25 e25
_ze_yty_r_44__26 e26
_ze_yty_r_44__27 e27
_ze_yty_r_44__28 e28
_ze_yty_r_44__29 e29
_ze_yty_r_44__30 e30
_ze_yty_r_44__31 e31
_ze_yty_r_44__32 e32
_ze_yty_r_44__33 e33
_ze_yty_r_44__34 e34
_ze_yty_r_44__35 e35
_ze_yty_r_44__36 e36
_ze_yty_r_44__37 e37
_ze_yty_r_44__38 e38
_ze_yty_r_44__39 e39
_ze_yty_r_44__40 e40
_ze_yty_r_44__41 e41
_ze_yty_r_44__42 e42
_ze_yty_r_44__43 e43
_ze_yty_r_44__44 e44
_ze_yty_r_44__45 e45
_ze_yty_r_44__46 e46
_ze_yty_r_44__47 e47
_ze_yty_r_44__48 e48
_ze_yty_r_44__49 e49
_ze_yty_r_44__50 e50
_ze_yty_r_44__51 e51
_ze_yty_r_44__52 e52
_ze_yty_r_44__53 e53
_ze_yty_r_44__54 e54
_ze_yty_r_44__55 e55
_ze_yty_r_44__56 e56
_ze_yty_r_44__57 e57
_ze_yty_r_44__58 e58
_ze_yty_r_44__59 e59
_ze_yty_r_44__60 e60
_ze_yty_r_44__61 e61
_ze_yty_r_44__62 e62
_ze_yty_r_44__63 e63
_ze_yty_r_44__64 e64
_ze_yty_r_44__65 e65
_ze_yty_r_44__66 e66
_ze_yty_r_44__67 e67
_ze_yty_r_44__68 e68
_ze_yty_r_44__69 e69
_ze_yty_r_44__70 e70
_ze_yty_r_44__71 e71
_ze_yty_r_44__72 e72
_ze_yty_r_44__73 e73
_ze_yty_r_44__74 e74
_ze_yty_r_44__75 e75
_ze_yty_r_44__76 e76
_ze_yty_r_44__77 e77
_ze_yty_r_44__78 e78
_ze_yty_r_44__79 e79
_ze_yty_r_44__80 e80
_ze_yty_r_44__81 e81
_ze_yty_r_44__82 e82
_ze_yty_r_44__83 e83
_ze_yty_r_44__84 e84
_ze_yty_r_44__85 e85
_ze_yty_r_44__86 e86
_ze_yty_r_44__87 e87
_ze_yty_r_44__88 e88
_ze_yty_r_44__89 e89
_ze_yty_r_44__90 e90
_ze_yty_r_44__91 e91
_ze_yty_r_44__92 e92
_ze_yty_r_44__93 e93
_ze_yty_r_44__94 e94
_ze_yty_r_44__95 e95
_ze_yty_r_44__96 e96
_ze_yty_r_44__97 e97
_ze_yty_r_44__98 e98
_ze_yty_r_44__99 e99

4
_44_
_yty_
C
_ze_yty_r_44__
5
l_44__h_to_h_ _yty_
_h_hone C
_h__44_ge_cow_ _yty_
clock _yty_
com_yty_ X
3
_yty_ X
X _44_
X _ze_yty_r_44__

Sample Output

Code: Select all

1

0

1

4

2

49

9

4

100

1

[metaphysis]

Here is some input - output for those getting WA. Also note that you don't need to use edmonds-karp/ford-fulkerson algorithm to solve this problem. It's a bipartite graph and can be solved by an n^3 algorithm explained here.

http://www.geeksforgeeks.org/maximum-bi ... -matching/

Output for this input is verified through here -> http://www.uvatoolkit.com/problemssolve.php
Also my AC program runs in around 0.016 seconds for this input.

Also note that receptor names and device names are unique for the judge data. Although problem description doesn't specifies that for receptor names specifically.

To solve it, you can construct the general graph first and then run BFS from every device. If a device say laptop connects to B, then don't run BFS again for pager because both laptop and pager will have same adjacency list as they connect to B. Once you do that you will get a bipartite graph like this:

laptop -> A,B,D
phone -> C
pager -> A,B,D
clock -> A,B,D
comb -> A,D

Now just run the MCBM algorithm and subtract the result from number of devices.

Sample Input

Code: Select all

10

4
_44_
_yty_
C
_ze_yty_r_44__
5
l_44__h_to_h_ _yty_
_h_hone C
_h__44_ge_cow_ _yty_
clock _yty_
com_yty_ X
3
_yty_ X
X _44_
X _ze_yty_r_44__

5
_44_
_yty_
C
_ze_yty_r_44__
E
5
_44_ 0
_yty_ 1
c 2
_ze_yty_r_44__ 3
e 4
9
0 _44_
0 _ze_yty_r_44__
1 _44_
1 _yty_
2 _yty_
2 C
2 E
3 C
4 _yty_

5
_44_
_yty_
C
_ze_yty_r_44__
E
6
_44_ C
_yty_ C
c C
_ze_yty_r_44__ C
e _44_
f _44_
4
C E
E _ze_yty_r_44__
E _yty_
_yty_ _44_

5
_44_
_yty_
C
_ze_yty_r_44__
E
4
_44_ W
_yty_ X
c Y
_ze_yty_r_44__ Z
4
W X
X Y
Y Z
Z Q

30
_cow_0
_cow_1
_cow_2
_cow_3
_cow_4
_cow_5
_cow_6
_cow_7
_cow_8
_cow_9
_cow_10
_cow_11
_cow_12
_cow_13
_cow_14
_cow_15
_cow_16
_cow_17
_cow_18
_cow_19
_cow_20
_cow_21
_cow_22
_cow_23
_cow_24
_cow_25
_cow_26
_cow_27
_cow_28
_cow_29
30
_ze_yty_r_44__0 _h_0
_ze_yty_r_44__1 _h_1
_ze_yty_r_44__2 _h_2
_ze_yty_r_44__3 _h_3
_ze_yty_r_44__4 _h_4
_ze_yty_r_44__5 _h_5
_ze_yty_r_44__6 _h_6
_ze_yty_r_44__7 _h_7
_ze_yty_r_44__8 _h_8
_ze_yty_r_44__9 _h_9
_ze_yty_r_44__10 _h_10
_ze_yty_r_44__11 _h_11
_ze_yty_r_44__12 _h_12
_ze_yty_r_44__13 _h_13
_ze_yty_r_44__14 _h_14
_ze_yty_r_44__15 _h_15
_ze_yty_r_44__16 _h_16
_ze_yty_r_44__17 _h_17
_ze_yty_r_44__18 _h_18
_ze_yty_r_44__19 _h_19
_ze_yty_r_44__20 _h_20
_ze_yty_r_44__21 _h_21
_ze_yty_r_44__22 _h_22
_ze_yty_r_44__23 _h_23
_ze_yty_r_44__24 _h_24
_ze_yty_r_44__25 _h_25
_ze_yty_r_44__26 _h_26
_ze_yty_r_44__27 _h_27
_ze_yty_r_44__28 _h_28
_ze_yty_r_44__29 _h_29
100
_h_15 _cow_19
_h_12 _cow_21
_h_12 _cow_11
_h_7 _cow_2
_h_10 _cow_16
_h_29 _cow_4
_h_3 _cow_17
_h_23 _cow_28
_h_27 _cow_1
_h_18 _cow_2
_h_3 _cow_29
_h_5 _cow_8
_h_14 _cow_9
_h_23 _cow_0
_h_29 _cow_0
_h_18 _cow_14
_h_19 _cow_22
_h_27 _cow_24
_h_3 _cow_5
_h_18 _cow_5
_h_21 _cow_10
_h_10 _cow_17
_h_27 _cow_25
_h_15 _cow_16
_h_27 _cow_4
_h_18 _cow_22
_h_25 _cow_15
_h_0 _cow_9
_h_25 _cow_23
_h_1 _cow_16
_h_16 _cow_11
_h_0 _cow_27
_h_3 _cow_19
_h_13 _cow_29
_h_24 _cow_2
_h_4 _cow_8
_h_4 _cow_6
_h_2 _cow_2
_h_9 _cow_21
_h_28 _cow_19
_h_13 _cow_24
_h_4 _cow_14
_h_3 _cow_21
_h_29 _cow_27
_h_7 _cow_15
_h_8 _cow_29
_h_13 _cow_12
_h_19 _cow_18
_h_20 _cow_7
_h_5 _cow_16
_h_6 _cow_22
_h_9 _cow_8
_h_25 _cow_18
_h_29 _cow_15
_h_9 _cow_4
_h_18 _cow_13
_h_2 _cow_25
_h_25 _cow_10
_h_24 _cow_0
_h_14 _cow_5
_h_19 _cow_17
_h_3 _cow_1
_h_17 _cow_8
_h_18 _cow_15
_h_23 _cow_27
_h_23 _cow_10
_h_8 _cow_14
_h_25 _cow_7
_h_10 _cow_21
_h_17 _cow_12
_h_16 _cow_4
_h_14 _cow_10
_h_5 _cow_21
_h_8 _cow_24
_h_0 _cow_11
_h_17 _cow_17
_h_11 _cow_5
_h_2 _cow_26
_h_25 _cow_17
_h_6 _cow_25
_h_23 _cow_24
_h_24 _cow_12
_h_29 _cow_28
_h_11 _cow_1
_h_19 _cow_20
_h_5 _cow_5
_h_24 _cow_19
_h_7 _cow_21
_h_10 _cow_7
_h_7 _cow_11
_h_10 _cow_25
_h_20 _cow_22
_h_22 _cow_15
_h_18 _cow_17
_h_24 _cow_17
_h_4 _cow_18
_h_11 _cow_29
_h_22 _cow_2
_h_3 _cow_8
_h_15 _cow_0

100
_cow_0
_cow_1
_cow_2
_cow_3
_cow_4
_cow_5
_cow_6
_cow_7
_cow_8
_cow_9
_cow_10
_cow_11
_cow_12
_cow_13
_cow_14
_cow_15
_cow_16
_cow_17
_cow_18
_cow_19
_cow_20
_cow_21
_cow_22
_cow_23
_cow_24
_cow_25
_cow_26
_cow_27
_cow_28
_cow_29
_cow_30
_cow_31
_cow_32
_cow_33
_cow_34
_cow_35
_cow_36
_cow_37
_cow_38
_cow_39
_cow_40
_cow_41
_cow_42
_cow_43
_cow_44
_cow_45
_cow_46
_cow_47
_cow_48
_cow_49
_cow_50
_cow_51
_cow_52
_cow_53
_cow_54
_cow_55
_cow_56
_cow_57
_cow_58
_cow_59
_cow_60
_cow_61
_cow_62
_cow_63
_cow_64
_cow_65
_cow_66
_cow_67
_cow_68
_cow_69
_cow_70
_cow_71
_cow_72
_cow_73
_cow_74
_cow_75
_cow_76
_cow_77
_cow_78
_cow_79
_cow_80
_cow_81
_cow_82
_cow_83
_cow_84
_cow_85
_cow_86
_cow_87
_cow_88
_cow_89
_cow_90
_cow_91
_cow_92
_cow_93
_cow_94
_cow_95
_cow_96
_cow_97
_cow_98
_cow_99
100
_ze_yty_r_44__0 _h_0
_ze_yty_r_44__1 _h_1
_ze_yty_r_44__2 _h_2
_ze_yty_r_44__3 _h_3
_ze_yty_r_44__4 _h_4
_ze_yty_r_44__5 _h_5
_ze_yty_r_44__6 _h_6
_ze_yty_r_44__7 _h_7
_ze_yty_r_44__8 _h_8
_ze_yty_r_44__9 _h_9
_ze_yty_r_44__10 _h_10
_ze_yty_r_44__11 _h_11
_ze_yty_r_44__12 _h_12
_ze_yty_r_44__13 _h_13
_ze_yty_r_44__14 _h_14
_ze_yty_r_44__15 _h_15
_ze_yty_r_44__16 _h_16
_ze_yty_r_44__17 _h_17
_ze_yty_r_44__18 _h_18
_ze_yty_r_44__19 _h_19
_ze_yty_r_44__20 _h_20
_ze_yty_r_44__21 _h_21
_ze_yty_r_44__22 _h_22
_ze_yty_r_44__23 _h_23
_ze_yty_r_44__24 _h_24
_ze_yty_r_44__25 _h_25
_ze_yty_r_44__26 _h_26
_ze_yty_r_44__27 _h_27
_ze_yty_r_44__28 _h_28
_ze_yty_r_44__29 _h_29
_ze_yty_r_44__30 _h_30
_ze_yty_r_44__31 _h_31
_ze_yty_r_44__32 _h_32
_ze_yty_r_44__33 _h_33
_ze_yty_r_44__34 _h_34
_ze_yty_r_44__35 _h_35
_ze_yty_r_44__36 _h_36
_ze_yty_r_44__37 _h_37
_ze_yty_r_44__38 _h_38
_ze_yty_r_44__39 _h_39
_ze_yty_r_44__40 _h_40
_ze_yty_r_44__41 _h_41
_ze_yty_r_44__42 _h_42
_ze_yty_r_44__43 _h_43
_ze_yty_r_44__44 _h_44
_ze_yty_r_44__45 _h_45
_ze_yty_r_44__46 _h_46
_ze_yty_r_44__47 _h_47
_ze_yty_r_44__48 _h_48
_ze_yty_r_44__49 _h_49
_ze_yty_r_44__50 _h_50
_ze_yty_r_44__51 _h_51
_ze_yty_r_44__52 _h_52
_ze_yty_r_44__53 _h_53
_ze_yty_r_44__54 _h_54
_ze_yty_r_44__55 _h_55
_ze_yty_r_44__56 _h_56
_ze_yty_r_44__57 _h_57
_ze_yty_r_44__58 _h_58
_ze_yty_r_44__59 _h_59
_ze_yty_r_44__60 _h_60
_ze_yty_r_44__61 _h_61
_ze_yty_r_44__62 _h_62
_ze_yty_r_44__63 _h_63
_ze_yty_r_44__64 _h_64
_ze_yty_r_44__65 _h_65
_ze_yty_r_44__66 _h_66
_ze_yty_r_44__67 _h_67
_ze_yty_r_44__68 _h_68
_ze_yty_r_44__69 _h_69
_ze_yty_r_44__70 _h_70
_ze_yty_r_44__71 _h_71
_ze_yty_r_44__72 _h_72
_ze_yty_r_44__73 _h_73
_ze_yty_r_44__74 _h_74
_ze_yty_r_44__75 _h_75
_ze_yty_r_44__76 _h_76
_ze_yty_r_44__77 _h_77
_ze_yty_r_44__78 _h_78
_ze_yty_r_44__79 _h_79
_ze_yty_r_44__80 _h_80
_ze_yty_r_44__81 _h_81
_ze_yty_r_44__82 _h_82
_ze_yty_r_44__83 _h_83
_ze_yty_r_44__84 _h_84
_ze_yty_r_44__85 _h_85
_ze_yty_r_44__86 _h_86
_ze_yty_r_44__87 _h_87
_ze_yty_r_44__88 _h_88
_ze_yty_r_44__89 _h_89
_ze_yty_r_44__90 _h_90
_ze_yty_r_44__91 _h_91
_ze_yty_r_44__92 _h_92
_ze_yty_r_44__93 _h_93
_ze_yty_r_44__94 _h_94
_ze_yty_r_44__95 _h_95
_ze_yty_r_44__96 _h_96
_ze_yty_r_44__97 _h_97
_ze_yty_r_44__98 _h_98
_ze_yty_r_44__99 _h_99
100
_h_95 _cow_21
_h_44 _cow_99
_h_52 _cow_5
_h_53 _cow_24
_h_92 _cow_32
_h_89 _cow_20
_h_85 _cow_45
_h_33 _cow_32
_h_89 _cow_45
_h_14 _cow_38
_h_27 _cow_77
_h_47 _cow_32
_h_8 _cow_99
_h_3 _cow_50
_h_77 _cow_78
_h_0 _cow_72
_h_99 _cow_96
_h_23 _cow_4
_h_1 _cow_29
_h_80 _cow_45
_h_61 _cow_70
_h_66 _cow_99
_h_67 _cow_99
_h_83 _cow_8
_h_97 _cow_98
_h_46 _cow_76
_h_75 _cow_93
_h_8 _cow_35
_h_93 _cow_11
_h_85 _cow_70
_h_90 _cow_37
_h_94 _cow_41
_h_33 _cow_69
_h_45 _cow_87
_h_98 _cow_26
_h_32 _cow_12
_h_96 _cow_98
_h_63 _cow_15
_h_50 _cow_46
_h_23 _cow_99
_h_44 _cow_69
_h_75 _cow_20
_h_14 _cow_84
_h_7 _cow_7
_h_47 _cow_45
_h_29 _cow_37
_h_82 _cow_23
_h_31 _cow_68
_h_45 _cow_76
_h_55 _cow_43
_h_54 _cow_87
_h_7 _cow_2
_h_38 _cow_22
_h_17 _cow_40
_h_69 _cow_40
_h_39 _cow_65
_h_61 _cow_66
_h_37 _cow_76
_h_2 _cow_45
_h_83 _cow_50
_h_90 _cow_65
_h_39 _cow_24
_h_88 _cow_70
_h_92 _cow_33
_h_99 _cow_47
_h_29 _cow_53
_h_35 _cow_88
_h_56 _cow_25
_h_11 _cow_73
_h_65 _cow_32
_h_66 _cow_56
_h_97 _cow_27
_h_22 _cow_87
_h_55 _cow_25
_h_32 _cow_91
_h_27 _cow_74
_h_56 _cow_66
_h_98 _cow_96
_h_89 _cow_91
_h_82 _cow_88
_h_38 _cow_11
_h_93 _cow_25
_h_51 _cow_49
_h_50 _cow_14
_h_75 _cow_67
_h_98 _cow_41
_h_23 _cow_48
_h_20 _cow_98
_h_35 _cow_28
_h_23 _cow_67
_h_19 _cow_2
_h_41 _cow_75
_h_68 _cow_91
_h_71 _cow_9
_h_82 _cow_53
_h_97 _cow_73
_h_16 _cow_91
_h_98 _cow_20
_h_92 _cow_1
_h_86 _cow_67

20
_cow_0
_cow_1
_cow_2
_cow_3
_cow_4
_cow_5
_cow_6
_cow_7
_cow_8
_cow_9
_cow_10
_cow_11
_cow_12
_cow_13
_cow_14
_cow_15
_cow_16
_cow_17
_cow_18
_cow_19
20
_ze_yty_r_44__0 _h_0
_ze_yty_r_44__1 _h_1
_ze_yty_r_44__2 _h_2
_ze_yty_r_44__3 _h_3
_ze_yty_r_44__4 _h_4
_ze_yty_r_44__5 _h_5
_ze_yty_r_44__6 _h_6
_ze_yty_r_44__7 _h_7
_ze_yty_r_44__8 _h_8
_ze_yty_r_44__9 _h_9
_ze_yty_r_44__10 _h_10
_ze_yty_r_44__11 _h_11
_ze_yty_r_44__12 _h_12
_ze_yty_r_44__13 _h_13
_ze_yty_r_44__14 _h_14
_ze_yty_r_44__15 _h_15
_ze_yty_r_44__16 _h_16
_ze_yty_r_44__17 _h_17
_ze_yty_r_44__18 _h_18
_ze_yty_r_44__19 _h_19
20
_h_10 _cow_7
_h_5 _cow_1
_h_6 _cow_10
_h_15 _cow_2
_h_17 _cow_9
_h_10 _cow_3
_h_6 _cow_3
_h_6 _cow_14
_h_4 _cow_16
_h_3 _cow_5
_h_6 _cow_17
_h_9 _cow_4
_h_2 _cow_19
_h_19 _cow_0
_h_3 _cow_1
_h_7 _cow_0
_h_2 _cow_6
_h_10 _cow_10
_h_8 _cow_19
_h_19 _cow_19

3
_44_
_yty_
C
5
_44_ _44_
_yty_ _yty_
c c
x _h_99
_ze_yty_r_44__ _ze_yty_r_44__
100
_h_1 _h_0
_h_2 _h_1
_h_3 _h_2
_h_4 _h_3
_h_5 _h_4
_h_6 _h_5
_h_7 _h_6
_h_8 _h_7
_h_9 _h_8
_h_10 _h_9
_h_11 _h_10
_h_12 _h_11
_h_13 _h_12
_h_14 _h_13
_h_15 _h_14
_h_16 _h_15
_h_17 _h_16
_h_18 _h_17
_h_19 _h_18
_h_20 _h_19
_h_21 _h_20
_h_22 _h_21
_h_23 _h_22
_h_24 _h_23
_h_25 _h_24
_h_26 _h_25
_h_27 _h_26
_h_28 _h_27
_h_29 _h_28
_h_30 _h_29
_h_31 _h_30
_h_32 _h_31
_h_33 _h_32
_h_34 _h_33
_h_35 _h_34
_h_36 _h_35
_h_37 _h_36
_h_38 _h_37
_h_39 _h_38
_h_40 _h_39
_h_41 _h_40
_h_42 _h_41
_h_43 _h_42
_h_44 _h_43
_h_45 _h_44
_h_46 _h_45
_h_47 _h_46
_h_48 _h_47
_h_49 _h_48
_h_50 _h_49
_h_51 _h_50
_h_52 _h_51
_h_53 _h_52
_h_54 _h_53
_h_55 _h_54
_h_56 _h_55
_h_57 _h_56
_h_58 _h_57
_h_59 _h_58
_h_60 _h_59
_h_61 _h_60
_h_62 _h_61
_h_63 _h_62
_h_64 _h_63
_h_65 _h_64
_h_66 _h_65
_h_67 _h_66
_h_68 _h_67
_h_69 _h_68
_h_70 _h_69
_h_71 _h_70
_h_72 _h_71
_h_73 _h_72
_h_74 _h_73
_h_75 _h_74
_h_76 _h_75
_h_77 _h_76
_h_78 _h_77
_h_79 _h_78
_h_80 _h_79
_h_81 _h_80
_h_82 _h_81
_h_83 _h_82
_h_84 _h_83
_h_85 _h_84
_h_86 _h_85
_h_87 _h_86
_h_88 _h_87
_h_89 _h_88
_h_90 _h_89
_h_91 _h_90
_h_92 _h_91
_h_93 _h_92
_h_94 _h_93
_h_95 _h_94
_h_96 _h_95
_h_97 _h_96
_h_98 _h_97
_h_99 _h_98
_h_0 _44_

100
_44_0
_44_1
_44_2
_44_3
_44_4
_44_5
_44_6
_44_7
_44_8
_44_9
_44_10
_44_11
_44_12
_44_13
_44_14
_44_15
_44_16
_44_17
_44_18
_44_19
_44_20
_44_21
_44_22
_44_23
_44_24
_44_25
_44_26
_44_27
_44_28
_44_29
_44_30
_44_31
_44_32
_44_33
_44_34
_44_35
_44_36
_44_37
_44_38
_44_39
_44_40
_44_41
_44_42
_44_43
_44_44
_44_45
_44_46
_44_47
_44_48
_44_49
_44_50
_44_51
_44_52
_44_53
_44_54
_44_55
_44_56
_44_57
_44_58
_44_59
_44_60
_44_61
_44_62
_44_63
_44_64
_44_65
_44_66
_44_67
_44_68
_44_69
_44_70
_44_71
_44_72
_44_73
_44_74
_44_75
_44_76
_44_77
_44_78
_44_79
_44_80
_44_81
_44_82
_44_83
_44_84
_44_85
_44_86
_44_87
_44_88
_44_89
_44_90
_44_91
_44_92
_44_93
_44_94
_44_95
_44_96
_44_97
_44_98
_44_99
100
_yty_0 c0
_yty_1 c1
_yty_2 c2
_yty_3 c3
_yty_4 c4
_yty_5 c5
_yty_6 c6
_yty_7 c7
_yty_8 c8
_yty_9 c9
_yty_10 c10
_yty_11 c11
_yty_12 c12
_yty_13 c13
_yty_14 c14
_yty_15 c15
_yty_16 c16
_yty_17 c17
_yty_18 c18
_yty_19 c19
_yty_20 c20
_yty_21 c21
_yty_22 c22
_yty_23 c23
_yty_24 c24
_yty_25 c25
_yty_26 c26
_yty_27 c27
_yty_28 c28
_yty_29 c29
_yty_30 c30
_yty_31 c31
_yty_32 c32
_yty_33 c33
_yty_34 c34
_yty_35 c35
_yty_36 c36
_yty_37 c37
_yty_38 c38
_yty_39 c39
_yty_40 c40
_yty_41 c41
_yty_42 c42
_yty_43 c43
_yty_44 c44
_yty_45 c45
_yty_46 c46
_yty_47 c47
_yty_48 c48
_yty_49 c49
_yty_50 c50
_yty_51 c51
_yty_52 c52
_yty_53 c53
_yty_54 c54
_yty_55 c55
_yty_56 c56
_yty_57 c57
_yty_58 c58
_yty_59 c59
_yty_60 c60
_yty_61 c61
_yty_62 c62
_yty_63 c63
_yty_64 c64
_yty_65 c65
_yty_66 c66
_yty_67 c67
_yty_68 c68
_yty_69 c69
_yty_70 c70
_yty_71 c71
_yty_72 c72
_yty_73 c73
_yty_74 c74
_yty_75 c75
_yty_76 c76
_yty_77 c77
_yty_78 c78
_yty_79 c79
_yty_80 c80
_yty_81 c81
_yty_82 c82
_yty_83 c83
_yty_84 c84
_yty_85 c85
_yty_86 c86
_yty_87 c87
_yty_88 c88
_yty_89 c89
_yty_90 c90
_yty_91 c91
_yty_92 c92
_yty_93 c93
_yty_94 c94
_yty_95 c95
_yty_96 c96
_yty_97 c97
_yty_98 c98
_yty_99 c99
100
_ze_yty_r_44__0 e0
_ze_yty_r_44__1 e1
_ze_yty_r_44__2 e2
_ze_yty_r_44__3 e3
_ze_yty_r_44__4 e4
_ze_yty_r_44__5 e5
_ze_yty_r_44__6 e6
_ze_yty_r_44__7 e7
_ze_yty_r_44__8 e8
_ze_yty_r_44__9 e9
_ze_yty_r_44__10 e10
_ze_yty_r_44__11 e11
_ze_yty_r_44__12 e12
_ze_yty_r_44__13 e13
_ze_yty_r_44__14 e14
_ze_yty_r_44__15 e15
_ze_yty_r_44__16 e16
_ze_yty_r_44__17 e17
_ze_yty_r_44__18 e18
_ze_yty_r_44__19 e19
_ze_yty_r_44__20 e20
_ze_yty_r_44__21 e21
_ze_yty_r_44__22 e22
_ze_yty_r_44__23 e23
_ze_yty_r_44__24 e24
_ze_yty_r_44__25 e25
_ze_yty_r_44__26 e26
_ze_yty_r_44__27 e27
_ze_yty_r_44__28 e28
_ze_yty_r_44__29 e29
_ze_yty_r_44__30 e30
_ze_yty_r_44__31 e31
_ze_yty_r_44__32 e32
_ze_yty_r_44__33 e33
_ze_yty_r_44__34 e34
_ze_yty_r_44__35 e35
_ze_yty_r_44__36 e36
_ze_yty_r_44__37 e37
_ze_yty_r_44__38 e38
_ze_yty_r_44__39 e39
_ze_yty_r_44__40 e40
_ze_yty_r_44__41 e41
_ze_yty_r_44__42 e42
_ze_yty_r_44__43 e43
_ze_yty_r_44__44 e44
_ze_yty_r_44__45 e45
_ze_yty_r_44__46 e46
_ze_yty_r_44__47 e47
_ze_yty_r_44__48 e48
_ze_yty_r_44__49 e49
_ze_yty_r_44__50 e50
_ze_yty_r_44__51 e51
_ze_yty_r_44__52 e52
_ze_yty_r_44__53 e53
_ze_yty_r_44__54 e54
_ze_yty_r_44__55 e55
_ze_yty_r_44__56 e56
_ze_yty_r_44__57 e57
_ze_yty_r_44__58 e58
_ze_yty_r_44__59 e59
_ze_yty_r_44__60 e60
_ze_yty_r_44__61 e61
_ze_yty_r_44__62 e62
_ze_yty_r_44__63 e63
_ze_yty_r_44__64 e64
_ze_yty_r_44__65 e65
_ze_yty_r_44__66 e66
_ze_yty_r_44__67 e67
_ze_yty_r_44__68 e68
_ze_yty_r_44__69 e69
_ze_yty_r_44__70 e70
_ze_yty_r_44__71 e71
_ze_yty_r_44__72 e72
_ze_yty_r_44__73 e73
_ze_yty_r_44__74 e74
_ze_yty_r_44__75 e75
_ze_yty_r_44__76 e76
_ze_yty_r_44__77 e77
_ze_yty_r_44__78 e78
_ze_yty_r_44__79 e79
_ze_yty_r_44__80 e80
_ze_yty_r_44__81 e81
_ze_yty_r_44__82 e82
_ze_yty_r_44__83 e83
_ze_yty_r_44__84 e84
_ze_yty_r_44__85 e85
_ze_yty_r_44__86 e86
_ze_yty_r_44__87 e87
_ze_yty_r_44__88 e88
_ze_yty_r_44__89 e89
_ze_yty_r_44__90 e90
_ze_yty_r_44__91 e91
_ze_yty_r_44__92 e92
_ze_yty_r_44__93 e93
_ze_yty_r_44__94 e94
_ze_yty_r_44__95 e95
_ze_yty_r_44__96 e96
_ze_yty_r_44__97 e97
_ze_yty_r_44__98 e98
_ze_yty_r_44__99 e99

4
_44_
_yty_
C
_ze_yty_r_44__
5
l_44__h_to_h_ _yty_
_h_hone C
_h__44_ge_cow_ _yty_
clock _yty_
com_yty_ X
3
_yty_ X
X _44_
X _ze_yty_r_44__

Sample Output

Code: Select all

1

0

1

4

2

49

9

4

100

1

I check the sample input on uvatoolkit and uDebug, the correct output should be:

Code: Select all

1

0

1

1

2

49

9

3

100

1

The output of eighth case should be 3, not 4.