| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 37 | 8 | 7 | 22.581% |
Osim ako živite ispod kamena, zasigurno ste upoznati s činjenicom da će Josip, Marin i Paula predstavljati hrvatsku na finalu studentskog ICPC natjecanja (削除) 2020. (削除ここまで) 2021. godine u Rusiji. Zanimljivo je da su im pripreme za natjecanje pomalo nekonvencionalne. Naime, umjesto da rješavaju stara finala, oni uporno smišljaju nove, vlastite zadatke i sudjeluju u organizaciji srednjoškolskih natjecanja. Između ostalog, članovi su znanstvenog povjerenstva i ovogodišnjih Izbornih Priprema.
Vidjevši rezultate prvog dana, odlučili su u potpunosti promijeniti skup zadataka (engl. problemset) prvotno namijenjen drugom danu. Radili su na zadacima cijeli dan i cijelu noć te konačno završili s poslom oko četiri sata ujutro. Zaključili su da im se ne isplati spavati, te su početak natjecanja odlučili zajedno pričekati u lokalnom lokalu gdje za okruglim stolom mogu pijuckati viski s coca-colom.
Marin: Gledajte, u ovom lokalu nalazi se kladomat. Hoćemo li zaigrati jedan tiket?
Josip: Nitko normalan nije ni budan nedjeljom u 4:20 ujutro, a kamoli da se igra neka profesionalna sportska liga.
Paula: Ne znam o čemu pričate, ja samo vidim neke peseke koji trče u krug.
I tako su se naši finalisti odlučili okladiti na utrku pasa. U utrci sudjeluje $N$ pasa označenih prirodnim brojevima od 1ドル$ do $N$. Svaki od naših finalista kladio se na točan poredak pasa, odnosno na tiketu im piše neka permutacija brojeva od 1ドル$ do $N$ za koju smatraju da će odgovarati konačnom poretku pasa.
Priprema, pozor, sad!
Finalisti su grčevito držali tikete sve dok i zadnji pas nije ušao u cilj. Potom se na displeju pojavila permutacija brojeva od 1ドル$ do $N$ koja odgovara konačnom poretku. Više sreće drugi put. . .
Marin: Dajte da vidim vaše tikete, zanima me broj parova pasa za koje smo svo troje pogodili ili svoje troje pogriješili relativan poredak.
Josip: Hm, zvuči kao dobar zadatak, možda bolje da stavimo to nego da ponovimo onaj sa xorovima.
Paula: Taman stignemo, ali ovaj puta ja radim primjere!
Sve vam je jasno, odredite broj parova pasa $(a, b)$ takvih da je u konačnom poretku pas $a$ stigao u cilj prije psa $b,ドル te se na svakom tiketu pas $a$ nalazi prije psa $b$ ili se na svakom tiketu pas $b$ nalazi prije psa $a$.
U prvom je retku prirodan broj $N,ドル broj pasa.
U drugom se retku nalazi permutacija brojeva od 1ドル$ do $N$ koja predstavlja konačan poredak pasa na utrci (od prvog prema posljednjem).
U trećem se retku nalazi permutacija brojeva od 1ドル$ do $N$ koja predstavlja Josipovu okladu (od prvog psa prema posljednjem).
U četvrtom se retku nalazi permutacija brojeva od 1ドル$ do $N$ koja predstavlja Marinovu okladu (od prvog psa prema posljednjem).
U petom se retku nalazi permutacija brojeva od 1ドル$ do $N$ koja predstavlja Paulinu okladu (od prvog psa prema posljednjem).
U jedini redak ispišite traženi broj parova pasa iz teksta zadatka.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 7 | 2ドル ≤ N ≤ 5,000円$ |
| 2 | 8 | 2ドル ≤ N ≤ 500,000円,ドル Josip i Marin su se kladili na identičan poredak pasa. |
| 3 | 29 | 2ドル ≤ N ≤ 50,000円$ |
| 4 | 56 | 2ドル ≤ N ≤ 500,000円$ |
3 2 3 1 1 2 3 1 2 3 2 3 1
1
4 3 1 2 4 4 3 2 1 1 2 3 4 1 2 4 3
0
5 1 3 2 4 5 4 3 5 2 1 4 3 1 2 5 1 2 4 3 5
3
Pojašnjenje trećeg probnog primjera: Svo troje su ispravno pogodili da će pas 3ドル$ stići u cilj prije psa 5ドル,ドル te da će pas 4ドル$ stići u cilj prije psa 5ドル$. Također, svo troje su pogrešno procijenili da će pas 4ドル$ stići u cilj prije psa 3ドル$.