Informatica Online Judge

  사탕 사 먹기 [2282 / 08EA]

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


The Champion of this Problem (C++) : tlsdydaud1 - 0ms / 350byte
My Best Submission (C++) : N/A

[codeforces Edu Round]

Background

경곽이는 축제에서 사탕을 사먹기로 했다.

사탕을 파는 가게는 모두 n개가 있으며 각 가게에는 1부터 n까지의 번호가 부여되어 있다.

이 가게는 원형으로 배치되어 있어서 1과 n은 연결된다.

경곽이는 현재 T원을 가지고 있으며 각 i번째 가게에서 사탕 한 개를 a_i원에 팔고 있다.

경곽이는 다음과 같은 방법으로 사탕을 사 먹기로 했다.

-------------------------------------------------------------------------------------

- 처음에 먼저 가게 1을 방문한다.

- 만약 경곽이가 가진 돈으로 방문한 가게의 사탕을 살 수 있으면 정확히 1개의 사탕을 사 먹는다. 그렇지 않으면 그냥 지나간다.

- 다음으로 시계방향으로 이동하여 다음 가게로 간다. 이와 같이 진행하면서 더 이상 사먹을 수 없으 때까지 사탕을 사 먹는다.

-------------------------------------------------------------------------------------


주어진 정보들을 이용하여 경곽이가 최대 몇 개의 사탕을 사먹을 수 있는지 구하는 프로그램을 작성하시오.

Input

첫 번째 줄에 두 개의 자연수 n과 T가 입력된다.

다음 줄에 각 i번째 가게의 사탕 가격이 공백으로 구분되어 입력된다.

[입력값의 정의역]
1 <= n <= 200,000
1 <= T <= 10^18
0 <= a_i <= 10^9

Output

경곽이가 사 먹을 수 있는 사탕의 수를 출력한다.

IO Example

입력1
3 38
5 2 5

출력1
10

입력2
5 21
2 4 100 2 6

출력2
6

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