Codeforces Round 342 Div. 2 A Guest From the Past
問題
Problem - A - Codeforces問題概要
ケフィアを大量に摂取したい。Aルーブルで1リットルかBルーブルで1リットルを摂取することができる。Bルーブル払った場合は瓶を返すことでCルーブル返してもらえます。Nルーブル持っている時に摂取できるケフィアの量の最大値を求めよ。
解法
まず、BがA以下の場合を考える。Bを支払った場合は後で C返してもらえるので、Aルーブル払うメリットがない。従って、Bルーブル支払った後にCルーブルをもらう、といったことを持ち金がB以下になるまで繰り返せばよいことがわかる。次に、AがB以下の場合を考える。この時はさらに2つの場合分けが出来、AがB-C以下の時とそうでない時に分けられる。
前者の場合、Bルーブル支払うメリットがないので先ほどと同様Aルーブルだけでどれだけ摂取できるかを計算すれば良い。
後者の場合、AがB-Cより大きい時、まずBルーブルで支払えるだけ支払った後に、Aルーブルを支払うといった操作を行えば摂取量を最大にすることができる。
コード
#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> #include <fstream> #include <queue> #include <complex> #define INF 100000000 #define YJ 1145141919 #define INF_INT_MAX 2147483647 #define INF_LL_MAX 9223372036854775807 #define EPS 1e-10 #define Pi acos(-1) #define LL long long #define ULL unsigned long long #define LD long double using namespace std; LL N; LL A, B, C; int main(){ cin >> N; cin >> A >> B >> C; LL ret = 0; if(N < min(A,B)){ cout << 0 << endl; return 0; } if(A >= B){ ret = (N-B)/(B-C); N -= ret*(B-C); while(N >= B){ ret++; N = N - B + C; } cout << ret << endl; return 0; } else{ if(A > (B-C)){ if(N >= B){ ret = (N-B)/(B-C); N -= ret*(B-C); if(N >= B){ ret++; N = N - B + C; } } ret += N/A; cout << ret << endl; return 0; } else{ cout << N/A << endl; } } return 0; }