結果

問題 No.7 プライムナンバーゲーム
ユーザー tabataba
提出日時 2024-07-30 11:10:51
言語 Rust
(1.77.0 + proconio)
結果
AC  
実行時間 49 ms / 5,000 ms
コード長 1,451 bytes
コンパイル時間 14,078 ms
コンパイル使用メモリ 401,400 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-30 11:11:08
合計ジャッジ時間 15,726 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 45 ms
6,812 KB
testcase_01 AC 49 ms
6,944 KB
testcase_02 AC 46 ms
6,940 KB
testcase_03 AC 45 ms
6,944 KB
testcase_04 AC 45 ms
6,940 KB
testcase_05 AC 45 ms
6,944 KB
testcase_06 AC 45 ms
6,944 KB
testcase_07 AC 46 ms
6,940 KB
testcase_08 AC 46 ms
6,940 KB
testcase_09 AC 46 ms
6,944 KB
testcase_10 AC 46 ms
6,940 KB
testcase_11 AC 49 ms
6,944 KB
testcase_12 AC 47 ms
6,940 KB
testcase_13 AC 48 ms
6,940 KB
testcase_14 AC 47 ms
6,940 KB
testcase_15 AC 46 ms
6,940 KB
testcase_16 AC 46 ms
6,940 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
warning: unused import: `proconio::marker::Chars`
 --> src/main.rs:3:5
  |
3 | use proconio::marker::Chars;
  |     ^^^^^^^^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: function `proc` is never used
  --> src/main.rs:20:4
   |
20 | fn proc(n: u64) -> u64 {
   |    ^^^^
   |
   = note: `#[warn(dead_code)]` on by default

ソースコード

diff # 

use std::collections::HashMap;

use proconio::marker::Chars;

fn main() {
    proconio::input! {
        n: u64,
    }
    let mut memo = HashMap::new();
    for n in 2..=10000 {
        winlose(n, &mut memo);
    }
    if winlose(n, &mut memo) {
        println!("Win");
    } else {
        println!("Lose");
    }
}

fn proc(n: u64) -> u64 {
    (n / 3 + n / 5) * 2
}

const PRIME_NUM: [u64; 1229] = {
    let mut tbl = [0; 1229];
    let mut i = 0;
    let mut p = 0;
    while p < PRIME.len() as u64 {
        if PRIME[p as usize] {
            tbl[i] = p;
            i += 1;
        }
        p += 1;
    }
    tbl
};
const PRIME: [bool; 10001] = create_prime();
const fn create_prime<const N: usize>() -> [bool; N] {
    let mut table = [true; N];
    table[0] = false;
    table[1] = false;
    let mut i = 2;
    while i < N {
        if table[i] {
            let mut j = i * 2;
            while j < N {
                table[j] = false;
                j += i;
            }
        }
        i += 1;
    }
    table
}

fn winlose(n: u64, memo: &mut HashMap<u64, bool>) -> bool {
    if n < 2 {
        return true;
    }
    if let Some(&memo) = memo.get(&n) {
        return memo;
    }
    let result = PRIME_NUM
        .iter()
        .copied()
        .take_while(|&x| x < n)
        .any(|x| !winlose(n - x, memo));
    memo.insert(n, result);
    result
}

#[cfg(test)]
mod test {
    use super::*;
    #[test]
    fn test() {}
}
0