結果

問題 No.176 2種類の切手
ユーザー codershifthcodershifth
提出日時 2015-12-31 12:17:49
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 2,175 bytes
コンパイル時間 1,311 ms
コンパイル使用メモリ 158,568 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-04-16 22:20:12
合計ジャッジ時間 2,258 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 1 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 2 ms
5,376 KB
testcase_09 AC 1 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 2 ms
5,376 KB
testcase_12 AC 2 ms
5,376 KB
testcase_13 AC 2 ms
5,376 KB
testcase_14 AC 1 ms
5,376 KB
testcase_15 AC 2 ms
5,376 KB
testcase_16 AC 2 ms
5,376 KB
testcase_17 AC 2 ms
5,376 KB
testcase_18 AC 2 ms
5,376 KB
testcase_19 AC 2 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 2 ms
5,376 KB
testcase_22 AC 1 ms
5,376 KB
testcase_23 AC 1 ms
5,376 KB
testcase_24 AC 2 ms
5,376 KB
testcase_25 AC 2 ms
5,376 KB
testcase_26 AC 2 ms
5,376 KB
testcase_27 AC 2 ms
5,376 KB
testcase_28 AC 1 ms
5,376 KB
testcase_29 AC 2 ms
5,376 KB
testcase_30 AC 1 ms
5,376 KB
testcase_31 AC 1 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;

template<typename T>
T gcd(T a, T b)
{
    if ( std::abs(a) < std::abs(b) )
        std::swap(a,b);
    if ( b == 0 )
        return a;
    return gcd(b, a%b);
}
class TwoKindsOfStamp
{
public:
    ll roundUp(ll a, ll b) {
        ll x = ceil((double)a/b);
        return (x>=0)? x : 0;
    }
    void solve(void)
    {
        ll A,B,T;
        cin>>A>>B>>T;

        // f(n,m) = n*A + m*B >= T
        // を満たす f(n,m) の最小値をもとめればよい
        //
        // A,B < 10^9 なので単純な全探索では間に合わない。
        //
        // m を固定してみる。このとき条件をみたすには n は
        // n >= (T - m*B)/A
        // n >= ceil((T-m*B)/A)
        // を満たす必要がある。
        //
        // よって m を固定したときのとりうる f(n,m) の最小値は
        // f(n,m) = ceil((T-m*B)/A)*A + m*B
        //
        // m > T/B を超えると T-m*B < 0 になってしまうので m <= T/B まで探索すればよい。
        // このままだと B が小さいときは T < 10^9 のままなので間に合わない
        //
        // そこで m > A のときを考えると
        // f(n,m) = n*A + (m'-A*k)*B  (m = m'-A*k, k >= 1)
        //        = (n-B*k)*A + m'*B (m' < A)
        // とかけるので m <= A と見なしてよい
        //
        // よって探索上限は min(T/B,A) となり
        // T/B == A つまり O(√T) < 10^4 にて計算できる。

        // A,B > T のケースもあるので +1 して計算する
        ll ret = max((T/A+1)*A, (T/B+1)*B);
        for (ll m = 0; m <= min(T/B+1,A); ++m)
        {
            ll x = roundUp(T-m*B,A)*A + m*B;
            ret = min(ret,x);
        }
        cout<<ret<<endl;
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new TwoKindsOfStamp();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0