QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#373818 | #2042. The Balance | KKT89 | 100 ✓ | 0ms | 3760kb | C++17 | 1.2kb | 2024-04-02 07:49:36 | 2024-04-02 07:49:38 |
Judging History
answer
#include <stdio.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <cstdio>
#include <ctime>
#include <assert.h>
#include <chrono>
#include <random>
#include <numeric>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
using namespace std;
typedef long long int ll;
typedef unsigned long long ull;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll myRand(ll B) {
return (ull)rng() % B;
}
int main(){
cin.tie(nullptr);
ios::sync_with_stdio(false);
ll a,b,d;
while(cin >> a >> b >> d,a){
int g=__gcd(__gcd(a,b),d);
a/=g; b/=g; d/=g;
pair<ll,ll> res;
res=make_pair(1e9,1e9);
ll sum=res.first+res.second;
ll ans=res.first*a+res.second*b;
for(ll x=0;x<=50000;x++){
if(sum<=x)break;
if((a*x-d)%b==0){
ll y=abs((a*x-d)/b);
if((sum>x+y)||(sum==x+y&&ans>x*a+b*y)){
sum=x+y;
res=make_pair(x,y);
ans=res.first*a+res.second*b;
}
}
if((a*x+d)%b==0){
ll y=abs((a*x+d)/b);
if((sum>x+y)||(sum==x+y&&ans>x*a+b*y)){
sum=x+y;
res=make_pair(x,y);
ans=res.first*a+res.second*b;
}
}
}
printf("%lld %lld\n",res.first,res.second);
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3760kb
input:
1 2 50000 9999 10000 1 58 14 5762 1620 5418 3240 3027 9259 26491 3349 4530 6564 3759 479 1355 6259 6201 15544 1141 4904 45837 1137 7358 3311 6656 907 26450 7114 3129 558 1 4733 35498 3491 151 2265 1147 3389 27770 360 5506 47160 3020 4061 7176 7268 510 23100 5416 922 1156 382 4803 2284 1637 1600 1352...
output:
0 25000 1 1 95 18 2 0 2059 676 1686 1245 12 97 268 268 871 212 1149 178 422 3126 1191 2708 2367 7 0 15 429 137 131 0 707 524 45 596 149 874 2068 164 629 652 25 860 540 248 420 1782 325 34 10 0 291 1395 99 98 272 680 2229 354 167 1633 785 59 211 27 625 170 1585 999 1305 1555 638 15 461 827 2288 780 4...
result:
ok 100 lines