プログラミングは芸術だ!

web系エンジニアの備忘録 「プログラミングは芸術」を座右の銘として日々勉強中 最近Androidもやってます

AOJ1192 Tax Rate Changed【競技プログラミング】

AOJ1192 Tax Rate Changed

Tax Rate Changed | Aizu Online Judge

今年度(2014)のACM-ICPCの国内予選のA問題です
個人的にはA問題にしては少し意地悪かなと思います。

問題は消費税が変更になったので、2つの商品の考えられる消費税変更後の最大価格を求めるというもの

仮定
消費税率が x% のとき, 税抜価格が p 円である商品の税込価格は, p (100+x) / 100 円を小数点以下切り捨てたものである.
複数の商品についてまとめて支払う際の税込合計価格は,個々の商品の税込価格の合計額とする.

解法
入力で受け取るのは消費税率変更前の税込合計価格なので、
2分割全パターンにおいて、それぞれの税抜き価格を求めて、それぞれの消費税変更後の値を計算して、足し合わせ、それの最大値が答え

import java.util.Scanner;

public class AOJ1192 {
    final double eps = 0.000000001;
    void run() {
        Scanner sc = new Scanner(System.in);
        int x,y,s,max;
        while(true){
            x = sc.nextInt();
            y = sc.nextInt();
            s = sc.nextInt();
            max = 0;
            if(x+y+s == 0) break;
            for(int i = 1; i <= s/2; i++){
                int s1 = i;
                int s2 = s-i;
                int ps1 = getNoTaxPrice(s1, x);
                int ps2 = getNoTaxPrice(s2, x);
                int ys1 = (int) Math.floor(ps1 * ((100.0+y)/100.0) + eps);
                int ys2 = (int) Math.floor(ps2 * ((100.0+y)/100.0) + eps);
                max = Math.max(max, ys1+ys2);
            }
            System.out.println(max);
        }
    }
    /*
     * 税抜き価格を返します
     *
     * 税抜き価格は必ず税込価格以下なので
     * sから1つずつ試して、再度税込価格を計算し、元の税込価格を等しかったら返す
     */
    int getNoTaxPrice(int s,int x){
        for(int i = s; 0 < i; i--){
            int temp = (int) Math.floor(i * ((100.0+x)/100.0) + + eps);
            if(temp == s){
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        new AOJ1192().run();
        // new Main().run();
    }
}

感想
アルゴリズムは単純ですごく簡単なのだがdouble計算の誤差をどうするのかという問題

税抜き価格を求めるのが厄介で、かっこ良く1つの計算式で求めようと思ったが、
うまくいかなったので、税抜き価格も全パターン探索という形にした
O(s^2)になりそうだが、sの上限は1000と小さいなので問題なし

入力の上限が小さいときなどで全探索で実装できることは結構大事だと思っています。
自分もよくいい方法があるはずと思考が固まってしまうので気をつけたいところ。