fork(30) download
  1. #include <algorithm>
  2. #include <iostream>
  3. #include <random>
  4. #include <map>
  5. using namespace std;
  6.  
  7. random_device rd;
  8. mt19937 rng(rd());
  9. uniform_int_distribution<int> d4(0,3), d10(0,9);
  10.  
  11. int state[4][4];
  12.  
  13. void reset() { for (int r=0; r<4; ++r) for (int c=0; c<4; ++c) state[r][c]=0; }
  14.  
  15. bool is_game_over() {
  16. for (int r=0; r<4; ++r) for (int c=0; c<4; ++c) if (state[r][c]==0) return false;
  17. for (int r=0; r<4; ++r) for (int c=0; c<3; ++c) if (state[r][c]==state[r][c+1]) return false;
  18. for (int r=0; r<3; ++r) for (int c=0; c<4; ++c) if (state[r][c]==state[r+1][c]) return false;
  19. return true;
  20. }
  21.  
  22. void get_random_empty_cell(int &r, int &c) {
  23. r=-1; c=-1;
  24. int seen = 0;
  25. for (int rr=0; rr<4; ++rr) for (int cc=0; cc<4; ++cc) if (state[rr][cc]==0) ++seen;
  26. if (!seen) return;
  27. while (true) { r=d4(rng); c=d4(rng); if (state[r][c]==0) return; }
  28. }
  29.  
  30. bool add_random_cell() {
  31. int r, c; get_random_empty_cell(r,c);
  32. if (r==-1) return false;
  33. state[r][c] = ( d10(rng)==0 ? 4 : 2 );
  34. return true;
  35. }
  36.  
  37. bool compress(int *row) {
  38. int tmp[4], dal=0, hlp[4], bol=0;
  39. bool change = false;
  40. for (int i=0; i<4; ++i) if (row[i]) tmp[dal++]=row[i];
  41. for (int i=0; i<4; ++i) hlp[i]=0;
  42. for (int i=0; i<dal; ) { if (i+1<dal && tmp[i]==tmp[i+1]) { hlp[bol++]=2*tmp[i]; i+=2; } else { hlp[bol++]=tmp[i]; i+=1; } }
  43. for (int i=0; i<4; ++i) if (row[i]!=hlp[i]) change = true;
  44. for (int i=0; i<4; ++i) row[i]=hlp[i];
  45. return change;
  46. }
  47.  
  48. bool move1(int r0, int c0, int dr, int dc) {
  49. int tmp[4];
  50. for (int i=0; i<4; ++i) tmp[i]=state[r0+i*dr][c0+i*dc];
  51. bool change = compress(tmp);
  52. for (int i=0; i<4; ++i) state[r0+i*dr][c0+i*dc]=tmp[i];
  53. return change;
  54. }
  55.  
  56. void move(int d) {
  57. bool change = false;
  58. if (d==0) for (int c=0; c<4; ++c) change |= move1(0,c, 1,0);
  59. if (d==1) for (int c=0; c<4; ++c) change |= move1(3,c,-1,0);
  60. if (d==2) for (int r=0; r<4; ++r) change |= move1(r,0,0, 1);
  61. if (d==3) for (int r=0; r<4; ++r) change |= move1(r,3,0,-1);
  62. if (change) add_random_cell();
  63. }
  64.  
  65. int game() {
  66. reset();
  67. add_random_cell();
  68. add_random_cell();
  69. while (!is_game_over()) move( d4(rng) );
  70. int answer = 0;
  71. for (int r=0; r<4; ++r) for (int c=0; c<4; ++c) answer = max( answer, state[r][c] );
  72. return answer;
  73. }
  74.  
  75. int main() {
  76. map<int,int> stats;
  77. long long games; cin >> games;
  78. while (--games) ++stats[ game() ];
  79. for (auto tmp:stats) cout << tmp.first << ": " << tmp.second << endl;
  80. }
Success #stdin #stdout 0s 3440KB
stdin
50
stdout
32: 2
64: 20
128: 23
256: 4