Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | atena.in, atena.out | Sursă | Tabăra ICHB 2012, Ziua 2, Grupa 2 |
| Autor | Dan Constantin Spatarel | Adăugată de |  Dan-Constantin Spatarel •spatarel |
| Timp execuţie pe test | 0.2 sec | Limită de memorie | 16384 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Atena
În Grecia antică, reţeaua stradală a oricărui oraş era formată din intersecţii legate prin drumuri bidirecţionale, construite în aşa fel încât din orice intersecţie să se poată ajunge în oricare altă intersecţie, direct sau indirect, trecând prin alte intersecţii. De asemenea, între oricare două intersecţii ale unui oraş existau cel mult un drum direct şi nu existau drumuri de la o intersecţie la ea însăşi.
Se ştie că în acele vremuri, reţeaua stradală a oraşului Atena avea N1 intersecţii, legate prin M1 drumuri bidirecţionale, în timp ce reţeaua stradală a oraşului Sparta avea N2 intersecţii, legate prin M2 drumuri bidirecţionale. Intersecţiile din Atena se consideră numerotate cu numere de la 1 la N1, în timp ce intersecţiile din Sparta se consideră numerotate cu numere de la N1 + 1 la N1 + N2.
Pericle, regele Atenei, a decis să afle în ce măsură reţeaua de străzi a Spartei este asemănătoare cu reţeaua de străzi a oraşului Atena. În acest scop, el i-a cerut unuia dintre matematicienii atenieni, Parmenide, să afle dacă reţeaua de străzi a Spartei este inclusă în reţeaua de străzi a Atenei.
Pericle consideră că reţeaua de străzi a Spartei este inclusă în reţeaua de străzi a Atenei dacă şi numai dacă există submulţimi disjuncte două câte două nevide A1, A2, ..., ANi ale mulţimii { 1, 2, ..., Ni } cu proprietatea că pentru orice drum între două intersecţii N1 + a şi N1 + b în Sparta există un drum între o intersecţie c şi o intersecţie d în Atena, cu c din Aa, d din Ab şi 1 <= a, b <= N2, 1 <= c, d <= N1.
Din păcate Parmenide a murit în timp ce încerca să ajungă la Congresul de Matematică Aplicată din Siracuza, aşa că sarcina lui v-a revenit vouă. Totuşi Parmenide a menţionat în treacăt înainte să plece că rezolvarea problemei se bazează în mod esenţial pe următoarele două proprietăţi ale reţelei stradale din Atena:
- N1 ≥ 2 * M2;
- Oricum am alege o intersecţie a din Atena, şi alte 3 intersecţii distincte b, c şi d legate prin drumuri de a, există un drum între b şi c, sau un drum intre c şi d, sau un drum între b şi d (pot exista chiar două dintre aceste drumuri, sau toate trei la un loc).
Scrieţi un program care determină dacă reţeaua stradală din Sparta este inclusă în reţeaua stradală din Atena, în sensul dat de Pericle. Dacă răspunsul este afirmativ, atunci programul trebuie să determine şi mulţimile A1, A2, ..., ANi.
Date de intrare
Fişierul de intrare atena.in ...
Date de ieşire
În fişierul de ieşire atena.out ...
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| atena.in | atena.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
