今日勉強したことを
つらつらと
logo

abc158_cの解き方の解説 総当りでAC

2020/05/29 13:05
AtCoder Beginner Contest 158のC問題 Tax Increaseを解く。

感謝の正拳突き1万回ならぬ、競プロサイトで 1 日 1AC(正解)するように頑張る。

今日は簡単めなABC158 の C 問題 Tax Increaseを解いていきます。

制約に注目すると、全探索可能だとわかる

制約を見ると、1 <= a <= b <= 100 となっています。条件を満たす税抜価格の最大価格は 13 以上 1000 以下となります。すべてチェックしても全然間に合います。

比較する

_i _ 0.08 の小数点切り捨て == a* && i * 0.1 の小数点切り捨て == bとなるか全探索すれば OK です。

一致する数字がない場合も忘れない

一致する数字があったら、main 関数を抜けるようにしておきます。こうしておくと、ループを抜けた = 一致するものがないと判定できるので、最後に-1 を出力する処理を書いておきます。

できあがり

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a,b  ;
    cin >> a >> b;
    for(int i = 0; i <= 1000; i++) {
        if((int)(i * .08) == a && (int)(i * .1) == b) {
            cout << i;
            return 0;
        }
    }
    cout << -1;
}

もう少し考える

今回は制約がゆるいので、ありえる範囲を全探索しました。しかしもっと広い範囲だと、探索しきれない可能性があります。

i の下限値は a / 0.08、上限は(b + 1) / 0.1 となります。ループの範囲を適正にしてあげれば、100 倍高速になります。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int a,b  ;
    cin >> a >> b;
    for(int i = a / .08; i <= (b + 1) / .1; i++) {
        if((int)(i * .08) == a && (int)(i * .1) == b) {
            cout << i;
            return 0;
        }
    }
    cout << -1;
}

© 2021 simodake