UVa/VolumeC7
Last-modified: 2008-05-23 (金) 11:19:33
VolumeC7
- 10701:Pre, in and post
- Tree
- http://acm.uva.es/p/v107/10701.html
木のpre-orderとin-orderのリストが与えられて
post-orderで出力しろ。
pre-orderはroot-left-right、
in-orderはleft-root-right、
post-orderはleft-right-rootなので、
このまま再起関数を作る。
- 10705:The Fun Number System
- AdHoc?
- 入力されたNを普通に2進展開する.
次に、下の桁から走査してnegabitのビットを探す.
ネガビットを見つけたら、
それよりひとつ上の桁に1を足す.
繰上げも普通に処理.
ひとつ上の桁がネガビットかポジビットかは気にしない.
これを最後まで繰り返す.
途中で与えられた桁数を超えたらImpossible.
- 10706:Number Sequence
- Mathematics?
- 数列を一般化.結構めんどい.
- 10714:Ants
- Simulation?
- DPっぽいけど、そうじゃなくてめちゃ簡単.
アリが一番長くいられるのは、単純に、
一番端にいるアリが内側に向かって歩いていき、他のアリに可能な限り当たるとき.
- 10717:Mint
- Mathematics?
- 色々考えそうだけど、結局割り切れるかどうか調べるだけ.
- 10718:Bit Mask
- Mathematics?
- 最上位ビットからUを超えないように、かつ、Lに届かなくならないようにビットを立てていく.
ただし、Nのビットが立っているところは立てる必要はない.
問題文の``print in a line the minimum value of M''に注意.
- 10719:Quotient Polynomial
- Mathematics?
- kが分かってるから逆算していけばいい.
- 10759:Dice Throwing
- Mathematics? + Dynamic Programming?
- n個のサイコロを投げたとき、それらの上面に出てきた値の合計が少なくともxになる確率を求める. 少なくともxなので、xに満たない場合の数を求める.
多倍長っぽいけど、データは全てunsigned long long型に収まる.
Dynamic Programmingの要領で、1個のサイコロを投げたとき、2個のサイコロを投げたとき、と繰り返していけば速くなる.
- 10761:Broken Keyboard
- String?
- キーボードの壊れた部分の文字と、文章が与えられて、「完全に入力出来る行」と「壊れても良いキーボード」を出力する.
壊れても良いキーボードとは、文章中に出てこない文字である.
言われた通りにやれば良いが、Stringだけに面倒.
- 10719:Quotient Polynomial
- AdHoc?
- 交換留学生のデータが与えられて、そのような交換が全て可能かを調べる問題.
ある留学生がAからBへと留学したいとすると、BからAへと留学したい別の留学生がいれば交換が上手くいく.
データをコピーして同じものを二つ作り、それを昇順と降順にソートして、二つが一致するか調べるだけ.