API tools faq
paste
Advertisement
Hinski2

Untitled

Hinski2
Jun 15th, 2024
13
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.84 KB | None | 0 0
raw download clone embed print report
  1. #include <bits/stdc++.h>
  2. #include <sys/resource.h>
  3. using namespace std;
  4.  
  5. #define fi first
  6. #define se second
  7.  
  8. typedef pair<int, int> pii;
  9. const int mak = 70;
  10. const int target = 757;
  11.  
  12. pii setup[25];
  13. int score;
  14.  
  15. void print_ans(){
  16. cout << score << endl;
  17. int cnt = 0;
  18. for(int i = 1; i < 25; i++){
  19. if(setup[i] != make_pair(-1, -1)){
  20. cnt += i * i;
  21. cout << 1;
  22. }
  23. else
  24. cout << 0;
  25. }
  26. cout << endl << 70 * 70 - cnt << endl;
  27.  
  28. char board[mak][mak];
  29. for(int i = 0; i < mak; i++)
  30. for(int j = 0; j < mak; j++)
  31. board[i][j] = '.';
  32.  
  33. for(int i = 1; i < 25; i++){
  34. if(setup[i] == make_pair(-1, -1)) continue;
  35. for(int x = setup[i].first; x < setup[i].first + i; x++)
  36. for(int y = setup[i].second; y < setup[i].second + i; y++)
  37. board[x][y] = 'A' -1 + i;
  38. }
  39.  
  40. for(int i = 0; i < mak; i++){
  41. for(int j = 0; j < mak; j++)
  42. cout << board[i][j];
  43. cout << endl;
  44. }
  45. cout << endl;
  46. }
  47.  
  48. void set_block(int x, int y, int sajz){
  49. setup[sajz] = {x, y};
  50. score -= sajz * sajz;
  51.  
  52. if(score <= target){
  53. print_ans();
  54. exit(0);
  55. }
  56. }
  57.  
  58. void unset_block(int x, int y, int sajz){
  59. setup[sajz] = {-1, -1};
  60. score += sajz * sajz;
  61. }
  62.  
  63. inline bool square_intersect(pii a, int aLen, pii b, int bLen){
  64. pii l1 = a, r1 = {a.fi + aLen - 1, a.se + aLen - 1};
  65. pii l2 = b, r2 = {b.fi + bLen - 1, b.se + bLen - 1};
  66.  
  67. if(l1.fi > r2.fi || l2.fi > r1.fi) return false;
  68. if(l1.se > r2.se || l2.se > r2.se) return false;
  69. return true;
  70. }
  71.  
  72. bool free_point(int x, int y, int sajz){
  73. for(int i = 24; i > 0; i--){
  74. if(setup[i] == make_pair(-1, -1)) continue;
  75. if(square_intersect(make_pair(x, y), sajz, setup[i], i))
  76. return false;
  77. }
  78. return true;
  79. }
  80.  
  81. pii get_first_bot(int x){
  82. for(int j = 0; j <= mak - x; j++)
  83. for(int i = 0; i <= mak - x; i++)
  84. if(free_point(i, j, x))
  85. return(make_pair(i, j));
  86. return make_pair(-1, -1);
  87. }
  88.  
  89. pii get_first_left(int x){
  90. for(int i = 0; i <= mak - x; i++)
  91. for(int j = 0; j <= mak - x; j++)
  92. if(free_point(i, j, x))
  93. return(make_pair(i, j));
  94. return make_pair(-1, -1);
  95. }
  96.  
  97. void backtrack(bool to_l){
  98. for(int x = 24; x > 0; x--){
  99. if(setup[x] != make_pair(-1, -1)) continue;
  100. pii poss;
  101.  
  102. if(to_l){
  103. poss = get_first_left(x);
  104. if(poss != make_pair(-1, -1)){
  105. set_block(poss.fi, poss.se, x);
  106. backtrack(to_l^1);
  107. unset_block(poss.fi, poss.se, x);
  108. }
  109. poss = get_first_bot(x);
  110. if(poss != make_pair(-1, -1)){
  111. set_block(poss.fi, poss.se, x);
  112. backtrack(to_l^1);
  113. unset_block(poss.fi, poss.se, x);
  114. }
  115. }
  116. else{
  117. poss = get_first_bot(x);
  118. if(poss != make_pair(-1, -1)){
  119. set_block(poss.fi, poss.se, x);
  120. backtrack(to_l^1);
  121. unset_block(poss.fi, poss.se, x);
  122. }
  123.  
  124. poss = get_first_left(x);
  125. if(poss != make_pair(-1, -1)){
  126. set_block(poss.fi, poss.se, x);
  127. backtrack(to_l^1);
  128. unset_block(poss.fi, poss.se, x);
  129. }
  130. }
  131. }
  132. }
  133.  
  134. int main(){
  135.  
  136. //początkowe ustawienie planszy
  137. score = 4900;
  138.  
  139. for(int i = 1; i < 25; i++)
  140. setup[i] = setup[i] = {-1, -1};
  141.  
  142. //ustawiam ciąg fibonacciego w lewym górym rogu
  143. set_block(0, 0, 21);
  144. set_block(21, 0, 5);
  145. set_block(26, 0, 8);
  146. set_block(21, 5, 1);
  147. set_block(21, 6, 2);
  148. set_block(21, 8, 13);
  149. set_block(23, 5, 3);
  150.  
  151. backtrack(1);
  152. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!