Educational Codeforces Round 53 (Rated for Div. 2) D - Berland Fair

D. 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 nn booths, arranged in a circle. The booths are numbered 11through nn clockwise with nn being adjacent to 11. The ii-th booths sells some candies for the price of aiai burles per item. Each booth has an unlimited supply of candies.

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

• at first, he visits booth number 11;
• 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 nn and TT (1≤n≤2⋅1051≤n≤2⋅105, 1≤T≤10181≤T≤1018) — the number of booths at the fair and the initial amount of burles Polycarp has.

The second line contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤1091≤ai≤109) — the price of the single candy at booth number ii.

Output

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

Examples

input

Copy

3 38
5 2 5

output

Copy

10

input

Copy

5 21
2 4 100 2 6

output

Copy

6

 

题意:

你有T元钱，然后这里有一个1-n的环，环上有n个点，每一个点都有一个商店，供应无限的糖果。

然后a[i]表示第i个商店的糖果的售价。对于你从i=1的商店开始走到i=2,i=3.....，顺时针走到n,再走回到1继续走。

每到达一个点，如果你口袋里的钱T>=a[i]，那么你就买一个糖果，然后继续走。这样一直走到你的钱再也不能买任何一个糖果为止。问你最后你能买到的糖果数量是多少。

 

解析:

想这道题的时候脑子一直有点乱，被他的题意给绕进去了。所以当时没有做出来，

后来想了一个早上，发现，其实每一次你都找现在存在的环里面，前缀和第一个大于T的点，然后把这个点

从环里面删掉，然后继续找。每一次找完，你都判断一下，当前环能不能用T 走一遍，能得话就看用T能走几遍，

然后加上答案，对应T减少。这样每一次，都一定会有一个点被删除，然后找第一个大于T的用二分，前缀和和环的数量

用树状数组维护，所以总的复杂度是O(nlognlogn)

但是....我后来看了榜上的大佬，发现用暴力直接就可以过......

每一次都用T 走一遍n个点，记录下花费s和买的糖果数量k，然后T/s*k加上答案，对应T减少，

然后继续这么做下去直到当前的T<糖果的最小售价就停止。

这个复杂度我算不来...我感觉是O(n*n)的复杂度，但是我比较了一下速度竟然比我的还快....（我用了140ms，大佬的用了70ms)

O(nlognlogn)

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const int MAXN = 2e5+100;
int n;
ll a[MAXN],c[MAXN];
int num[MAXN];

int lowbit(int x)
{
	return x&(-x);
}

void add_val(int x,ll y)
{
	int i;
	for(i=x;i<=n;i+=lowbit(i))
		c[i]+=y;
}

void add_num(int x,int y)
{
	int i;
	for(i=x;i<=n;i+=lowbit(i))
		num[i]+=y;
}

ll sum_val(int x)
{
	int i;
	ll s=0;
	for(i=x;i>0;i-=lowbit(i))
	{
		s+=c[i];
	}
	return s;
}

int sum_num(int x)
{
	int i;
	int s=0;
	for(i=x;i>0;i-=lowbit(i))
	{
		s+=num[i];
	}
	return s;
}

int bin_search(int l,int r,ll T)
{
    int ans=0;
    while(l<r)
    {
        int mid=(l+r)>>1;
        if(sum_val(mid)>T) ans=mid,r=mid;
        else l=mid+1;
    }
    if(sum_val(l)>T) ans=l;
    return ans;
}


int main()
{
    ll T;
    scanf("%d%lld",&n,&T);
    for(int i=1;i<=n;i++)
    {
        ll tmp;
        scanf("%lld",&tmp);
        a[i]=tmp;
        add_val(i,tmp);
        add_num(i,1);
    }

    ll ans=0;
    int plu=n;
    while(plu&&T)
    {
        int ind=bin_search(1,n,T);
        if(ind!=0){
            add_val(ind,-a[ind]);
            add_num(ind,-1);
        }
        ll p=sum_val(n);
        plu=sum_num(n);
        if(p<=T&&p)
        {
            ans+=(T/p)*plu;
            T=T%p;
        }
    }
    printf("%lld\n",ans);
    return 0;

}

大佬版的暴力

#include<bits/stdc++.h>
using namespace std;
int a[200005];
int main(){
	int n,mn=1e9;
	long long m,ans=0;
	scanf("%d %I64d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),mn=min(mn,a[i]);
	while(m>=mn){
		int s=0;
		long long k=0;
		for(int i=1;i<=n;i++) if(m>=a[i]) m-=a[i],s++,k+=a[i];
		ans+=s+(long long)m/k*s,m%=k;
	}
	printf("%lld",ans);
	return 0;
}