HDu-円卓会議
2202 ワード
法則+数論
円卓会議
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 2523 Accepted Submission(s): 1745
Problem Description
HDU ACM合宿チームのメンバーは夏休みの合宿でよく自分の問題を討論します.自分で解決できない問題に直面するたびに、丸いテーブルのそばに座って交流します.みんなの討論を経て、一般的に解決できない問題はありません.これもHDU ACM合宿チーム特有の円卓会議だけです.ある日、あなたも入って体得することができます.ある日の討論の時、Eddyは極めて奇妙な考えを思いついた.もし彼らが毎分、隣接する2人のACM隊員が席を交換したら、元の状態とは逆の席順を得るにはどのくらいの時間がかかるのだろうか.(つまり、すべての選手に対して、もともと彼の左にいた選手は後で彼の右にいて、もともと彼の右にいた選手は彼の左にいます)これはもちろん他の賢い他のチームメイトたちを倒すことができなくて、すぐにこの奇妙な問題を解決して、あなたはどのように解決したか知っていますか?
Input
与えられた数N(1<=N<=32767)に対して、N人がいることを示し、元の状態とは逆の座席順序(reverse)を得るにはどのくらいの時間がかかるかを求める.すなわち、一人一人に対して、元の左にいた人が右にいて、元の右にいた人が左にいる.
Output
データごとに1行出力し、所要時間(分単位)を表します.
Sample Input
Sample Output
問題解決の考え方:
毎分1対しかありません.そして、このペアは隣の人が位置を交換しなければなりません.問題の意味を理解することに注意してください.
リングでなければ、このように逆シーケンスにしたいのは、泡のソートに似ています.そうすれば、n人がいれば、n*(n-1)/2ステップが必要です.
では、1つのリングにとって、どのようにして最も速いソート方法に達することができるのか、実は前のように、このリングを2つの「線分」に「切る」ことであり、この2つの線分が逆順に並ぶと同時に、このリングも逆順になる.
例えば、5人が円卓に囲まれて1~5の番号をつけていれば、逆順になりたい.1、2人と3、4、5人の2つのケースと見なすことができる.1、2が逆順になる2、1が1歩、3、4、5が逆順になる5、4、3が3歩、このときのシーケンスは2、1、5、4、3が目的を達成する.
移動の過程は、円環を2つのセグメントに分けて移動します.では、どこでセグメント化しますか?
答えはできるだけ2段の長さを等しくすることです.
なぜですか?証明は以下の通りです.
nを総長とし、2段に分け、長さはそれぞれa、bとする.総回数=a*(a-1)/2+b*(b-1)/2=a*(a-1)/2+(n-a-1)/2=(2*a^2-2*n*a+n^2)/2.
ここで、nは定数であり、aは変数である.二次曲線の開口は上向きであり、最小値に対応するa=-(-2*n)/(2*2)=n/2である.明らかにaは整数を要求する.
円卓会議
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 2523 Accepted Submission(s): 1745
Problem Description
HDU ACM合宿チームのメンバーは夏休みの合宿でよく自分の問題を討論します.自分で解決できない問題に直面するたびに、丸いテーブルのそばに座って交流します.みんなの討論を経て、一般的に解決できない問題はありません.これもHDU ACM合宿チーム特有の円卓会議だけです.ある日、あなたも入って体得することができます.ある日の討論の時、Eddyは極めて奇妙な考えを思いついた.もし彼らが毎分、隣接する2人のACM隊員が席を交換したら、元の状態とは逆の席順を得るにはどのくらいの時間がかかるのだろうか.(つまり、すべての選手に対して、もともと彼の左にいた選手は後で彼の右にいて、もともと彼の右にいた選手は彼の左にいます)これはもちろん他の賢い他のチームメイトたちを倒すことができなくて、すぐにこの奇妙な問題を解決して、あなたはどのように解決したか知っていますか?
Input
与えられた数N(1<=N<=32767)に対して、N人がいることを示し、元の状態とは逆の座席順序(reverse)を得るにはどのくらいの時間がかかるかを求める.すなわち、一人一人に対して、元の左にいた人が右にいて、元の右にいた人が左にいる.
Output
データごとに1行出力し、所要時間(分単位)を表します.
Sample Input
4
5
6
Sample Output
2
4
6
問題解決の考え方:
毎分1対しかありません.そして、このペアは隣の人が位置を交換しなければなりません.問題の意味を理解することに注意してください.
リングでなければ、このように逆シーケンスにしたいのは、泡のソートに似ています.そうすれば、n人がいれば、n*(n-1)/2ステップが必要です.
では、1つのリングにとって、どのようにして最も速いソート方法に達することができるのか、実は前のように、このリングを2つの「線分」に「切る」ことであり、この2つの線分が逆順に並ぶと同時に、このリングも逆順になる.
例えば、5人が円卓に囲まれて1~5の番号をつけていれば、逆順になりたい.1、2人と3、4、5人の2つのケースと見なすことができる.1、2が逆順になる2、1が1歩、3、4、5が逆順になる5、4、3が3歩、このときのシーケンスは2、1、5、4、3が目的を達成する.
移動の過程は、円環を2つのセグメントに分けて移動します.では、どこでセグメント化しますか?
答えはできるだけ2段の長さを等しくすることです.
なぜですか?証明は以下の通りです.
nを総長とし、2段に分け、長さはそれぞれa、bとする.総回数=a*(a-1)/2+b*(b-1)/2=a*(a-1)/2+(n-a-1)/2=(2*a^2-2*n*a+n^2)/2.
ここで、nは定数であり、aは変数である.二次曲線の開口は上向きであり、最小値に対応するa=-(-2*n)/(2*2)=n/2である.明らかにaは整数を要求する.
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int a,b,n;
while(~scanf("%d",&n))
{
a=n/2;
b=n-a;
printf("%d
",(a*(a-1)+b*(b-1))/2);
}
return 0;
}