External link:

http://codeforces.com/gym/100159
http://www.facebook.com/hackercup/scoreboard?round=225705397509134

Problem A. Checkpoint

Brief description:

。。我们定义到 (m, n) 的经过 (a, b) 的 2 格点路径为。。。
。从 (0, 0) 出发到 (a, b) 再到 (m, n) 的路径。。(a <= m, b <= n)。。 现在询问方案数等于 S 的二阶格点路径最少有多少步。。。。

Analysis:

… 预处理 D[x] 表示到达组合数 x 所需要的最少步数。。
。。之后将 s 分解成 a * b 即可。（。O(sqrt(s))

//}/* .................................................................................................................................. */

const int N = int(1e7);
int D[N+1];
int s;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    REP_1(i, N) D[i] = i;

    FOR(i, 2, 30){ // C(j, i) .. .
        LL x = 1; for (int j=i;x<=N;++j,x=x*j/(j-i)){
            checkMin(D[x], j);
        }
    }

    Rush{
        int res = RD(s)+1; for (int a=1;sqr(a)<=s;++a){
            int b=s/a; if (a*b!=s) continue;
            checkMin(res, D[a]+D[b]);
        }
        OT(res);
    }
}

Problem B. Recover the Sequence

Note:

… 严格按照题目的要求递归下去就好了。。）

//}/* .................................................................................................................................. */

const int N = int(1e4) + 9;
int R[N], P[N];
int n;

void gao(int l, int r){
    if (l+1 >= r) return;
    int m = l + r >> 1;
    gao(l, m), gao(m, r);

    int a = l, b = m, i = l;
    while (a < m && b < r){
        if (RC() == '1') P[i++] = R[a++];
        else P[i++] = R[b++];
    }
    while (a < m) P[i++] = R[a++];
    while (b < r) P[i++] = R[b++];

    FOR(i, l, r) R[i] = P[i];
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    Rush{
        REP_C(i, RD(n)) R[i] = i; gao(0, n); REP(i, n) P[R[i]] = i+1;
        int res = 1; REP(i, n) MUL(res, 31), INC(res, P[i]);
        OT(res);
    }
}

Problem C. Squished Status

Note:

… 暴力 DP 。。注意模数超 int。。

int Case; template<class T> inline void OT(const T &x){
    printf("Case #%d: %u\n", ++Case, x);
    //printf("%.2lf\n", x);
    //printf("%d\n", x);
    //cout << x << endl;
}
//}

//}/* .................................................................................................................................. */

const UINT MOD = 0xfaceb00c;
inline void INC(UINT &a, UINT b){LL aa = a; aa += b; if (aa >= MOD) aa -= MOD; a = aa;}

const int N = 1009;
char str[N]; UINT dp[N], n, m;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    Rush{
        RD(m); n = strlen(RS(str));
        REP_S(cur, str) *cur -= '0';
        RST(dp), dp[0] = 1; REP(i, n) if (dp[i] && str[i]){
            int x = 0; FOR(j, i, n){
                x *= 10, x += str[j]; if (x > m) break;
                INC(dp[j+1], dp[i]);
            }
        }
        OT(dp[n]);
    }
}

Posted by xiaodao
Category: Facebook Hacker Cup