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 dă un graf cu N + 1 numerotate de la 0 la N. Există muchii de la nodul N la toate celelalte N noduri şi între oricare două noduri A şi B cu proprietatea că A, B < N şi (A + 1) = B mod N. Se observă că numărul total de muchii este 2 * N.
Cerinţă
Se cere să coloraţi muchiile grafului cu un număr cît mai mic de culori astfel încat între oricare două noduri să existe cel puţin un drum care conţine doar muchii colorate distinct.
Date de intrare
Pe prima linie a fişierului color5.in se va afla un singur număr natural N avînd semnificaţia din enunţ.
Date de ieşire
În fişierul color5.out se va afişa pe prima linie un singur număr natural M reprezentînd numărul de culori folosit. Următoarele 2 * N linii vor conţine cîte trei numere A, B şi C, semnificînd faptul că muchia dintre nodurile A şi B a fost colorată în culoarea C.
Restricţii
- 3 ≤ N ≤ 100
- Culorile afişate în fişierul de ieşire trebuie să fie numere naturale din intervalul [1, M], unde M este numărul de culori folosite.
- Scorul pe care îl veţi obţine pe ficare test va fi calculat folosind formula: [(Răspuns_optim / Răspuns_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 între oricare două noduri, deci putem folosi o singură culoare pentru colorarea grafului.
