아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

멈추지 않는 주행

시간 제한1초메모리 제한128 MB

요약
2시 정각에 초록불로 시작하는 신호등 최대 6개의 주기를 보고, 빨간불에 걸리지 않고 주행할 수 있는 30에서 60mph 사이의 정수 속도를 모두 찾는다.
난이도

보통10점 중 5점

유형
시뮬레이션, 수학, 구현, 완전 탐색
정답자
아직 제출이 없습니다

문제

필은 야간 근무를 마치고 매일 새벽 정확히 2시에 회사 주차장을 나선다. 집으로 가는 길은 신호등이 하나 이상 놓인 직선 도로다. 필은 각 신호등의 위치와 주기가 주어졌을 때, 빨간불 때문에 속도를 올리거나 줄이지 않고도 집까지 갈 수 있는 속도가 있는지 궁금해한다. 이를 알려 주는 프로그램을 작성하라.

프로그램은 필이 귀갓길에 사용할 수 있는 모든 정수 속도(시속 마일)를 찾아야 한다. 어떤 속도가 가능하다는 것은, 새벽 2시에 주차장을 나서는 순간부터 집에 도착할 때까지 그 속도를 그대로 유지하면서(감속할 공간이 충분한 긴 진입로가 있다고 가정한다) 빨간불을 단 한 번도 지나치지 않는 경우를 뜻한다. 신호가 노란불에서 빨간불로 바뀌는 바로 그 순간, 또는 빨간불이 초록불로 바뀌는 바로 그 순간에는 통과할 수 있다. 필은 준법정신이 강하므로 시속 60마일 이하만 고려하고, 지나치게 느리게 달리고 싶지도 않으므로 시속 30마일 이상만 고려한다.

입력

입력은 신호등 집합을 설명하는 하나 이상의 데이터 집합으로 이루어지며, 정수 −1-1로 끝난다.

각 데이터 집합의 첫 정수는 신호등의 개수 NN이며 N≤6N \le 6이다. 그 뒤에 신호등마다 네 값 LL, GG, YY, RR이 순서대로 NN묶음 주어진다. LL은 주차장에서 잰 신호등의 위치(마일)를 나타내는 양의 실수다. GG, YY, RR은 각각 그 신호등 주기의 초록불, 노란불, 빨간불 지속 시간(초)이다. NN개의 신호등은 모두 새벽 2시에 정확히 초록불로 시작한다.

출력

각 데이터 집합마다 (1부터 시작하는) 경우 번호를 출력한 뒤, 모든 빨간불을 피할 수 있는 정수 속도를 모두 나열한다.

연속된 속도는 구간 표기 L-H로 적는데, 여기서 L과 H는 그 구간의 가장 낮은 속도와 가장 높은 속도다. 길이가 1인 구간(L-L)은 값 하나 L로만 적는다. 구간은 쉼표로 구분한다. 가능한 속도가 하나도 없으면 대신 No acceptable speeds. 문구를 출력한다. 형식은 예제를 참고하라.

예제1

  1. 예제 1

    입력
    1
    5.5  40 8 25
    
    3
    10.7  10 2 75
    12.5  12 5 57
    17.93 15 4 67
    
    -1
    
    예상 출력
    Case 1: 30, 32-33, 36-38, 41-45, 48-54, 59-60
    Case 2: No acceptable speeds.