No.3389 k-Days Later
タグ : / 解いたユーザー数 76
作問者 :
yu23578
/ テスター :
GaLLium
yt142857
aa36
Germanium32
Problem Statement
In the calendar of the Kingdom of yu23578, a year consists of $N$ months: month $1$, month $2$, $\cdots$, month $N$. Month $i (1 \le i \le N)$ consists of $D_i$ days: day $1$, day $2$, $\cdots$, day $D_i$.
You are given $Q$ queries. In the $i$-th query, you are given $y_i,m_i,d_i,k_i$. Find the date (year, month, and day) that is $k_i$ days after year $y_i$, month $m_i$, day $d_i$.
Constraints
- $1 \le N,Q \le 10^5$
- $1 \le D_i \le 10^9$
- $1 \le y_i \le 10^{18}$
- $1 \le m_i \le N$
- $1 \le d_i \le D_{m_i}$
- $1 \le k_i \le 10^{18}$
- All input values are integers.
Input
$N$ $D_1\ D_2\ \cdots\ D_N$ $Q$ $y_1\ m_1\ d_1\ k_1$ $y_2\ m_2\ d_2\ k_2$ $\vdots$ $y_Q\ m_Q\ d_Q\ k_Q$
Output
Output $Q$ lines. On the $i$-th line, when the date $k_i$ days after year $y_i$, month $m_i$, day $d_i$ is year $a_i$, month $b_i$, day $c_i$, output $a_i,b_i,c_i$ in this order, separated by spaces.
Print a newline at the end.
Sample
Sample 1
Input
5 2 3 5 7 8 5 1 1 2 1 1 2 1 2 1 1 1 25 23 5 7 8 271828182845904523 5 3 602874713526624977
Output
1 2 1 1 2 3 2 1 1 24 3 2 295943171386969522 5 5
In query number $1$, since month $1$ only has days up to day $2$, the date $1$ day after year $1$, month $1$, day $2$ is year $1$, month $2$, day $1$.
In query number $2$, since month $2$ has days up to day $3$, the date $2$ days after year $1$, month $2$, day $1$ is year $1$, month $2$, day $3$.
In query number $3$, since $1$ year has $25$ days, the date $25$ days after year $1$, month $1$, day $1$ is year $2$, month $1$, day $1$.
As in query number $5$, the input may not fit in a 32-bit integer.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。