use grid::{Coordinate, Map2d, ADJACENTS, DIRECTIONS}; #[allow(unused_macros)] macro_rules! chmin { ($base:expr, $($cmps:expr),+ $(,)*) => {{ let cmp_min = min!($($cmps),+); if $base > cmp_min { $base = cmp_min; true } else { false } }}; } #[allow(unused_macros)] macro_rules! chmax { ($base:expr, $($cmps:expr),+ $(,)*) => {{ let cmp_max = max!($($cmps),+); if $base < cmp_max { $base = cmp_max; true } else { false } }}; } #[allow(unused_macros)] macro_rules! min { ($a:expr $(,)*) => {{ $a }}; ($a:expr, $b:expr $(,)*) => {{ std::cmp::min($a, $b) }}; ($a:expr, $($rest:expr),+ $(,)*) => {{ std::cmp::min($a, min!($($rest),+)) }}; } #[allow(unused_macros)] macro_rules! max { ($a:expr $(,)*) => {{ $a }}; ($a:expr, $b:expr $(,)*) => {{ std::cmp::max($a, $b) }}; ($a:expr, $($rest:expr),+ $(,)*) => {{ std::cmp::max($a, max!($($rest),+)) }}; } macro_rules! get { ($t:ty) => { { let mut line: String = String::new(); std::io::stdin().read_line(&mut line).unwrap(); line.trim().parse::<$t>().unwrap() } }; ($($t:ty),*) => { { let mut line: String = String::new(); std::io::stdin().read_line(&mut line).unwrap(); let mut iter = line.split_whitespace(); ( $(iter.next().unwrap().parse::<$t>().unwrap(),)* ) } }; ($t:ty; $n:expr) => { (0..$n).map(|_| get!($t) ).collect::>() }; ($($t:ty),*; $n:expr) => { (0..$n).map(|_| get!($($t),*) ).collect::>() }; ($t:ty ;;) => { { let mut line: String = String::new(); std::io::stdin().read_line(&mut line).unwrap(); line.split_whitespace() .map(|t| t.parse::<$t>().unwrap()) .collect::>() } }; ($t:ty ;; $n:expr) => { (0..$n).map(|_| get!($t ;;)).collect::>() }; } const MAP_SIZE: usize = 20; const MAX_MOVES: usize = 400; const DEFAULT_PROB: f64 = 1.0 - 0.1875; #[derive(Debug, Clone, Copy)] struct Input { p: f64, } #[derive(Debug, Clone)] struct State { map: Map2d<[Edge; 4]>, } #[derive(Debug, Clone, Copy)] struct Edge { next: Option, state: EdgeState, } impl Edge { fn new(next: Option, state: EdgeState) -> Self { Self { next, state } } } #[derive(Debug, Clone, Copy)] enum EdgeState { NotEnter, NoWall, MayBeWall(i32), } impl EdgeState { #[inline] fn prob(&self, p: f64) -> f64 { match self { EdgeState::NotEnter => DEFAULT_PROB, EdgeState::NoWall => 1.0, EdgeState::MayBeWall(c) => p.powi(*c), } } } fn main() { let (input, state) = read_input(); let score = solve(&input, state); eprintln!("score: {}", score); } fn read_input() -> (Input, State) { let (_, _, p) = get!(usize, usize, i64); let p = p as f64 * 0.01; let mut map = Map2d::new( vec![[Edge::new(None, EdgeState::NotEnter); 4]; MAP_SIZE * MAP_SIZE], MAP_SIZE, ); for row in 0..MAP_SIZE { for col in 0..MAP_SIZE { let c = Coordinate::new(row, col); for (dir, adj) in ADJACENTS.iter().enumerate() { let next = c + *adj; if next.in_map(MAP_SIZE) { map[c][dir].next = Some(next); } } } } let input = Input { p }; let state = State { map }; (input, state) } fn solve(input: &Input, mut state: State) -> i64 { for trial in 0.. { let moves = dp(input, &state); if let Some(stop) = write_output(&moves) { update_state(&mut state, &moves[..stop], moves[stop]) } else { return 1001 - trial - 1; } } 0 } fn dp(input: &Input, state: &State) -> Vec { let mut dp = vec![Map2d::new(vec![0.0; MAP_SIZE * MAP_SIZE], MAP_SIZE); MAX_MOVES + 1]; let mut from = vec![Map2d::new(vec![0; MAP_SIZE * MAP_SIZE], MAP_SIZE); MAX_MOVES + 1]; dp[0][Coordinate::new(0, 0)] = 1.0; for turn in 0..MAX_MOVES { for row in 0..MAP_SIZE { for col in 0..MAP_SIZE { let c = Coordinate::new(row, col); for dir in 0..4 { let edge = state.map[c][dir]; if let Some(next) = edge.next { let prob = edge.state.prob(input.p); if chmax!(dp[turn + 1][next], dp[turn][c] * prob) { from[turn + 1][next] = dir; } } } } } } let mut max_prob = 0.0; let mut max_turn = 0; let goal = Coordinate::new(MAP_SIZE - 1, MAP_SIZE - 1); for turn in 0..=MAX_MOVES { if chmax!(max_prob, dp[turn][goal]) { max_turn = turn; } } let mut current = goal; let mut turn = max_turn; let mut moves = vec![]; while turn > 0 { let dir = from[turn][current]; moves.push(dir); current = current + ADJACENTS[dir ^ 2]; turn -= 1; } moves.reverse(); moves } fn update_state(state: &mut State, ok: &[usize], ng: usize) { let mut current = Coordinate::new(0, 0); for &ok in ok { state.map[current][ok].state = EdgeState::NoWall; current = current + ADJACENTS[ok]; } state.map[current][ng].state = match state.map[current][ng].state { EdgeState::NotEnter => EdgeState::MayBeWall(1), EdgeState::NoWall => unreachable!(), EdgeState::MayBeWall(c) => EdgeState::MayBeWall(c + 1), } } fn write_output(moves: &[usize]) -> Option { let output = moves.iter().map(|dir| DIRECTIONS[*dir]).collect::(); println!("{}", output); let judge = get!(i64); if judge == -1 { None } else { Some(judge as usize) } } #[allow(dead_code)] mod grid { #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] pub struct Coordinate { pub row: usize, pub col: usize, } impl Coordinate { pub const fn new(row: usize, col: usize) -> Self { Self { row, col } } pub fn in_map(&self, size: usize) -> bool { self.row < size && self.col < size } pub const fn to_index(&self, size: usize) -> usize { self.row * size + self.col } pub const fn dist(&self, other: &Self) -> usize { Self::dist_1d(self.row, other.row) + Self::dist_1d(self.col, other.col) } const fn dist_1d(x0: usize, x1: usize) -> usize { (x0 as i64 - x1 as i64).abs() as usize } } #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] pub struct CoordinateDiff { pub dr: usize, pub dc: usize, } impl CoordinateDiff { pub const fn new(dr: usize, dc: usize) -> Self { Self { dr, dc } } pub const fn invert(&self) -> Self { Self::new(0usize.wrapping_sub(self.dr), 0usize.wrapping_sub(self.dc)) } } impl std::ops::Add for Coordinate { type Output = Coordinate; fn add(self, rhs: CoordinateDiff) -> Self::Output { Coordinate::new(self.row.wrapping_add(rhs.dr), self.col.wrapping_add(rhs.dc)) } } pub const ADJACENTS: [CoordinateDiff; 4] = [ CoordinateDiff::new(!0, 0), CoordinateDiff::new(0, 1), CoordinateDiff::new(1, 0), CoordinateDiff::new(0, !0), ]; pub const DIRECTIONS: [char; 4] = ['U', 'R', 'D', 'L']; #[derive(Debug, Clone)] pub struct Map2d { pub width: usize, pub height: usize, map: Vec, } impl Map2d { pub fn new(map: Vec, width: usize) -> Self { let height = map.len() / width; debug_assert!(width * height == map.len()); Self { width, height, map } } } impl std::ops::Index for Map2d { type Output = T; #[inline] fn index(&self, coordinate: Coordinate) -> &Self::Output { &self.map[coordinate.row * self.width + coordinate.col] } } impl std::ops::IndexMut for Map2d { #[inline] fn index_mut(&mut self, coordinate: Coordinate) -> &mut Self::Output { &mut self.map[coordinate.row * self.width + coordinate.col] } } impl std::ops::Index<&Coordinate> for Map2d { type Output = T; #[inline] fn index(&self, coordinate: &Coordinate) -> &Self::Output { &self.map[coordinate.row * self.width + coordinate.col] } } impl std::ops::IndexMut<&Coordinate> for Map2d { #[inline] fn index_mut(&mut self, coordinate: &Coordinate) -> &mut Self::Output { &mut self.map[coordinate.row * self.width + coordinate.col] } } impl std::ops::Index for Map2d { type Output = [T]; #[inline] fn index(&self, row: usize) -> &Self::Output { let begin = row * self.width; let end = begin + self.width; &self.map[begin..end] } } impl std::ops::IndexMut for Map2d { #[inline] fn index_mut(&mut self, row: usize) -> &mut Self::Output { let begin = row * self.width; let end = begin + self.width; &mut self.map[begin..end] } } }