[UVa] 10161 - Ant on a Chessboard

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

題意:
(from luckycat)


解法: 稍微看一下就能夠看出規律，若要求第 n 秒的位置，先找出一個最小的平方數 s = k^2 ，滿足 s >= n，先討論 n 是偶數，會發現若 s-n+1 <= k，則 x = k, y = s-n+1，否則 x = n-(k-1)*(k-1), y = k，若 n 是奇數，可以先用偶數的方法求出座標，再把座標反過來即可。

TAG: ad hoc

注意:

程式碼:

	/**
	* Tittle: 10161 - Ant on a Chessboard
	* Author: Cheng-Shih, Wong
	* Date: 2015/04/15
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <cmath>
	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) )
	typedef long long ll;
	// declarations
	ll n, g;
	// functions
	// main function
	int main( void )
	{
	ll x, y;
	// input
	while( scanf( "%lld", &n )==1 && n ) {
	// solve
	g = sqrt( n );
	if( g*g < n ) ++g;
	if( g*g-n+1 <= g ) x = g, y = g*g-n+1;
	else x = n-(g-1)*(g-1), y = g;
	if( g&1LL ) swap( x, y );
	// output
	printf( "%lld %lld\n", x, y );
	}
	return 0;
	}

view raw 10161 - Ant on a Chessboard.cpp hosted with ❤ by GitHub