QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#39735#2944. Transporting SpaghettiLangdao_ZhangWA 3ms3644kbC++969b2022-07-13 09:39:372022-07-13 09:39:40

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-13 09:39:40]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3644kb
  • [2022-07-13 09:39:37]
  • 提交

answer

#include<iostream>
#include<algorithm>

#define lint int64_t

#define gcd __gcd

using
		namespace
					std;

lint a,b,c,d;

pair<lint,lint> p;

pair<lint,lint> exgcd(lint a,lint b,lint c){
	
	if(b==0) return pair<lint,lint>(c/a,0);
	p=exgcd(b,a%b,c);
	return {p.second,p.first-a/b*p.second};
}

signed main(){
	
	cin>>a>>b>>c>>d;
	
	if(d%gcd(a,b)){
		
		printf("No solution.\n");
		return EOF+1;
	}
	
	pair<lint,lint> kotae=exgcd(a,-b,d);
	
	lint k=kotae.first/b;
	kotae.first-=k*b;
	kotae.second+=k*a;
	
	kotae.first+=200*b;
	kotae.second+=200*a;
	
	lint g=gcd(a,b);
	
	lint da=a/g,db=b/g;
	
	while((kotae.second-da)*b>=c){
		
		kotae.first-=db;
		kotae.second-=da;
	}
	
	printf("We need %lld truck",kotae.first);
	if(kotae.first!=1) putchar('s');
	printf(" and %lld boat",kotae.second);
	if(kotae.second!=1) putchar('s');
	printf(".\n");
	
end:
	return EOF+1;
}
/*
31 13 50 28
100 20 30 10
1 1 1 100
*/

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 3ms
memory: 3644kb

input:

31 13 50 28

output:

We need 263 trucks and 5 boats.

result:

wrong answer 1st lines differ - expected: 'We need 3 trucks and 5 boats.', found: 'We need 263 trucks and 5 boats.'