Hacker WorldCup 2011 -the qualification round-

I got the result of the qualification round of Hacker World Cup 2011, run by facebook, which determines who is the best hacker in the world.

It seems I'm qualified to advance to round 1, with the perfect score :D

The problems are kind of easy.

One can be solved just by using next_permutation() in STL.

Another can be solved by implementing just as it was described in the problem.

The other is a little difficult. It's DP problem, which is similar to the Pascal's Triangle.

Here, I'll post my solution to these problems.

Double Square:

view plainprint?

1. int main() {  
2.     ifstream in(INPUT);  
3.     ofstream out(OUTPUT);  
4.   
5.     int n;  
6.     long long int x;  
7.     in >> n;  
8.   
9.     REP(i, n) {  
10.         in >> x;  
11.         int ret = 0;  
12.   
13.         for (long long int j = 0; j*j*2 <= x; j++) {  
14.             long long int y = x - j*j;  
15.             long long int y2 = sqrt(y) + .5;  
16.             if (y2 * y2 == y)  
17.                 ++ret;  
18.         }  
19.         out << ret << endl;  
20.     }  
21.   
22.     cout << "done." << endl;  
23.     return 0;  
24. }  

int main() {
    ifstream in(INPUT);
    ofstream out(OUTPUT);

    int n;
    long long int x;
    in >> n;

    REP(i, n) {
        in >> x;
        int ret = 0;

        for (long long int j = 0; j*j*2 <= x; j++) {
            long long int y = x - j*j;
            long long int y2 = sqrt(y) + .5;
            if (y2 * y2 == y)
                ++ret;
        }
        out << ret << endl;
    }

    cout << "done." << endl;
    return 0;
}

Peg Game:

view plainprint?

1. double dp[256], dpt[256];  
2. char bd[256][256];  
3.   
4. void solve(int r, int c) {  
5.     REP(i, r) {  
6.         memset(dpt, 0, sizeof(dpt));  
7.         REP(j, 2*(c-1)+1) {  
8.             if (bd[i][j] == '.')  
9.                 dpt[j] += dp[j];  
10.             else {  
11.                 if (j - 1 < 0 + (i%2 != 0))  
12.                     dpt[j+1] += dp[j];  
13.                 else if (j + 1 >= 2*(c-1)+1-(i%2 != 0))  
14.                     dpt[j-1] += dp[j];  
15.                 else {  
16.                     dpt[j-1] += dp[j] * .5;  
17.                     dpt[j+1] += dp[j] * .5;  
18.                 }  
19.             }  
20.         }  
21.         memcpy(dp, dpt, sizeof(dp));  
22.     }  
23. }  
24.   
25. int main() {  
26.     ifstream in(INPUT);  
27.     ofstream out(OUTPUT);  
28.   
29.     int n;  
30.     in >> n;  
31.   
32.     REP(i, n) {  
33.         int r, c, k, m;  
34.         in >> r >> c >> k >> m;  
35.   
36.         REP(ii, r) {  
37.             if (ii % 2) REP(jj, 2*(c-2)+1) {  
38.                 bd[ii][jj] = (jj % 2) ? '.' : 'x';  
39.             }  
40.             else REP(jj, 2*(c-1)+1) {  
41.                 bd[ii][jj] = (jj % 2) ? '.' : 'x';  
42.             }  
43.         }  
44.   
45.         REP(j, m) {  
46.             int ri, ci;  
47.             in >> ri >> ci;  
48.             bd[ri][2*ci] = '.';  
49.         }  
50.   
51.         REP(j, r) {  
52.             if (j % 2) {  
53.                 char tmp[256];  
54.                 tmp[0] = '.';  
55.                 REP(jj, 2*(c-2)+1)  
56.                     tmp[jj+1] = bd[j][jj];  
57.                 tmp[2*(c-2)+2] = '.';  
58.                 memcpy(bd[j], tmp, sizeof(bd[j]));  
59.   
60.             }  
61.         }  
62.   
63.         double prb = .0;  
64.         int ret = -1;  
65.         REP(p, c-1) {  
66.             memset(dp, 0, sizeof(dp));  
67.   
68.             dp[2*p+1] = 1.;  
69.             solve(r, c);  
70.   
71.             if (dp[2*k+1] > prb)  
72.                 prb = dp[2*k+1], ret = p;  
73.         }  
74.   
75.         char rprb[16];  
76.         sprintf(rprb, "%.6lf", prb);  
77.         out << ret << " " << rprb << endl;  
78.     }  
79.     cout << "done." << endl;  
80.     return 0;  
81. }  

