CSES - Datatähti 2022 alku - Spiraali
  • Language:
  • Time limit: 1.00 s
  • Memory limit: 512 MB

Tarkastellaan n \times n -kokoista spiraalia, joka sisältää luvut 1 \dots n^2 aloittaen vasemmasta yläkulmasta ja kiertäen vastapäivään. Tämän tehtävän oletuksena on, että n on aina parillinen.

Esimerkiksi tapauksessa n=6 spiraali näyttää tältä:

Tehtäväsi on selvittää tehokkaasti tietyssä kohdassa spiraalia oleva luku.

Syöte

Syötteen ensimmäisellä rivillä on kaksi lukua n ja t: spiraalin koko ja testien määrä.

Tämän jälkeen syötteessä on t riviä, joista jokainen kuvaa yhden testin. Rivillä on kaksi kokonaislukua y ja x: rivi ja sarake.

Tuloste

Tulosta jokaisesta testistä rivillä y sarakkeessa x oleva luku.

Esimerkki

Syöte:

6 5
1 1
2 5
4 2
4 4
5 6

Tuloste:

1
30
23
35
12

Osatehtävä 1 (15 pistettä)

  • n=10
  • t=100

Osatehtävä 2 (20 pistettä)

  • n=1000
  • t=1000

Osatehtävä 3 (65 pistettä)

  • n=10^9
  • t=1000