| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 18 | 8 | 8 | 44.444% |
En illustration av det första exempelfallet och en optimala lösningen.
Lisa har kommit till tivolit och har bestämt vilka $N$ attraktioner hon vill åka, hon vill åka varje attraktion en gång. För varje attraktion finns det två stycken anläggningar som är likvärdiga, det finns alltså totalt 2ドルN$ anläggningar. Givet positionerna för samtliga anläggninar, hjälp Lisa att planera vilka $N$ anläggningar hon ska välja och i vilken ordning för att minimera den sträcka hon måste gå för att ha åkt alla $N$ attraktioner. Hon börjar dessutom vid entrén och ska också sluta där. Entrén är vid origo.
Första raden består av heltalet $N,ドル antalet attraktioner Lisa vill åka (1ドル \le N \le 15$). Därefter följer $N$ rader, där den första raden beskriver attraktion nummer 1ドル,ドル den andra raden attraktion nummer 2ドル$ o.s.v. Varje rad innehåller fyra heltal: x- och y-koordinat för den första anläggningen av denna attraktion, samt x- och y-koordinat för den andra anläggningen av denna attraktion. Koordinaternas absolutbelopp understiger en miljon.
Ingen anläggning är på samma plats som en annan, eller på origo.
Den första raden av utdatan ska bestå av ett flyttal: hur långt Lisa måste gå. Därefter ska $N$ rader följa med två heltal vardera, varav det första inom (mellan 1ドル$ och $N$) säger vilken attraktion hon ska gå till, och det andra inom (1ドル$ eller 2ドル$) vilken av anläggningarna.
Om det finns flera vägar som ger lika kort sträcka (det finns ju åtminstone alltid två håll att gå) kan du ange vilken som helst av dem.
Det relativa eller absoluta felet ska understiga 10ドル^{-5}$.
3 3 5 1 -1 -2 0 0 4 4 4 0 6
14.233345 2 2 1 1 3 1
Olympiad > Swedish Olympiad in Informatics > 2012 > Online Qualification ?번