Informatica Online Judge

  계량 [0958 / 03BE]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 7   Total Tried : 13


The Champion of this Problem (C++) : N/A
My Best Submission (C++) : N/A

[Jihak Yoon (koistudy.net)]

Background

경곽이는 L리터짜리 큰 수조와 A리터와 B리터의 작은 컵을 가지고 있다.

경곽이는 다음과 같은 6가지의 행동을 할 수 있다.

1. 수조를 가득 채운다.
2. 수조를 텅텅 비운다.
3. 수조에 A리터를 더한다. 단, A리터를 더할 수 없으면 가득 채운다.
4. 수조에서 A리터를 뺀다. 단, A리터를 뺄 수 없으면 텅텅 비운다.
5. 수조에 B리터를 더한다. 단, B리터를 더할 수 없으면 가득 채운다.
6. 수조에서 B리터를 뺀다. 단, B리터를 뺄 수 없으면 텅텅 비운다.

경곽이는 위의 6가지 행동을 여러 번 반복하면서 신기한 점을 발견했다.

그것은 처음에 수조에 담긴 액체의 양에 따라 마지막에 수조에 담길 수 있는 액체의 양이 달라진다는 점이었다.

경곽이를 괴롭히기를 좋아하는 지학이는 N개의 수 X(i)들을 늘어놓고, 다음과 같은 문제를 냈다.

“이 수들 중 몇 개를 지워서 남은 M개의 수들을 Y(j)라 할 때, 1<=j<M인 모든 j에 대하여 수조에 Y(j)리터가 담긴 상태에서 수조에 Y(j+1)리터가 담긴 상태로 만들 수 있는 가장 큰 M은 무엇일까? 단, 이 문제는 너무 쉬우니까 모든 i에 대하여 Y(1)=X(i)인 가장 큰 M을 찾아야 해.”

N이 너무 컸기 때문에 경곽이는 답을 구할 수 없었다. 경곽이를 도와주자.

Input

첫 줄에 L,A,B가 공백을 사이에 두고 주어진다. ( 1<=A,B,L<=1,000,000,000 , A+B<=L )
다음 줄에 N이 주어진다. ( 1<=N<=100,000 )
다음 줄에 N개의 수 X(i)들이 공백을 사이에 두고 주어진다. ( 0<=X(i)<=L )

Output

첫 줄에 모든 i에 대하여 Y(1)=X(i)일 때 가장 큰 M을 출력한다.

IO Example

입력1

5 1 1
6
0 1 2 3 4 5

출력1

6 5 4 3 2 1

입력2

6 2 4
7
0 1 2 3 4 5 6

출력2

4 4 3 3 2 2 1

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