Ms. Iyo Kiffa-Australis has a balance and only two kinds of weights to measure a dose of medicine. For example, to measure 200mg of aspirin using 300mg weights and 700mg weights, she can put one 700mg weight on the side of the medicine and three 300mg weights on the opposite side (Figure 1).
重り を使う量を決めると重りを使う量が決まる．また重り を決めると重りを使う量が決まる．それぞれ使う量を全探索してどちらも使う量が非負整数の時に量の和，重さの和の最小を答える．上限を何も考えずに まで回したらオーバーフローで死んだ(完)． までで良かった．
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>
#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair
using namespace std ;
typedef long long ll ;
typedef pair < int , int > P ;
int main () {
int a , b , d ;
while ( cin >> a >> b >> d ) {
if ( a == 0 && b == 0 && d == 0 ) break ;
int g = __gcd ( a , b );
a /= g ;
b /= g ;
d /= g ;
int x = INF , y = INF , sum = INF , prod = INF ;
for ( int i = 0 ; i < 50000 ; i ++ ) {
int c = d - a * i ;
if ( abs ( c ) % b == 0 ) {
int j = abs ( c / b );
if ( i + j < sum ) {
sum = i + j ;
prod = a * i + b * j ;
x = i ;
y = j ;
} else if ( i + j == sum && a * i + b * j < prod ) {
sum = i + j ;
prod = a * i + b * j ;
x = i ;
y = j ;
}
}
}
for ( int j = 0 ; j < 50000 ; j ++ ) {
int c = d - b * j ;
if ( abs ( c ) % a == 0 ) {
int i = abs ( c / a );
if ( i + j < sum ) {
sum = i + j ;
prod = a * i + b * j ;
x = i ;
y = j ;
} else if ( i + j == sum && a * i + b * j < prod ) {
sum = i + j ;
prod = a * i + b * j ;
x = i ;
y = j ;
}
}
}
cout << x << " " << y << endl ;
}
return 0 ;
}