2/2 PKU

2644 Maze

迷路上に人がいる。人は自分の位置を知らない。うまく動作の列を定めてやることにより、人がどこにいても脱出できるようにせよ。人は外周のマスに達した時に脱出でき、一度脱出してしまったら後の動作は無視してよい。また移動先に壁がある場合は動かない。

最良優先探索。A* ?

1945 Power Hungry Cows

X^Pを計算するのに、2つの変数を用いる。最初(1, X)が入っている。2つの数(同じ変数のものでもよい)の積/商を求め、どちらかの変数に戻すという操作ができる。X^Pを計算するのに最短何回かかるか。

途中経過における変数の指数の上界を見積もる / 既出か確認するのに自前でhashを書く / GCD(x,y)がPを割り切らないものは即刻排除 / 最良優先探索 などの工夫により通る。