102812: [AtCoder]ABC281 C - Circular Playlist
Description
Score : $300$ points
Problem Statement
We have a playlist with $N$ songs numbered $1, \dots, N$.
Song $i$ lasts $A_i$ seconds.
When the playlist is played, song $1$, song $2$, $\ldots$, and song $N$ play in this order. When song $N$ ends, the playlist repeats itself, starting from song $1$ again. While a song is playing, the next song does not play; when a song ends, the next song starts immediately.
At exactly $T$ seconds after the playlist starts playing, which song is playing? Also, how many seconds have passed since the start of that song?
There is no input where the playlist changes songs at exactly $T$ seconds after it starts playing.
Constraints
- $1 \leq N \leq 10^5$
- $1 \leq T \leq 10^{18}$
- $1 \leq A_i \leq 10^9$
- The playlist does not change songs at exactly $T$ seconds after it starts playing.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
$N$ $T$ $A_1$ $\ldots$ $A_N$
Output
Print an integer representing the song that is playing at exactly $T$ seconds after the playlist starts playing, and an integer representing the number of seconds that have passed since the start of that song, separated by a space.
Sample Input 1
3 600 180 240 120
Sample Output 1
1 60
When the playlist is played, the following happens. (Assume that it starts playing at time $0$.)
- From time $0$ to time $180$, song $1$ plays.
- From time $180$ to time $420$, song $2$ plays.
- From time $420$ to time $540$, song $3$ plays.
- From time $540$ to time $720$, song $1$ plays.
- From time $720$ to time $960$, song $2$ plays.
- $\qquad\vdots$
At time $600$, song $1$ is playing, and $60$ seconds have passed since the start of that song.
Sample Input 2
3 281 94 94 94
Sample Output 2
3 93
Sample Input 3
10 5678912340 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Sample Output 3
6 678912340
Input
题意翻译
给定 $n$ 首歌曲,每首歌的时间是 $a_i$ 秒。从 $a_1$ 开始循环播放($a_1 \to \cdots \to a_n \to a_1 \to \cdots$)。 求 $T$ 秒后正在播哪首曲子,同时已经播了多长时间。 translated by @[liangbowen](https://www.luogu.com.cn/user/367488)。Output
问题描述
我们有一个包含 $N$ 首歌曲的播放列表,编号为 $1, \dots, N$。歌曲 $i$ 的时长为 $A_i$ 秒。
当播放列表播放时,歌曲 $1$、歌曲 $2$、$\ldots$、歌曲 $N$ 按此顺序播放。当歌曲 $N$ 结束时,播放列表会从歌曲 $1$ 开始重复。当一首歌正在播放时,下一首歌不会播放;当一首歌结束时,下一首歌会立即开始。
在播放列表开始播放后的确切 $T$ 秒,正在播放哪首歌?此外,从那首歌开始播放已经过去了多少秒?
输入中不会有播放列表在开始播放后的确切 $T$ 秒换歌的情况。
约束
- $1 \leq N \leq 10^5$
- $1 \leq T \leq 10^{18}$
- $1 \leq A_i \leq 10^9$
- 播放列表在开始播放后的确切 $T$ 秒不会换歌。
- 输入中的所有值都是整数。
输入
输入以标准输入的以下格式给出:
$N$ $T$ $A_1$ $\ldots$ $A_N$
输出
输出一个表示播放列表开始播放后的确切 $T$ 秒正在播放的歌曲的整数,以及表示从那首歌开始播放已经过去的时间的整数,用空格分隔。
样例输入 1
3 600 180 240 120
样例输出 1
1 60
当播放列表播放时,会发生以下情况。(假设它从时间 $0$ 开始播放。)
- 从时间 $0$ 到时间 $180$,歌曲 $1$ 播放。
- 从时间 $180$ 到时间 $420$,歌曲 $2$ 播放。
- 从时间 $420$ 到时间 $540$,歌曲 $3$ 播放。
- 从时间 $540$ 到时间 $720$,歌曲 $1$ 播放。
- 从时间 $720$ 到时间 $960$,歌曲 $2$ 播放。
- $\qquad\vdots$
在时间 $600$,歌曲 $1$ 正在播放,从那首歌开始播放已经过去了 $60$ 秒。
样例输入 2
3 281 94 94 94
样例输出 2
3 93
样例输入 3
10 5678912340 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
样例输出 3
6 678912340