Problem G
Tomtplanering
Enligt FN uppnådde jordens befolkning 8 miljarder människor i november 2022. En som tydligt märker av detta är tomten. Han måste nämligen dela ut presenter till flera miljarder barn.
Tyvärr kommer tomten inte hinna dela ut presenter till alla barn i år. Istället behöver han välja ut en grupp barn som får presenter. För att det ska bli rättvist tänker han att exakt hälften av alla barn ska få presenter, medan andra hälften blir utan. På så sätt innehåller de två grupperna exakt lika många barn, och då blir ingen grupp avundsjuk på den andra. ”Perfekt balanserat”, som tomten brukar säga.
Du är ansvarig för att planera vilka hus som tomten ska besöka. Det finns $N$ hus numrerade från $1$ till $N$, där hus nummer $i$ har koordinater $(x_ i, y_ i)$. Att färdas mellan två punkter $(x_ i, y_ i)$ och $(x_ j, y_ j)$ tar $|x_ i-x_ j| + |y_ i-y_ j|$ sekunder1. Din uppgift är att hitta en ordnad lista med $N/2$ olika hus ($N$ är alltid jämnt), så att den totala tiden att besöka husen i den ordningen är så liten som möjligt. Tomten börjar sin resa vid det första huset i din lista, och avslutar den vid det sista huset i din lista.
Indata
Indatan består av $10$ testfall.
Den första raden innehåller ett heltal $T$ ($0 \leq T \leq 10$), numret på testfallet ($0$ är exempelfallet nedan).
Den andra raden innehåller ett heltal $N$ ($1 \le N \le 10^5$), antalet hus.
De följande $N$ raderna innehåller två heltal $x_ i$ och $y_ i$ ($0 \le x_ i, y_ i \le 10^6$), koordinaterna som det $i$:te huset ligger på. Inga två hus ligger på samma koordinater.
Utdata
Skriv ut en rad med $N/2$ heltal, numren på de hus som ska besökas i ordning.
Poängsättning
Ditt program kommer att testas på $10$ testfall och poängsättas baserat på hur den står sig relativt domarnas lösning.
Låt $P_1$ vara det totala avståndet tomten behöver åka i din lösning, och låt $P_2$ vara motsvarande för domarnas lösning. Du får då $\min (10 \cdot \frac{P_2}{P_1}, 10)$ poäng på testfallet. Du kan alltså aldrig få mer än $10$ poäng på ett testfall, även om din lösning är bättre än den domarna skrivit. Domaren kan dock visa en större poäng per testfall i användargränssnittet för inskickningsdetaljer, så att du kan se exakt hur bra din lösning är.
Din poäng för en inskickning är summan av poängen för testfallen, och din totala poäng är poängen för den bästa inskickningen. Det går alltså inte att kombinera testfall mellan olika inskickningar, utan du måste skicka in ett enda program som maximerar din poäng på alla testfall samtidigt.
Exempeltestfallet kommer alltid att ge $0$ poäng.
Testfall
Här är beskrivningar av de $10$ testfallen som förekommer. I alla testfall så har koordinaterna genererats likformigt slumpmässigt mellan $0$ och $10^6$, såvida inte något annat anges.
|
Testfall |
Gränser |
Beskrivning |
|
$1$ |
$N = 10^5$ |
$y_ i = 0$ för alla $i$ |
|
$2$ |
$N = 10^5$ |
$0 \leq y_ i \leq 20$ för alla $i$ |
|
$3$ |
$N = 10$ |
|
|
$4$ |
$N = 40$ |
|
|
$5$ |
$N = 200$ |
|
|
$6$ |
$N = 800$ |
|
|
$7$ |
$N = 7000$ |
|
|
$8$ |
$N = 40000$ |
|
|
$9$ |
$N = 80000$ |
|
|
$10$ |
$N = 10^5$ |
Förklaring av exampelfall 1
I exempelfallet så uppnår exempellösningen det totala avståndet $40$ eftersom avståndet mellan hus $2$ och hus $4$ är $5$, och avståndet mellan hus $4$ och hus $1$ är $35$. Det finns flera sätt att uppnå ett bättre svar, till exempel genom att besöka husen i ordningen 4 2 1. Då blir det totala avståndet $35$ istället.
| Sample Input 1 | Sample Output 1 |
|---|---|
0 6 0 0 10 20 1000000 1000000 15 20 10 30 50 60 |
2 4 1 |
Footnotes
- $|a|$ är den matematiska notationen för absolutbeloppet av talet $a$, definerat som $a$ om $a \ge 0$ och $-a$ om $a < 0$.
