Euler Projesi 232. Soru

Yarış

İki oyuncu hileli bir parayı sırasıyla kullanarak "Yarış" oyununu oynuyorlar. Oyuncu 1 parayı bir kere atıyor: Tura gelirse, 1 puan alıyor; yazı gelirse puan almıyor. Oyuncu 2 bir T pozitif tam sayı seçip parayı bu sayıda atıyor: Hepsi tura gelirse 2^T-1 puan alıyor; aksi takdirde puan almıyor. İlk Oyuncu 1 başlıyor. 100 veya daha fazla puan alan kazanıyor.

Her sıra geldiğinde Oyuncu 2 bir T sayısı seçerek kazanma olasılığını maksimize etmek istiyor.

Oyuncu 2'nin kazanma olasılığı nedir?

Cevabınızı 8 ondalık basamağa kadar 0, abcdefgh biçiminde veriniz.

Cevap: 0.83648556

C++:

#include <stdio.h>


int main()  {
 
 int i,j,k,s;
        double A,B,maxi,maxi2,p[101][101],pow2[10];
 
 pow2[0]=1.0;
 for(i=1;i<10;i++)  pow2[i]=0.5*pow2[i-1];
 for(i=0;i<100;i++)  p[100][i]=0.0,p[i][100]=1.0;
 p[100][100]=1.0;
 for(i=99;i>=0;i--)  {
  for(j=99;j>=0;j--)  {
   maxi=0.0;
   for(k=1;j+(1<<(k-1))<=200;k++)  {
                           s=j+(1<<(k-1));
      if(s>100)  s=100;
                           A=1.0-(1.0-pow2[k])*0.5;
      B=(1.0-pow2[k])*0.5*p[i+1][j]+pow2[k]*(0.5*p[i][s]+0.5*p[i+1][s]);
      maxi2=B/A;
      if(maxi<maxi2)  maxi=maxi2;
          }
   p[i][j]=maxi;
  }
 }
 printf("%.8lf\n",0.5*(p[0][0]+p[1][0]));
 return 0;
}

Mathematica:

Clear[probfirst, probsecond, strat];
probfirst[b_, c_] := probfirst[b, c] =
 If[c >= 100, 1, 1/2 probsecond[b, c] + 1/2 probsecond[b + 1, c]]
probsecond[b_, c_] := probsecond[b, c] = 
If[b ≥ 100, 0, Max[Table[strat[t, b, c], {t, 1, 8}]]]
strat[t_, b_, c_] := p[t]probfirst[b, c + 2^(t - 1)] + (1-p[t])probsecond[b + 1, c]
p[t_]:=2/(1+2^t)
Timing[Table[probfirst[100 - i, 100 - j], {i, 100}, {j, 100}];]
N[probfirst[0, 0],8]

Java:

public class Euler232 {
 static int lim = 100;
 static double[][] p1 = new double[lim + 1][lim + 1], p2 = new double[lim + 1][lim + 1];
 
 public static void main(String[] args) {
  for(int i = 0; i < lim; ++i) p2[lim][i] = 1.0;
  
  for(int i = lim - 1; i >= 0; --i) for(int j = lim - 1; j >= 0; --j) {
   double np2 = p2[i + 1][j];
   double bestp2 = 2, bestp1 = 2;
   for(int t = 1, pt = 2; ; ++t, pt *= 2) {
    int j2 = j + (pt / 2);
    if(j2 > lim) j2 = lim;
    double np1 = p1[i][j2];
    double cp1 = (np1 + pt * np2) / (1 + pt);
    double cp2 = 2 * (np1 - np2) / (1 + pt) + np2;
    if(cp2 < bestp2) {
     bestp2 = cp2;
     bestp1 = cp1;
    }
    if(j2 == lim) break;
   }
   p1[i][j] = bestp1;
   p2[i][j] = bestp2;
  }

  System.out.println(1 - p1[0][0]);
 }
}

Python:

nmax = 100

a = [[0 for j in range(nmax + 1)] for i in range(nmax + 1)]
b = [[0 for j in range(nmax + 1)] for i in range(nmax + 1)]

for i in range(1, nmax + 1):
    a[i][0] = 1
    b[i][0] = 1

for i in range(1, nmax + 1):
    for j in range(1, nmax + 1):
        b[i][j] = 0
        while True:
            q = b[i][j]
            a[i][j] = (b[i][j] + b[i-1][j]) / 2
            for n in range(1, nmax + 1):
                if 2 ** (n - 2) > j:
                    break
                b[i][j] = max(b[i][j], a[i][j] * (1 - 1 / 2 ** n) +
                        (a[i][j-2**(n-1)] if j >= 2**(n-1) else 1) / 2 ** n)
            if abs(q - b[i][j]) < 1e-12:
                break

print(a[nmax][nmax])

Matlab:

function p = euler232()
tic;
global memoGrid;
memoGrid = cell(100,1);
for i=1:100, memoGrid{i} = -1*ones(i,i);end
p1 = getProb(0,0,100);
p = 1-p1;
toc;

function p = getProb(s1, s2, k)
global memoGrid;
if s1 == k
    p = 1;
    return;
elseif s2 == k
    p = 0;
    return;
end
if memoGrid{k}(s1+1,s2+1) ~= -1
    p = memoGrid{k}(s1+1,s2+1);
    return;
end
maxT = 1;
while(2^(maxT-1)<= (k-s2)), maxT=maxT+1;end
if s1+1 == k
    p1 = 1;
else
    p1 = zeros(maxT, 1);
    for i=1:maxT
        [s1T s2T kT] = adjust(s1+1, s2+2^(i-1), k);
        p1(i) = 1/2^i*getProb(s1T, s2T, kT);
        [s1T s2T kT] = adjust(s1+1, s2, k);
        p1(i) = p1(i) + (2^i-1)/2^i*getProb(s1T, s2T, kT);
    end
    p1 = min(p1);
end

p = zeros(maxT, 1);
for T=1:maxT
    [s1T s2T kT] = adjust(s1, s2+2^(T-1), k);
    a = p1/2 + (1/2^T)*(getProb(s1T, s2T, kT))/2;
    b = (1-1/2^T)/2;
    p(T) = a/(1-b);
end
p = min(p);
memoGrid{k}(s1+1,s2+1) = p;


function [s1 s2 k] = adjust(s1, s2, k)
m = min([s1 s2 k]);
s1 = s1 - m;
s2 = s2-m;
k = k - m;
if(s1>k)
    s1 = k;
elseif s2 > k
    s2 = k;
end