AOJ1248 The Balance
問題ページ
The Balance | Aizu Online Judge
考えたこと
- aグラムがi個、bグラムがj個のとき ai + bj = d, ai + d = bj, ai = bj + d を満たせばdグラムを測れる
- iを決め打てばjは自動的に決まる
- iは何通りくらいあるのか?
- a=1,b=2,d=50000みたいなときに5*10^4個必要になってそれくらいが最悪パターンになりそう
- ちょっと怖かったのと実行時間にだいぶ余裕があるのでi=0~5*10^5まで試すことにして投げると通った
O(変数の取りうる値^数式の変数の数) から O(変数の取りうる値^(数式の変数の数-1)) に落とすいつもの
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll using VI = vector<int>; using VVI = vector<VI>; using PII = pair<int, int>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define PB push_back const ll LLINF = (1LL<<60); const int INF = (1LL<<30); const int MOD = 1000000007; template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } template <typename T> bool IN(T a, T b, T x) { return a<=x&&x<b; } template<typename T> T ceil(T a, T b) { return a/b + !!(a%b); } template<class S,class T> ostream &operator <<(ostream& out,const pair<S,T>& a){ out<<'('<<a.first<<','<<a.second<<')'; return out; } template<class T> ostream &operator <<(ostream& out,const vector<T>& a){ out<<'['; REP(i, a.size()) {out<<a[i];if(i!=a.size()-1)out<<',';} out<<']'; return out; } int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0}; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); while(true) { int a, b, d; cin >> a >> b >> d; if(!a) break; int ansi = LLINF, ansj = LLINF; REP(i, 500000) { // a*i + d = b*j if((a*i+d)%b == 0) { int j = (a*i+d)/b; if(i+j < ansi + ansj || (i+j == ansi+ansj && i*a+j*b < ansi*a+ansj*b)) { ansi = i, ansj = j; } } // a*i + b*j = d if(d>=a*i && (d-a*i)%b == 0) { int j = (d-a*i)/b; if(i+j < ansi + ansj || (i+j == ansi+ansj && i*a+j*b < ansi*a+ansj*b)) { ansi = i, ansj = j; } } // a*i = b*j + d if(a*i>=d && (a*i-d)%b == 0) { int j = (a*i-d)/b; if(i+j < ansi + ansj || (i+j == ansi+ansj && i*a+j*b < ansi*a+ansj*b)) { ansi = i, ansj = j; } } } assert(ansi!=LLINF); cout << ansi << " " << ansj << endl; } return 0; }