Tävlingsprogrammering/Uppgifter/Klotter

Klotter

Mitt i stadsparken har ett stort utomhusbräde (storlek NxN) målats i ett schackmönster. Raderna och kolumnerna är numrerade från 1 till N (se figur 1). De två olika typerna av diagonaler är numrerade från 1 till 2N-1 enligt figur 2 respektive figur 3. Rutan längst ner till vänster är alltså grå.

På natten har några ungdomar förstört delar av brädet med klotter. Alla rutor längs fyra linjer - en lodrät, en horisontell och två med var sin diagonaltyp - har blivit förstörda och måste målas om. Skriv ett program som beräknar hur många olika rutor totalt som har förstörts, och hur många av dem som är vita respektive gråa.

Indata

Den första raden innehåller ett heltal N (1 ≤ N ≤ 10 000 000), storleken på schackbrädet. Den andra raden innehåller fyra heltal. Dessa motsvarar, i ordning, vilken rad, kolumn, diagonal av den första typen och diagonal av den andra typen som blivit förstörda.

Utdata

Programmet ska skriva ut en rad innehållandes två heltal, antalet gråa respektive vita rutor som måste målas om.

Exempel 1: Indata

4 1 1 4 4

Exempel 1: Utdata

6 6

Exempel 2: Indata

7 1 4 11 5

Exempel 2: Utdata

13 6

Exempel 3: Indata

8 2 6 7 12

Exempel 3: Utdata

16 8

Lösning

Det finns många sätt att lösa detta problem. Man kan använda sig av en matematisk approach med en massa if-satser, men en sådan lösning blir lätt oöverskådlig och det är lätt att göra fel.

Om man är lite mer pragmatisk kan man inse att längden på linjerna inte är så långa (max 10⁷), vilket gör att man helt enkelt kan loopa över linjerna och räkna de vita och gråa rutorna, respektive. Tricket är förstås att inte räkna en ruta flera gånger, men det kan man ganska lätt lösa genom följande approach:

 foreach(square x,y in horizontalLine) 
   countSquare(x,y)
 foreach(square x,y in verticalLine) 
   if x,y not in horizontalLine
     countSquare(x,y)
 foreach(square x,y in diagonalLine1)
   if x,y not in horizontalLine and not in verticalLine
     countSquare(x,y)
 foreach(square x,y in diagonalLine2)
   if x,y not in horizontalLine and not in verticalLine and not in diagonalLine1
     countSquare(x,y)