Baltic Olympiad in Informatics 2018 - day 1

Start

2018-04-27 23:00 AKDT

Baltic Olympiad in Informatics 2018 - day 1

End

2018-04-28 04:00 AKDT
The end is near!
Contest is over.
Not yet started.
Contest is starting in -952 days 17:38:39

Time elapsed

5:00:00

Time remaining

0:00:00

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}

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