fork download
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7.  
  8. #define fi first
  9. #define se second
  10. #define mp make_pair
  11. #define pb push_back
  12.  
  13. typedef long long ll;
  14. typedef pair<ll,ll> ii;
  15. typedef vector<int> vi;
  16. typedef unsigned long long ull;
  17. typedef long double ld;
  18. typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;
  19.  
  20. char a[55][55];
  21. ll f[111];
  22. const ll INF = ll(1e18)+1201;
  23.  
  24. ll add(ll a, ll b)
  25. {
  26. a+=b;
  27. return min(a,INF);
  28. }
  29.  
  30. bool used[133];
  31. ii dp[55][55];
  32.  
  33. ll test(int n, int m)
  34. {
  35. dp[0][0]=mp(1,0);
  36. for(int i=0;i<n;i++)
  37. {
  38. for(int j=0;j<m;j++)
  39. {
  40. if(a[i][j]=='X')
  41. {
  42. dp[i][j+1].fi+=dp[i][j].fi;
  43. dp[i][j+1].se+=dp[i][j].se;
  44. dp[i+1][j].fi+=dp[i][j].fi;
  45. dp[i+1][j].se+=dp[i][j].se;
  46. }
  47. else if(a[i][j]=='r')
  48. {
  49. dp[i][j+1].se+=dp[i][j].fi;
  50. dp[i][j+1].se+=dp[i][j].se;
  51. }
  52. else if(a[i][j]=='d')
  53. {
  54. dp[i+1][j].fi+=dp[i][j].fi;
  55. dp[i+1][j].fi+=dp[i][j].se;
  56. }
  57. else
  58. {
  59. dp[i+1][j].fi+=dp[i][j].fi;
  60. dp[i][j+1].se+=dp[i][j+1].se;
  61. }
  62. }
  63. }
  64. return add(dp[n-1][m-1].fi,dp[n-1][m-1].se);
  65. }
  66.  
  67. int main()
  68. {
  69. ios_base::sync_with_stdio(0); cin.tie(0);
  70. f[0]=1;
  71. f[1]=1;
  72. for(int i=2;i<=100;i++) f[i]=add(f[i-1],f[i-2]);
  73. vector<int> vec;
  74. ll k; cin>>k;
  75. int n,m;
  76. if(k<=19)
  77. {
  78. n=m=5;
  79. }
  80. else
  81. {
  82. n=m=45;
  83. }
  84. int mx=-1;
  85. for(int i=2*(n-2);i>=0;i--)
  86. {
  87. if(k>=f[i])
  88. {
  89. k-=f[i]; used[i]=1; mx=max(mx,i);
  90. }
  91. }
  92. for(int i=0;i<n-1;i++) a[i][m-1]='d';
  93. for(int i=0;i<m-1;i++) a[n-1][i]='r';
  94. a[n-1][m-1]='.';
  95. if(mx%2==0)
  96. {
  97. for(int i=0;i<n-1;i++)
  98. {
  99. for(int j=0;j<m-1;j++)
  100. {
  101. a[i][j]='.';
  102. }
  103. }
  104. for(int i=0;i<=mx/2;i++)
  105. {
  106. for(int j=0;j<=mx/2;j++)
  107. {
  108. a[i][j]='X';
  109. }
  110. }
  111. for(int i=1;i<=mx/2;i++)
  112. {
  113. if(!used[2*(i-1)]) a[i][i-1]='r';
  114. for(int j=0;j<i-1;j++)
  115. {
  116. a[i][j]='d';
  117. }
  118. }
  119. for(int i=0;i<mx/2;i++)
  120. {
  121. if(!used[2*i+1]) a[i][min(i+2,mx/2)]='d';
  122. for(int j=i+3;j<=mx/2;j++) a[i][j]='r';
  123. }
  124. a[mx/2][mx/2]='r';
  125. }
  126. else
  127. {
  128. mx++;
  129. for(int i=0;i<n-1;i++)
  130. {
  131. for(int j=0;j<m-1;j++)
  132. {
  133. a[i][j]='.';
  134. }
  135. }
  136. for(int i=0;i<=mx/2;i++)
  137. {
  138. for(int j=0;j<=mx/2;j++)
  139. {
  140. a[i][j]='X';
  141. }
  142. }
  143. for(int i=1;i<=mx/2;i++)
  144. {
  145. if(!used[2*(i-1)]) a[i][i-1]='r';
  146. for(int j=0;j<i-1;j++)
  147. {
  148. a[i][j]='d';
  149. }
  150. }
  151. if(!used[mx-2])
  152. {
  153. a[mx/2-1][mx/2-1]='r';
  154. }
  155. else
  156. {
  157.  
  158. }
  159. a[mx/2-1][mx/2]='r';
  160. for(int i=0;i<mx/2;i++)
  161. {
  162. if(!used[2*i+1]) a[i][min(i+2,mx/2)]='d';
  163. for(int j=i+3;j<=mx/2;j++) a[i][j]='r';
  164. }
  165. a[mx/2][mx/2]='.';
  166. }
  167. for(int i=0;i<=mx/2;i++)
  168. {
  169. for(int j=mx/2+1;j<m-1;j++) a[i][j]='r';
  170. }
  171. for(int i=mx/2+1;i<n-1;i++)
  172. {
  173. for(int j=0;j<=mx/2;j++) a[i][j]='d';
  174. }
  175. //cerr<<test(n,m)<<'\n';
  176. cout<<n<<' '<<m<<'\n';
  177. for(int i=0;i<n;i++)
  178. {
  179. for(int j=0;j<m;j++)
  180. {
  181. cout<<a[i][j];
  182. }
  183. cout<<'\n';
  184. }
  185. }
  186.  
