Codeforces 1073D：Berland Fair（模拟）

time limit per test: 2 seconds
memory limit per test: 256 megabytes
input: standard input
output: standard output

XXI Berland Annual Fair is coming really soon! Traditionally fair consists of $n$n booths, arranged in a circle. The booths are numbered $1$1through $n$n clockwise with $n$n being adjacent to $1$1. The $i$i-th booths sells some candies for the price of $a_i$ai​i burles per item. Each booth has an unlimited supply of candies.

Polycarp has decided to spend at most $T$T burles at the fair. However, he has some plan in mind for his path across the booths:

• at first, he visits booth number $1$1;
• if he has enough burles to buy exactly one candy from the current booth, then he buys it immediately;
• then he proceeds to the next booth in the clockwise order (regardless of if he bought a candy or not).

Polycarp’s money is finite, thus the process will end once he can no longer buy candy at any booth.

Calculate the number of candies Polycarp will buy.

Input

The first line contains two integers $n$n and $T (1≤n≤2⋅10^5, 1≤T≤10^{18})$T(1≤n≤2⋅105,1≤T≤1018) — the number of booths at the fair and the initial amount of burles Polycarp has.

The second line contains nn integers $a_1,a_2,…,a_n (1≤a_i≤10^9)$a1​,a2​,…,an​(1≤ai​≤109) — the price of the single candy at booth number $i$i.

Output

Print a single integer — the total number of candies Polycarp will buy.

Examples

input

3 38
5 2 5

output

10

input

5 21
2 4 100 2 6

output

6

Note

Let’s consider the first example. Here are Polycarp’s moves until he runs out of money:

1. Booth $1$1, buys candy for $5$5, $T=33$T=33;
2. Booth $2$2, buys candy for $2$2, $T=31$T=31;
3. Booth $3$3, buys candy for $5$5, $T=26$T=26;
4. Booth $1$1, buys candy for $5$5, $T=21$T=21;
5. Booth $2$2, buys candy for $2$2, $T=19$T=19;
6. Booth $3$3, buys candy for $5$5, $T=14$T=14;
7. Booth $1$1, buys candy for $5$5, $T=9$T=9;
8. Booth $2$2, buys candy for $2$2, $T=7$T=7;
9. Booth $3$3, buys candy for $5$5, $T=2$T=2;
10. Booth $1$1, buys no candy, not enough money;
11. Booth $2$2, buys candy for $2$2, $T=0$T=0.

No candy can be bought later. The total number of candies bought is $10$10.

In the second example he has $1$1 burle left at the end of his path, no candy can be bought with this amount.

题意

$n$n种糖果围成一圈，每种糖果每个$a_i$ai​元。初始时你有$T$T元，接着你从$1$1开始绕圈。一旦你发现有糖果能买，你就买一个。直到一个糖果都买不起。问最后买了多少个糖果。

Slove

首先对数据进行处理：$n$n种糖果全部买一次需要多少钱，找到$n$n种糖果中最便宜的价格

然后计算所有的糖果均能买的圈数有多少。

将剩余的钱进行进行按圈数模拟：一圈一圈的模拟肯定是不行的，稳稳地超时，所以需要进行优化

将剩余的钱数与当前所在位置的糖果价格进行比较，更新钱数，并记录每一圈结束后的次大值，当次大值等于最小值的时候，证明已经不能买除了最便宜的糖果外的其他糖果，此时结束循环。将剩余的钱数除以最小值（向下取整）可得到最终剩余的钱能买糖果数

Code

代码用时：77ms

/*************************************************************************
    > File Name: D.cpp
    > Author: WZY
    > Created Time: 2019年02月15日 16:33:54
 ************************************************************************/

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ms(a,b) memset(a,b,sizeof(a))
#define pi acos(-1.0)
#define INF 0x7f7f7f7f
#define debug(...) cerr<<"["<<#__VA_ARGS__":"<<(__VA_ARGS__)<<"]"<<"\n"
const double E=exp(1);
const int maxn=1e6+10;
const int mod=1e9+7;
using namespace std;
ll a[maxn];
ll sum[maxn];
int main(int argc, char const *argv[])
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	ll t;
	cin>>n>>t;
	ll minn=1e18+10;
	ll sum=0;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sum+=a[i];
		minn=min(minn,a[i]);
	}
	ll ans=0;
	ll res=t/sum;
	ans+=res*n;
	ll s=t%sum;
	if(s==0)
	{
		cout<<ans<<endl;
		return 0;
	}
	ll minnn=1e9+10;
	while(s>minn)
	{
		ll _=minnn;
		for(int i=1;i<=n;i++)
		{
			if(s>=a[i])
			{
				s-=a[i];
				ans++;
				// 更新次小值
				if(a[i]!=minn&&a[i]<minnn&&a[i]!=minn)
					minnn=a[i];
			}
		}
		// 如果次小值没有得到更新，并且次小值大于剩余钱数，证明只有最小钱数的糖果可以购买
		if(minnn==_&&s<minnn)
			break;
	}
	ans+=s/minn;
	cout<<ans<<endl;
	return 0;
}