Fişierul intrare/ieşire: | psychtraining.in, psychtraining.out | Sursă | FMI No Stress 6 |
Autor | Mihai Calancea | Adăugată de | |
Timp execuţie pe test | 0.25 sec | Limită de memorie | 20480 kbytes |
Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Psychtraining
Deşi naţionala de fotbal s-a calificat la Euro 2016, fanii nu sunt prea mulţumiţi de jocul echipei. Antrenorul a fost înlocuit, după o campanie intensă de scouting, cu Marius Dumitran, care va coordona echipa din Londra. Marius a realizat că mare parte din problemele naţionalei izvorăsc din psihicul jucătorilor. Astăzi Marius vrea să rezolve rivalităţile din cadrul echipei. El a numerotat jucătorii din lotul extins cu numere de la 1 la N. Şi-a notat de asemenea cele M relaţii de rivalitate din cadrul echipei. El doreşte să organizeze un număr de meciuri în cadrul sesiunii de antrenamente, astfel încât oricare 2 jucători care sunt rivali să joace la un moment dat unul împotriva altuia. La fiecare meci el va împărţi toţi jucătorii în exact 2 echipe, nu neaparat egale, una dintre ele posibil vide.
Marius n-are timp acum să organizeze meciurile, dar vă face cinste cu o anumită băutură alcoolică dacă o faceţi voi. Deoarece jucătorii s-au cam îngrăşat din cauza aceleiaşi băuturi alcoolice, nu ar trebui să dispute prea multe meciuri. Mai exact, soluţia voastră va primi punctaj pe test doar dacă numărul de meciuri este maxim 10.
Date de intrare
Fişierul de intrare psychtraining.in va conţine pe prima sa linie numerele N şi M, reprezentând numărul de jucători din lotul lărgit al României, respectiv numărul de relaţii de rivalitate dintre aceştia. Urmează M linii, fiecare conţinând o pereche de numere X Y, semnificând faptul că jucătorul cu numărul X şi jucătorul numărul Y au o rivalitate crâncenă.
Date de ieşire
Fişierul de ieşire psychtraining.out va conţine pe prima sa linie numărul MATCHES. Acesta este numărul de partide desfăşurat în soluţia voastră, iar el trebuie să fie maxim 10. Următoarele MATCHES linii vor conţine un şir de lungime N cu caractere din mulţimea {'a', 'b'}. Dacă poziţia i a şirului conţine caracterul a, atunci al i-lea jucător va fi în prima echipa, altfel va fi în a doua echipă. Ordinea echipelor este irelevantă, i.e şirurile aba şi bab sunt identice.
Restricţii
- 1 ≤ N ≤ 500
- 1 ≤ M ≤ N * (N - 1) / 2
Exemplu
psychtraining.in | psychtraining.out |
---|---|
3 2 1 2 1 3 | 2 aab aba |
Explicaţie
Avem rivalităţi între jucătorii 1 şi 3, respectiv între 1 şi 2. Observăm că există soluţie cu un singur meci desfăşurat, între echipele {1} şi {2, 3} (codată prin stringul "abb" sau "baa"). Însă soluţia din exemplu este de-asemenea corectă, deoarece numărul de meciuri este mai mic sau egal cu 10.