No.2589 Prepare Integers
タグ : / 解いたユーザー数 9
作問者 :
Problem Statement
You are going to prepare integers for a Christmas party.
Initially, you have $10^{1000}$ copies of the integer $0$. You also own a machine that, when given $2$ non-negative integers $X,Y$, consumes them and produces the non-negative integer $Z$ determined as follows:
- For any non-negative integer $i$, let $x,y$ be the digits at the $K^i$ place of $X,Y$ written in base $K$, respectively. Then the digit at the $K^i$ place of $Z$ written in base $K$ is $(x+y)\bmod K$ (where $K$ is an integer of at least $2$ given in the input).
You are given $Q$ queries. Process them in the given order. Each query gives integers $t,x\ (1\leq t\leq 3)$.
- If $t=1$: you newly obtain $10^{1000}$ copies of the positive integer $x$. This also affects subsequent queries; in particular, the set of good numbers may change before and after this query.
- If $t=2$: print the $x$-th smallest value among the good numbers. If there are fewer than $x$ distinct good numbers, print
-1instead. - If $t=3$: print the number of good numbers that are at most $x$.
Input
$K\ Q$ $t_1\ x_1$ $\vdots$ $t_Q\ x_Q$
- $2\leq K\leq 10^9$
- $1\leq Q\leq 10^4$
- $1\leq t_i\leq 3$
- If $t_i=1$, then $1\leq x_i\leq 10^9$
- If $t_i=2$, then $1\leq x_i\leq 10^{18}$
- If $t_i=3$, then $0\leq x_i\leq 10^{18}$
- All input values are integers.
Output
Let $M$ be the number of queries among the $Q$ queries whose $t$ is $2$ or $3$. Print $M$ lines.
On line $j\ (1\leq j\leq M)$, print the integer as instructed by the $j$-th query among those whose $t$ is $2$ or $3$.
Print a newline after the output on line $M$ as well.
Sample
Sample 1
Input
2 8 1 13 1 5 1 9 2 5 3 5 1 11 2 5 3 5
Output
8 4 4 6
After processing up to the $3$rd query, the good numbers are $0,1,4,5,8,9,12,13$. After processing up to the $6$th query, the good numbers are $0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15$.
Sample 2
Input
17 10 1 20 2 23 3 12 1 17 2 20 3 23 1 12 2 17 3 20 2 23
Output
-1 1 19 24 16 21 22
Sample 3
Input
30 10 1 68045 1 39072 1 14466 2 846282 3 472013 2 294767 1 37755 2 50526 3 710447 3 946027
Output
-1 7867 -1 505228 71046 81000
Sample 4
Input
100000000 10 1 280891310 1 866405535 2 507843655 3 7490561978746756 1 181882853 2 869882551 3 44425977686455401 1 843088846 2 395320008 3 5837034220072028
Output
5039218270 749056200000000 869882550 10000000000000000 395320007 5837034220072029
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。