Euler Projesi 260. Soru

Taş Oyunu

Üç taş yığını ve iki oyuncu ile oynanan bir oyun.
Sırasına göre her bir oyuncu yığınlardan bir veya daha fazla taşı alıp çıkarır. Ancak birden fazla yığından taş alırsa, seçilen yığınların her birinden aynı sayıda taş çıkarması gerekir.

Başka bir deyişle, oyuncu bir N> 0 seçer ve aşağıdaki şekilde çıkarma yapar:

Tek bir yığından N taş; veya
İki yığının her birinden N taş (toplam 2N); veya
Üç yığının her birinden N taş (toplam 3N).
Son taş(lar)ı alan oyuncu oyunu kazanır.

Kazanan bir konfigürasyon, ilk oyuncunun kazanmasını zorunlu hale getiren bir konfigürasyondur.
Örneğin (0,0,13), (0,11,11) ve (5,5,5) konfigürasyonları kazanandır, çünkü ilk oyuncu hemen tüm taşları alabilir.

Kaybeden bir konfigürasyon, ilk oyuncunun ne yaptığına bakılmaksızın ikinci oyuncunun kazanmasını zorunlu hale getirecek bir konfigürasyondur. Örneğin (0,1,2) ve (1,3,3) konfigürasyonları kaybedendir: Herhangi bir geçerli hamle ikinci oyuncu için kazanan bir yapılandırma bırakır.

x_i ≤ y_i ≤ z_i ≤ 100 için tüm kaybeden (x_i, y_i, z_i) konfigürasyonlarını göz önünde bulundurun.
Bunlar için Σ (x_i + y_i + z_i) = 173895 olduğunu doğrulayabiliriz.

