G. Coins

\emph{Input contains multiple but no more than 10 test cases}, the first line of input is an integer T, the number of test cases.

In the following T lines each line has for integers ( $1 \le N, X, Y, Z \le 10^9$ ), and the meaning of them have been mentioned.

C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 476K, 提交时间: 2019-10-22 20:54:29

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
    int T;
    ll n,x,y,z;
    scanf("%d",&T);
    while(T--) {
        scanf("%lld%lld%lld%lld",&n,&x,&y,&z);
        ll ans=(z+n-1)/n,now=0;
        for(int i=0;i<ans;) {
            ll k=now/x;
            n+=k*y,now%=x;
            ans=min(ans,(z-now+n-1)/n+i);
            k=(x-now+n-1)/n;
            now+=k*n;
            i+=k;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 4ms, 内存消耗: 348K, 提交时间: 2020-03-26 21:46:34

#include<iostream>
#include<cstdio>
int T;
long long n,x,y,z;
int main()
{
	std::cin>>T;
	while(T--)
	{
		std::cin>>n>>x>>y>>z;
		long long ans=(z+n-1)/n;
		long long now=0;
		for(int i=0;i<ans;)
		{
			long long k=now/x;
			n+=k*y;
			now-=k*x;
			ans=std::min(ans,(z-now+n-1)/n+i);
			k=(x-now+n-1)/n;
			now+=k*n;
			i+=k;
		}
		std::cout<<ans<<std::endl;
	}
	return 0;
}

详情