読者です 読者をやめる 読者になる 読者になる

解いた問題のソースコードと解説など。


POJ 1455 Crazy tea party

問題

http://poj.org/problem?id=1455
n人が車座になって座っている。一回の席交換で隣り合う二人が入れ替わる。はじめとは逆順に座るためには席交換を最小で何回行えばいいか。

やりかた

n人を半分こしてそれらごとにひっくり返せばいい。
1234|5678 → 4321|8765
こんな感じ。ひっくり返し方はグループにm人いればm * (m - 1) / 2。

以下ソース。

int main(){
  int t; cin >> t;
  while(t--){
    int n; cin >> n;
    cout << (n / 2) * (n / 2 - 1) / 2 
      + (n - n / 2) * (n - n / 2 - 1) / 2 << endl;
  } 
  return 0;
}

何回か実験したら思い浮かんだ。
TCO R3Aでpractice roomから閉めだされてしまったのでPOJで時間つぶし。

しょげないでよBaby 眠れば治る