#[allow(unused)] mod rnd { static mut S:usize=88172645463325252; #[inline] pub fn next()->usize{ unsafe{ S=S^S<<7; S=S^S>>9; S } } #[inline] pub fn nextf()->f64{ (next()&4294967295) as f64/4294967296. } } #[allow(unused)] struct Scanner<'a>{ stack:std::str::SplitAsciiWhitespace<'a> } #[allow(unused)] impl<'a> Scanner<'a>{ #[inline] fn new()->Self{ Self{stack:"".split_ascii_whitespace()} } #[inline] fn read(&mut self)->T{ loop{ if let Some(v)=self.stack.next(){ return v.parse::().unwrap_or_else(|_|panic!("parse error")); } let mut tmp=String::new(); std::io::stdin().read_line(&mut tmp).unwrap(); assert!(!tmp.is_empty()); self.stack=Box::leak(tmp.into_boxed_str()).split_ascii_whitespace(); } } } #[derive(PartialEq, PartialOrd)] struct Hoge(T); impl Eq for Hoge{} impl Ord for Hoge{ fn cmp(&self, other:&Self)->std::cmp::Ordering{ self.0.partial_cmp(&other.0).unwrap() } } const N:usize=20; const S:f64=0.19; const DY:[usize;4]=[1,!0,0,0]; const DX:[usize;4]=[0,0,1,!0]; const DC:[char;4]=['D','U','R','L']; struct Solver{ p:f64, aru:[[[f64;4];N];N], nai:[[[f64;4];N];N], map:[[[f64;4];N];N], log:Vec> // y,x,r } impl Solver{ #[inline] fn new(scan:&mut Scanner)->Solver{ let h=scan.read(); let w=scan.read(); assert_eq!((h,w),(N,N)); let p:usize=scan.read(); let p=p as f64*0.01; Solver{ p, aru:[[[S;4];N];N], nai:[[[1.-S;4];N];N], map:[[[S;4];N];N], log:vec![] } } #[inline] fn isok(&self,seen:&[[[usize;4];N];N],at:usize)->bool{ 'outer: for l in &self.log{ for &(y,x,r) in l{ if seen[y][x][r]!=at && self.map[y][x][r]!=0.{ continue 'outer; } } return false; } true } #[inline] fn next_cmds(&mut self)->Vec<(usize,usize,usize)>{ let mut cur=vec![]; let mut edge=[[[0.;4];N];N]; let mut seen=[[0;N];N]; let mut prev=[[!0;N];N]; let mut at=0; let mut que=std::collections::BinaryHeap::new(); let mut tmp=[[[0;4];N];N]; let mut iter=1; let ret=loop{ if iter&255==0 && rnd::next()&3==0{ for i in 0..N{ for j in 0..N{ for k in 0..4{ self.aru[i][j][k]=S; self.nai[i][j][k]=1.-S; self.map[i][j][k]=S; } } } } for i in 0..N{ for j in 0..N{ for k in 0..4{ edge[i][j][k]=self.map[i][j][k]*rnd::nextf(); } } } at+=1; que.clear(); que.push((Hoge(1.),0,!0,(0,0))); while let Some((Hoge(f),_,r,(y,x)))=que.pop(){ if seen[y][x]!=at{ seen[y][x]=at; prev[y][x]=r; if (y,x)==(N-1,N-1){ break; } else{ for (i,(&dy,&dx)) in DY.iter().zip(DX.iter()).enumerate(){ let ny=y+dy; let nx=x+dx; if ny)->bool{ for (_,_,r) in &cmds{ print!("{}",DC[*r]); } println!(); let result:i64=scan.read(); if result==-1{ true } else{ for i in 0..result{ let (y,x,r)=cmds[i as usize]; self.aru[y][x][r]=0.; self.aru[y+DY[r]][x+DX[r]][r^1]=0.; } let (y,x,r)=cmds[result as usize]; let (ny,nx,nr)=(y+DY[r],x+DX[r],r^1); self.aru[y][x][r]*=1.-self.p; self.aru[ny][nx][nr]=self.aru[y][x][r]; self.nai[y][x][r]*=self.p; self.nai[ny][nx][nr]=self.nai[y][x][r]; let mut sum=1.; for &(y,x,r) in &cmds{ let aru=self.aru[y][x][r]; let nai=self.nai[y][x][r]; self.map[y][x][r]=aru/(aru+nai); sum*=1.-self.map[y][x][r]; self.map[y+DY[r]][x+DX[r]][r^1]=self.map[y][x][r]; } for &(y,x,r) in &cmds{ self.nai[y][x][r]*=1.-sum/(1.-self.map[y][x][r]); } for &(y,x,r) in &cmds{ let aru=self.aru[y][x][r]; let nai=self.nai[y][x][r]; self.map[y][x][r]=aru/(aru+nai); sum*=1.-self.map[y][x][r]; self.map[y+DY[r]][x+DX[r]][r^1]=self.map[y][x][r]; } self.log.push(cmds); false } } } fn main(){ let mut scan=Scanner::new(); let mut solver=Solver::new(&mut scan); let mut score=/*square*/1001; loop{ score-=1; if score==0{break;} let next_cmds=solver.next_cmds(); if solver.run_cmds(&mut scan,next_cmds){ break; } } eprintln!("{:?}",score); }