首页 > ACM题库 > HDU-杭电 > HDU 4229-Vive la Difference! [解题报告]HOJ
2015
05-23

HDU 4229-Vive la Difference! [解题报告]HOJ

Vive la Difference!

问题描述 :

Take any four positive integers: a, b, c, d. Form four more, like this:
|a-b| |b-c| |c-d| |d-a|

That is, take the absolute value of the differences of a with b, b with c, c with d, and d with a. (Note that a zero could crop up, but they’ll all still be non-negative.) Then, do it again with these four new numbers. And then again. And again. Eventually, all four integers will be the same. For example, start with 1,3,5,9:
1 3 5 9
2 2 4 8 (1)
0 2 4 6 (2)
2 2 2 6 (3)
0 0 4 4 (4)
0 4 0 4 (5)
4 4 4 4 (6)
In this case, the sequence converged in 6 steps. It turns out that in all cases, the sequence converges very quickly. In fact, it can be shown that if all four integers are less than 2^n, then it will take no more than 3*n steps to converge!
Given a, b, c and d, figure out just how quickly the sequence converges.

输入:

There will be several test cases in the input. Each test case consists of four positive integers on a single line (1 ≤ a,b,c,d ≤ 2,000,000,000), with single spaces for separation. The input will end with a line with four 0s.

输出:

There will be several test cases in the input. Each test case consists of four positive integers on a single line (1 ≤ a,b,c,d ≤ 2,000,000,000), with single spaces for separation. The input will end with a line with four 0s.

样例输入:

1 3 5 9
4 3 2 1
1 1 1 1
0 0 0 0

样例输出:

6
4
0

/**
 * ID: ping128
 * LANG: C++
 */

#include <stdio.h>
#include <iostream>
#include <sstream>
#include <stdlib.h>
#include <string>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <list>
#include <math.h>
#include <algorithm>
#include <map>
#include <string.h>

using namespace std;

typedef long long LL;
typedef pair<int,int>PII;
typedef pair<PII,int>PII2;

LL absL(LL x)
{
	if(x < 0) return -x;
	return x;
}

int main(){
	
	LL in[4];
	LL a[4];
	while(1)
	{
		cin >> in[0] >> in[1] >> in[2] >> in[3];
		if(!in[0] && !in[1] && !in[2] && !in[3]) break;
		int num = 0;
		while(in[0] != in[1] || in[1] != in[2] || in[2] != in[3])
		{
			num++;
			for(int i = 0; i < 4; i++ )
			{
				a[i] = absL(in[i] - in[(i + 1)%4]);
			}
			for(int i = 0; i < 4; i++ )
				in[i] = a[i];
		}
		
		cout << num << endl;
	}	
	
return 0;
}