PKU

PKU 2897 Dramatic Multiplications

問題 ある数がn-dramaticであるとは、 n倍したときに10進法での最下位の数字が、最上位に巡回シフトされるような数を言う。最下位がkであるようなn-dramaticな数のうち最小であるものを求めよ。 制約条件 n, k≦9

PKU 3213 PM 3

問題 行列A, B, Cが与えられる。 A x B = Cになっているかどうかを検算せよ。 なっている場合はYes, そうでない場合はNoと、 Cの間違っている成分の行、列およびその成分の正しい値を出力せよ。 Cの成分は高々一つしか間違っていない。 制約条件 Aの行数, A…

PKU 3092 Non-divisible 2-3 Power Sums

問題 与えられた数nを、 n=Σ2^ni 3^miの形の和で表せ。 ただし、任意の互いに異なるi, jについて2^ni 3^miは2^nj 3^mjを割り切ってはならない。 制約条件 n<2^31

PKU 3640 Conformity

PKU

問題 n人の人の時間割が与えられる。 時間割は5つの授業の番号により与えられる。 同じ時間割(順序を入れ替えても同じとみなす)の人数が最大である時間割 (複数ある場合は全て)を選んだ人数を求めよ。 制約条件 n≦10000 時間割番号は100以上499以下

PKU 3646 The Dragon of Loowater

問題 二つの数列a[i]およびb[i]が与えられる。 b[i]から数列c[i]を選び(一つの項は高々一回までしか選ぶことができない)、 すべてのiについてa[i]≦c[i]となるようにしたい。 このときΣc[i]の最小値を求めよ。 制約条件 n≦20000

PKU 3639 Exchange Rates

問題 明日からn日間の米ドルとカナダドルのレートがわかっている。 取引には、3%の手数料がかかり、更に1セント未満は切り捨てられる。 今1000カナダドルを持っているとき、n日後、最大カナダドルをいくらに出来るか、求めよ。 制約条件 n≦365

PKU 2323 PERMS

問題 1〜nの順列のうち、転置がちょうどk個あるようなものはいくつあるか、求めよ。 制約条件 n≦18

PKU 2288 Islands and Bridges

問題 n頂点からなる無向グラフが与えられる。 頂点にはそれぞれ値x[i]がついている。 このグラフのハミルトンパス(全ての頂点を1度ずつ通るパス)のうち、 次のスコアを最大にするパスのスコアおよび、総数を出力せよ。 ハミルトンパスが存在しないときは0 …

PKU 1042 Gone Fishing

問題 n個の湖でhの制限時間内で釣りをする。 最初、1番の湖から出発する。 i番目の湖からはi+1番目の湖に行くか、その湖で釣りを終了するかしかできない。 i番目の湖からi+1番目の湖へはt[i]の時間がかかる。 i番目の湖では最初の1単位時間ではf[i]の魚が取…

PKU 1077 Eight

問題 8-パズルの初期盤面が与えられる。 これが解けるならその手順を、そうでないならunsolvableを出力せよ。

PKU 1065 Wooden Sticks

問題 n本の木の棒があり、それぞれの太さはw[i], 長さはl[i]である。 この木の棒を好きな順番で機械に入れていく。 最初の一本を入れるときには1のコストがかかる。 前の棒が(w[i], l[i])であるとき、次の棒(w'[i], l'[i])が w[i]≦w'[i]かつl[i]≦l'[i]ならば…

PKU 1019 Number Sequence

問題 11212312341234512345612345671234567812345678912345678910123456789101112345678910... と続く数列がある。この数列のi番目の数字を求めよ。 制約条件 i≦2147483647

POJ 2480 Longge's problem

問題 整数Nに対してΣ[i=1,N]gcd(i,N)を求めよ。 制約条件 N<2^31

POJ 1150 The Last Non-zero Digit

問題 nPmの、末尾の0を全て取り除いた時の下1桁を求めよ。 制約条件 n,m≦20000000

POJ 2085 Inversion

問題 1〜nを並べ替えた数列のうち、 転置がちょうどm個あるもので、辞書順最小のものを求めよ。 制約条件 n≦50000 m≦n(n-1)/2

POJ 2063 Investment

問題 d個の金融商品があり、それぞれの値段および年間の利益が与えられる。 それぞれの商品の金額は固定であるが、同じ種類の商品をいくつも買うことができる。 capの資産を持っている人がn年資産運用するとき、 最大でいくらまで資産を増やせるか求めよ。 …

POJ 2062 Card Game Cheater