double dp[256], dpt[256];
char bd[256][256];

void solve(int r, int c) {
    REP(i, r) {
        memset(dpt, 0, sizeof(dpt));
        REP(j, 2*(c-1)+1) {
            if (bd[i][j] == '.')
                dpt[j] += dp[j];
            else {
                if (j - 1 < 0 + (i%2 != 0))
                    dpt[j+1] += dp[j];
                else if (j + 1 >= 2*(c-1)+1-(i%2 != 0))
                    dpt[j-1] += dp[j];
                else {
                    dpt[j-1] += dp[j] * .5;
                    dpt[j+1] += dp[j] * .5;
                }
            }
        }
        memcpy(dp, dpt, sizeof(dp));
    }
}

int main() {
    ifstream in(INPUT);
    ofstream out(OUTPUT);

    int n;
    in >> n;

    REP(i, n) {
        int r, c, k, m;
        in >> r >> c >> k >> m;

        REP(ii, r) {
            if (ii % 2) REP(jj, 2*(c-2)+1) {
                bd[ii][jj] = (jj % 2) ? '.' : 'x';
            }
            else REP(jj, 2*(c-1)+1) {
                bd[ii][jj] = (jj % 2) ? '.' : 'x';
            }
        }

        REP(j, m) {
            int ri, ci;
            in >> ri >> ci;
            bd[ri][2*ci] = '.';
        }

        REP(j, r) {
            if (j % 2) {
                char tmp[256];
                tmp[0] = '.';
                REP(jj, 2*(c-2)+1)
                    tmp[jj+1] = bd[j][jj];
                tmp[2*(c-2)+2] = '.';
                memcpy(bd[j], tmp, sizeof(bd[j]));

            }
        }

        double prb = .0;
        int ret = -1;
        REP(p, c-1) {
            memset(dp, 0, sizeof(dp));

            dp[2*p+1] = 1.;
            solve(r, c);

            if (dp[2*k+1] > prb)
                prb = dp[2*k+1], ret = p;
        }

        char rprb[16];
        sprintf(rprb, "%.6lf", prb);
        out << ret << " " << rprb << endl;
    }
    cout << "done." << endl;
    return 0;
}

Studious Student:

view plainprint?

1. int main() {  
2.     ifstream in(INPUT);  
3.     ofstream out(OUTPUT);  
4.   
5.     int n, m;  
6.     in >> n;  
7.   
8.     REP(i, n) {  
9.         in >> m;  
10.   
11.         vector<string>ss;  
12.         string str, ret = "";  
13.         REP(j, m) {  
14.             in >> str;  
15.             ss.PB(str);  
16.         }  
17.         sort(ALL(ss));  
18.   
19.         do {  
20.             string ptr = "";  
21.             EACH(itr, ss)  
22.                 ptr += *itr;  
23.   
24.             if (ret == "" || ret > ptr)  
25.                 ret = ptr;  
26.   
27.         } while (next_permutation(ALL(ss)));  
28.   
29.         out << ret << endl;  
30.     }  
31.   
32.     cout << "done." << endl;  
33.   
34.     return 0;  
35. }  

int main() {
    ifstream in(INPUT);
    ofstream out(OUTPUT);

    int n, m;
    in >> n;

    REP(i, n) {
        in >> m;

        vector<string>ss;
        string str, ret = "";
        REP(j, m) {
            in >> str;
            ss.PB(str);
        }
        sort(ALL(ss));

        do {
            string ptr = "";
            EACH(itr, ss)
                ptr += *itr;

            if (ret == "" || ret > ptr)
                ret = ptr;

        } while (next_permutation(ALL(ss)));

        out << ret << endl;
    }

    cout << "done." << endl;

    return 0;
}

I'm shooting for advancing to round2 !!