2011-10-24から1日間の記事一覧

POJ 3720 Occurrence of Digits

問題 1/2 = .5, 1/3 = .(3), 1/4 = .25 ,...1/nと書いていったとき、 小数部分に数字kは何回現れるか求めよ。 制約条件 n≦100 k≦10

POJ 3456 Frobenius

問題 正の整数a,b,c,dに対するFrobenius数とは、w,x,y,z≧0に対してwa+xb+yc+zdとして表すことのできない最大の数である。1000000以下の、wa+xb+yc+zdとして表せない数の個数および、Frebonius数を求めよ。 Frebonius数が1000000より大きい場合-1を出力せよ。…

POJ 3421 X-factor Chains

問題 整数Xに対してX-factor chainとは次を満たす列のことを言う。 1 = X0 < X1 < …… < Xm = X; かつXi+1はXiで割りきれる。 正の整数Xが与えられたとき、このような列のうち最大の長さをもつものおよび、 そのような長さを持つ列の数を出力せよ。 制約条件 …

POJ 3414 Pots

問題 容量AリットルとBリットルの二つの容器がある。 以下の操作を繰り返してどちらかの容器に入っている水の量をCリットルする。 最短手順の操作をどれか一つ出力せよ。 不可能な場合impossibleを出力せよ。 Aの容器を満タンにする Bの容器を満タンにする A…

POJ 3411 Paid Roads

問題 n個の都市がある。 1番の都市からn番の都市へ行きたい。 道路がm本あり、それぞれの道路は都市a[i]とb[i]を結んでいる。 道路を通るには交通料がかかり、 都市c[i]を事前に訪れている場合P[i]、そうでない場合R[i]のコストがかかる。 n番の都市へ行くの…

POJ 3407 Brookebond s'en va en guerre...

問題 地球上の二点が緯度と経度により指定される。 その二点間の、地表での距離を1メートルの精度で求めよ。 ただし地球は半径6370kmの真球と仮定せよ。 制約条件 なし

POJ 3404 Bridge over a rough river

問題 N人が橋を渡りたい。 橋は同時に2人までしか渡ることができず、また一つしかない懐中電灯を持って渡る必要がある。 それぞれの人に対して橋を渡るのにかかる時間が決まっている。 二人が同時に渡るときは遅い人に合わせる。 全員が橋を渡り終えるのにか…

POJ 3400 Dropping the stones

問題 2つのどぶにN個の石を投げる。 それぞれの石には重さp[i]および価値v[i]が定まっており、 次の条件を満たすように好きな順にどぶに投げ入れる。 最初に投げるのはAのどぶへ 二つのどぶに入っている石の重さの差がDを超えたら投げ入れるどぶを換える こ…