Tower.cpp 3.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <cstdlib>
  4. #include <ctime>
  5. #include <cmath>
  6. const int MaxH = 100 + 1;
  7. const int HashSize = 59997;
  8. const double HashSave_LowerBound = 0;
  9. const double HashSave_UpperBound = 1e15;
  10. struct Tdat
  11. {
  12. int N , H , M;
  13. double ret;
  14. };
  15. int N , H , M;
  16. double power[MaxH];
  17. Tdat data[HashSize];
  18. int HashCount; // 统计hash表中的元素数目
  19. int RequestTime; // hash查询次数
  20. int FindTime; // hash查找次数
  21. inline int min_need(int H , int M)
  22. {
  23. if(H <= M) return (M + M - H + 1) * H / 2;
  24. else return (M + 1) * M / 2 + (H - M) * 2 - (H - M) / 2;
  25. }
  26. inline int max_need(int H , int M)
  27. {
  28. return (M + M + H - 1) * H / 2;
  29. }
  30. void init()
  31. {
  32. int i;
  33. scanf("%d%d%d" , &N , &H , &M);
  34. if(max_need(H , M) < N) N = max_need(H , M);
  35. power[0] = 1;
  36. for(i=1; i<=H; i++)
  37. power[i] = power[i-1] * 2;
  38. for(i=0; i<HashSize; i++)
  39. data[i].ret = -1;
  40. }
  41. inline int hash(int N , int H , int M)
  42. {
  43. return ((N * 127 + H) * 127 + M) % HashSize * 127 % HashSize;
  44. }
  45. bool find_hash(int N , int H , int M , double& ret)
  46. {
  47. int h = hash(N , H , M);
  48. RequestTime++; FindTime ++;
  49. while(data[h].ret >= 0)
  50. {
  51. if(data[h].N == N && data[h].H == H && data[h].M == M)
  52. {
  53. ret = data[h].ret;
  54. return 1;
  55. }
  56. h = (h + 1) % HashSize;
  57. FindTime ++;
  58. }
  59. return 0;
  60. }
  61. void insert_hash(int N , int H , int M , double ret)
  62. {
  63. int h = hash(N , H , M);
  64. while(data[h].ret >= 0)
  65. {
  66. h = (h + 1) % HashSize;
  67. }
  68. data[h].N = N; data[h].H = H;
  69. data[h].M = M; data[h].ret = ret;
  70. HashCount++;
  71. }
  72. double dfs(int N , int H , int M)
  73. {
  74. if(M <= 0) return 0;
  75. if(min_need(H , M) > N) return 0;
  76. if(max_need(H , M) <= N && H <= M) return power[H-1];
  77. if(max_need(H , M) <= N) N = max_need(H , M);
  78. double ret;
  79. if(find_hash(N , H , M , ret)) return ret;
  80. double a = dfs(N - M , H - 1 , M - 1);
  81. double b = dfs(N - M , H - 1 , M + 1);
  82. ret = a + b;
  83. if(HashSave_LowerBound <= ret && ret <= HashSave_UpperBound)
  84. insert_hash(N , H , M , ret);
  85. return ret;
  86. }
  87. void print_way(double k)
  88. {
  89. int curt = M; printf("%d" , curt);
  90. int TN = N;
  91. double tmp;
  92. for(int i=1; i<H; i++)
  93. {
  94. TN -= curt;
  95. tmp = dfs(TN , H - i , curt - 1);
  96. if(tmp >= k) curt--;
  97. else
  98. {
  99. k -= tmp; curt++;
  100. }
  101. printf(" %d" , curt);
  102. }
  103. putchar('\n');
  104. }
  105. int main()
  106. {
  107. freopen("Tower.in" , "r" , stdin);
  108. freopen("Tower.out", "w" , stdout);
  109. HashCount = 0;
  110. FindTime = 0;
  111. RequestTime = 0;
  112. init();
  113. printf("%.0lf\n" , dfs(N , H , M));
  114. double k;
  115. while(scanf("%lf" , &k) , k > 0)
  116. {
  117. print_way(k);
  118. }
  119. fprintf(stderr, "------------------- details -------------------\n");
  120. fprintf(stderr, "Program Running Time : %.4lfs\n" , clock()/(double)CLK_TCK);
  121. fprintf(stderr, "Hash Table Saved : %-8d\n" , HashCount);
  122. fprintf(stderr, "Hash Table Request Time : %-8d\n" , RequestTime);
  123. fprintf(stderr, "Hash Table findtime : %-8d\n" , FindTime);
  124. fprintf(stderr, "Average Find findtime : %.5lf\n" , (double)FindTime / RequestTime);
  125. return 0;
  126. }
  127. //对于极限数据,double可能存在精度问题,改成longdouble即可