2017/07/19 ~ 2017/07/20

税率変更

以下のように1つのループで税込み価格を探索しようとしたが失敗した

for (int p1=1; p1<s; p1++) {
  int p2 = s-p1;
}

税抜き価格で全探索する

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int main() {
  int x, y, s;
  while (cin >> x >> y >> s, x && y && s) {
    int ans = 0;

    for (int o1=1; o1<s; o1++) {
      for (int o2=1; o2<s; o2++) {

        int p1 = o1 * (100+x) / 100.0;
        int p2 = o2 * (100+x) / 100.0;

        if (p1+p2 != s) continue;

        int n1 = o1 * (100+y) / 100;
        int n2 = o2 * (100+y) / 100;

        ans = max(ans, n1+n2);

      }
    }

    cout << ans << endl;
  }
  return 0;
}

Amida, the City of Miracle

Amida, the City of Miracle | Aizu Online Judge

あみだくじの枝を高さでソートする
始点を選び，辿っていく
[解説](http://www.deqnotes.net/acmicpc/p0102/)をみてmultisetを使った

イテレータにはドット演算子ではアクセスできない
アロー演算子を使う必要がある
C++よくわかっていないので原因はあとで調べる

pair v = it.second; // ダメ
pair v = it->second;
pair v = (*it).second;

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

typedef multimap< int, pair<int, int> > HL;

int main() {
  int n, m, ans;
  int h, p, q;

  while (cin >> n >> m >> ans, n && m && ans) {
    set<int> hs;
    multimap<int, pair<int, int>> hl;

    rep (i, m) {
      cin >> h >> p >> q;
      hs.insert(h);
      hl.insert(make_pair(h, make_pair(p, q)));
    }

    for (set<int>::reverse_iterator sit=hs.rbegin(); sit!=hs.rend(); sit++) {
      int hhead = *sit;

      for (multimap<int, pair<int, int>>::iterator it = hl.lower_bound(hhead); it != hl.upper_bound(hhead); it++) {
        pair<int, int> v = it->second;
        if (v.first == ans) {
          ans = v.second;
          break;
        }
        else if (v.second == ans ) {
          ans = v.first;
          break;
        }
      }
    }

    cout << ans << endl;
  }
  return 0;
}

幸運の操作者

Luck Manipulator | Aizu Online Judge

10000+1 (0回目+10000回の試行) の乱数生成結果を先に作る
あとは作った乱数とYを照合する
計算はもっとサボれる (毎回10000回乱数生成をする必要はない) が，
一番楽な実装でも十分間に合いそうだったのでこのまま

//#define _GRIBCXX_DEBUG
#include <bits/stdc++.h>
# define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;

int solve(int n, int a, int b, int c, int x, vector<int> &y, vector<int> &z) {
  int head = 0;
  rep (t, 10000+1) {
    if (y[head] == z[t]) head++;
    if (head == n) return t;
  }
  return -1;
}

int main() {
  int n, a, b, c, x;
  vector<int> y;
  vector<int> z(10000);

  while(cin >> n >> a >> b >> c >> x, n) {
    y.resize(n); z[0] = x;
    rep (i, n) cin >> y[i];

    for (int i=1; i<=10000; i++) z[i] = (a*z[i-1] + b) % c;
    cout << solve(n, a, b, c, x, y, z) << endl;
  }
  return 0;
}