Algorithm
Problem Name: 2 AD-HOC - beecrowd | 2102
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/2102
Counting in Chinese
By XIII Maratona de Programação IME-USP, 2009 
Brazil
Timelimit: 1
China is one of the biggest countries in the world and the most populous. To do a census in the country is almost a war effort. The government sends to each canton a huge matrix which must be filled with every citizen’s characteristics. Each one of these matrixes has the same size: on the lines there are the various ethnicities (there are thousands) and on the columns the characteristics that you want to measure (it could get to millions). We know that few elements of each of these matrixes are in fact filled with values different than zero.
The work of the government company that does the census is, then, to receive the P matrixes M × N (1 ≤ N ≤ 100), each one given through its non-null elements and calculate the sum matrix of the various matrixes.
Input
The input is composed by various instances. The first line of the input has a whole number T indicating the number of instances.
The first line of each instance has two integers, N and L representing respectively the size of the matrices and the total amount of non-null inputs. The following L lines contain four integers Pk, lk, ck and vk indicating that the matrix Pk has value vk at the position in line lk and collum ck
Output
For each instance print the non-null inputs of the matrix addition. For each non-null imput of the matrix, print its line, column and value correspondent, separated by a space. The output need to be sorted
Between two instances print a blank line.
| Sample Input | Sample Output |
|
3 1000 4 1 1 1 1 2 1 1 2 3 1 2 100 1 1 2 1 2 2 1000 2 2 1 500 2 2 1 50 4 1 50 1 1 2 48 1 2 3 50 1 100 1 49 2 1 |
1 1 3 1 2 101 2 2 2 48 1 2 49 2 1 50 1 101 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <cstdio>
#include <map>
#define MP make_pair
using namespace std;
typedef pair < int, int> ii;
map mapa;
int TC, m, n;
int main() {
scanf("%d", &TC);
for (int tc = 1; tc < = TC; tc++) {
if (tc != 1) printf("\n");
scanf("%d %d", &m, &n);
mapa.clear();
while (n--) {
int p, v, l, c;
scanf("%d %d %d %d", &p, &l, &c, &v);
mapa[MP(l, c)] += v;
}
for (auto it = mapa.begin(); it != mapa.end(); it++) {
printf("%d %d %d\n", (*it).first.first, (*it).first.second,
(*it).second);
}
}
return 0;
}
Input
1000 4
1 1 1 1
2 1 1 2
3 1 2 100
1 1 2 1
2 2 1000 2 2 1
500 2 2 1
50 4
1 50 1 1
2 48 1 2
3 50 1 100
1 49 2 1
Output
1 2 101
2 2 2
48 1 2
49 2 1
50 1 101