某岛

… : "…アッカリ~ン . .. . " .. .
May 10, 2020

SRM 639

这场前两题都好暴力。。

275

给定 x,求最小的 y,使得 x*y 为回文数。
(x <= 1e5, y <= 1e9)

直接枚举 y 是会 T 的,做法参考 USACO 的那个回文素数,生成 1e14 范围内所有回文数,再求出最小的解即可。
数据范围刚好可以这样通过。

500

某人在 TC 和 CF 分别有两个 rating,rating 的分布在 [1, 1000] 区间。
每周比赛,TC 和 CF 的分数都会 +- 100 范围内,在 [1, 1000] 等概率波动。
问进行了 n 周比赛后,有多少概率中间某一周会出现恰好两个 rating 相等的情况。

直接概率 DP,然后用二维树状数组优化转移即可。

950

NIM 取子游戏,Bob 可以修改初始的状态,挑选出一些 pile 加石子,
问最少增加多少石子可以保证自己获胜。(求总数最少,可以不同的 pile 加不同数目的石子)

/* &*#()&*#)&E*F& */

#include <iostream>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <string>
#include <vector>
#include <map>

using namespace std;

#define REP(I, N) for (int I=0;I<int(N);++I)
#define FOR(I, A, B) for (int I=int(A);I<int(B);++I)
#define DWN(I, B, A) for (int I=int(B-1);I>=int(A);--I)
#define REP_1(i, n) for (int i=1;i<=n;++i)
#define FOR_1(i, a, b) for (int i=a;i<=b;++i)
#define ECH(it, A) for (typeof(A.begin()) it=A.begin(); it != A.end(); ++it)

#define ALL(A) A.begin(), A.end()
#define CLR(A) A.clear()
#define CPY(A, B) memcpy(A, B, sizeof(A))
#define INS(A, P, B) A.insert(A.begin() + P, B)
#define ERS(A, P) A.erase(A.begin() + P)
#define SRT(A) sort(ALL(A))
#define SZ(A) int(A.size())
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef double DB;

template<class T> inline void RST(T &A){memset(A, 0, sizeof(A));}
template<class T> inline void FLC(T &A, int x){memset(A, x, sizeof(A));}

template<class T> inline void checkMin(T &a, T b){if (b<a) a=b;}
template<class T> inline void checkMax(T &a, T b){if (b>a) a=b;}

/* -&$&#*( &#*@)^$@&*)*/

const int MOD = 1000000007;
const int INF = 0x7fffffff;

const int N = 1000;
int n = 1000;

DB dp[2][N+1][N+1];
DB u;

int low_bit(int x){
    return x & -x;
}

void Modify(int p, int x, int y){
    while (x > 0){
        for (int t = y; t > 0; t -= low_bit(t))
            dp[p][x][t] += u;
        x -= low_bit(x);
    }
}

DB Query(int p, int x, int y){
    DB res = 0; while (x <= n){
        for (int t = y; t <= n; t += low_bit(t))
            res += dp[p][x][t];
        x += low_bit(x);
    }
    return res;
}


class EllysTwoRatings {
public:
    double getChance(int NN, int A, int B) {
        RST(dp); int p = 1, q = 0;
        int x1 = A, x2 = A, y1 = B, y2 = B;

        u = 1;
        Modify(p, x2, y2);
        Modify(p, x1-1, y1-1);
        u = -u;
        Modify(p, x2, y1-1);
        Modify(p, x1-1, y2);
        
        
        cout << Query(p, A,B) << endl;
        
        
        DB z = 0;
        
        REP(i, NN) {
            swap(p, q); RST(dp[p]);
            
            REP_1(a,N) REP_1(b,N){
                u = Query(q, a, b);
                //DB u = dp[q][a][b]
                if (a == b) {
                    z += u;
                    continue;
                }
                if (u <= 1e-9) continue;
                
                int x1 = a - 100; checkMax(x1, 1);
                int x2 = a + 100; checkMin(x2, N);
                int y1 = b - 100; checkMax(y1, 1);
                int y2 = b + 100; checkMin(y2, N);

                u /= (DB)(x2-x1+1)*(y2-y1+1);
                Modify(p, x2, y2);
                Modify(p, x1-1, y1-1);
                u = -u;
                Modify(p, x2, y1-1);
                Modify(p, x1-1, y2);
                /*
                FOR_1(a, a0, x2) FOR_1(b, b0, b1) {
                    dp[p][a][b] += u;
                }*/
            }
        }
        
        
        REP_1(j, N) z += Query(p, j, j);
        return z;
    }
};


// BEGIN CUT HERE
namespace moj_harness {
    int run_test_case(int);
    void run_test(int casenum = -1, bool quiet = false) {
        if (casenum != -1) {
            if (run_test_case(casenum) == -1 && !quiet) {
                cerr << "Illegal input! Test case " << casenum << " does not exist." << endl;
            }
            return;
        }
        
        int correct = 0, total = 0;
        for (int i=0;; ++i) {
            int x = run_test_case(i);
            if (x == -1) {
                if (i >= 100) break;
                continue;
            }
            correct += x;
            ++total;
        }
        
        if (total == 0) {
            cerr << "No test cases run." << endl;
        } else if (correct < total) {
            cerr << "Some cases FAILED (passed " << correct << " of " << total << ")." << endl;
        } else {
            cerr << "All " << total << " tests passed!" << endl;
        }
    }
    
