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 BR 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
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

Instancia 1
ok

Instancia 2
1 4 5 6

 

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;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
5
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

x
+
cmd
Instancia 1
ok
Instancia 2
1 4 5 6
Advertisements

Demonstration


Previous
#1816 Beecrowd Online Judge Solution 1816 Prague Vikings? Solution in C, C++, Java, Js and Python
Next
#1827 Beecrowd Online Judge Solution 1827 Square Array IV Solution in C++, Java, Js and Python