28939번 - Шкаф для обуви
메이블 가족에게 새 신발장이 생겼습니다. 이 신발장은 대 가족과 많은 손님을 맞이하게 되어 금방 채워졌습니다.
메이블은 사람들이 신발장에 신발을 어떻게 넣고 가져가는지 주의 깊게 관찰했습니다.
메이블의 관찰 결과
이 신발장의 선반은 다양한 높이로 배치되어 있습니다. 1번째 선반은 바닥에서 h_1만큼의 높이에 있고, 2번째 선반은 h_2의 높이에 있고, ... n 번째 선반은 높이 h_n에 있습니다.
메이블은 사람들의 키가 height일 때, height보다 큰 높이의 선반에는 신발을 놓을 수 없으며, height / k보다 낮은 높이의 선반에 신발을 놓을 수 없다는 것을 관찰했습니다.
또한 키가 height인 사람의 신발 크기는 height / m_1보다 작지 않고 height / m_2보다 크지 않다는 것을 알았습니다.
이제 메이블은 신발장을 보고 있는데, 마술처럼 신발 몇 켤레가 거기서 나왔다고 생각하고 있습니다 - 관찰한 바에 따르면 아무도 신발을 거기에 놓을 수 없습니다.
이를 확인하도록 도와주세요 - 관찰한 것과 일치하지 않는 신발의 수를 세어보세요.
입력
첫 번째 줄에는 찬장에 있는 선반의 수인 숫자 n이 주어집니다(1 <= n <= 10^5).
두 번째 줄에는 세 개의 숫자 k, m_1, m_2,
메이블(1 <= k <= 100; 1 <= m2 <= m1 <= 100)에 의해 유도된 계수가 주어집니다.
다음 n줄은 선반에 대한 설명입니다.
설명의 시작 부분은 i번째 선반의 높이가 주어집니다.
숫자 h_i - 선반의 높이입니다(1 <= h_1 <= 10^7, h_{i-1} < h_i <= 10^7 --- 모든 i > 1에 대해)
그 다음 이 선반에 있는 신발 켤레의 수 k_i(1 <= k_i <= 10^5)가 주어집니다.
그런 다음 k_i개의 선반에 있는 신발 한 켤레당 크기가 주어집니다(1 <= size <= 10^7).
출력
메이블의 관찰결과를 만족하지 않는 신발 켤레의 수를 한 줄에 출력하십시오.
예시
예제입력에서 2번째 선반(h_2)을 예로 들면
첫번째 신발의 크기는 1 이므로
height/m1 <= 신발의 크기 <= height/m2
= 신발의 크기* m2 <= height <= 신발의 크기* m1
= 1 <= height <= 1
신발을 놓기 위한 조건은
h_2 <= height , h_2 >= height/k 이므로 둘을 height에 대해 정리하면
h_2 <= height <= h_2 * k
= 2 <= height <= 4
이기 때문에 겹치는 범위가 없으므로 이 신발의 주인은 h_2선반에 신발을 놓을 수 없습니다.
메이블의 관찰 결과를 만족하지 않습니다.
댓글을 작성하려면 로그인해야 합니다.
rty3394 2년 전 2
메이블 가족에게 새 신발장이 생겼습니다. 이 신발장은 대 가족과 많은 손님을 맞이하게 되어 금방 채워졌습니다.
메이블은 사람들이 신발장에 신발을 어떻게 넣고 가져가는지 주의 깊게 관찰했습니다.
메이블의 관찰 결과
이 신발장의 선반은 다양한 높이로 배치되어 있습니다. 1번째 선반은 바닥에서 h_1만큼의 높이에 있고, 2번째 선반은 h_2의 높이에 있고, ... n 번째 선반은 높이 h_n에 있습니다.
메이블은 사람들의 키가 height일 때, height보다 큰 높이의 선반에는 신발을 놓을 수 없으며, height / k보다 낮은 높이의 선반에 신발을 놓을 수 없다는 것을 관찰했습니다.
또한 키가 height인 사람의 신발 크기는 height / m_1보다 작지 않고 height / m_2보다 크지 않다는 것을 알았습니다.
이제 메이블은 신발장을 보고 있는데, 마술처럼 신발 몇 켤레가 거기서 나왔다고 생각하고 있습니다 - 관찰한 바에 따르면 아무도 신발을 거기에 놓을 수 없습니다.
이를 확인하도록 도와주세요 - 관찰한 것과 일치하지 않는 신발의 수를 세어보세요.
입력
첫 번째 줄에는 찬장에 있는 선반의 수인 숫자 n이 주어집니다(1 <= n <= 10^5).
두 번째 줄에는 세 개의 숫자 k, m_1, m_2,
메이블(1 <= k <= 100; 1 <= m2 <= m1 <= 100)에 의해 유도된 계수가 주어집니다.
다음 n줄은 선반에 대한 설명입니다.
설명의 시작 부분은 i번째 선반의 높이가 주어집니다.
숫자 h_i - 선반의 높이입니다(1 <= h_1 <= 10^7, h_{i-1} < h_i <= 10^7 --- 모든 i > 1에 대해)
그 다음 이 선반에 있는 신발 켤레의 수 k_i(1 <= k_i <= 10^5)가 주어집니다.
그런 다음 k_i개의 선반에 있는 신발 한 켤레당 크기가 주어집니다(1 <= size <= 10^7).
출력
메이블의 관찰결과를 만족하지 않는 신발 켤레의 수를 한 줄에 출력하십시오.
예시
예제입력에서 2번째 선반(h_2)을 예로 들면
첫번째 신발의 크기는 1 이므로
height/m1 <= 신발의 크기 <= height/m2
= 신발의 크기* m2 <= height <= 신발의 크기* m1
= 1 <= height <= 1
신발을 놓기 위한 조건은
h_2 <= height , h_2 >= height/k 이므로 둘을 height에 대해 정리하면
h_2 <= height <= h_2 * k
= 2 <= height <= 4
이기 때문에 겹치는 범위가 없으므로 이 신발의 주인은 h_2선반에 신발을 놓을 수 없습니다.
메이블의 관찰 결과를 만족하지 않습니다.