Problem E
Expressrecept
Languages
en
sv
Du har precis börjat prenumerera på tjänsten EGOI (Expressrecept - Gott Och Inspirerande) som skickar ut recept regelbundet för att hjälpa till med matinspiration. Det innebär att du kommer få $N$ recept skickade på posten det kommande året.
Du har insett att om man har $N$ recept som ligger i en oordnad hög är det ofta svårt att hitta rätt bra recept att laga när man är stressad.
För att motverka att det blir så för dig i framtiden har du skaffat dig en pärm med $2N$ plastfickor där du kan lägga in dina recept.
Du vill lägga in recepten ordnat efter hur lång tid de tar att laga eftersom det då blir lätt att hitta något passande att laga beroende på hur stressad du är. Eftersom det inte går att flytta runt plastfickorna i pärmen kan det vara så att du behöver flytta gamla recept till andra plastfickor när du ska lägga in ett nytt recept. Exempelvis, om du tidigare har lagt ett recept som tar $7$ minuter att laga i plastfickan precis efter ett recept som tar $5$ minuter att laga och sedan får ett recept som tar $6$ minuter att laga måste du flytta på åtminstone ett av de gamla recepten för att kunna lägga in det nya.
Även medan du flyttar runt recepten måste de alltid vara kvar i rätt ordning; annars kanske du blir förvirrad och råkar ha kvar dem i en felaktig ordning även efter att du har lagt in det nya receptet.
Nu vill du försöka minimera antalet förflyttningar av recepten du totalt måste göra genom att lägga in dem i pärmen strategiskt redan från början.
Det är garanterat att alla recept tar olika lång tid att laga och det gör inget om det finns tomma plastfickor mellan recepten när du är klar.
Interaktion
På första raden kommer du att läsa in ett heltal $N$ ($2 \leq N \leq 1000$), antalet recept du kommer att få i år. Pärmen innehåller alltid $2N$ plastfickor.
Därefter kommer du att få $N$ recept. För varje recept ska du först läsa in ett heltal $t$ ($1 \leq t \leq 10^9$), antalet minuter receptet tar att laga, och sedan ska svara med vilka förflyttningar du vill göra.
Förflyttningarna ska vara på formen ”$a$ $b$”, vilket betyder att du vill flytta receptet som tar $a$ minuter att laga till plastficka $b$. $a$ måste antingen vara tiden $t$ eller tiden det tar att laga ett recept som du har fått tidigare. $b$ måste vara ett tal mellan $0$ och $2N-1$, notera i synnerhet att pärmen alltså är $0$-indexerad. Så fort du skriver in en förflyttning som beskriver var receptet som tar $t$ minuter att laga ska hamna kommer det att stoppas in i pärmen och efter det förväntas du läsa in tiden för nästa recept.
Se till att flusha outputen efter varje query, annars kan du få Time Limit Exceeded. I C++ kan detta göras med exempelvis cout << flush; eller fflush(stdout);, i Python med sys.stdout.flush() och i Java med System.out.flush();. Koden för att generera recepttiderna deterministisk, vilket innebär att samma recepttider kommer att genereras om samma lösning skickas in flera gånger. Dessutom kan domaren vara adaptiv, vilket innebär att den anpassar sin strategi efter din lösning.
För att förenkla testning av ditt program tillhandahåller vi ett verktyg som du kan ladda ner längst ned vid ”attachments” på det här problemets Kattissida. Se kommentaren högst upp i filen för en beskrivning av hur det kan användas.
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
Låt $Q$ vara det maximala antal förfyttningar du får göra.
|
Grupp |
Poäng |
Gränser |
|
$1$ |
$10$ |
$N = 2, Q = 5$ |
|
$2$ |
$10$ |
$N \leq 10, Q = 1000$ |
|
$3$ |
$20$ |
$N \leq 1000, Q = 1000000$ |
|
$4$ |
$25$ |
$N \leq 1000, Q = 100000$ |
|
$5$ |
$10$ till $35$ |
$N \leq 1000, Q = 50000$ |
Poänggrupp $5$ använder sig av adaptiv poängsättning. Om du använder som mest $25000$ förflyttningar, får du $35$ poäng. Annars får du $60-\lfloor \frac{q}{1000}\rfloor $ poäng, där $q$ är antal förflyttningar du använt.
Förklaring av exempelfall
Först placeras receptet med som tar $7$ minuter på plats $0$. Sedan får vi ett recept som tar $2$ minuter. Eftersom det måste läggas in före receptet som tar $7$ minuter måste vi flytta på det receptet. Därför flyttar vi receptet som tar $7$ minuter till plats $1$, och placerar receptet som tar $2$ minuter på plats $0$. Sedan kommer ett recept som tar $12$ minuter som vi placerar på plats $2$. När receptet som tar $9$ minuter kommer måste vi dock flytta på receptet som tar $12$ minuter, så vi lägger det på plats $3$ och receptet som tar $9$ minuter på plats $2$. Slutligen får vi ett recept som tar $18$ minuter som vi kan lägga var som helst längst bak i pärmen.
| Read | Sample Interaction 1 | Write |
|---|
5 7
7 0
2
7 1 2 0
12
12 2
9
12 3 9 2
18
18 5