CSES - Datatähti 2017 alku - Bittijono
  • Time limit: 2.00 s
  • Memory limit: 512 MB

Ääretön bittijono on muodostettu aloittamalla jonosta 0 ja lisäämällä joka vaiheessa jonon perään senhetkinen jono niin, että jokainen bitti on käänteinen.

Bittijono alkaa siis muodostua seuraavasti:

  • 0
  • 01
  • 0110
  • 01101001
  • 0110100110010110
  • 01101001100101101001011001101001
  • ...

Tehtäväsi on vastata nn kyselyyn koskien bittijonon sisältöä. Jokaisessa kyselyssä sinulle annetaan kokonaisluku kk ja sinun tulee ilmoittaa jonon kohdassa kk oleva bitti. Bitit on numeroitu alkaen luvusta 1.

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku nn: kyselyiden määrä.

Sitten syötteessä on nn riviä, joista jokaisella on yksi kokonaisluku kk: kohta bittijonossa.

Tuloste

Tulosta jokaiseen kyselyyn bittijonon kohdassa kk oleva bitti.

Esimerkki

Syöte:

3
5
2
7

Tuloste:

1
1
0

Osatehtävä 1 (10 pistettä)

  • 1n1001 \le n \le 100
  • 1k1001 \le k \le 100

Osatehtävä 2 (19 pistettä)

  • 1n1051 \le n \le 10^5
  • 1k1061 \le k \le 10^6

Osatehtävä 3 (71 pistettä)

  • 1n1051 \le n \le 10^5
  • 1k10181 \le k \le 10^{18}