No.3715 Tomorrow is MONDAY!!!!!!
Problem Statement
Kazuppa, the king of the Kingdom of kazuppa, has a hobby of angering his citizens by saying "Tomorrow is Monday!" every Sunday.
From here on, every date mentioned is assumed to be in the year 2026.
The calendar of the Kingdom of kazuppa is described by positive integers $K,N$ and a sequence of positive integers $(D_1,D_2,\dotsc,D_K)$ as follows.
- $1$ year consists of $K$ months in total, months $1,2,\dotsc,K$, and month $i$ consists of $D_i$ days in total, days $1,2,\dotsc,D_i$.
- Day $1$ of month $1$ is a Sunday, and none of the days from the day after it through $N-1$ days after it is a Sunday.
- A week has $N$ days. That is, if a certain day is a Sunday, then the days $N$ days after it and $N$ days before it are also Sundays.
Kazuppa can perform the following operation any number of times.
- Choose one pair of integers $(i,j)\ (1\leq i,j\leq K)$. Decrease $D_i$ by $1$ and increase $D_j$ by $1$. However, during the process of operations, there must never exist an $i$ satisfying $D_i= 0$.
For each $m=1,2,\dotsc,K$, answer the following independent problem.
Find the minimum number of operations required for the number of Sundays in month $m$ of the modified calendar to be strictly greater than the number of Sundays in month $m$ of the original calendar. If no operations satisfy the condition, output
-1.
Constraints
- $1\leq K\leq 2\times 10^5$
- $2\leq N\leq 2\times 10^{14}$
- $1\leq D_i\leq 10^9$
- All input values are integers.
Input
$K\ N$ $D_1\ D_2\ \dotsc\ D_K$
Output
Output $K$ lines.
On the $i$-th line, output the answer for $m=i$.
Sample
Sample 1
Input
6 3 1 6 9 2 3 1
Output
3 3 1 1 3 3
For example, when $m=1$, suppose we perform operations choosing $(i,j)=(2,1),(3,1),(2,1)$. The number of Sundays in month $m$ is then as follows: in the calendar before the operations, $(1,6,9,2,3,1)$, there is a total of $1$ day, namely month $1$, day $1$; in the calendar after the operations, $(4,4,8,2,3,1)$, there is a total of $2$ days, namely month $1$, day $1$ and month $1$, day $4$. Thus the goal is achieved with $3$ operations. The goal cannot be achieved with fewer than $3$ operations, so the answer is $3$.
Sample 2
Input
1 2 169231
Output
-1
If no operations satisfy the condition, output -1.
Sample 3
Input
2 2 2 2
Output
1 -1
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。
kazuppa
ぽえ