19879번 - Икебана
<문제>
당신은 대나무 자르기 대회에 참가하였다. 모든 참가자들에게는 일직선으로 \(n\)개의 대나무가 심겨 있는 밭이 주어진다.
왼쪽에서 \(i\)번째 대나무의 높이는 대회 첫날 05:00에 \(a_i\)이며, 매일 자정에 \(b_i\)만큼 자란다.
매일 06:00부터 참가자는 연속된 구간 \( [i,j] ( 1 \le i \le j \le n ) \) 과 높이 \( l ( 0 \le l \le 2 \cdot 10^9) \)을 선택하여 대나무를 자를 수 있다.
대나무를 자르기로 선택하였다면 왼쪽에서 \(i\)번째부터 \(j\)번째까지의 대나무 중 높이가 \(l\) 이상인 대나무는 높이가 \(l\)이 된다.
대회 마지막날 정오에 심사가 이루어지며, 밭에 있는 \(n\)개의 대나무의 높이가 모두 \(h\)인 참가자가 우승한다.
당신이 우승할 수 있는지 예측하는 프로그램을 작성해보자.
<입력>
첫번째 줄에 대나무의 개수를 나타내는 정수 \(n(1\le n\le 10^5)\), 대회 기간을 나타내는 정수 \(m(1\le m\le 10^9)\), 심사 기준이 되는 대나무의 높이를 나타내는 정수 \(h(0\le h\le 10^9)\)가 공백으로 구분되어 주어진다.
두 번째 줄부터 \(m\)개의 줄에는 각 대나무의 대회 시작날 높이 \(a_i\)와 매일 자정에 자라는 높이 \(b_i\)가 주어진다. \((0\le a_i , b_i \le 10^9)\)
<출력>
우승하기 위해 대나무를 잘라야 하는 최소 횟수를 정수 하나로 출력한다.
우승할 수 없다면 -1을 출력한다.
-1
댓글을 작성하려면 로그인해야 합니다.
iktk 2년 전 1
<문제>
당신은 대나무 자르기 대회에 참가하였다. 모든 참가자들에게는 일직선으로 \(n\)개의 대나무가 심겨 있는 밭이 주어진다.
왼쪽에서 \(i\)번째 대나무의 높이는 대회 첫날 05:00에 \(a_i\)이며, 매일 자정에 \(b_i\)만큼 자란다.
매일 06:00부터 참가자는 연속된 구간 \( [i,j] ( 1 \le i \le j \le n ) \) 과 높이 \( l ( 0 \le l \le 2 \cdot 10^9) \)을 선택하여 대나무를 자를 수 있다.
대나무를 자르기로 선택하였다면 왼쪽에서 \(i\)번째부터 \(j\)번째까지의 대나무 중 높이가 \(l\) 이상인 대나무는 높이가 \(l\)이 된다.
대회 마지막날 정오에 심사가 이루어지며, 밭에 있는 \(n\)개의 대나무의 높이가 모두 \(h\)인 참가자가 우승한다.
당신이 우승할 수 있는지 예측하는 프로그램을 작성해보자.
<입력>
첫번째 줄에 대나무의 개수를 나타내는 정수 \(n(1\le n\le 10^5)\), 대회 기간을 나타내는 정수 \(m(1\le m\le 10^9)\), 심사 기준이 되는 대나무의 높이를 나타내는 정수 \(h(0\le h\le 10^9)\)가 공백으로 구분되어 주어진다.
두 번째 줄부터 \(m\)개의 줄에는 각 대나무의 대회 시작날 높이 \(a_i\)와 매일 자정에 자라는 높이 \(b_i\)가 주어진다. \((0\le a_i , b_i \le 10^9)\)
<출력>
우승하기 위해 대나무를 잘라야 하는 최소 횟수를 정수 하나로 출력한다.
우승할 수 없다면
-1을 출력한다.