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
redigeraDet 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 107), 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)