Algorithm
Problem Name: 2 AD-HOC - beecrowd | 1820
Problem Link: https://www.beecrowd.com.br/judge/en/problems/view/1820
Sing Pil University Groups
By VIII Maratona de Programação, IME–USP 
Brazil
Timelimit: 0
In the famous university of Sing Pil the students always make the work in group. The rules for the group formation, however, are written and the rector always checks if there is a group of students who violated the rules.
Well, to tell the truth, the only existing rule dates back to the creation of the university. At that time the students comprised groups of three students to do the tasks. Four students, called Ting, Ling, Xing e Ming were close friends and, for all the tasks that need be made, they used comprise a group between them. That was too bad, because forcing the tasks into groups aimed to increase interaction among students. Since then was banned in Sing Pil the square formation, i.e, that four students assemble four groups in which only they are the members.
For students {Ting, Xing, Ling, Ming} (we will use only the first letter for short) a square would be formed by four groups as follows:
{TLX, TXM, MXL, LMT}.
Your task in this problem is write a program to help the university president to verify whether or not there are squares in groups.
Input
Several instances are given. For each instance it is given the number m (0 ≤ m ≤ 50) groups. The value m = 0 indicates the end of the data and it should not be processed.
Each student in Sing Pil is identified with an integer number between 1 and 100 inclusive. In the next m lines are given, in each row, three numbers corresponding to three students who form a group.
Output
For each solve instence, you should print a identifier Instancia h wherein h is an integer, and increasing sequentially from number 1. If there are no squares in groups, your program should print ok. Otherwise, your program should print all found squares, one per line, with the students numbers separated by a blank space. To facillitate the readind of the rector, the students numbers in a square should be in ascending order and the squares should be listed in ascending lexicographic order.
A blank line should separate the output of each instance.
| Sample Input | Sample Output |
|
5 |
Instancia 1 Instancia 2 |
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <algorithm>
#include <cstdio>
#include <unordered_map>
#include <unordered_set>
#define CONV1 101
#define CONV2 10001
using namespace std;
int main() {
int m, instancia = 1;
while (scanf("%d", &m) && m) {
printf("Instancia %d\n", instancia++);
unordered_set < int> conjunto;
unordered_map<int, int> frequencia;
for (int i = 0; i < m; i++) {
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
if (a > c) swap(a, c);
if (a > b) swap(a, b);
if (b > c) swap(b, c);
conjunto.insert(a + b * CONV1 + c * CONV2);
frequencia[a]++;
frequencia[b]++;
frequencia[c]++;
}
int ok = 1;
for (int i = 1; i < = 100; i++) {
if (frequencia[i] < 4) continue;
for (int j = i + 1; j < = 100; j++) {
if (frequencia[j] < 4) continue;
for (int k = j + 1; k < = 100; k++) {
if (frequencia[k] < 4) continue;
if (!conjunto.count(i + CONV1 * j + CONV2 * k)) continue;
for (int l = k + 1; l < = 100; l++) {
if (frequencia[l] < 4) continue;
if (!conjunto.count(i + CONV1 * j + CONV2 * l))
continue;
if (!conjunto.count(i + CONV1 * k + CONV2 * l))
continue;
if (!conjunto.count(j + CONV1 * k + CONV2 * l))
continue;
printf("%d %d %d %d\n", i, j, k, l);
ok = 0;
}
}
}
}
if (ok) printf("ok\n");
printf("\n");
}
return 0;
}
Input
1 2 3
4 5 6
1 5 6
3 6 7
8 6 1
8
1 2 3
4 5 6
1 5 4
7 6 4
5 1 6
3 6 5
6 1 4
2 5 6
0
Output
ok
Instancia 2
1 4 5 6