x_i ≤ y_i ≤ z_i ≤ 1000 için (x_i, y_i, z_i) kaybeden konfigürasyonlar olmak üzere Σ (x_i + y_i + z_i) değerini bulunuz.
Cevap: 167542057
C/C++: #include <stdio.h> #define N 1000 char w[N+1][N+1][N+1]; long long int answer = 0; int min(int a, int b) { return ((a>b)?b:a);} int max(int a, int b) { return ((a>b)?a:b);} int main(int argc, char **argv) { int i, j, k, l; int lim; int s; w[0][0][0] = 1; for (i=1; i<=N; i++) { w[0][0][i] = -1; w[0][i][i] = -1; w[i][i][i] = -1; } for (i=0; i<=N; i++) for (j=i; j<=N; j++) for (k=j; k<=N; k++) { if (w[i][j][k] != 0) continue; // check phase // 1 pile remove for (l=0; l<i; l++) if (w[l][j][k] == 1) goto Label_k_end; for (l=0; l<i; l++) if (w[l][i][k] == 1) goto Label_k_end; for (; l<j; l++) if (w[i][l][k] == 1) goto Label_k_end; for (l=0; l<i; l++) if (w[l][i][j] == 1) goto Label_k_end; for (; l<j; l++) if (w[i][l][j] == 1) goto Label_k_end; for (; l<k; l++) if (w[i][j][l] == 1) goto Label_k_end; // 2 piles remove for (l=1; l<=i; l++) if (w[i-l][j-l][k] == 1) goto Label_k_end; lim = min(i, k-j); for (l=1; l<=lim; l++) if (w[i-l][j][k-l] == 1) goto Label_k_end; for (; l<=i; l++) if (w[i-l][k-l][j] == 1) goto Label_k_end; lim = min(j, j-i); for (l=1; l<=lim; l++) if (w[i][j-l][k-l] == 1) goto Label_k_end; lim = min(j, k-i); for (; l<=lim; l++) if (w[j-l][i][k-l] == 1) goto Label_k_end; for (; l<=j; l++) if (w[j-l][k-l][i] == 1) goto Label_k_end; // 3 piles remove for (l=1; l<=i; l++) if (w[i-l][j-l][k-l] == 1) goto Label_k_end; // lose case // optimization phase // 1 pile add for (l=k+1; l<=N; l++) w[i][j][l] = -1; for (l=j+1; l<=k; l++) w[i][l][k] = -1; for (; l<=N; l++) w[i][k][l] = -1; for (l=i+1; l<=j; l++) w[l][j][k] = -1; for (; l<=k; l++) w[j][l][k] = -1; for (; l<=N; l++) w[j][k][l] = -1; // 2 piles add for (l=1; l<=N-k; l++) w[i][j+l][k+l] = -1; lim = min (N-k, j-i); for (l=1; l<=lim; l++) w[i+l][j][k+l] = -1; for (; l<=N-k; l++) w[j][i+l][k+l] = -1; lim = min (N-j, k-j); for (l=1; l<=lim; l++) w[i+l][j+l][k] = -1; lim = min (N-j, k-i); for (; l<=lim; l++) w[i+l][k][j+l] = -1; for (; l<=N-j; l++) w[k][i+l][j+l] = -1; // 3 piles add for (l=1; l<=N-k; l++) w[i+l][j+l][k+l] = -1; answer += i+j+k; w[i][j][k] = 1; continue; Label_k_end: // win w[i][j][k] = -1; } printf ("answer: %lld\n", answer); } Python: program p260 integer,parameter:: SIZE=1000 logical:: xx(0:SIZE,0:SIZE)=.false. logical:: xd(0:SIZE,0:SIZE)=.false. logical:: dd(0:SIZE,0:SIZE)=.false. integer:: s=0 integer:: x,y,z,n do z=0,SIZE do y=0,z if (xx(z,y)) cycle do x=0,y if (xx(z,x)) cycle if (xx(y,x)) cycle if (xd(z,y-x)) cycle if (xd(y,z-x)) cycle if (xd(x,z-y)) cycle if (dd(z-y,y-x)) cycle ! write(*,*) x,y,z s=s+x+y+z xx(z,y)=.true. xx(z,x)=.true. xx(y,x)=.true. xd(z,y-x)=.true. xd(y,z-x)=.true. xd(x,z-y)=.true. dd(z-y,y-x)=.true. exit end do end do end do write(*,*) s end program p260 Java: public class E260 { static int N = 1000; static int N1 = N + 1; static int N2 = N1 * N1; public static int[] pairs = new int[N2]; public static boolean[] df2 = new boolean[N2]; public static boolean[] df3 = new boolean[N2]; public static boolean[] df6 = new boolean[N2]; public static boolean[] df1 = new boolean[N1]; static int mindiff; static long totsum; public static void register(int p, int q, int r){ pairs[N1*p + q] = r; if (q != r) { pairs[N1*p + r] = q; } if (q != p) { pairs[N1*q + r] = p; } df3[N1*(q-p)+ r] = true; if (r - p >= q) df2[N1*q + r - p] = true; else df3[N1*(r-p) + q] = true; if (r - q >= p) df2[N1*p + r - q] = true; else df3[N1*(r-q) + p] = true; df6[N1*(q-p)+ r - q] = true; df1[r-q] = true; if (r-q == mindiff) do { mindiff++; }while (df1[mindiff]); totsum += p + q + r; System.out.println("losers " + p + ", " + q + ", " + r + ": total " + totsum); return; } public static void next1(int p){ for (int i = 0; i < N1; i++) df1[i] = false; mindiff = 0; return; } public static int next2(int p, int q){ int q1 = q + 1; while (q1 < N1){ //System.out.println("testing 2 " + p + ", " + q1 + ", pairing" + pairs[N1*p + q1]); if (pairs[N1*p + q1] < 0) return q1; else q1++; } return q1; } public static void test3(int p, int q, int r){ int r1 = r; while (r1 < N1){ if (eval(p,q,r1)) r1++; else { register(p,q,r1); return; } } return; } public static boolean eval(int p,int q, int r){ // returns true if position is a win boolean ok = df1[r-q] ||(pairs[N1*p + r] >=0) || (pairs[N1*q + r] >=0) || df6[N1*(q-p)+ r - q] || df3[N1*(q-p)+ r] || ((r - p >= q) && df2[N1*q + r - p])|| ((r - q <= p) && df3[N1*(r-q) + p]) || ((r - p <= q) && df3[N1*(r-p) + q])|| ((r - q >= p) && df2[N1*p + r-q]); /* System.out.println("evaluating " + p + ", " + q + ", " + r ); System.out.println(df1[r-q] + ", " + pairs[N1*p + r] + ", " + pairs[N1*q + r] + ", " + df6[N1*(q-p)+ r - q] + ", " + df3[N1*(q-p)+ r] + ", " + ((r - p >= q) && df2[N1*q + r - p]) + ", " + ((r - p <= q) && df3[N1*(r-p) + q]) + ", " + ((r - p <= q) && df3[N1*(r-p) + q]) + ", " + ((r - p <= q) && df3[N1*(r-p) + q])); */ return ok; } public static void main(String[] args) { totsum = 0; next1(0); register(0,0,0); for (int i = 1; i < N1; i++) df1[i] = false; for (int i = 1; i < N2; i++){ df2[i] = false; df3[i] = false; pairs[i] = -1; } for (int i = 1; i < N2; i++) df6[i] = false; int m1 = 0; int m2 = 0; while (m1 < N){ m2 = next2(m1,m2); if (mindiff + m2 < N1)test3(m1,m2,mindiff + m2); else { m1++; next1(m1); m2 = m1; if (pairs[N1*m1 + m2] >= 0) m2 = next2(m1,m2); test3(m1,m2,m2); } } System.out.println("final total " + totsum); } } Magma: mx := 1000; T := ZeroMatrix(Integers(),mx+1,mx+1); // Compute the minimal excluded element of L. function mexify(L) mex := -1; if (#L eq 0) then mex := 0; end if; if (#L gt 0) and (L[1] ne 0) then mex := 0; end if; if (mex eq -1) then ind := 2; done := false; while done eq false do if ind gt #L then mex := L[#L] + 1; done := true; end if; if (done eq false) then if L[ind] gt L[ind-1] + 1 then mex := L[ind-1]+1; done := true; else ind := ind + 1; end if; end if; end while; end if; return mex; end function; for sm in [0..2*mx] do for a in [Max(0,sm-mx)..Min(mx,Floor(sm/2))] do b := sm-a; lst := [ T[a+1][b+1-i] : i in [1..b]] cat [ T[a+1-i][b+1] : i in [1..a]] cat [ T[a+1-i][b+1-i] : i in [1..Min(a,b)]]; lst := lst cat [ T[a+1][b+1-i] + i : i in [1..b]] cat [ T[a+1-i][b+1] + i : i in [1..a]] cat [ T[a+1-i][b+1-i] + i : i in [1..Min(a,b)]]; // Compute the smallest entry not in lst. mex := mexify(Sort(lst)); //printf "For a = %o, b = %o, lst = %o.\n",a,b,Sort(lst); //printf "We have T(%o,%o) = %o.\n",a,b,mex; T[a+1][b+1] := mex; T[b+1][a+1] := mex; if (mex le mx) then T[a+1][mex+1] := b; T[mex+1][a+1] := b; T[b+1][mex+1] := a; T[mex+1][b+1] := a; end if; end for; end for; colds2 := Sort([ [a,b,T[a+1][b+1]] : b in [a..mx], a in [0..mx] | (T[a+1][b+1] le mx) and (T[a+1][b+1] ge b) ]); printf "Sum for losing configurations is %o.\n",&+[ &+colds2[i] : i in [1..#colds2]];