/* CERC 2011 * Solution to the problem Cards * Idea: find a solution to the set of at most five equations x = a_i mod m_i * using a similar recursive approach as the Euclid's algorithm * Author: Josef Cibulka */ #include #include #include #include #define MAXPL 1000 #define CPERP 5 #define MAXN (CPERP*MAXPL) // number of cards and of players int n, pcnt; // the card dealing permutation - perm[i]=place where card from place i is moved int perm[MAXN]; // init[i] = initial positions of card i (inverse perm. to the input) // only for the important cards - 1...CPERP int init[CPERP]; // in how many turns does the card return to its initial position int cyclen[CPERP]; // when player has the card (up to 5 times within the card's cycle) int whenphasc[MAXPL][CPERP][CPERP]; int whenphasccnt[MAXPL][CPERP]; // cnts[i] = number of cards in each dealing round i and cntssum[i] = sum from rounds 1..i-1 int cnts[CPERP] = {2,2,1,0,0}; int cntssum[CPERP] = {0,2,4,5,5}; // greatest common divisor -- Euler's algorithm long long gcd(long long a, long long b) { if(a==0 || a==b) return b; if(b==0) return a; if(a=m // if no solution, return -1 long long subsolve(long long a, long long b, long long m) { long long mnew, bnew, subres, ret; assert(a>=m); assert(gcd(a,m)==1); if(b==0) return 0; mnew = a%m; assert(mnew != 0); bnew = mnew - 1 - ((b-1)%mnew); subres = subsolve(m, bnew, mnew); // now subres*m = bnew mod mnew // that is subres*m + b = 0 mod mnew because bnew = -b mod mnew // then ((subres*m+b)/mnew) * a = (a mod m)*((subres*m+b)/mnew) mod m = subres*m+b mod m = b mod m ret = (subres*m+b)/mnew; assert(ret*mnew == subres*m+b); return ret%m; } // solves the set of equations and returns smallest positive solution // (if no solution, return -1): // x = pert[0] mod per[0] // ... // x = pert[cnt-1] mod per[cnt-1] long long solve(int cnt, int *per, int *pert) { int i; long long val, valmodg, val1, val2, mod, mod1, mod2, g, tmp; if(cnt==0) return 1; val = pert[0]; mod = per[0]; for(i=1;i 1 we check if there is a solution and if there is, divide by g g = gcd(mod, per[i]); if((val%g) != (pert[i]%g)) return -1; valmodg = val%g; val1 = val/g; val2 = pert[i]/g; mod1 = mod/g; mod2 = per[i]/g; // transform to form acceptable for subsolve if(mod1=val1) tmp = val2-val1; else { assert(val2 + ((val1-val2-1)/mod2 + 1)*mod2>=val1); tmp = val2 + ((val1-val2-1)/mod2 + 1)*mod2 - val1; } assert(tmp=1); ret = -1; for(i=0; i-1 && (ret==-1 || tmp-1) { if(winner==-1 || tmpll