[UVa] 10164 - Number Game

題目網址: http://goo.gl/oKHyV8

題意:
(from luckycat)


解法: 有點不知道怎麼幫這題分類，其實這題有一點鴿籠原理的感覺，但是卻說不出來XD，一開始我們拿到 2N-1 個數字時，把所有的數字分成偶數一堆、奇數一堆，接著盡量把兩堆各自兩兩抓成偶數對、奇數對，把每對相加我們就能獲得 N-1 個偶數，剩下的一個數字就不理它，再把這 N-1 個偶數除以 2，我們就得到新的 N-1 個數，再重複上面的方法，一直做下去直到最後只剩下一個數，則結束，且這個數不知不覺中已經被除以 2^k 了，所以這 2N-1 個數字不論怎麼給，都有解，如果看的懂我說的方法的話，應該就能聞到鴿籠原理的味道(?)XD。

TAG: Math

注意:

程式碼:

	/**
	* Tittle: 10164 - Number Game
	* Author: Cheng-Shih, Wong
	* Date: 2015/04/16
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <vector>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define N 1100
	#define pb push_back
	class Node {
	public:
	int v;
	int l, r;
	Node( int _v=0, int _l=-1, int _r=-1 ):
	v(_v), l(_l), r(_r) {}
	};
	typedef vector<int> VI;
	typedef vector<Node> VN;
	// declarations
	int n;
	int val[2*N];
	VN tree;
	// functions
	bool space;
	void output( const Node &u )
	{
	if( u.l==-1 && u.r==-1 ) {
	if( space ) putchar(' ');
	else space = true;
	printf( "%d", u.v );
	} else {
	output( tree[u.l] );
	output( tree[u.r] );
	}
	}
	// main function
	int main( void )
	{
	int k, v;
	VI pre;
	VI odd, even;
	// input
	while( scanf( "%d", &n )==1 && n ) {
	FOR( i, 1, 2*n-1 ) scanf( "%d", &val[i] );
	// solve
	k = 1;
	while( (1<<k) != n ) ++k;
	tree.clear();
	pre.clear();
	FOR( i, 1, 2*n-1 ) {
	tree.pb( Node(val[i]) );
	pre.pb(tree.size()-1 );
	}
	FOR( round, 1, k ) {
	odd.clear();
	even.clear();
	for( VI::iterator it=pre.begin(); it!=pre.end(); ++it ) {
	v = *it;
	if( tree[v].v&1 ) odd.pb(v);
	else even.pb(v);
	}
	pre.clear();
	for( int i=0; i+1<odd.size(); i+=2 ) {
	const Node &a = tree[odd[i]];
	const Node &b = tree[odd[i+1]];
	tree.pb( Node((a.v+b.v)/2,odd[i],odd[i+1]) );
	pre.pb( tree.size()-1 );
	}
	for( int i=0; i+1<even.size(); i+=2 ) {
	const Node &a = tree[even[i]];
	const Node &b = tree[even[i+1]];
	tree.pb( Node((a.v+b.v)/2,even[i],even[i+1]) );
	pre.pb( tree.size()-1 );
	}
	}
	// output
	puts("Yes");
	space = false;
	output( tree.back() );
	putchar('\n');
	}
	return 0;
	}

view raw 10164 - Number Game.cpp hosted with ❤ by GitHub