結果
問題 | No.533 Mysterious Stairs |
ユーザー |
|
提出日時 | 2017-10-11 11:37:39 |
言語 | Rust (1.83.0 + proconio) |
結果 |
AC
|
実行時間 | 83 ms / 5,000 ms |
コード長 | 2,201 bytes |
コンパイル時間 | 13,059 ms |
コンパイル使用メモリ | 384,728 KB |
実行使用メモリ | 56,572 KB |
最終ジャッジ日時 | 2024-11-17 09:21:55 |
合計ジャッジ時間 | 14,803 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 28 |
ソースコード
#[allow(unused_imports)]use std::cmp::{max, min};#[allow(unused_imports)]use std::collections::{HashMap, HashSet};mod util {use std::io::stdin;use std::str::FromStr;use std::fmt::Debug;#[allow(dead_code)]pub fn line() -> String {let mut line: String = String::new();stdin().read_line(&mut line).unwrap();line.trim().to_string()}#[allow(dead_code)]pub fn get<T: FromStr>() -> Twhere<T as FromStr>::Err: Debug,{let mut line: String = String::new();stdin().read_line(&mut line).unwrap();line.trim().parse().unwrap()}#[allow(dead_code)]pub fn gets<T: FromStr>() -> Vec<T>where<T as FromStr>::Err: Debug,{let mut line: String = String::new();stdin().read_line(&mut line).unwrap();line.split_whitespace().map(|t| t.parse().unwrap()).collect()}#[allow(dead_code)]pub fn get2<T: FromStr, U: FromStr>() -> (T, U)where<T as FromStr>::Err: Debug,<U as FromStr>::Err: Debug,{let mut line: String = String::new();stdin().read_line(&mut line).unwrap();let mut iter = line.split_whitespace();(iter.next().unwrap().parse().unwrap(),iter.next().unwrap().parse().unwrap(),)}}#[allow(unused_macros)]macro_rules! debug {($x: expr) => {println!("{}: {:?}", stringify!($x), $x)}}const M: usize = 1000000007;fn main() {let n: usize = util::get();let mut dp = vec![vec![0; 3]; max(n + 1, 4)];dp[1][0] = 1;dp[2][1] = 1;dp[3][2] = 1;for i in 1..n + 1 {if i >= 1 {dp[i][0] = (dp[i][0] + dp[i - 1][1]) % M;dp[i][0] = (dp[i][0] + dp[i - 1][2]) % M;}if i >= 2 {dp[i][1] = (dp[i][1] + dp[i - 2][0]) % M;dp[i][1] = (dp[i][1] + dp[i - 2][2]) % M;}if i >= 3 {dp[i][2] = (dp[i][2] + dp[i - 3][0]) % M;dp[i][2] = (dp[i][2] + dp[i - 3][1]) % M;}}println!("{}", dp[n].iter().fold(0, |a, &b| (a + b) % M));}