Quadradets P76718


Statement
 

pdf   zip

thehtml
La Ivet s’està avorrint molt. En lloc de posar-se a estudiar, ha decidit dibuixar creus a l’atzar en un full quadriculat de mides n × n. Ara té curiositat per saber quants quadradets 2 × 2 ha dibuixat. Un quadradet no pot ser adjacent (horitzontalment, verticalment, o diagonalment) a cap altra creu. A l’exemple de la dreta, l’únic quadradet està pintat de verd.

Com que encara li sobra una mica de temps, la Ivet també vol comptar quants quasi-quadradets ha dibuixat. Un quasi-quadradet és un quadradet al qual li falta exactament una creu. A l’exemple de la dreta, els quatre quasi-quadradets estan pintats de vermell.





vermell1 0.5 0.5 verd0.7 1 0.7 unit=0.25cm fillstyle=solid

(26,26) fillcolor=verd (22,4)(22,8)(26,8)(26,4)

fillcolor=vermell (2,2)(2,6)(6,6)(6,2) (2,18)(2,22)(6,22)(6,18) (8,4)(8,8)(12,8)(12,4) (22,22)(22,26)(26,26)(26,22)

linecolor=blue (2,2)(2,26) (4,2)(4,26) (6,2)(6,26) (8,2)(8,26) (10,2)(10,26) (12,2)(12,26) (14,2)(14,26) (16,2)(16,26) (18,2)(18,26) (20,2)(20,26) (22,2)(22,26) (24,2)(24,26) (26,2)(26,26) (2,2)(26,2) (2,4)(26,4) (2,6)(26,6) (2,8)(26,8) (2,10)(26,10) (2,12)(26,12) (2,14)(26,14) (2,16)(26,16) (2,18)(26,18) (2,20)(26,20) (2,22)(26,22) (2,24)(26,24) (2,26)(26,26)

linecolor=black [dotsize=4mm,dotstyle=x](3,3) [dotsize=4mm,dotstyle=x](5,3) [dotsize=4mm,dotstyle=x](17,3) [dotsize=4mm,dotstyle=x](3,5) [dotsize=4mm,dotstyle=x](9,5) [dotsize=4mm,dotstyle=x](11,5) [dotsize=4mm,dotstyle=x](17,5) [dotsize=4mm,dotstyle=x](23,5) [dotsize=4mm,dotstyle=x](25,5) [dotsize=4mm,dotstyle=x](11,7) [dotsize=4mm,dotstyle=x](23,7) [dotsize=4mm,dotstyle=x](25,7) [dotsize=4mm,dotstyle=x](3,11) [dotsize=4mm,dotstyle=x](13,11) [dotsize=4mm,dotstyle=x](15,11) [dotsize=4mm,dotstyle=x](23,11) [dotsize=4mm,dotstyle=x](3,13) [dotsize=4mm,dotstyle=x](5,13) [dotsize=4mm,dotstyle=x](11,15) [dotsize=4mm,dotstyle=x](15,13) [dotsize=4mm,dotstyle=x](3,15) [dotsize=4mm,dotstyle=x](11,17) [dotsize=4mm,dotstyle=x](13,17) [dotsize=4mm,dotstyle=x](21,17) [dotsize=4mm,dotstyle=x](23,17) [dotsize=4mm,dotstyle=x](25,17) [dotsize=4mm,dotstyle=x](5,19) [dotsize=4mm,dotstyle=x](19,19) [dotsize=4mm,dotstyle=x](21,19) [dotsize=4mm,dotstyle=x](23,19) [dotsize=4mm,dotstyle=x](3,21) [dotsize=4mm,dotstyle=x](5,21) [dotsize=4mm,dotstyle=x](13,21) [dotsize=4mm,dotstyle=x](9,23) [dotsize=4mm,dotstyle=x](11,23) [dotsize=4mm,dotstyle=x](23,23) [dotsize=4mm,dotstyle=x](9,25) [dotsize=4mm,dotstyle=x](11,25) [dotsize=4mm,dotstyle=x](23,25) [dotsize=4mm,dotstyle=x](25,25)

(3,1)1 (5,1)2 (7,1)3 (9,1)4 (11,1)5 (13,1)6 (15,1)7 (17,1)8 (19,1)9 (21,1)10 (23,1)11 (25,1)12

(1,3)1 (1,5)2 (1,7)3 (1,9)4 (1,11)5 (1,13)6 (1,15)7 (1,17)8 (1,19)9 (1,21)10 (1,23)11 (1,25)12

Donades totes les creus, podeu comptar el nombre de quadradets i de quasi-quadradets?

Entrada

L’entrada conté diversos casos. Cada cas comença amb la mida n del tauler, seguida del nombre de creus c. Segueixen c parells x y indicant la posició de cada creu. Podeu suposar 2 ≤ n ≤ 109, 3 ≤ c ≤ min(n2, 105), que totes les x i les y es troben entre 1 i n, i que no hi ha dues o més creus a la mateixa posició. (El primer de tots els exemples d’entrada es correspon a la figura anterior.)

Sortida

Per a cada cas, escriviu el nombre de quadradets i de quasi-quadradets.

Puntuació

  • Cas A:  ‍ Casos amb n ≤ 30, com l’exemple d’entrada 1.  ‍60% Punts ‍
  • Cas B:  ‍ Casos de tot tipus.  ‍40% Punts ‍
Public test cases

  • Input

    12 40
1 1  2 1  8 1  1 2  4 2  5 2  8 2  11 2  12 2  5 3  11 3  12 3  1 5  6 5  7 5
11 5  1 6  2 6  5 7  7 6  1 7  5 8  6 8  10 8  11 8  12 8  2 9  9 9  10 9
11 9  1 10  2 10  6 10  4 11  5 11  11 11  4 12  5 12  11 12  12 12
2 4
2 2  1 2  2 1  1 1

    Output

    1 4
1 0

  • Input

    1000000000 3
1000000000 1000000000  1000000000 999999999  999999999 1000000000

    Output

    0 1
    • Information
    Author
    Salvador Roura
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++