#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> devise_strategy(int N)
{
vector<vector<int>> result(37, vector<int>(N + 1, 0));
int power = 12;
for (int i = 0; i < 12; i++)
{
for (int j = 1; j <= N; j++)
if (j & (1 << power))
result[i][j] = 13 + i;
else
result[i][j] = 25 + i;
power--;
}
// cas final on verifie la pow 0 (0 ou 1) et on decide directement car forcement differents
for (int j = 1; j <= N; j++)
if (j % 2 == 0)
result[12][j] = -2; // prend sac A
else
result[12][j] = -1; // prend sac B
power = 12;
for (int i = 13; i < 25; i++)
{
// sac A a la power `power` active
result[i][0] = 1;
for (int j = 1; j <= N; j++)
if (j & (1 << power))
result[i][j] = i - 12;
else
result[i][j] = -1; // prend sac B
power--;
}
power = 12;
for (int i = 25; i < 37; i++)
{
// sac A a la power `power` disactive
result[i][0] = 2;
for (int j = 1; j <= N; j++)
if (j & (1 << power))
result[i][j] = -2; // prend sac A
else
result[i][j] = i - 24;
power--;
}
return result;
}
#ifdef HOME
int main()
{
int N;
cin >> N;
vector<vector<int>> result = devise_strategy(N);
// for (int i = 0; i < 37; i++)
// {
// cout << "I read " << i << " on board, I will see bag " << result[i][0] << " and write on board: ";
// for (int j = 1; j <= N; j++)
// cout << result[i][j] << " ";
// cout << endl;
// }
random_device rd;
uniform_int_distribution<> dis(1, N);
for (int i = 0; i < 50; i++)
{
int tab = 0;
int sacA = dis(rd), sacB = dis(rd);
while (tab >= 0)
if (result[tab][0] == 0)
tab = result[tab][sacA];
else
tab = result[tab][sacB];
if (tab == -2 && sacA < sacB or tab == -1 && sacA > sacB)
;
else
cout << "I lose! A = " << sacA << " B = " << sacB << endl;
}
return 0;
}
#endif
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |