Codeforces #200, Division 2, B : Simple Molecules

問題文

http://codeforces.com/contest/344/problem/B

概要

三頂点からなるグラフがある。
このグラフは多重辺を許可し、ループを許可しない。
グラフの各頂点について、次数が指定される。
その制約を満たすグラフを構築できるならば、そのときの辺の張り方を答えよ。
そうでないとき、"Impossible" と出力せよ。

解法

三頂点を A, B, C と表すとします。
A-B 間の辺の本数を決めたとき、B の次数の制約から B-C 間の辺の本数が決まります。
C-A 間についても同様です。
従って、ある一箇所の辺の本数を決めるとそれ以外の場所の辺の本数が決まることが分かります。
その一箇所の辺の本数を全部試して、valid な張り方があればそれが答えです。
張り方が valid であるとは、次の条件を満たすときです。

• 各頂点間の辺の本数が非負
• 辺の本数の総和の二倍と a + b + c が等しい

コード

#define REP( i, m, n ) for ( int i = (int)( m ); i < (int)( n ); ++i )

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

	int a, b, c;
	cin >> a >> b >> c;

	REP( r1, 0, a + 1 )
	{
		int r2 = b - r1;
		int r3 = c - r2;

		if ( 0 <= min( r1, min( r2, r3 ) ) && ( r1 + r2 + r3 ) * 2 ==  a + b + c )
		{
			cout << r1 << ' ' << r2 << ' ' << r3 << endl;
			return 0;
		}
	}

	cout << "Impossible" << endl;

	return 0;
}