ZCMU 1153

1153: 有趣的排列問題

Description

有N對雙胞胎，他們的年齡分别是1，2，3，……，N歲，他們手拉手排成一隊到野外去玩，要經過一根獨木橋，為了安全起見，要求年齡大的和年齡小的排在一起，好讓年齡大的保護年齡小的，然後從頭到尾，每個人報告自己的年齡，就得到了一個年齡的序列。比如有4對雙胞胎，他們報出來的年齡序列是：41312432。突然，他們中間最聰明的小明發現了一個有趣的現象，原來，這個年齡序列有一個規律，兩個1中間有1個數，兩個2中間有2個數，兩個3中間有3個數，兩個4中間有4個數。但是，如果是2對雙胞胎，那麼無論他們怎麼排年齡序列，都不能滿足這個規律。

你的任務是，對于給定的N對雙胞胎，是否有一個年齡序列，滿足這一規律，如果是，就輸出Y，如果沒有，輸出N。

Input

共有若幹行，每行一個正整數N<100000，表示雙胞胎的數量；如果N=0，表示結束。

Output

共有若幹行，每行一個正整數，表示對應輸入行是否有一個年齡序列，滿足這一規律，如果是，就輸出Y，如果沒有，輸出N

Sample Input

4
2
1309
0
           

Sample Output

Y
N
N
           

HINT

解決之道：

準備知識：

①n對數，共2n個數。是以要有2n個位置來放置這2*n個數。②sum()表示求和運算。

正式解決：

①設k（k=1,2,…,n)放置的第一個位置為ak，第二個位置為bk。顯然有bk-ak=k+1（假定下一個位置在上一個位置之前）。

那麼會有sum(bk-ak)=2+3+4+…+(n+1)=(1+2+3+…+n)+(1+1+…+1)=n*(n+1)/2+n。

②又因為要有2n個位置來放置這2n個數。則sum(ak+bk)=1+2+3+…+2n=(1+2n)(2n)/2=(1+2*n)*n。

③sum(ak+bk)=sum(ak+ak+k+1)=sum(2ak+bk-ak)=2sum(ak)+sum(bk-ak)=2sum(ak)+n(n+1)/2+n。

④比較②③可得：(1+2n)n=2sum(ak)+n(n+1)/2+n。可得sum(ak)=n*(3*n-1)/4。

⑤就像前面已經說過的一樣，ak表示數k第一次出現的位置。ak不易确定。當可以肯定的是sum(ak)一定為正整數。

那麼就會有n=4p或者3n-1=4*p（p為正整數）。

（反正。我是沒看懂）

Code：

#include<stdio.h>
int main()
{
	int n;
	while(~scanf("%d",&n))
	{
	    if(n==0)break;
		if(n%4==0 || (3*n-1)%4==0)
		    printf("Y\n");
		else
		    printf("N\n");
	}
	return 0;
}