Success #stdin #stdout 0s 15288KB
stdin
Standard input is empty
stdout
45 45
XXdrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrd
rXXdrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrd
drXXdrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrd
ddXXXdrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrd
dddrXXdrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrd
ddddXXXdrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrd
dddddrXXdrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrd
ddddddXXXdrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrd
dddddddXXXdrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrd
ddddddddXXXXrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrd
dddddddddrXXdrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrd
ddddddddddrXXdrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrd
dddddddddddXXXdrrrrrrrrrrrrrrrrrrrrrrrrrrrrrd
ddddddddddddXXXdrrrrrrrrrrrrrrrrrrrrrrrrrrrrd
dddddddddddddXXXdrrrrrrrrrrrrrrrrrrrrrrrrrrrd
ddddddddddddddrXXdrrrrrrrrrrrrrrrrrrrrrrrrrrd
dddddddddddddddrXXdrrrrrrrrrrrrrrrrrrrrrrrrrd
ddddddddddddddddrXXdrrrrrrrrrrrrrrrrrrrrrrrrd
dddddddddddddddddrXXdrrrrrrrrrrrrrrrrrrrrrrrd
ddddddddddddddddddrXXdrrrrrrrrrrrrrrrrrrrrrrd
dddddddddddddddddddXXXdrrrrrrrrrrrrrrrrrrrrrd
ddddddddddddddddddddrXXXrrrrrrrrrrrrrrrrrrrrd
dddddddddddddddddddddrXXdrrrrrrrrrrrrrrrrrrrd
ddddddddddddddddddddddrXXXrrrrrrrrrrrrrrrrrrd
dddddddddddddddddddddddrXXXrrrrrrrrrrrrrrrrrd
ddddddddddddddddddddddddrXXXrrrrrrrrrrrrrrrrd
dddddddddddddddddddddddddrXXdrrrrrrrrrrrrrrrd
ddddddddddddddddddddddddddrXXdrrrrrrrrrrrrrrd
dddddddddddddddddddddddddddrXXXrrrrrrrrrrrrrd
ddddddddddddddddddddddddddddrXXdrrrrrrrrrrrrd
dddddddddddddddddddddddddddddrXXXrrrrrrrrrrrd
ddddddddddddddddddddddddddddddrXXdrrrrrrrrrrd
dddddddddddddddddddddddddddddddrXXdrrrrrrrrrd
ddddddddddddddddddddddddddddddddXrrrrrrrrrrrd
dddddddddddddddddddddddddddddddddr.rrrrrrrrrd
ddddddddddddddddddddddddddddddddddd.........d
ddddddddddddddddddddddddddddddddddd.........d
ddddddddddddddddddddddddddddddddddd.........d
ddddddddddddddddddddddddddddddddddd.........d
ddddddddddddddddddddddddddddddddddd.........d
ddddddddddddddddddddddddddddddddddd.........d
ddddddddddddddddddddddddddddddddddd.........d
ddddddddddddddddddddddddddddddddddd.........d
ddddddddddddddddddddddddddddddddddd.........d
rrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrrr.