ferinの競プロ帳

競プロについてのメモ

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;
}