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; }