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