Informatica Online Judge

  롤케잌 자르기 [1900 / 076C]

Time Limit(Test case) : 2000 (ms)
Number of users who solved : 14   Total Tried : 20


The Champion of this Problem (C++) : t1234 - 19ms / 383byte
My Best Submission (C++) : N/A

[koistudy.net (T JKJeong 2017)]
Writer ID : [jkjeong]

Background

각 영역의 가치가 1부터 100까지인 길이가 n인 롤케잌이 있다.

길동이는 이 롤케잌을 두 동생들에게 나눠주려고 한다.

롤케잌의 적당한 부분을 잘라서 앞부분은 길삼이, 뒷부분은 길순이에게 주려고 한다.

자를 때는 영역의 경계부분 중 한 곳을 자를 수 있다.

길동이는 길삼이와 길순이가 받게되는 가치의 비율이 x:y가 되도록 나눠주고자 한다.

만약 정확히 x:y로 나눌 수 없다면 길삼이가 비율 x를 초과하지 않도록 최대한 분배해야 한다.

당연히 길순이는 길삼이에게 분배하고 남은 모든 롤케잌을 가지게 된다.

길동이는 비율을 잘 정하기 위해 여러분에게 m번의 질문을 한다.

각 질문은 x, y의 값이 주어진다.

각 질문들에 대해서 어디를 잘라야 하는지 알려주는 프로그램을 작성하시오.

만약 케잌의 크기가 5이고 각 영역의 가치가 1, 2, 3, 4, 5라면 자르는 영역의 번호는 다음과 같이 주어진다.

1 | 2 | 3 | 4 | 5
(0) (1) (2) (3) (4) (5)



(0), (5)번을 자른다는 의미는 주어진 비율로 계산하면 둘 중 한 명에게 모든 케잌을 줄 경우라고 할 수 있음에 주의한다.

Input

첫 번째 줄에 케잌의 영역수를 나타내는 자연수 n이 주어진다.

두 번째 줄에 영역의 가치를 나타내는 값 n개가 공백으로 구분되어 입력된다.

세 번째 줄에 질문의 수 m이 입력된다.

다음 줄 부터 m줄에 걸쳐서 한 줄에 하나씩 x, y의 값이 공백으로 구분되어 입력된다.

[입력값의 정의역]

1 <= n <= 1,000,000
1 <= m <= 100,000
0 <= x, y <= 1,000,000,000
1 <= 각 케잌의 가치 <= 1,000

Output

m개의 질문에 대해서 한 줄에 하나씩 어디를 잘라야하는지 하나의 정수를 출력한다.

IO Example

입력
5
1 2 3 4 5
3
1 1
2 1
0 1

출력
3
4
0

* 설명 :
첫 번째 질문은 1:1로 분배하라고 했다.
이 때 3번을 자르게 되면 앞부분은 합은 6 뒷부분은 9이다.
하지만 4번을 자르게 되면 앞부분이 10, 뒷부분은 5가 된다. 앞부분의 비율 x를 초과하지 않아야 된다고 했으므로 3번을 잘라야 한다.

두 번째 질문은 2:1이므로 4번을 자르면 10과 5가 되어 정확하게 분배할 수 있다.

마지막 질문은 0:1로 자르라고 했으므로 모두 길순이에게 줘야한다. 따라서 0을 자르면 된다.

Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]