問題一覧 > 通常問題

No.3715 Tomorrow is MONDAY!!!!!!

レベル : / AI推定難易度 : 1200 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 40
作問者 : kazuppa / テスター : ぽえ 👑 loop0919
お気に入りにしたユーザー ProblemId : 13984 / 自分の提出
問題文最終更新日: 2026-09-21 12:48:42
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 514 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。