HDU2554：N對數的排列問題
題目為：有N對雙胞胎，他們的年齡分别是1，2，3，……，N歲，他們手拉手排成一隊到野外去玩，要經過一根獨木橋，為了安全起見，要求年齡大的和年齡小的排在一起，好讓年齡大的保護年齡小的，然後從頭到尾，每個人報告自己的年齡，就得到了一個年齡的序列。比如有4對雙胞胎，他們報出來的年齡序列是：41312432。突然，他們中間最聰明的小明發現了一個有趣的現象，原來，這個年齡序列有一個規律，兩個1中間有1個數，兩個2中間有2個數，兩個3中間有3個數，兩個4中間有4個數。但是，如果是2對雙胞胎，那麼無論他們怎麼排年齡序列，都不能滿足這個規律。
你的任務是，對于給定的N對雙胞胎，是否有一個年齡序列，滿足這一規律，如果是，就輸出Y，如果沒有，輸出N。
參考 HDU2554 N對數的排列 的方法。
1. 由題目可以将問題轉化為：當n在什麼情況下， 對于任意一個數k in n, 不妨假設右邊的位置kr>左邊的位置kl， 有kr-kl =k+1。（如果序列a存在，必然有這樣的關系式kr-kl=k+1, for every k。如果關系式kr-kl=k+1, for every k， 那麼序列a一定存在[反證法即可]）。換句話說，kr-kl =k+1成立時，n滿足什麼條件？
2. 在上述作者的文中可以知道定義的sum這個函數是一個線性函數，是以以下的推導都是充分必要條件。由kr-kl =k+1可知，sum(kr+kl)=sum(kr+kl+k+1)=sum(2kl+k+1)=2sum(kl)+ n(n+1)/2+n, 又因為sum(kr+kl)=sum(2n)=(1+2n)n
可得sum(kl)= n(3n-1)/4, 由于sum(kl)是正整數，是以n應該滿足n mod 4 =0或者 3n-1 mod 4 =0
1 #include <iostream>
2 using namespace std;
3 int main(int argc, char *argv[])
4 {
5 int n;
6 while(cin>>n && n){
7 if(n%4 == 0 || (3*n-1) % 4 ==0)
8 cout <<"Y"<<endl;
9 else
10 cout <<"N"<<endl;
11 }
12 return 0;
13 } 另外這裡用cout，cin時間很長，甚至會逾時。我剛好是953ms，就不用printf，puts之類的了。
轉載于:https://www.cnblogs.com/linspirit/articles/3871311.html