NOI '17 P1 - Integers

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

There is an integer x, initially zero.

There are n operations. Each operation is one of the following types:

  • 1 a b: Add a \cdot 2^b to x where a is an integer (that can be negative) and b is a non-negative integer.
  • 2 k: Write x in binary, and compute the value of the digit corresponding to a weight of 2^k.

It is guaranteed that x \geq 0 at any time.

Input Specification

The first line of the input consists of four integers, n,t_1,t_2,t_3.

In the following n lines, each line describes an operation.

Two adjacent elements in a line are separated by exactly one space.

Output Specification

For each type 2 k query, output a line with an integer (0 or 1) denoting the answer. There shall be no output for each operation of 1 a b.

Sample Input

10 3 1 2
1 100 0
1 2333 0
1 -233 0
2 5
2 7
2 15
1 5 15
2 15
1 -1 12
2 15

Sample Output

0
1
0
1
0

Additional Samples

integer.zip

Constraints

For all test cases, 1 \leq t_1 \leq 3, 1 \leq t_2 \leq 4, 1 \leq t_3 \leq 2.

Explanation of t_1
  • If a test case has t_1 = 1, then a = 1.
  • If a test case has t_1 = 2, then |a| = 1.
  • If a test case has t_1 = 3, then |a| \leq 10^9.
Explanation of t_2
  • If a test case has t_2 = 1, then 0 \leq b,k \leq 30.
  • If a test case has t_2 = 2, then 0 \leq b,k \leq 100.
  • If a test case has t_2 = 3, then 0 \leq b,k \leq n.
  • If a test case has t_2 = 4, then 0 \leq b,k \leq 30n.
Explanation of t_3
  • If t_3 = 1, then all queries are after updates.
  • If t_3 = 2, then there are no additional constraints.
Test case n \leq t_1 t_2t_3
110312
21002
32\,000
44\,00013
56\,00031
68\,00022
79\,00034
810\,0003
930\,0004
1050\,0001
1160\,00032
1265\,00024
1370\,0003
14200\,000
15300\,0002
16400\,0003
17500\,0003
18600\,0004
19700\,000
20800\,0001
21900\,0002
22930\,00033
23960\,00041
24990\,00032
251\,000\,0004

Comments

There are no comments at the moment.