QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#92949	#5259. Skills in Pills	Redcrown	AC ✓	4ms	10400kb	C++17	1.6kb	2023-03-31 09:08:39	2023-03-31 09:08:48

Judging History

你现在查看的是最新测评结果

[2023-08-10 23:21:45]
System Update: QOJ starts to keep a history of the judgings of all the submissions.

[2023-03-31 09:08:48]
评测

测评结果：AC
用时：4ms
内存：10400kb

查看

[2023-03-31 09:08:39]
提交

answer

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int MAXN = 1e6 + 5;

ll n,a,b,sum[MAXN],sum1[MAXN],sum2[MAXN];
int solve(ll sum[], ll nowa, ll nowb)
{
	ll i;
	for(i=1;i<=n;i++)
	{
		if(nowa == a)
		{
			sum[i] ++; nowa = 0;
		}
		if(nowb == b)
		{
			if(sum[i]) return i-1;
			sum[i] ++; nowb = 0;
		}
		nowa ++; nowb ++; sum[i] += sum[i-1];
		//printf("%lld nowans: %lld %lld %lld\n",i,sum[i],nowa,nowb);
	}
	return n;
}

int main()
{
	ll l,l1,l2,d,ans,nowl1,nowl2,p,pls;
	scanf("%lld%lld%lld",&a,&b,&n);
	if(__gcd(a,b) > 1)
	{
		d = a*b/__gcd(a,b)-1;
		//printf("d: %lld n: %lld\n",d,n);
		if(d >= n)
        {
            printf("%lld\n",n/a+n/b);
            return 0;
        }
		ans = d/a+d/b + 2;
		d ++;
		ans += min((n+1-d)/a+(n-d)/b,(n+1-d)/b+(n-d)/a);
		printf("%lld\n",ans);
		return 0;
	}
	l = solve(sum,1,1);
	if(l >= n)
	{
		printf("%lld\n",sum[n]); return 0;
	}
	ans = n;
	d = n-l+1;
	l1 = solve(sum1,a,b-1)-1;
	l2 = solve(sum2,a-1,b)-1;
	//printf("%lld %lld %lld %lld %lld %lld goin!\n",d,l1,l2,sum1[l1],sum2[l2],sum[l]);
	nowl1 = d/l1; nowl2 = 0;
	while(nowl1 >= 0)
	{
		while(l1*nowl1+l2*nowl2+l2 <= d) nowl2 ++;
		p = d-l1*nowl1-l2*nowl2;
		//printf("now: %lld %lld %lld %lld %lld %lld\n",d,nowl1,nowl2,l1,l2,p);
		if(p > 1)
		{
			pls = n;
			if(p <= l1+1) pls = min(pls,sum1[p]);
			if(p <= l2+1) pls = min(pls,sum2[p]);
		}
		else pls = 0;
		//printf("pls: %lld\n",pls);
		ans = min(ans,sum[l]+sum1[l1]*nowl1+sum2[l2]*nowl2+pls);
		nowl1 --;
	}
	printf("%lld\n",ans);
	return 0;
}

源文件, 语言: C++17

詳細信息

Test #1:

score: 100

Accepted

time: 0ms

memory: 3600kb

input:

3 9 20

output:

result:

ok single line: '8'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3828kb

input:

8 2 12

output:

result:

ok single line: '7'

Test #3:

score: 0

Accepted

time: 1ms

memory: 3652kb

input:

2 5 15

output:

result:

ok single line: '10'

Test #4:

score: 0

Accepted

time: 1ms

memory: 3592kb

input:

10 8 13

output:

result:

ok single line: '2'

Test #5:

score: 0

Accepted

time: 2ms

memory: 3820kb

input:

6 6 19

output:

result:

ok single line: '6'

Test #6:

score: 0

Accepted

time: 2ms

memory: 3572kb

input:

2 3 5

output:

result:

ok single line: '3'

Test #7:

score: 0

Accepted

time: 2ms

memory: 3836kb

input:

4 2 8

output:

result:

ok single line: '6'

Test #8:

score: 0

Accepted

time: 0ms

memory: 3716kb

input:

5 5 5

output:

result:

ok single line: '2'

Test #9:

score: 0

Accepted

time: 0ms

memory: 3824kb

input:

3 8 11

output:

result:

ok single line: '4'

Test #10:

score: 0

Accepted

time: 2ms

memory: 3844kb

input:

5 8 16

output:

result:

ok single line: '5'

Test #11:

score: 0

Accepted

time: 0ms

memory: 3636kb

input:

9 7 279

output:

result:

ok single line: '70'

Test #12:

score: 0

Accepted

time: 0ms

memory: 3828kb

input:

8 3 56

output:

result:

ok single line: '25'

Test #13:

score: 0

Accepted

time: 2ms

memory: 3720kb

input:

5 9 46

output:

result:

ok single line: '14'

Test #14:

score: 0

Accepted

time: 2ms

memory: 3652kb

input:

8 4 251

output:

result:

ok single line: '93'

Test #15:

score: 0

Accepted

time: 0ms

memory: 3632kb

input:

8 7 41

output:

result:

