QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #39736 | #2944. Transporting Spaghetti | Langdao_Zhang | AC ✓ | 2ms | 3780kb | C++ | 1.1kb | 2022-07-13 09:46:14 | 2022-07-13 09:46:16 |
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){
//cout<<a<<' '<<b<<' '<<c<<endl;
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(){
scanf("%lld %lld %lld %lld",&a,&b,&c,&d);
if(d%gcd(a,b)){
printf("No solution.\n");
return EOF+1;
}
pair<lint,lint> kotae=exgcd(a,-b,d);
//cout<<kotae.first<<' '<<kotae.second<<endl;
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: 100
Accepted
time: 0ms
memory: 3776kb
input:
31 13 50 28
output:
We need 3 trucks and 5 boats.
result:
ok single line: 'We need 3 trucks and 5 boats.'
Test #2:
score: 0
Accepted
time: 1ms
memory: 3700kb
input:
100 20 30 10
output:
No solution.
result:
ok single line: 'No solution.'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3780kb
input:
1 1 1 100
output:
We need 101 trucks and 1 boat.
result:
ok single line: 'We need 101 trucks and 1 boat.'
Test #4:
score: 0
Accepted
time: 0ms
memory: 3744kb
input:
20 5 5 15
output:
We need 1 truck and 1 boat.
result:
ok single line: 'We need 1 truck and 1 boat.'
Test #5:
score: 0
Accepted
time: 2ms
memory: 3660kb
input:
100 20 100 100
output:
We need 2 trucks and 5 boats.
result:
ok single line: 'We need 2 trucks and 5 boats.'
Test #6:
score: 0
Accepted
time: 2ms
memory: 3764kb
input:
1 1 0 0
output:
We need 0 trucks and 0 boats.
result:
ok single line: 'We need 0 trucks and 0 boats.'
Test #7:
score: 0
Accepted
time: 2ms
memory: 3740kb
input:
1 5 10 50
output:
We need 60 trucks and 2 boats.
result:
ok single line: 'We need 60 trucks and 2 boats.'
Test #8:
score: 0
Accepted
time: 2ms
memory: 3720kb
input:
100 1 100 100
output:
We need 2 trucks and 100 boats.
result:
ok single line: 'We need 2 trucks and 100 boats.'
Test #9:
score: 0
Accepted
time: 1ms
memory: 3744kb
input:
1 1 100 100
output:
We need 200 trucks and 100 boats.
result:
ok single line: 'We need 200 trucks and 100 boats.'
Test #10:
score: 0
Accepted
time: 2ms
memory: 3772kb
input:
1 1 97 100
output:
We need 197 trucks and 97 boats.
result:
ok single line: 'We need 197 trucks and 97 boats.'