問題 二人のプレイヤーがk枚のカードを一列に向かい合うようにして並べる。 向かい合ったそれぞれのカードについて、大きいほうに1点が入る。 相手のカードとその並べ方がわかっているとき、獲得できる点数の最大値を求めよ。 制約条件 k≦26

POJ 3003 Spiderman’s workout

問題 n個の上り下りの記録が与えられる。 それぞれの数字は上り下りの距離であるが、その方向はわからない。 最初は0mの高さにいて、全ての上り下りを終えた時点でも0mの高さにいる。 上り下りの途中で高さが0mを下回ることはない。 この条件を満たす上で、…

POJ 3001 Gallup

問題 何人からアンケートを取って、 それぞれの項目の割合を、小数点k桁未満を四捨五入して算出した。 アンケートの元の人数としてありえるもののうち、最小のものを答えよ。 1以上9999以下に答えがない場合errorを出力せよ。 制約条件 小数点は最大5桁まで

POJ 3310 Caterpillar

問題 無向グラフが与えられる。 グラフがキャタピラであるかを判定せよ。 ただしグラフがキャタピラであるとは、 グラフ上にあるパスが存在し、グラフの任意の点からのそのパスへの最短距離が1以下であることを言う。 制約条件 グラフの頂点数≦100 グラフの…

POJ 3311 Hie with the Pie

問題 n+1頂点からなるグラフが、距離行列の形で与えられる。 0番の頂点を出発し、全ての頂点を一度以上通り、0番の頂点へ戻ってくるのに必要な移動距離の最小値を求めよ。 制約条件 n≦10

POJ 3312 Mahershalalhashbaz, Nebuchadnezzar, and Billy Bob Benjamin Go to the Regionals

問題 n人の人をk人ずつチームにわける。 各チームにおいて、 「チームの全員の名前の長さの平均」と任意の人の名前の長さの差が2を超えてはいけない。 このとき、チーム分けが可能であるかどうか、判定せよ。 制約条件 n≦1000 kはnの約数 各人の名前は80文字…

POJ 3385 Genealogy

問題 宇宙人は、1人の子に対して親が最大d人までいる。 親子関係がツリーとして与えられるが、一部が欠けていて、親がd人より多くなっている宇宙人がいる。ツリーに適当に宇宙人を挿入し、1人の子の親がd人以下にしたい。 挿入しなければならない宇宙人の最…

POJ 3020 Antenna Placement

問題 hxwのグリッドがあり、各マスはアンテナ'*'および何もない'o'のいずれかである。 縦または横に隣り合う二つ(一つだけでもかまわない)のアンテナを丸で囲む。 全てのアンテナを囲むのに必要な丸の数を求めよ。 制約条件 h≦40 w≦10

POJ 3368 Frequent values

問題 単調非減少な数列A[i]が与えられる。 m個のクエリが与えられるのでそれに答えよ。クエリ: 二つの整数l,rが与えられる。Aのl番目〜r番目の項のうち、最も出現回数が多い数字の出現回数はいくつか。 制約条件 -100000≦A[i]≦100000 m≦100000 数列の項≦100…

POJ 3367 Expressions

問題 アルファベットの小文字であらわされる数値および、アルファベットの大文字であらわされる演算子からなる式が与えられる。ただし式は後置記法になっていて、 abOは、 スタックにaを積む スタックにbを積む スタックからa,bを取り出し、スタックにb O a…

POJ 3367 Evacuation

写経してただけなのにWAが出続けてイミフだった。 自分の2部グラフの最大マッチングがバグっているのだろうか。 問題 XxYマスの部屋がある。 それぞれのマスは、床'.',壁'X',ドア'D'のいずれかであり、 ドアは部屋の内部にはない。 最初それぞれの床には一人…

POJ 3359 Wordfish

問題 文字列が与えられる。 文字列の順列のうち、与えられた文字列の次の10個および前の10個に対して、 隣り合う文字間の距離の最小値が最大のもの、およびその値を求めよ。 ただし文字aと文字b間の距離とはabs((int)a-(int)b)を意味する。

POJ 3357 Oreon

問題 無向グラフが与えられるので、その最小全域木を求めよ。 同じコストの最小全域木が複数あるときは、 アルファベット順で最も最初にくるものを求めよ。 制約条件 頂点数≦26

POJ 3338 Rectangle Cutting

問題 hxwの長方形のケーキに対して、n個の長方形の切れ目を入れる。 それぞれの切れ目はx1,y1,x2,y2によって指定される。 全ての切れ目を入れ終えた後、ケーキはいくつの部分に分割されているか求めよ。 制約条件 h,w≦20 n≦50 座標およびh,wは全て整数