Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1426
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1426
Add Bricks in The Wall
EspañaTimelimit: 1
This in not "another brick in the wall", it's just a matter of adding numbers.
Suppose you have a wall with the shape of a triangle, like the one shown below. The wall has 9 rows and row i has exactly i bricks, considering that top row is the first one and bottom row is the ninth. Some bricks are labeled with a number and other ones are blank. Notice that labeled bricks appear only on odd rows and they occupy odd positions within the row.
The problem you must solve is finding a suitable number for each blank brick taking into account one simple rule: the number of a brick is obtained by adding the numbers of the two bricks below it. Obviously, this rule does not apply to the ninth row. Numbers are supposed to be integers.
Note: Here we have an example with two test cases. The first one corresponds to the wall depicted above.
Input
The first line of the input contains an integer N, indicating the number of test cases. This line is followed by the lines corresponding to the test cases. Each test case is described in five lines. These five lines correspond to odd rows of the wall, from top to bottom, as described above. Line i contains the numbers corresponding to odd bricks on row i of the wall (that is, non blank bricks), enumerated from left to right and separated with a single space.
It is supposed that each test case is correct, that is, there exists a solution to the problem that the case describes.
Output
For each test case, the output should consist of nine lines describing the numbers of all bricks of the wall. So, line i should contain the numbers corresponding to the i bricks on row i of the wall, enumerated from left to right and separated by a single space.
| Sample Input | Sample Output |
|
2 |
255 |
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define true 1
#define false 0
int main(int argc, char **argv)
{
int n, k, i, j;
int fe, topo, fd;
int matriz[10][10];
scanf("%d", &n);
while (n--)
{
memset(matriz, -1, sizeof(matriz));
for(i = 0; i < = 8; i += 2)
for(j = 0, k = 0; j < = (i / 2); j++, k += 2)
scanf("%d", &matriz[i][k]);
for(i = 0; i < 8; i += 2){
for(j = 0, k = 0; j < = (i / 2); j++, k += 2){
topo = matriz[i][k];
fe = matriz[i + 2][k];
fd = matriz[i + 2][k + 2];
matriz[i + 2][k + 1] = ((topo - fe - fd) / 2);
matriz[i + 1][k] = fe + matriz[i + 2][k + 1];
matriz[i + 1][k + 1] = matriz[i + 2][k + 1] + fd;
}
}
for(i = 0; i < 9; i++){
for(j = 0; j < i; j++)
printf("%d ", matriz[i][j]);
printf("%d\n", matriz[i][j]);
}
}
return 0;
}
Input
255
54 67
10 18 13
3 3 5 2
2 1 2 1 1
256
64 64
16 16 16
4 4 4 4
1 1 1 1 1
Output
121 134
54 67 67
23 31 36 31
10 13 18 18 13
5 5 8 10 8 5
3 2 3 5 5 3 2
2 1 1 2 3 2 1 1
2 0 1 0 2 1 1 0 1
256
128 128
64 64 64
32 32 32 32
16 16 16 16 16
8 8 8 8 8 8
4 4 4 4 4 4 4
2 2 2 2 2 2 2 2
1 1 1 1 1 1 1 1 1
#2 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cfloat>
#include <climits>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <locale>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
#define FOR(i, a, b) for (int i = a; i < = b; ++i)
#define RFOR(i, b, a) for (int i = b; i >= a; --i)
#define REP(i, N) for (int i = 0; i < N; ++i)
#define MAX 310
#define pb push_back
#define mp make_pair
using namespace std;
const double pi = acos(-1.0);
int matrix[11][11];
int main()
{
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--) {
for (int i = 0; i < = 8; i += 2) {
for (int j = 0; j < = i; j += 2)
cin >> matrix[i][j];
}
for (int i = 8; i > 0; i -= 2) {
for (int j = 0; j < = i; j += 2) {
int a = matrix[i][j];
int b = matrix[i][j + 2];
int c = matrix[i - 2][j];
matrix[i][j + 1] = (c - a - b) / 2;
matrix[i - 1][j] = a + matrix[i][j + 1];
matrix[i - 1][j + 1] = matrix[i][j + 1] + b;
}
}
for (int i = 0; i < = 8; i++) {
for (int j = 0; j < = i; j++)
cout << (j ? " " : "") << matrix[i][j];
cout << endl;
}
}
return 0;
}
Input
255
54 67
10 18 13
3 3 5 2
2 1 2 1 1
256
64 64
16 16 16
4 4 4 4
1 1 1 1 1
Output
121 134
54 67 67
23 31 36 31
10 13 18 18 13
5 5 8 10 8 5
3 2 3 5 5 3 2
2 1 1 2 3 2 1 1
2 0 1 0 2 1 1 0 1
256
128 128
64 64 64
32 32 32 32
16 16 16 16 16
8 8 8 8 8 8
4 4 4 4 4 4 4
2 2 2 2 2 2 2 2
1 1 1 1 1 1 1 1 1