[UVa] 10257 - Dick and Jane

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

題意:
(from luckycat)


解 法:
參考 http://nc-oj.logdown.com/posts/2011/10/15/acm-10257。
假設烏龜(C)的年紀為 x 歲，而再假設 C = x + dx, 0 <= dx < 1，C 是烏龜當前實際的"實數"年齡，x 為 C 的整數部分， dx 為 C 的小數部分。
以此類推，烏龜出生時，貓(B) p 歲，所以 B = x + dx + p +dp, 0 <= dp < 1。
烏龜出生時，狗(A) y 歲，所以 A = x + dx + y + dy, 0 <= dy < 1。
由以上兩行可知，貓當前的年齡為 B' = x + p + (dx+dp), 0 <= dx+dp < 2，所以貓的年齡為 B' = x + p + { 0, 1 }，也就是可能為 x + p 或 x + p + 1。
而狗當前的年齡為 A' = x + y + (dx+dy), 0 <= dx+dy < 2 ，所以狗的年齡為 A' = x + y + { 0, 1 }。

而題目說 Dick + Jane 的"年齡" 等於 狗 + 貓 + 烏龜 的"年齡"。
也就是 D + J = ( x+y+{0,1} ) + (x+p+{0,1}) + x
=> D + J - y - p = 3*x + { 0, 1, 2 }
當 (D+J-y-p)%3 = 0 代表剛好整除，也就是 狗與貓的年齡 依序為 x+y, x+p 都不用加 1；而當 (D+J-y-p)%3 = 2 代表需要補 2 才能整除，也就是 狗與貓的年齡都需加 1，也就是 x+y+1, x+p+1；最後需要討論的是當 (D+J-y-p)%3 = 1，這時會不知道  是狗的年齡需要加 1 還是貓的年齡需要加 1。

我們知道狗實際的年齡為 A = x + dx + y + dy = x + dx + p + dp + s + ds，
而推出 y + dy = s + ds + p + dp，所以取整數部分來看的話，
因為 0 <= dy < 1, 0 <= (ds+dp) < 2，則得出 y = s + p + { 0, 1 }

接著 假設 若是當狗的年紀需要加 1 ，也就是 當我們取 A = x + dx + y + dy 的整數部分時，
答案是 A' = x+y+1，因而 1 <= dx+dy < 2
而此時 貓的年紀試不能加 1 的，也就是 B' = x+p，因而 0 <= dx+dp < 1
以上我們能代到 A 中，A = x + dx + p + dp + s + ds = x + p + s + (dx+dp) + ds，
因為 0 <= (dx+dp) + ds < 2，所以 A' = x+p+s+{0,1} = x+y+1，
且因為 x+p+s = x+y+1 不可能成立(因為 y = s+p+{0,1})，所以 x+p+s+1 = x+y+1會成立，
所以此時 y = p+s，也就是當 y = p+s 的時候，狗的年紀需要加 1 ，而貓不用。
# 另一種情況 貓加 1、狗不用，也是類似上面的方法 類推
# 就可以討論出 當(D+J-y-p)%3 = 1 兩種情況的條件！

TAG: Math,

注意:

程式碼:

	/**
	* Tittle: 10257 - Dick and Jane
	* Author: Cheng-Shih, Wong
	* Date: 2015/05/29
	*/
	// 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 s, p, y, j;
	// functions
	// main function
	int main( void )
	{
	int x;
	// input
	while( scanf( "%d%d%d%d", &s, &p, &y, &j )==4 ) {
	// solve & output
	x = (12+j-y-p)/3;
	switch( (12+j-y-p)%3 ) {
	case 0:
	printf( "%d %d %d\n", x+y, x+p, x );
	break;
	case 1:
	if( y == p+s+1 )
	printf( "%d %d %d\n", x+y, x+p+1, x );
	else
	printf( "%d %d %d\n", x+y+1, x+p, x );
	break;
	case 2:
	printf( "%d %d %d\n", x+y+1, x+p+1, x );
	break;
	}
	}
	return 0;
	}

view raw 10257 - Dick and Jane.cpp hosted with ❤ by GitHub