#UVa:305-Joseph

照著模擬砍的過程,去察覺若有某個m能夠讓砍掉前一半的人都在後半部的話就是答案。可以先將答案算出來並儲存起來,這樣可以加速重複要答案的部分。

C++(0.309)

/*******************************************************/
/* UVa 305 Joseph                                      */
/* Author: LanyiKnight [at] knightzone.org             */
/* Version: 2015/05/13                                 */
/*******************************************************/
#include <iostream>
#include <cstdio>
using namespace std;

int main(){
  int mem[15] = {0};
  for( int i = 1 ; i <= 14 ; ++i ){
    int m = i + 1;
    while( true ){
      int k = i * 2;

      int killPerson = -1;
      while( k > i ){
        killPerson += m;
        killPerson %= k;
        if( killPerson < i ){
          break;
        }
        --k;
        --killPerson;
      }

      if( k <= i ){
        mem[i] = m;
        break;
      }

      ++m;
    }
  }

  int k;
  while( scanf("%d", &k) != EOF && k != 0 ){
    printf("%d\n", mem[k]);
  }

  return 0;
}

沒有迴響

本文還沒有迴響,快來搶頭香!

發表迴響