Codeforces #199, A : Xenia and Divisors

問題文

http://codeforces.com/contest/342/problem/A

概要

要素数が 3n で、7 以下の正整数からなる列が与えられる。
この列から、以下の条件を満たす組 ( a, b, c ) を重複無く n 個取り出したい。

• 
• b は a の倍数
• c は b の倍数

条件を満たす取り出し方を一つ示せ。
取り出すことができないとき、-1 で示せ。

解法

7 以下という制約から、( a, b, c ) の取り出し方は次の三つしか無いことが分かります。

• 1, 2, 4
• 1, 2, 6
• 1, 3, 6

3 と 4 を取り出せるのはそれぞれ一つずつしか無いので、そのような取り出し方を先に試します。
このとき、どちらも取れるだけ取ります。
最後に、( 1, 2, 6 ) の取り出し方で取れるだけ取ります。
三通りの取り出し方を試した後、数が残っていたら解無しです。

typedef vector<int> VI;
typedef vector<VI> VVI;

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )
#define ALL( c ) (c).begin(), (c).end()

int main()
{
	cin.tie( 0 );
	ios::sync_with_stdio( false );

	int n;
	cin >> n;

	VI counts( 8 );
	REP( i, 0, n )
	{
		int a;
		cin >> a;
		counts[a] ++;
	}

	VVI targets = {
		{ 1, 2, 4 },
		{ 1, 3, 6 },
		{ 1, 2, 6 }
	};

	VI res( 3 );
	REP( i, 0, 3 )
	{
		int num = INT_MAX;
		REP( j, 0, 3 )
		{
			num = min( num, counts[ targets[i][j] ] );
		}
		res[i] = num;
		REP( j, 0, 3 )
		{
			counts[ targets[i][j] ] -= num;
		}
	}

	if ( any_of( ALL( counts ), bind1st( not_equal_to<int>(), 0 ) ) )
	{
		cout << -1 << endl;
		return 0;
	}

	REP( i, 0, 3 )
	{
		REP( j, 0, res[i] )
		{
			REP( k, 0, 3 )
			{
				cout << targets[i][k] << ( k < 2 ? ' ' : '\n' );
			}
		}
	}
	cout << flush;

	return 0;
}