kmjp's blog

競技プログラミング参加記です

Codeforces #194 Div1. A. Secrets

CF194は参加したけど、Aの題意がいまいちつかめなくて最後までうまく答えが合わず惨敗した回…。
http://codeforces.com/contest/333/problem/A

問題

この国のコインは1マルク、3マルク、9マルク、27マルク…と3の累乗マルクのコインがある。

ここでNマルクを払いたいとする。
Nマルクぴったりは払えないけど、Nマルクより多くは払えるようなコインの組み合わせにおいて、最小枚数でNマルクを超えて払えるようにしたい。
そのような組み合わせの最大枚数を答えよ。

解法

問題文を言い換えると、3の倍数の数値だけをP個集めた和S>Nで、かつP個のうちの最小値QにおいてS-QNかつS-Q

void solve() {
	int f,i,j,k,l, x,y;
	ll r=0,mi=0,N;
	
	cin>>N;
	while(N%3==0) N/=3;
	cout << N/3+1 << endl;
	return;
}

まとめ

うーん、題意がつかめないのが痛かった。