POJ-1017, LiveArchive-5526, UVa-311, TJU-1022, ZOJ-1307 : Packets

問題概要

1*1, 2*2, ..., 6*6の板を6*6マスの盤に埋め込む。盤は最小いくつ必要か求める問題。

解法

だいたい直感通りに貪欲に詰めていく。こういうのは場合分けを減らしたいんだけど難しい。

acceptされたコード

#include <cstdio>
using namespace std;

int as[7];

bool init(){
	for(int i=0; i<6; ++i){
		scanf("%d", as+1+i);
	}
	for(int i=1; i<=6; ++i){
		if(as[i]){
			return true;
		}
	}
	return false;
}

int solve(){
	//6を詰める
	int ans = as[6];

	//5を詰める
	{
		ans += as[5];
		as[1] -= as[5] * 11;
	}

	//4を詰める
	{
		ans += as[4];
		int two = as[4] * 5;
		if(two <= as[2]){
			as[2] -= two;
		}
		else{
			two -= as[2];
			as[2] = 0;
			as[1] -= two * 4;
		}
	}

	//3を詰める
	{
		ans += (as[3] + 3) / 4;
		int two = 0, one = 0;
		if(as[3] % 4 == 1){
			two = 5;
			one = 7;
		}
		else if(as[3] % 4 == 2){
			two = 3;
			one = 6;
		}
		else if(as[3] % 4 == 3){
			two = 1;
			one = 5;
		}

		if(two <= as[2]){
			as[2] -= two;
		}
		else {
			two -= as[2];
			as[2] = 0;
			one += two * 4;
		}
		as[1] -= one;
	}


	//2を詰める
	{
		ans += (as[2] + 8) / 9;
		int one = 0;
		if(as[2] % 9){
			one = ( 9 - as[2]%9 ) * 4;
		}
		as[1] -= one;
	}

	//1を詰める
	if(as[1] > 0){
		ans += (as[1] + 35) / 36;
	}

	return ans;
}

int main(){
	for(;init();){
		printf("%d\n", solve());
	}

	return 0;
}