iktk   2년 전

문제.

당신은 여행 중이며, 지금 한 정류장에서 버스를 기다리고 있다. 운이 나쁘게도 이 정류장은 세계에서 최악의 버스 배차 간격을 가지고 있다. $N$개의 버스 노선이 있으며, 노선별로 각각 배차 간격은 $M$개의 정수$m_1$, $m_2$, $\cdots$, $m_M$으로 주어진다.

모든 버스 노선의 첫차는 $0$ 시점에 출발하며, 그 이후에는 배차 간격이 지난 후에 출발한다. 배차 간격은 순환한다. 예를 들어, $2$번째 차는 $m_1$ 시점에 출발하고, $3$번째 차는 $m_1+m_2$ 시점에, ... , $M+2$번째 차는 $m_1 + \sum m_i$ 시점에 출발한다.각 배차 간격은 $1$ 이상 $1\;000$ 이하의 정수이다.

입력.

테스트케이스의 수는 100개 이하이다.

각 테스트케이스는 다음과 같이 구성된다.

  1. 첫 번째 줄에 START N이 주어진다. $(1\le N\le 20)$
  2. 두 번째 줄부터 $N$개의 줄에 각 버스 노선의 배차 간격이 공백으로 구분된 $1$개 이상 $10$개 이하의 정수로 주어진다.
  3. 그 다음 줄에는 당신의 도착 시점 $A$가 주어진다. $0$시점에 도착하는 경우도 있다.
  4. 그 다음 줄에는 END가 주어진다.

출력.

테스트케이스별로 당신이 버스를 타기 위해 기다려야 하는 최소 시간을 정수로 출력한다. 아무 버스 노선이나 탈 수 있는 것으로 가정한다.

댓글을 작성하려면 로그인해야 합니다.