ok single line: '10'

Test #16:

score: 0

Accepted

time: 2ms

memory: 3848kb

input:

60 17 360

output:

result:

ok single line: '27'

Test #17:

score: 0

Accepted

time: 2ms

memory: 3788kb

input:

16 55 388

output:

result:

ok single line: '31'

Test #18:

score: 0

Accepted

time: 2ms

memory: 3616kb

input:

25 38 292

output:

result:

ok single line: '18'

Test #19:

score: 0

Accepted

time: 1ms

memory: 3596kb

input:

22 59 177

output:

result:

ok single line: '11'

Test #20:

score: 0

Accepted

time: 2ms

memory: 3656kb

input:

4 3 82

output:

result:

ok single line: '50'

Test #21:

score: 0

Accepted

time: 2ms

memory: 3860kb

input:

77 18 511543

output:

result:

ok single line: '35070'

Test #22:

score: 0

Accepted

time: 2ms

memory: 3740kb

input:

37 32 987861

output:

result:

ok single line: '57612'

Test #23:

score: 0

Accepted

time: 2ms

memory: 3632kb

input:

29 8 300899

output:

result:

ok single line: '48059'

Test #24:

score: 0

Accepted

time: 2ms

memory: 3816kb

input:

73 83 533839

output:

result:

ok single line: '13745'

Test #25:

score: 0

Accepted

time: 2ms

memory: 3832kb

input:

12 23 181193

output:

result:

ok single line: '23008'

Test #26:

score: 0

Accepted

time: 1ms

memory: 3820kb

input:

2 2 864514

output:

result:

ok single line: '864514'

Test #27:

score: 0

Accepted

time: 0ms

memory: 3660kb

input:

27 7 165249

output:

result:

ok single line: '29765'

Test #28:

score: 0

Accepted

time: 1ms

memory: 3668kb

input:

15 2 751665

output:

result:

ok single line: '429522'

Test #29:

score: 0

Accepted

time: 2ms

memory: 3596kb

input:

2 16 818146

output:

result:

ok single line: '460207'

Test #30:

score: 0

Accepted

time: 1ms

memory: 3876kb

input:

43 88 631366

output:

result:

ok single line: '21860'

Test #31:

score: 0

Accepted

time: 2ms

memory: 3668kb

input:

215 1222 3597

output:

result:

ok single line: '18'

Test #32:

score: 0

Accepted

time: 2ms

memory: 8376kb

input:

9619 3375 604892

output:

result:

ok single line: '241'

Test #33:

score: 0

Accepted

time: 4ms

memory: 6088kb

input:

861 1924 311511

output:

result:

ok single line: '522'

Test #34:

score: 0

Accepted

time: 1ms

memory: 10400kb

input:

9249 3782 866972

output:

result:

ok single line: '322'

Test #35:

score: 0

Accepted

time: 3ms

memory: 5216kb

input:

7055 8386 206874

output:

result:

ok single line: '53'

Test #36:

score: 0

Accepted

time: 2ms

memory: 4676kb

input:

6273 7732 122377

output:

result:

ok single line: '34'

Test #37:

score: 0

Accepted

time: 1ms

memory: 4268kb

input:

8057 7746 89137

output:

result:

ok single line: '22'

Test #38:

score: 0

Accepted

time: 2ms

memory: 4156kb

input:

9215 8952 74618

output:

result:

ok single line: '16'

Test #39:

score: 0

Accepted

time: 3ms

memory: 4644kb

input:

7246 3709 129579

output:

result:

ok single line: '51'

Test #40:

score: 0

Accepted

time: 2ms

memory: 10136kb

input:

4052 6785 831888

output:

result:

ok single line: '327'

Test #41:

score: 0

Accepted

time: 2ms

memory: 3636kb

input:

9 2 91067

output:

result:

ok single line: '56916'

Test #42:

score: 0

Accepted

time: 2ms

memory: 3636kb

input:

10 3 913595

output:

result:

ok single line: '406041'

Test #43:

score: 0

Accepted

time: 2ms

memory: 3624kb

input:

2 2 152575

output:

result:

ok single line: '152575'

Test #44:

score: 0

Accepted

time: 2ms

memory: 3612kb

input:

2 2 927771

output:

result:

ok single line: '927771'

Test #45:

score: 0

Accepted

time: 2ms

memory: 3580kb

input:

6 7 637014

output:

result:

ok single line: '200204'

Test #46:

score: 0

Accepted

time: 2ms

memory: 3848kb

input:

5 3 721417

output:

result:

ok single line: '400786'

Test #47:

score: 0

Accepted

time: 2ms

memory: 3844kb

input:

5 9 183079

output:

result:

ok single line: '57538'

Test #48:

score: 0

Accepted

time: 2ms

memory: 3720kb

input:

9 2 579290

output:

result:

ok single line: '362055'

Test #49:

score: 0

Accepted

time: 2ms

memory: 3604kb

input:

3 4 546909

output:

result:

ok single line: '341817'

Test #50:

score: 0

Accepted

time: 2ms

memory: 3780kb

input:

2 2 932611

output:

result:

ok single line: '932611'