mayoko’s diary

プロコンとかいろいろ。

GCJ Round 1C Problem C. Fashion Police

問題

Dashboard - Round 1C 2016 - Google Code Jam

A 枚のジャケット, B 枚のパンツ, C 枚のシャツがある。これらを適当に組み合わせて, (a, b, c) というようなペアにして服を着る。
ところでこの世界にはファッション警察がいて, (a, b, c) というペアの服装で 2 日以上出かけると逮捕される。また, (a, b) の組, (b, c) の組, (c, a) の組を K+1 日以上かぶらせても逮捕される。この世界で逮捕されないように外出できる最大日数を求め, その際の服の着方を示せ。

解法

A*B*C の直方体を考えます。問題で課せられている条件は,

  • (a, b, c) をかぶらせてはいけない
    • 直方体のセル (a, b, c) は 1 回しか選べない
  • (a, b) のようなペアを K+1 回以上選んではいけない
    • x = a, y = b となるような直線上では K 個以下のセルしか選べない

です。2 つ目の条件から, 解の上界は A*B*K であるとわかります。で, 実際に A*B*K の解が存在します。それはどうするかというと, 各セル(a, b) に対して K 個のセルを選ばないといけないですが, これを (a+b+k)%C で選びます(k は 0 以上 K 未満の整数)。

二次元で考えると, (a+k)%C は各高さ c で K 個以下のセルしか選ばれません。これを二次元にするなら両方向に足せば良いので (a+b+k)%C という式が出てきます。

struct ABC {
	int a, b, c;
	ABC();
	ABC(int a, int b, int c) : a(a), b(b), c(c) {}
};

void solve() {
	int A, B, C, K;
	cin >> A >> B >> C >> K;
	K = min(C, K);
	vector<ABC> ans;
	for (int a = 0; a < A; a++) for (int b = 0; b < B; b++) {
		for (int k = 0; k < K; k++) {
			ans.emplace_back(a, b, (a+b+k)%C);
		}
	}
	cout << ans.size() << endl;
	for (ABC el : ans) 
		cout << el.a+1 << " " << el.b+1 << " " << el.c+1 << endl;
}

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int T;
	cin >> T;
	for (int t = 1; t <= T; t++) {
		cout << "Case #" << t << ": " ;
		solve();
	}
	return 0;
}