[200]158号ジョセフス問題



1158号ジョセフス問題


質問する


ジョセフス問題は以下の通りです.
1番からN番までは、N人が1つの円に座り、正の整数K(≦N)を与えます.今は順番にK人目を除いています.一人が取り除かれると、残りの人からなる円に沿ってこの過程が続きます.この過程はN人全員がクリアされるまで続く.円上の人々が消去される順序を(N,K)−ジョセフス配列と呼ぶ.例えば、(7,3)−ジョセフス配列<3,6,2,7,5,1,4>である.
NとKをあげると(N,K)-ジョセフスシーケンスを求めるプログラムを書きます.

入力


第1行NとKは、スペースを隔てて順次与えられる.(1 ≤ K ≤ N ≤ 5,000)

しゅつりょく


例に示すように、ジョセフスシーケンスを出力します.

コピー例入力1

7 3

コピー例出力1

<3, 6, 2, 7, 5, 1, 4>

コード#コード#

//---- 세팅 ----//
const fs = require('fs');
const stdin = (
  process.platform === 'linux'
    ? fs.readFileSync('/dev/stdin').toString()
    : `\
7 3
`
).split('\n');

const input = (() => {
  let line = 0;
  return () => stdin[line++];
})();

//---- 풀이 -----//
const [n, k] = input().split(' ').map(Number);
const arr = [...Array(n)].map((v, i) => i + 1);
const res = [];

while (arr.length) {
  [...Array(k)].forEach(() => {
     arr.push(arr.shift());
  })
  res.push(arr.pop());
}

console.log('<' + res.join(', ') + '>');

に答える

arrが空になるまで、ジョセフスk次変換を推進します.
k回終了後、最後の要素がターゲット要素であるため、popはres配列に押される.