SPOJ-EBOXES: Empty Boxes

問題概要

最初にN個の箱がある。そのうち任意個数の空箱を選んで、箱の中にK個の新しい箱を詰める。このような作業をT回繰り返した結果、空の箱がF個ある。全ての箱の個数を求める問題。数字はいずれも10^6以下。

解法

式一発で求められる。非空の箱の個数さえ求めれば良い。箱をK個詰めるとき、空の箱の個数はK-1個増え、非空な箱は1個増える。したがって、非空な箱をxとすると、x*(K-1) + N = F。よって、非空な箱の個数は(F-N)/(K-1)となる。

acceptされたコード

計算量O(1)。

#include <cstdio>
using namespace std;

int solve(int N, int K,int T, int F){
	return (F - N)/(K-1) + F;
}

int main(){
	int C;
	scanf("%d",&C);
	while(C--){
		int N, K, T, F;
		scanf("%d%d%d%d",&N,&K,&T,&F);
		printf("%d\n", solve(N,K,T,F));
	}

	return 0;
}