30366번 - Roller Coaster
일본 놀이공원 그룹(JAG)에서는 더 많은 사람들을 끌어들이기 위해 더 나은 오락 시설에 대해 논의하고 있습니다. 최근에는 대기 시간으로 인한 스트레스를 줄이는 것에 관심이 있습니다.
JAG의 멤버로서, 당신은 대기 시간을 아는 것이 이러한 종류의 스트레스를 줄일 수 있다는 가설을 발견했습니다. 따라서, 롤러코스터의 대기 시간을 예측하는 프로그램을 작성하기로 결정했습니다.
\(N\)개의 그룹이 롤러코스터를 타기 위해 줄을 서 있으며, 그룹들은 1부터 \(N\)까지 번호가 매겨져 있습니다. 그룹 \(i\)는 \(a_i\)명의 사람들로 구성되어 있습니다. 줄을 선 사람들은 그룹 번호의 오름차순으로 롤러코스터를 탑니다.
첫 번째 롤러코스터는 0분에 출발하며, 이후 매 분마다 출발합니다. 롤러코스터는 최대 \(M\)명까지 탑승할 수 있습니다.
각 그룹의 모든 멤버는 반드시 동시에 롤러코스터를 타야 합니다. 또한, 정확히 \(M\)명이 롤러코스터에 탑승할 필요는 없습니다. 각 그룹은 가능한 한 빨리 롤러코스터를 타기를 원하므로, 탑승이 가능하다면 바로 탑승합니다.
\(N\)개의 줄을 출력해야 합니다. \(i\)번째 줄에는 그룹 \(i\)가 롤러코스터를 탈 수 있는 시간을 출력해야 합니다.
\(N\) \(M\) \(a_1\) \(a_2\) \(\dots\) \(a_N\)
첫 번째 줄은 1 이상 100,000 이하의 정수 \(N\)과 1 이상 10⁹ 이하의 정수 \(M\)으로 구성됩니다. \(N\)은 그룹의 수를 나타내고, \(M\)은 롤러코스터의 수용 인원을 나타냅니다.
두 번째 줄은 1 이상 \(M\) 이하의 \(N\)개의 정수로 구성됩니다. 각 \(i\) (1 ≤ i ≤ N)에 대해, \(a_i\)는 그룹 \(i\)의 인원수를 나타냅니다.
\(N\)개의 줄을 출력합니다. \(i\)번째 줄에는 그룹 \(i\)에 대한 답을 출력해야 합니다.
3 5 2 4 1
0 1 1
2 1000000000 1000000000 1000000000
0 1
댓글을 작성하려면 로그인해야 합니다.
hanzch 2년 전 3
롤러코스터
일본 놀이공원 그룹(JAG)에서는 더 많은 사람들을 끌어들이기 위해 더 나은 오락 시설에 대해 논의하고 있습니다. 최근에는 대기 시간으로 인한 스트레스를 줄이는 것에 관심이 있습니다.
JAG의 멤버로서, 당신은 대기 시간을 아는 것이 이러한 종류의 스트레스를 줄일 수 있다는 가설을 발견했습니다. 따라서, 롤러코스터의 대기 시간을 예측하는 프로그램을 작성하기로 결정했습니다.
\(N\)개의 그룹이 롤러코스터를 타기 위해 줄을 서 있으며, 그룹들은 1부터 \(N\)까지 번호가 매겨져 있습니다. 그룹 \(i\)는 \(a_i\)명의 사람들로 구성되어 있습니다. 줄을 선 사람들은 그룹 번호의 오름차순으로 롤러코스터를 탑니다.
첫 번째 롤러코스터는 0분에 출발하며, 이후 매 분마다 출발합니다. 롤러코스터는 최대 \(M\)명까지 탑승할 수 있습니다.
각 그룹의 모든 멤버는 반드시 동시에 롤러코스터를 타야 합니다. 또한, 정확히 \(M\)명이 롤러코스터에 탑승할 필요는 없습니다. 각 그룹은 가능한 한 빨리 롤러코스터를 타기를 원하므로, 탑승이 가능하다면 바로 탑승합니다.
\(N\)개의 줄을 출력해야 합니다. \(i\)번째 줄에는 그룹 \(i\)가 롤러코스터를 탈 수 있는 시간을 출력해야 합니다.
입력
\(N\) \(M\)
\(a_1\) \(a_2\) \(\dots\) \(a_N\)
첫 번째 줄은 1 이상 100,000 이하의 정수 \(N\)과 1 이상 10⁹ 이하의 정수 \(M\)으로 구성됩니다. \(N\)은 그룹의 수를 나타내고, \(M\)은 롤러코스터의 수용 인원을 나타냅니다.
두 번째 줄은 1 이상 \(M\) 이하의 \(N\)개의 정수로 구성됩니다. 각 \(i\) (1 ≤ i ≤ N)에 대해, \(a_i\)는 그룹 \(i\)의 인원수를 나타냅니다.
출력
\(N\)개의 줄을 출력합니다. \(i\)번째 줄에는 그룹 \(i\)에 대한 답을 출력해야 합니다.
예제
예제 입력 1
예제 출력 1
예제 입력 2
예제 출력 2
제한
1 ≤ M ≤ 10⁹
1 ≤ \(a_i\) ≤ M (1 ≤ i ≤ N)