結果

問題 No.176 2種類の切手
コンテスト
ユーザー codershifth
提出日時 2015-12-31 12:17:49
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2 ms / 1,000 ms
コード長 2,175 bytes
コンパイル時間 1,244 ms
コンパイル使用メモリ 159,880 KB
実行使用メモリ 6,820 KB
最終ジャッジ日時 2024-10-08 03:40:49
合計ジャッジ時間 2,105 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 29
権限があれば一括ダウンロードができます

ソースコード

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