QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#39735 | #2944. Transporting Spaghetti | Langdao_Zhang | WA | 3ms | 3644kb | C++ | 969b | 2022-07-13 09:39:37 | 2022-07-13 09:39:40 |
Judging History
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.'