PKU Judge Online 1455 Crazy tea party

■1455 Crazy tea party

□Problem
n人のcrazy tea party参加者が円テーブルに座っている．各ステップで，1組の隣り合う2人が位置を交代することが出来る．n人の位置を逆順にするための最小ステップ数を求めよ．

□Solution
f(n)=最小ステップ数
g(n)=n人が一直線上に座っているとした時の反転にかかる最小ステップ数とする．

g(n)を求める．
n=5の時，
12345
↓
23451
ここまでで，n-1ステップかかる．
残り2345を反転させるためにはg(4)ステップかかる．
よって，
g(n)=g(n-1)+n-1
g(1)=1
となるため，
g(n)=n(n-1)/2

f(n)を求める．
n人を2分割してそれぞれを反転させる(3分割してそれぞれを反転させても逆順にはならないので意味が無い)．
123|456
↓
321|654
n=2mの時は，
g(n)+g(n)<g(n-k)+g(n+k) (k>0)
より，丁度真ん中で分割した時が最小ステップとなる．
f(n)=g(m)+g(m)
n=2m+1の時も，(多分)同様にして示せるため
f(n)=g(m)+g(m+1)

□Code

view plainprint?

1. package p1455;  
2.   
3. import java.util.*;  
4. import java.lang.*;  
5. import java.math.*;  
6.   
7. public class Main{  
8.     Scanner sc=new Scanner(System.in);  
9.   
10.     void run(){  
11.         for(int t=sc.nextInt(); t>0; t--){  
12.             int n=sc.nextInt();  
13.             int r=n/2;  
14.             int s=n-r;  
15.             int ans=r*(r-1)/2+s*(s-1)/2;  
16.             println(""+ans);  
17.         }  
18.     }  
19.   
20.     void println(String s){  
21.         System.out.println(s);  
22.     }  
23.   
24.     void print(String s){  
25.         System.out.print(s);  
26.     }  
27.   
28.     public static void main(String[] args){  
29.         new Main().run();  
30.     }  
31. }  

package p1455;

import java.util.*;
import java.lang.*;
import java.math.*;

public class Main{
    Scanner sc=new Scanner(System.in);

    void run(){
        for(int t=sc.nextInt(); t>0; t--){
            int n=sc.nextInt();
            int r=n/2;
            int s=n-r;
            int ans=r*(r-1)/2+s*(s-1)/2;
            println(""+ans);
        }
    }

    void println(String s){
        System.out.println(s);
    }

    void print(String s){
        System.out.print(s);
    }

    public static void main(String[] args){
        new Main().run();
    }
}