26062번 - Туристы, достопримечательности и телескопы
한 나라에는 N개의 도시가 있고, 이 도시는 일직선 위에 위치해 있다. 각 도시는 s_i개의 관광지를 가지고 있다.
관광객들이 한 도시의 관광지뿐 아니라 다른 도시의 관광지도 즐길 수 있도록, X-tensive 회사는 각 도시에 망원경을 설치하기로 했다.
그러나 한 도시에서 관광객들이 볼 수 있는 관광지의 수가 R개를 초과하면, 다른 도시에 방문할 필요가 없어지므로 안 된다.
이를 위해 각 망원경의 세기를 조절할 수 있다.
세기 <0> → 관광객은 해당 도시의 관광지만 볼 수 있다.
<0>
세기 <1> → 관광객은 인접한 도시들의 관광지도 함께 볼 수 있다.
<1>
세기 <2> → 관광객은 그 이웃의 이웃 도시까지 볼 수 있고, 이런 식으로 확장된다.
<2>
물론, 망원경의 세기가 너무 커서 나라의 경계를 넘어서는 경우는 허용되지 않는다.
X-tensive 회사는 충분히 논의한 끝에, 각 망원경을 가능한 최대 세기로 설정하되 모든 조건을 만족시키기로 했다.
여러분의 임무는 각 도시의 망원경 세기를 결정하거나, 불가능하다면 -1을 출력하는 것이다.
-1
첫 번째 줄에는 두 정수 N과 R이 주어진다.
N: 나라의 도시 개수
R: 한 도시에서 볼 수 있는 관광지의 최대 개수
(3≤N≤10^5, 1≤R≤10^14)
두 번째 줄에는 N개의 정수 s_i가 공백으로 구분되어 주어진다.
s_i: 각 도시에 있는 관광지의 개수
(1≤s_i≤10^9)
총 N줄을 출력한다.
i번째 줄에는 i번째 도시의 망원경 세기를 출력한다.
조건을 만족하는 세기를 설정할 수 없는 경우 -1을 출력한다.
댓글을 작성하려면 로그인해야 합니다.
rail 1년 전
문제
한 나라에는 N개의 도시가 있고, 이 도시는 일직선 위에 위치해 있다. 각 도시는 s_i개의 관광지를 가지고 있다.
관광객들이 한 도시의 관광지뿐 아니라 다른 도시의 관광지도 즐길 수 있도록, X-tensive 회사는 각 도시에 망원경을 설치하기로 했다.
그러나 한 도시에서 관광객들이 볼 수 있는 관광지의 수가 R개를 초과하면, 다른 도시에 방문할 필요가 없어지므로 안 된다.
이를 위해 각 망원경의 세기를 조절할 수 있다.
세기
<0>→ 관광객은 해당 도시의 관광지만 볼 수 있다.세기
<1>→ 관광객은 인접한 도시들의 관광지도 함께 볼 수 있다.세기
<2>→ 관광객은 그 이웃의 이웃 도시까지 볼 수 있고, 이런 식으로 확장된다.물론, 망원경의 세기가 너무 커서 나라의 경계를 넘어서는 경우는 허용되지 않는다.
X-tensive 회사는 충분히 논의한 끝에, 각 망원경을 가능한 최대 세기로 설정하되 모든 조건을 만족시키기로 했다.
여러분의 임무는 각 도시의 망원경 세기를 결정하거나, 불가능하다면
-1을 출력하는 것이다.입력
첫 번째 줄에는 두 정수 N과 R이 주어진다.
N: 나라의 도시 개수
R: 한 도시에서 볼 수 있는 관광지의 최대 개수
(3≤N≤10^5, 1≤R≤10^14)
두 번째 줄에는 N개의 정수 s_i가 공백으로 구분되어 주어진다.
s_i: 각 도시에 있는 관광지의 개수
(1≤s_i≤10^9)
출력
총 N줄을 출력한다.
i번째 줄에는 i번째 도시의 망원경 세기를 출력한다.
조건을 만족하는 세기를 설정할 수 없는 경우
-1을 출력한다.