Hatena::ブログ(Diary)

fura_2の日記

2012-11-24

POJ (PKU) 2828 : Buy Tickets

問題

n 人の人が順番にやってきて列を作ります。
i 番目の人は前から数えて pos[i] 番目に並んでいる人の直前に割り込みます。
n 人全員が並び終えたときの列を求めなさい。

  • 1 ¥le n ¥le 2¥times10^5

続きを読む

2012-06-20

POJ (PKU) 2032 : Square Carpets

問題

大きさ H × W の床があり、いくつかのマスは汚れています。
正方形のカーペットを何枚か使ってすべての汚れを覆いたい。
最小で何枚のカーペットが必要か求めてください。
ただし、カーペットで汚れていないマスを覆うことはできません。

  • 1 ¥le H, W ¥le 10

続きを読む

2012-01-26

POJ (PKU) 3811 : Infected Land

問題

n × n の盤上で 23/3 ルールのライフゲームを行います。
ただし、盤上には特別なコマが 1 つあり、そのコマは次のように振舞います。

  • 他のセルの生死判定の際は生きているセルとしてカウントされる
  • 特別なコマがいるセルは死んでいる
  • 毎ターンの最初に、隣接する 8 セルの中で死んでいるセルを 1 つ選んでそこに移動する

特別なコマを最適な手順で動かしたとして、すべてのセルを死滅させるのに最短で何手必要か求めてください。
そのような手順が存在しない場合は -1 を出力してください。

  • 1 ¥le n ¥le 5

続きを読む

2011-09-13

POJ (PKU) 3213 : PM3

問題

N × P の行列 A
P × M の行列 B
N × M の行列 C
が与えられるので、
A B = C
かどうか判定してください。

A B ≠ C の場合、( C において) 間違っている箇所と正しい値も答えてください。
間違いは高々 1 ヶ所ということがわかっています。

  • 1 ¥le N,¥:P,¥:M ¥le 1000

続きを読む

2011-08-14

POJ (PKU) 1065 : Wooden Sticks

問題

長さ l と重さ w で特徴付けられる棒が n 本あります。
これらの棒を 1 本ずつ順番に機械で処理することを考えます。

直前に処理した棒を (l_1,¥:w_1),次に処理する棒を (l_2,¥:w_2) とすると、l_1 ¥le l_2 ¥: {¥rm and} ¥: w_1 ¥le w_2 であれば、(l_2,¥:w_2) の処理にかかる時間は 0 分になります。
そうでなければ、処理にかかる時間は 1 分になります。

最適な順番で処理を行うとき、合計処理時間の最小値を求めてください。

  • 1 ¥le n ¥le 5000
  • 1 ¥le l_i,¥:w_i ¥le 10000

続きを読む

Connection: close