読者です 読者をやめる 読者になる 読者になる

yukicoder No. 176: 2種類の切手

yukicoder 競技プログラミング

解法

Bの枚数を0から総当りする。Bの枚数をiとした時、切手の合計額がTをギリギリ超えるようなAの枚数jは、以下のように書ける。

j = (T - B * i + A - 1) / A

B*iがTを超えていたりB*Aを超えていたりしたらbreakする。

コード

import java.io.IOException;

public class Main {

    public static void main(String[] args) {
        int A = nextInt();
        int B = nextInt();
        int T = nextInt();
        long min = Long.MAX_VALUE;

        for (int i = 0;; i++) {
            int j = (T - B * i + A - 1) / A;
            long next = B * i + A * j;

            min = Math.min(min, next);
            if (B * i > T || i > A) {
                break;
            }
        }

        System.out.println(min);

    }

    static int nextInt() {
        int c;
        try {
            c = System.in.read();
            while (c != '-' && (c < '0' || c > '9'))
                c = System.in.read();
            if (c == '-')
                return -nextInt();
            int res = 0;
            while (c >= '0' && c <= '9') {
                res = res * 10 + c - '0';
                c = System.in.read();
            }
            return res;
        } catch (IOException e) {
            // TODO Auto-generated catch block
            e.printStackTrace();
        }
        return -1;
    }
}