Advertisement
Guest User

Untitled

a guest
Jan 17th, 2019
65
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 5.80 KB | None | 0 0
  1.  
  2.  
  3.  
  4. #include <bits/stdc++.h>
  5. #pragma GCC optimize("O3")
  6. #define count masloriy1489
  7. #define ll long long
  8. #define pb push_back
  9. #define eb emplace_back
  10. #define all(v) v.begin(), v.end()
  11. #define rep(i, n) for(int i = 0; i < n; i++)
  12.  
  13. using namespace std;
  14. //freopen("input.txt", "r", stdin);
  15. //freopen("output.txt", "w", stdout);
  16.  
  17. int n;
  18. vector<int> a0[10];
  19. vector<int> a[10];
  20. bool was0[10][10] = { false };
  21. bool was[10][10] = { false };
  22.  
  23. void print(){
  24. for(int i = 1; i <= n; i++){
  25. for(int j = 0; j < i; j++){
  26. cout << a[i][j] << " ";
  27. }
  28. cout << '\n';
  29. }
  30. exit(0);
  31. }
  32.  
  33. bool prove2(int i, int j){
  34. if(j > i - 2)
  35. return true;
  36. if(was[i][j] && was[i-1][j] && was[i][j+1]){
  37. if(a[i-1][j] != a[i][j] + a[i][j+1])
  38. return false;
  39. }
  40. return true;
  41. }
  42.  
  43. bool solve2(int i, int j){
  44. if(j > i - 2)
  45. return false;
  46. if(!was[i][j] && a[i][j] == 0){
  47. if(was[i][j+1] && was[i-1][j]){
  48. a[i][j] = a[i-1][j] - a[i][j+1];
  49. was[i][j] = true;
  50. return true;
  51. }
  52. }else if(!was[i][j+1] && a[i][j+1] == 0){
  53. if(was[i][j] && was[i-1][j]){
  54. a[i][j+1] = a[i-1][j] - a[i][j];
  55. was[i][j+1] = true;
  56. return true;
  57. }
  58. }else if(!was[i-1][j] && a[i-1][j] == 0){
  59. if(was[i][j] && was[i][j+1]){
  60. a[i-1][j] = a[i][j] + a[i][j+1];
  61. was[i-1][j] = true;
  62. return true;
  63. }
  64. }
  65. return false;
  66. }
  67.  
  68. int solve3(int i, int j){
  69. if(j > i - 3)
  70. return 0;
  71. if(was[i][j]){
  72. if(was[i-2][j] && was[i][j+2]){
  73. if(!was[i-1][j]){
  74. int g = (!was[i][j+1]) + (!was[i-1][j]) + (!was[i-1][j+1]);
  75. if(g == 3){
  76. if((a[i-2][j] - a[i][j+2] - a[i][j]) % 2 == 1)
  77. return 0;
  78. a[i][j+1] = (a[i-2][j] - a[i][j+2] - a[i][j])/2;
  79. was[i][j+1] = true;
  80. a[i-1][j] = a[i][j] + a[i][j+1];
  81. was[i-1][j] = true;
  82. a[i-1][j+1] = a[i][j+1] + a[i][j+2];
  83. was[i-1][j+1] = true;
  84. return g;
  85. }
  86. }
  87. }
  88. }
  89. return 0;
  90. }
  91.  
  92. int solve4(int i, int j){
  93. if(j > i - 4)
  94. return 0;
  95. if(was[i][j]){
  96. if(was[i][j+3] && was[i-2][j] && was[i-2][j+1]){
  97. int g = (!was[i-1][j]) + (!was[i-1][j+1]) + (!was[i-1][j+2]) + (!was[i][j+1]) + (!was[i][j+2]);
  98. if(g == 5){
  99. if((a[i-2][j] + a[i-2][j+1] - a[i][j] - a[i][j+3]) % 3 != 0)
  100. return 0;
  101. a[i-1][j+1] = (a[i-2][j] + a[i-2][j+1] - a[i][j] - a[i][j+3]) / 3;
  102. was[i-1][j+1] = true;
  103. a[i-1][j] = a[i-2][j] - a[i-1][j+1];
  104. was[i-1][j] = true;
  105. a[i-1][j+2] = a[i-2][j+1] - a[i-1][j+1];
  106. was[i-1][j+2] = true;
  107. a[i][j+1] = a[i-1][j] - a[i][j];
  108. was[i][j+1] = true;
  109. a[i][j+2] = a[i-1][j+1] - a[i][j+1];
  110. was[i][j+2] = true;
  111. return g;
  112. }
  113. }
  114. }
  115. return 0;
  116. }
  117.  
  118. bool solve(int good){
  119. int prev = -1;
  120. while(good < (n*(n+1) / 2)){
  121. if(prev == good)
  122. return false;
  123. prev = good;
  124. for(int i = 2; i <= n; i++){
  125. for(int j = 0; j < i; j++){
  126. good += solve2(i, j);
  127. }
  128. }
  129. for(int i = 2; i <= n; i++){
  130. for(int j = 0; j < i; j++){
  131. good += solve3(i, j);
  132. }
  133. }
  134. for(int i = 2; i <= n; i++) {
  135. for (int j = 0; j < i; j++) {
  136. good += solve4(i, j);
  137. }
  138. }
  139. }
  140. for(int i = 2; i <= n; i++) {
  141. for (int j = 0; j < i; j++) {
  142. if(!prove2(i,j))
  143. return false;
  144. }
  145. }
  146. return true;
  147. }
  148.  
  149. bool solve0(int good){
  150. int prev = -1;
  151. while(good < (n*(n+1) / 2)){
  152. if(prev == good)
  153. return false;
  154. prev = good;
  155. for(int i = 2; i <= n; i++){
  156. for(int j = 0; j < i; j++){
  157. good += solve2(i, j);
  158. }
  159. }
  160. for(int i = 2; i <= n; i++){
  161. for(int j = 0; j < i; j++){
  162. good += solve3(i, j);
  163. }
  164. }
  165. for(int i = 2; i <= n; i++) {
  166. for (int j = 0; j < i; j++) {
  167. good += solve4(i, j);
  168. }
  169. }
  170. }
  171. return true;
  172. }
  173.  
  174.  
  175. int main()
  176. {
  177. ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  178. cin >> n;
  179. int good = 0;
  180. for(int i = 1; i <= n; i++){
  181. for(int j = 0; j < i; j++){
  182. int x;
  183. cin >> x;
  184. a0[i].pb(x);
  185. a[i].pb(x);
  186. if(x != 0){
  187. was0[i][j] = true;
  188. was[i][j] = true;
  189. good++;
  190. }
  191. }
  192. }
  193. if(solve0(good)){
  194. print();
  195. return 0;
  196. }
  197. for(int i = 1; i <= n; i++){
  198. for(int j = 0; j < i; j++){
  199. if(!was0[i][j]){
  200. for(int k = -20000; k <= 20000; k++){
  201. for(int q = 1; q <= n; q++)
  202. for(int qw = 0; qw < q; qw++)
  203. a[q][qw] = a0[q][qw];
  204. for(int q = 0; q < 10; q++)
  205. for(int qw = 0; qw < 10; qw++)
  206. was[q][qw] = was0[q][qw];
  207. was[i][j] = true;
  208. a[i][j] = k;
  209. if(solve(good+1)){
  210. print();
  211. return 0;
  212. }
  213. }
  214. }
  215. }
  216. }
  217. return 0;
  218. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement