Tävlingsprogrammering/Uppgifter/Partilojalitet

Partilojalitet

Partiledaren för det ledande partiet håller en konferens i partiets högkvarter. Partimedlemmarna bor i ett tvådimensionellt rutnät, en medlem per ruta (förutom ett antal rutor innehållandes hinder). Högkvarterat befinner sig i ruta 0,0, vilket också är den ruta som partiledaren bor i.

Politikerna rör sig en ruta i taget i någon av de fyra riktningarna (upp, ner, vänster, höger). De kan inte gå till rutor som innehåller hinder. Alla politiker som kan nå konferensen i högst S steg kommer att närvara på konferensen. Eftersom politiker är lata kommer de alltid att ta den kortaste vägen till högkvarteret (eller någon av dem, om det skulle finnas flera).

Partiledaren har upptäckt att politikerna ändrar lojalitet varje gång de rör sig ett steg. Eftersom landet bara har två partier innebär det att politikerna således alternerar mellan det ledande partiet i landet och oppositionspartiet för varje steg de tar på väg mot högkvarteret.

Skriv ett program som beräknar hur många av politikerna som kommer till konferensen som medlemmar i regeringspartiet och hur många som kommer dit som medlemmar i oppositionspartiet.

Indata

Den första raden innehåller två heltal H och S (0 ≤ H ≤ 10 000, 1 ≤ S ≤ 10 000 000), antalet hinder och antalet steg enligt problembeskrivningen.

De följande H raderna innehåller koordinaterna för hindren i rutnätet. Absolutvärdena för båda koordinaterna kommer att vara mindre än 1 000.

Alla hinder kommer att vara i olika rutor, och det kommer inte finnas något hinder i ruta (0,0).

Utdata

Skriv ut en rad innehållandes två heltal, antalet politiker som kommer till konferensen som medlemmar i det ledande partiet respektive oppositionspartiet. Notera att svaret inte nödvändigtvis ryms i en 32-bitars int.

Bedömning

I 20% av testfallen kommer enbart politiker vars bostäder har absoluta koordinater mindre än 1000 att nå högkvarteret i tid.

Exempel 1: Indata

0 2

Exempel 1: Utdata

9 4

Exempel 2: Indata

Exempel 2: Utdata

10 16

Exempel 3: Indata

Exempel 3: Utdata

6254997 6250000

Exempel 4: Indata

Exempel 4: Utdata

1 0

Lösning

Det är viktigt att notera att absolutvärdena för koordinaterna för hindren är mindre än 1000. Vi kan därför skapa en matris som är 2001x2001 stor och placera ut hindrena i den. För enkelhets skull förskjuter vi alla koordinater med 1000, så element 1000,1000 i matrisen motsvarar högkvarteret. Den yttre ramen i denna matris kommer dessutom inte innehålla några hinder.

Vi kan använda oss av en BFS-sökning (http://www.csc.kth.se/contest/ioi/ioitraning/sokning.htm) för att utforska hur lång tid det tar att nå alla rutor i matrisen från högkvarteret. För varje ruta som det tar högst S steg räknar vi in i svaret. För att avgöra om det är en partianhängare eller motståndare kollar vi helt enkelt om (x+y)%2 är 0 eller 1.

Denna ansats ger oss bara hur många partimedlemmar med absolutkoordinater <= 1000 som hinner fram. Resterande partimedlemmar bor utanför hindren och kan beräknas med några matematiska formler. Det finns två fall. Vi börjar med fallet då en politiker bor rakt "öster" (eller norr, söder, väster) om vår matris. I så fall kommer han gå rakt till vänster tills matriskanten nås, varifrån vi redan vet hur långt det är till högkvarteret. Dvs, om det tar k steg att nå koordinaten (1000,y), så kommer ytterligare S-k personer längs linjen (1001,y)-(INF,y) att hinna fram. Varannan av dessa tillhör det ledande partiet, varannan oppositionspartiet. Vi loopar därför längs de fyra kanterna i matrisen och kollar hur många som bor rakt öster, norr, söder respektive väster som hinner fram.

Återstår gör de fyra hörnen, dvs de som bor nordost, sydost, nordväst och sydväst om matrisen. De som bor nordost har båda koordinaterna >= 1001. Om vi utgår från koordinat 1000,1000 (dit vi vet det kortaste avståndet), så finns det en politiker i hörnet som har avstånd 2 till rutan 1000,1000, två politiker med avstånd 3, tre med avstånd 4 osv. De med avstånd 2, 4, 6, 8 etc tillhör regeringspartiet, de andra oppositionspartiet. Vi vill därför räkna ut summan 1+3+5+... och 2+4+6+... där den första summan ska innehålla (S-k)/2 termer och den andra (S-k-1)/2 termer, där k är antalet steg till ruta 1000,1000. Genom att utnyttja formeln 1+2+3+..n = n*(n+1)/2, får vi följande resultat:

long long m = S - k - 1;
long long total = m*(m + 1)/2;
long long odd = m/2;
long long oddSum = odd*(odd + 1);   // Antal anhängare av oppositionspartiet i hörnet
long long evenSum = total - oddSum; // Antal anhängare av regeringspartiet i hörnet