[UVa] 10120 - Gift?!

題目網址: http://goo.gl/1ywg2I

題 意: 有 n 個石頭在小溪上，石頭編號依序由 1....n，而編號 1 的石頭左邊有岸，編號 n 的石頭右邊也有岸，石頭間皆相距一公尺，而左岸與 1號石頭、右岸與 n 號石頭也都相距一公尺，有隻青蛙從左岸起步，第 i 次跳躍只能往左或右跳 (i*2-1) 公尺，若青蛙能夠到達 m 號石頭，則輸出 Let me try! ，無法則輸出 Don't make fun of me!，若青蛙跳到左岸或右岸則停止。


解法: 如果 n >= 49，則一定有解，證明: http://www.algorithmist.com/index.php/UVa_10120，若 n < 49，直接 DFS 求解。

TAG: Math, DFS

注意:

程式碼:

	/**
	* Tittle: 10120 - Gift?!
	* Author: Cheng-Shih, Wong
	* Date: 2015/03/31
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	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) )
	// declarations
	int n, m;
	// functions
	const bool check( int now, int step )
	{
	if( now < 1 || now > n ) return false;
	if( now == m ) return true;
	return check( now+2*step-1, step+1 ) || check( now-2*step+1, step+1 );
	}
	// main function
	int main( void )
	{
	// input
	while( scanf( "%d%d", &n, &m )==2 && (n||m) ) {
	// solve & output
	if( n >= 49 || check(1,2) ) puts("Let me try!");
	else puts("Don't make fun of me!");
	}
	return 0;
	}

view raw 10120 - Gift?!.cpp hosted with ❤ by GitHub