Problem A
Armastuse hulknurk
Nagu me kõik teame, on seebiooperite tegelased omavahel tõsiselt keerulistes suhetes. Ühes seebiooperis on $N$ tegelast, kellest igaüks armastab täpselt üht isikut. On ka võimalik, et tegelane armastab (alguses) ainult iseennast. Ütleme, et kaks tegelast on paarisuhtes, kui esimene armastab teist ja teine esimest.
Vahel tekib eriti keeruline suhe, mida nimetatakse “armastuse hulknurgaks”. Ütleme, et 3 või enam inimest on “armastuse hulknurgas”, kui esimene armastab teist, teine kolmandat jne, kuni viimane isik armastab esimest.
Vaatajaküsitlused näitavad, et televaatajad on sellisest draamast väsinud nig eelistaks midagi romantilisemat. Meil on võimalik muuta, keda inimene armastab, tulistades teda armunoolega. Eesmärgiks on, et kõik isikud oleksid paarisuhetes.
Mis on minimaalne arv armunooli, mis selleks tuleb kulutada?
Sisend
Esimesel real on täisarv $N$, mis tähistab seebiooperi tegelaste arvu. Järgmistel $N$ real on igaühel kaks tühikuga eraldatud nime $s$ ja $t$, mis tähendavad, et tegelane $s$ armastab alguses tegelast $t$. Nimed on ülimalt $10$ tähe pikkused ja koosnevad ladina tähestiku väiketähtedest.
Väljund
Väljundisse kirjutada üks täisarv – minimaalne armunoolte arv, mis kindlustaks, et kõik tegelased on suhtes. Kui see ei ole võimalik, väljastada -1.
Piirangud
Selles ülesandes on testid jagatud gruppidesse. Iga grupi eest saavad punkte ainult need programmid, mis lahendavad õigesti kõik gruppi kuuluvad testid. Sinu lõplik skoor on esitatud lahenduste skooride maksimum.
|
Grupp |
Punkte |
Piirangud |
Lisapiirangud |
|
1 |
21 |
$2 \le N \le 20$ |
|
|
2 |
25 |
$2 \le N \le 100\, 000$ |
Iga isiku puhul leidub keegi, kes teda armastab (võimalik, et ta ise). |
|
3 |
29 |
$2 \le N \le 100\, 000$ |
Alguses pole ühtki paarisuhet ega “armastuse hulknurka”. |
|
4 |
25 |
$2 \le N \le 100\, 000$ |
Näidete selgitus
![\includegraphics[width=0.5\textwidth ]{polygonfig.pdf}](/problems/lovepolygon/file/statement/et/img-0001.png)
Esimene näide on toodud joonisel. Ülemine osa illustreerib algset olukorda, kus nool, mis näitab isikult $s$ isikule $t$, tähendab, et isik $s$ armastab alguses isikut $t$, ning roosa värv tähistab kolme isikut, keda tuleb optimaalse olukorra saavutamiseks tulistada. Alumine osa näitab lõppseisu.
Teises näites (mis rahuldab alamülesande 3 tingimusi) on mitu võimalikku lahendust. Üks võimalus on tulistada iskuid a, b and d, nii et nad hakkavad armastama isikuid b, a ja c.
Kolmandas näites on meil armastuse kolmnurk ja ükskõik, kuidas nooli lasta, jääb keegi alati välja.
| Sisendi näide 1 | Väljundi näide 1 |
|---|---|
8 leonard emmy ada emmy isaac leonard emmy pierre pierre bernhard bernhard emmy sofia karl karl sofia |
3 |
| Sisendi näide 2 | Väljundi näide 2 |
|---|---|
4 a c b c c d d d |
3 |
| Sisendi näide 3 | Väljundi näide 3 |
|---|---|
3 rocky scarlet scarlet patrick patrick rocky |
-1 |
