[BOJ 1242]ハイキング(Java)

7494 ワード
せいすう論 数学 テキストリンク

質問する


東湖と東湖の4つのクラスの学生たちは山頂湖へピクニックに行きました.全部でN人がピクニックに参加して、KINゲームをします.このゲームは次のように行われます.
舞台に上がったN人は1番からN番まで時計回りに丸く座っていた.このゲームは1日から始まります.そして一人一人が時計回りに1 2...Kまで数える.Kと言った人は退場された.そして次の席に座っている人は1から数えます.東昊もM番学生としてこのゲームに参加した.東昊は自分が何度目の出場罰を受けたのか気になった.
例えば、5人の学生が参加していると言えば、K=2、東昊は3番の学生で、最初は1 2 3 4 5と一緒に座っていました.1からゲームが始まるので、1は1、2は2と言います.2退場処分を受ける.3は1、4は2と言います.4退場処分を受ける.そして1罰で出場.その後5罰で退場し、最後の3罰で退場した.東昊は3人目の学生だったので、5人目は出場を命じられた.
N,K,Mが与えられた時、東昊が何度目の出場を罰されたかを知るプログラムを書いた.

入力


第1行は3つの整数N,K,Mを与える.

しゅつりょく


1行目の印刷東昊は何度も退場された.

制限

  • 1 ≤ N, M ≤ 5,000,000
  • 1 ≤ K ≤ N

    • 方法


  • 時計回りにN個描くべきです.1つ目の方法は、キューを使用してそのまま実装することである.しかし、質問を読んでみると、Nは5000,000であることがわかりました.すなわち、キューを使用して各ゲームの退場を実行すると、最悪の場合、O(NK)の効率が得られます.(約500万^2=25兆)

  • より効率的な方法を考えてみましょう.角度を変えてすべての学生が東昊の位置だけを追跡することを考慮しない.

  • 東昊の状態は大きく二つの状況に分かれている.(1)1番からK番までドンホが黙っている場合と(2)1番からK番までドンホが番号を言っている場合.

  • (1)の場合、東昊の次のゲームでの順番は(現在の東昊の順番-淘汰者の順番).

  • (2)の場合、東昊の次のゲームでの順番は(現在のゲーム参加者-淘汰者の順番+現在の東昊の順番)である.

  • 東昊の順番が淘汰者の順番と同じなら、東昊がこのゲームで淘汰されたのを見ることができる.
    • に感謝
  • 数学と整数論の問題の多くは方法と方法を知らないときに大きな違いがある.アルゴリズムに詳しくない場合は、データ構造をレビューし、問題に基づいて最適化できます.
  • whileクエリ条件はm%nです.Input=(2.42)または(2.22)などの場合の処理要求.問題を解決するのは見逃しやすいので、気をつけてください.

    • ソースコード

    import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Picnic {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int k = Integer.parseInt(input[1]);
        int m = Integer.parseInt(input[2]);
        int cnt = 1;
        int removed;

        while ((removed = k % n) != m % n) {
            if (removed < m) {
                m -= removed;
            } else {
                m = n - removed + m;
            }
            n--;
            cnt++;
        }
        System.out.println(cnt);
    }
}

    結果


    CSSとは
    React - SPA, router