Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | color5.in, color5.out | Sursă | Lot Deva 2013 - Baraj 2 Seniori |
| Autor | Din Folclor | Adăugată de |  Heidelbacher Andrei •a_h1926 |
| Timp execuţie pe test | 0.05 sec | Limită de memorie | 65536 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Color5
Se da un graf cu N + 1 numerotate de la 0 la N. Exista muchii de la nodul N la toate celelalte N noduri si intre oricare doua noduri A si B cu proprietatea ca A, B < N si (A + 1) = B mod N. Se observa cu numarul total de muchii este 2 * N.
Cerinta
Se cere sa colorati muchiile grafului cu un numar cat mai mic de culori astfel incat intre oricare doua noduri sa existe cel putin un drum care contine doar muchii colorate distinct.
Date de intrare
Pe prima linie a fisierului color5.in se va afla un singur numar natural $N avand semnificatia din enunt.
Date de ieşire
In fisierul color5.out se va afisa pe prima linie un singur numar natural M reprezentand numarul de culori folosit. Urmatoarele 2 * N linii vor contine cate trei numere A, B si C, semnificand faptul ca muchia dintre nodurile A si B a fost colorata in culoarea C.
Restricţii
- 3 ≤ N ≤ 100
- Culorile afisate in fisierul de iesire trebuie sa fie numere naturale din intervalul [1, M], unde M este numarul de culori folosite.
- Scorul pe care il veti obtine pe ficare test va fi calculat folosind formula: [(Raspuns_optim / Raspuns_concurent)2 * 10)].
Exemplu
| color5.in | color5.out |
|---|---|
| 3 | 1 0 3 1 1 3 1 2 3 1 0 1 1 1 2 1 2 0 1 |
Explicaţie
Avem muchie intre oricare doua noduri, deci putem folosi o singura culoare pentru colorarea grafului.