    static const double MAX_DOUBLE_ERROR = 1e-9; static bool topcoder_fequ(double expected, double result) { if (isnan(expected)) { return isnan(result); } else if (isinf(expected)) { if (expected > 0) { return result > 0 && isinf(result); } else { return result < 0 && isinf(result); } } else if (isnan(result) || isinf(result)) { return false; } else if (fabs(result - expected) < MAX_DOUBLE_ERROR) { return true; } else { double mmin = min(expected * (1.0 - MAX_DOUBLE_ERROR), expected * (1.0 + MAX_DOUBLE_ERROR)); double mmax = max(expected * (1.0 - MAX_DOUBLE_ERROR), expected * (1.0 + MAX_DOUBLE_ERROR)); return result > mmin && result < mmax; } }
    double moj_relative_error(double expected, double result) { if (isnan(expected) || isinf(expected) || isnan(result) || isinf(result) || expected == 0) return 0; return fabs(result-expected) / fabs(expected); }
    
    int verify_case(int casenum, const double &expected, const double &received, clock_t elapsed) {
        cerr << "Example " << casenum << "... ";
        
        string verdict;
        vector<string> info;
        char buf[100];
        
        if (elapsed > CLOCKS_PER_SEC / 200) {
            sprintf(buf, "time %.2fs", elapsed * (1.0/CLOCKS_PER_SEC));
            info.push_back(buf);
        }
        
        if (topcoder_fequ(expected, received)) {
            verdict = "PASSED";
            double rerr = moj_relative_error(expected, received);
            if (rerr > 0) {
                sprintf(buf, "relative error %.3e", rerr);
                info.push_back(buf);
            }
        } else {
            verdict = "FAILED";
        }
        
        cerr << verdict;
        if (!info.empty()) {
            cerr << " (";
            for (int i=0; i<(int)info.size(); ++i) {
                if (i > 0) cerr << ", ";
                cerr << info[i];
            }
            cerr << ")";
        }
        cerr << endl;
        
        if (verdict == "FAILED") {
            cerr << "    Expected: " << expected << endl;
            cerr << "    Received: " << received << endl;
        }
        
        return verdict == "PASSED";
    }
    
    int run_test_case(int casenum) {
        switch (casenum) {
            case 0: {
                int N                     = 13;
                int A                     = 42;
                int B                     = 666;
                double expected__         = 0.001968164704;
                
                clock_t start__           = clock();
                double received__         = EllysTwoRatings().getChance(N, A, B);
                return verify_case(casenum, expected__, received__, clock()-start__);
            }
            case 1: {
                int N                     = 3;
                int A                     = 1;
                int B                     = 1000;
                double expected__         = 0.0;
                
                clock_t start__           = clock();
                double received__         = EllysTwoRatings().getChance(N, A, B);
                return verify_case(casenum, expected__, received__, clock()-start__);
            }
            case 2: {
                int N                     = 20;
                int A                     = 216;
                int B                     = 219;
                double expected__         = 0.083322288706;
                
                clock_t start__           = clock();
                double received__         = EllysTwoRatings().getChance(N, A, B);
                return verify_case(casenum, expected__, received__, clock()-start__);
            }
            case 3: {
                int N                     = 42;
                int A                     = 973;
                int B                     = 123;
                double expected__         = 0.019345240789;
                
                clock_t start__           = clock();
                double received__         = EllysTwoRatings().getChance(N, A, B);
                return verify_case(casenum, expected__, received__, clock()-start__);
            }
                
                // custom cases
                
                /*      case 4: {
                 int N                     = ;
                 int A                     = ;
                 int B                     = ;
                 double expected__         = ;
                 
                 clock_t start__           = clock();
                 double received__         = EllysTwoRatings().getChance(N, A, B);
                 return verify_case(casenum, expected__, received__, clock()-start__);
                 }*/
                /*      case 5: {
                 int N                     = ;
                 int A                     = ;
                 int B                     = ;
                 double expected__         = ;
                 
                 clock_t start__           = clock();
                 double received__         = EllysTwoRatings().getChance(N, A, B);
                 return verify_case(casenum, expected__, received__, clock()-start__);
                 }*/
                /*      case 6: {
                 int N                     = ;
                 int A                     = ;
                 int B                     = ;
                 double expected__         = ;
                 
                 clock_t start__           = clock();
                 double received__         = EllysTwoRatings().getChance(N, A, B);
                 return verify_case(casenum, expected__, received__, clock()-start__);
                 }*/
            default:
                return -1;
        }
    }
}

int main(int argc, char *argv[]) {
    if (argc == 1) {
        moj_harness::run_test();
    } else {
        for (int i=1; i<argc; ++i)
            moj_harness::run_test(atoi(argv[i]));
    }
}
// END CUT HERE