Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-07-08

[][] TopCoder 508 Div.1 250 DivideAndShift 07:02 はてなブックマーク -  TopCoder 508 Div.1 250 DivideAndShift - 練習帳

問題文

 問題文

要約

 1からNまで番号がついたスロットが横一列に並んでいる.これらに次の操作を行える.

  • Nで割り切れる素数pを適当にひとつ選び,N個のスロットp個ずつに分割する(1~N/p, N/p+1~2N/p ・・・)このうち1つを選び,N/pを新たなNとして,1からNの番号を振り直す
  • 左右どちらの方向かにスロット達を1つずつシフトする.

 左からM番目のスロットを1番目に持ってくるのに必要な最小操作回数を求めよ.

方針

 シフト=>分割と操作を行っている場合,もし,シフトによって分割のチャンクを跨ぐなら,順序を逆にして分割=>シフトとした方が最適,跨がなければこの2つの操作は書かん.従って,先に分割を繰り返してからシフトを行うと仮定してよい.

  • 分割を終了して,右シフトを繰り返して1番左まで持ってくる
  • 分割を終了して,左シフトを繰り返して1番右まで持ってくる
  • 分割を引き続き行う

のうち,最も回数の少ないものを選択する

コード例

#include <string>
#include <vector>
#include <string>
#include <iostream>
#include <sstream>
#include <cmath>

using namespace std;

bool isprime(int n){
  if(n < 2){
    return false;
  }
  for(int i = 2;i *i <=n;i++){
    if(n%i== 0){
      return false;
    }
  }
  return true;
}

int inf = 10000000;

int calc(int n, int m){
  //  cout << n << " " << m <<endl;
  
  if(m ==1){
    return 0;
  }
  int res = inf;
  int mx  = 1;

  if(n%2 == 0){
    int nextn = n/2;
    int nextm = ((m-1)%nextn)+1;
    res = min(res, calc(nextn, nextm) + 1);
    mx = 2;
  }

  for(int i = 2;i<=n;i++){
    if(n%i == 0 && isprime(i)){
      int nextn = n/i;
      int nextm = ((m-1)%nextn)+1;
      res = min(res, calc(nextn, nextm) + 1);
      mx = i;
    }
  }

  if(mx == 1){
    return 1;
  }

  res = min(m-1, min(n-m+1, res));

  return res;
}

class DivideAndShift {
public:
  int getLeast(int N, int M) {
    return calc(N, M);
  }
};