달팽이
면접 대비시간 제한1초메모리 제한512 MB
매일 N개의 단계로 오르내리며 높이가 0 아래로 내려가지 않는 달팽이가 처음으로 높이 H에 도달하는 날과 단계를 구하고, 영원히 도달하지 못하면 -1 -1을 출력한다.
문제
달팽이가 높이 H인 우물 바닥에 갇혀 있다. 달팽이는 처음에 높이 0에 있고, 우물 밖으로 나가려고 한다. 바닥, 즉 높이 0에 있는 데에는 장점도 있다. 달팽이는 더 아래로 미끄러질 수 없다. 높이가 음수가 될 수는 없다.
하루는 N개의 단계로 이루어진다. 각 단계에서 달팽이는 일정량만큼 오르려고 하거나, 쉬면서 일정량만큼 미끄러진다. 달팽이는 각 단계에서 얼마나 움직이는지 알고 있고, 이를 Pi로 나타낸다. Pi가 양수이면 달팽이가 위로 이동한다는 뜻이고, 음수이면 아래로 미끄러진다는 뜻이며(높이 0에 도달할 때까지), 0이면 높이를 유지한다.
달팽이가 우물을 빠져나가기 위해 높이 H에 처음 도달하는 날과 단계를 구하라.
입력
프로그램은 표준 입력에서 입력을 읽는다.
첫째 줄에는 우물의 높이를 나타내는 양의 정수 H와 하루의 단계 수를 나타내는 N이 주어진다.
다음 줄에는 달팽이의 일과를 나타내는 N개의 부호 있는 정수 P0, P1, P2, ..., PN−1이 공백으로 구분되어 주어진다. Pi는 단계 i에서 달팽이가 이동하는 양이다.
출력
프로그램은 표준 출력에 출력을 인쇄한다.
한 줄에 두 정수를 공백으로 구분하여 인쇄한다.
달팽이가 D일의 단계 P에서 처음으로 우물 꼭대기(높이 H)에 도달하면 D를 인쇄한 다음 P를 인쇄한다.
그렇지 않고 달팽이가 항상 우물에 갇혀 있으면 −1을 인쇄한 다음 −1을 인쇄한다.
제한
- 1 ≤ H ≤ 10^12
- −10^12 ≤ Pi ≤ 10^12
- 1 ≤ N ≤ 10 000