Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #pragma GCC optimize("O3")
- #define count masloriy1489
- #define ll long long
- #define pb push_back
- #define eb emplace_back
- #define all(v) v.begin(), v.end()
- #define rep(i, n) for(int i = 0; i < n; i++)
- using namespace std;
- //freopen("input.txt", "r", stdin);
- //freopen("output.txt", "w", stdout);
- int n;
- vector<int> a0[10];
- vector<int> a[10];
- bool was0[10][10] = { false };
- bool was[10][10] = { false };
- void print(){
- for(int i = 1; i <= n; i++){
- for(int j = 0; j < i; j++){
- cout << a[i][j] << " ";
- }
- cout << '\n';
- }
- exit(0);
- }
- bool prove2(int i, int j){
- if(j > i - 2)
- return true;
- if(was[i][j] && was[i-1][j] && was[i][j+1]){
- if(a[i-1][j] != a[i][j] + a[i][j+1])
- return false;
- }
- return true;
- }
- bool solve2(int i, int j){
- if(j > i - 2)
- return false;
- if(!was[i][j] && a[i][j] == 0){
- if(was[i][j+1] && was[i-1][j]){
- a[i][j] = a[i-1][j] - a[i][j+1];
- was[i][j] = true;
- return true;
- }
- }else if(!was[i][j+1] && a[i][j+1] == 0){
- if(was[i][j] && was[i-1][j]){
- a[i][j+1] = a[i-1][j] - a[i][j];
- was[i][j+1] = true;
- return true;
- }
- }else if(!was[i-1][j] && a[i-1][j] == 0){
- if(was[i][j] && was[i][j+1]){
- a[i-1][j] = a[i][j] + a[i][j+1];
- was[i-1][j] = true;
- return true;
- }
- }
- return false;
- }
- int solve3(int i, int j){
- if(j > i - 3)
- return 0;
- if(was[i][j]){
- if(was[i-2][j] && was[i][j+2]){
- if(!was[i-1][j]){
- int g = (!was[i][j+1]) + (!was[i-1][j]) + (!was[i-1][j+1]);
- if(g == 3){
- if((a[i-2][j] - a[i][j+2] - a[i][j]) % 2 == 1)
- return 0;
- a[i][j+1] = (a[i-2][j] - a[i][j+2] - a[i][j])/2;
- was[i][j+1] = true;
- a[i-1][j] = a[i][j] + a[i][j+1];
- was[i-1][j] = true;
- a[i-1][j+1] = a[i][j+1] + a[i][j+2];
- was[i-1][j+1] = true;
- return g;
- }
- }
- }
- }
- return 0;
- }
- int solve4(int i, int j){
- if(j > i - 4)
- return 0;
- if(was[i][j]){
- if(was[i][j+3] && was[i-2][j] && was[i-2][j+1]){
- int g = (!was[i-1][j]) + (!was[i-1][j+1]) + (!was[i-1][j+2]) + (!was[i][j+1]) + (!was[i][j+2]);
- if(g == 5){
- if((a[i-2][j] + a[i-2][j+1] - a[i][j] - a[i][j+3]) % 3 != 0)
- return 0;
- a[i-1][j+1] = (a[i-2][j] + a[i-2][j+1] - a[i][j] - a[i][j+3]) / 3;
- was[i-1][j+1] = true;
- a[i-1][j] = a[i-2][j] - a[i-1][j+1];
- was[i-1][j] = true;
- a[i-1][j+2] = a[i-2][j+1] - a[i-1][j+1];
- was[i-1][j+2] = true;
- a[i][j+1] = a[i-1][j] - a[i][j];
- was[i][j+1] = true;
- a[i][j+2] = a[i-1][j+1] - a[i][j+1];
- was[i][j+2] = true;
- return g;
- }
- }
- }
- return 0;
- }
- bool solve(int good){
- int prev = -1;
- while(good < (n*(n+1) / 2)){
- if(prev == good)
- return false;
- prev = good;
- for(int i = 2; i <= n; i++){
- for(int j = 0; j < i; j++){
- good += solve2(i, j);
- }
- }
- for(int i = 2; i <= n; i++){
- for(int j = 0; j < i; j++){
- good += solve3(i, j);
- }
- }
- for(int i = 2; i <= n; i++) {
- for (int j = 0; j < i; j++) {
- good += solve4(i, j);
- }
- }
- }
- for(int i = 2; i <= n; i++) {
- for (int j = 0; j < i; j++) {
- if(!prove2(i,j))
- return false;
- }
- }
- return true;
- }
- bool solve0(int good){
- int prev = -1;
- while(good < (n*(n+1) / 2)){
- if(prev == good)
- return false;
- prev = good;
- for(int i = 2; i <= n; i++){
- for(int j = 0; j < i; j++){
- good += solve2(i, j);
- }
- }
- for(int i = 2; i <= n; i++){
- for(int j = 0; j < i; j++){
- good += solve3(i, j);
- }
- }
- for(int i = 2; i <= n; i++) {
- for (int j = 0; j < i; j++) {
- good += solve4(i, j);
- }
- }
- }
- return true;
- }
- int main()
- {
- ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
- cin >> n;
- int good = 0;
- for(int i = 1; i <= n; i++){
- for(int j = 0; j < i; j++){
- int x;
- cin >> x;
- a0[i].pb(x);
- a[i].pb(x);
- if(x != 0){
- was0[i][j] = true;
- was[i][j] = true;
- good++;
- }
- }
- }
- if(solve0(good)){
- print();
- return 0;
- }
- for(int i = 1; i <= n; i++){
- for(int j = 0; j < i; j++){
- if(!was0[i][j]){
- for(int k = -20000; k <= 20000; k++){
- for(int q = 1; q <= n; q++)
- for(int qw = 0; qw < q; qw++)
- a[q][qw] = a0[q][qw];
- for(int q = 0; q < 10; q++)
- for(int qw = 0; qw < 10; qw++)
- was[q][qw] = was0[q][qw];
- was[i][j] = true;
- a[i][j] = k;
- if(solve(good+1)){
- print();
- return 0;
- }
- }
- }
- }
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement