Chokudai SpeedRun 002 I - カツサンドくん β (400 点)

面白かった

問題へのリンク

問題概要

個ある食べ物から最強の食べ物を決めたい。各食べ物は

• AP (攻撃力)：
• HP (体力)：

からなる。食べ物 は

• 

を満たすとき、 は より強いという。これらの値が等しい場合は引き分けである。

種類の食べ物のうち最強のもの (他の 種類すべてを相手に強い) が存在するならそれを答えよ。存在しなければ -1 を出力せよ。

制約

• 

考えたこと

まずはトーナメントを適当に作ってやらせる。 回の試合を行う。

これで優勝者を決めて、それが本当に最強かどうかを調べれば OK。

#include <iostream>
#include <vector>
using namespace std;
using pint = pair<int,int>;

bool iswin(long long a, long long b, long long aa, long long ab) {
    if ( (a + ab - 1) / ab > (aa + b - 1) / b) return true;
    else return false;
}

int main() {
    int N;
    cin >> N;
    int mai = -1;
    long long maa = -1, mab = -1;
    vector<long long> a(N), b(N);
    for (int i = 0; i < N; ++i) {
        cin >> a[i] >> b[i];
        if (mai == -1) {
            mai = i;
            maa = a[i];
            mab = b[i];
        }
        else {
            if (iswin(a[i], b[i], maa, mab)) {
                mai = i;
                maa = a[i];
                mab = b[i];
            }
        }
    }
 
    bool allwin = true;
    for (int i = 0; i < N; ++i) {
        if (mai == i) continue;
        if (!iswin(maa, mab, a[i], b[i])) allwin = false;
    }
    if (allwin) cout << mai + 1 << endl;
    else cout << -1 << endl;
}