みんなのプロコン2019 C - When I hit my pocket... (400)

C - When I hit my pocket...

概要

ビスケット1枚、お金0円でスタートし、以下の操作を好きな順にK回繰り返す。

• ビスケット1枚増やす
• ビスケットA枚減らし、お金1円増やす
• お金1円減らし、ビスケットB枚増やす

K回の操作後のビスケットの枚数の最大値を答えよ。

制約

1 <= K, A, B <= 10^9

方針

BがA未満、またはKがA以下なら、ビスケットを増やした方がよい。

それ以外については、下記の手順が最適。
(操作回数, ビスケット, お金, 操作回数) = (0, 1, 0)からスタート
(0, 1, 0) → (1, 2, 0) → ... → (A-1, A, 0) 　（ビスケットを叩く）

→ (A, 0, 1) → (A+1, B, 0) 　（ビスケット→お金、その後すぐお金→ビスケット）

→ (A+2, B - A, 1) → (A+3, 2*B - A, 0) 　（それの繰り返し）

→ (A+4, 2*B - 2*A, 1) →(A+5, 3*B - 2*A , 0) 　（それの繰り返し）

→ ...　

ただしK-Aが偶数の時、最後の操作はビスケットを換金するのでなく、ビスケットを叩いた方がよい。
例えば(A+1, B, 0) → (A+2, B - A, 1) でなく、 (A+1, B, 0) → (A+2, B+1, 0) が最適。

一応、max(, k+1)をかませる。

解答

Submission #4212848 - Yahoo Programming Contest 2019

#include <bits/stdc++.h>
 
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define rep(i,n) FOR(i,0,n)
#define RFOR(i,a,b) for(int i=(a)-1;i>=(b);i--)
#define rrep(i,n) RFOR(i,n,0)
 
using namespace std;
 
typedef long long ll;
typedef unsigned long long ull;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	ll k, a, b;
	cin >> k >> a >> b;
	if(b < a || k <= a){
		cout << (k+1) << endl;
		return 0;
	}
 
	ll d = k - a;
	ll ans;
	if(d % 2 == 0){
		ans = d / 2 * b - (d / 2 - 1) * a + 1;
	}else{
		ans = (d / 2 + 1) * b - d/2 * a;
	}
 
	ans = max(ans, k+1);
	cout << ans << endl;
}