「UVa問題日本語意訳100～110」の編集履歴（バックアップ）一覧はこちら
「UVa問題日本語意訳100～110」(2013/03/18 (月) 17:48:45) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
UVa問題日本語意訳100～110
UVaオンラインジャッジの個人による非公式意訳です。
英語が出来ない人のために翻訳しております。
公式から抗議があった場合このページは即座に消す予定です。
抗議はこちらへお願いします。
sinapusu2002@yahoo.co.jp
----
*UVa 100 - The 3n + 1 problem
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=36
数字ｎに対して以下のような操作を繰りかえすと最終的に1になる。
nが２の倍数ならn=n/2
それ以外ならn=3n+1
である。
入力として範囲i,jが与えられる.
i<=n<=jの範囲のどれか一つでｎを始めた時、上記操作を繰り返して１になるまでの数列の長さはそれぞれ違うが、この中でもっとも長くなる場合の長さを答えよ。
j<=n<=iである場合もあるので注意せよ。
入力が
4 2
なら
n=2で始めた時数列は 2,1
n=3で始めた時数列は 3,10,5,16,8,4,2,1
n=4で始めた時数列は 4,2,1
で3から始めた場合の長さ8が答えとなるので
答えは入力で与えられた範囲4と２それと答えである8を合わせて
4 2 8を一行に出力せよ。
入力の終わりはＥＯＦで与えられる。
入出力の詳細は原文を参照すること。
----
*UVa 101 - The Blocks Problem
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=37
0からｎ-1までの地点にブロック一つずつが入っている。
初期状態では0の地点に0のラベルが貼られたブロックが、１の地点には１のラベルが張られたブロックが、、、ｎ-1の地点にはn-1のラベルの張られたブロックが入っている。
アームロボットがこれらのブロックを移動した。
ロボットに与えられた命令が与えられるので移動後のブロックの状態を出力せよという問題。
命令は以下の４種類である
ブロックは地点の上で垂直に積み上げていくものとする。
move a onto b
aのブロックがある山でaが出てくるまでブロックを取り除く。
取り除いたブロックはブロックのラベル番号と同じ地点に移動する。
ｂのブロックがある山でも同様の操作を行い。
その後aの上にｂをのせよ。
move a over b
現在bのブロックがある山の上にaを追加せよ。
aの地点があった場所はaが出てくるまでブロックを取り除き、取り除いたブロックはブロックのラベル番号と同じ地点に置くこと。
pile a over b
aとaの上に乗ってるブロック全てをｂのラベルの貼られたブロックのある山の上にのっけよ。
pile a onto b
ｂのブロックのある山でまずｂがでてくるまでブロックを上から順に取り除き、取り除いたブロックはブロックのラベル番号と同じ場所に置くこと。
後はaとaの上に乗っているブロックすべてをｂの上に乗っけよ。
入力は最初のｎは地点の数。
その後命令が与えられる。
命令の終わりはquitで与えられる。
出力は
地点番号: その地点に乗ってるブロックを下から表示。
、、、
として表示する。
詳しくは原文のサンプルデータを参照すること。
----
*UVa 102 - Ecological Bin Packing
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=38
一つのデータセットが一行で与えられる問題。
３つの箱に３色のビンが入っている。
第一の箱のデータは最初の３つの数字で青(B)、緑(G)、透明色(C)のビンの数。
第２の箱のデータは4個目から～6個目までの数字で青、緑、透明色のビンの数。
第３の箱のデータは7～9個目までの数字で青、緑、透明色のビンの数が与えられる。
一つのビンを手に取り別の箱に入れる作業を１回の操作と定義する。
どの箱も同じ色の瓶しか入ってないようにビンの入れ替え作業をした時最小の操作回数は何回になるか答えよ。
答えは一つ目、２つ目、３つ目の箱を何色のビンを集めることに決めたかのＢＧＣの組み合わせと、最小の操作回数を一行に出力せよ。
何通りか答えがあるならＢＧＣがアルファベット順になる物が優先される。
----
*UVa103 - Stacking Boxes
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=39
小さなボックスを大きなボックスの中にいれてその大きなボックスをより大きなボックスにいれていく作業を繰り返していく。
この時もっともたくさんボックスが入れ子になる入れ方をどれか一つ答えよ。
入力はボックスの数ｎと次元数ｄが最初の行に与えられる。
その後ボックスの各辺の長さがｎ行与えられる。
ボックスはｄ次元直方体として与えられる。
例えば次元数が３次元ならボックスの縦横高さの３つの長さが与えられる。
ボックス回転してもよいがどのボックスも必ず回転後、全ての辺がどれかの次元の軸と平行にならなくてはいけない。
例えば３次元ならどのへんもＸ軸、Ｙ軸、Ｚ軸のどれかと平行になる回転しか許されない。
入力例
4 2
5 3
2 4
6 6
1 9
なら
2 4の長方形を、5 3の長方形の中に入れ5 3 の長方形を6 6の中に入れればよいので答えは
3
2 1 3
となる。
これは２番目の箱を１番目の箱に入れ、１番目の箱を３番目の箱に入れて箱は３重入れ子になったということを表している。
答え候補が複数ある場合はどれを出力しても良い。
入れる場合箱の辺は必ず大きくなくてはいけない。
例えば入力データが以下のようなものなら
2 2
1 3
2 3
だと３と３が同じ長さであるために(2 3)の箱に入れることが出来ない点に注意が必要。
箱の数は最大30、次元は１０次元までとなる。
----
*UVa 104 - Arbitrage
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=40
通貨売買を行って利益を得る問題。
通貨の種類ｎ＜=20までと通貨の交換レートの表が与えられる。
表は同じ通貨同士の交換は歯抜けで与えられる。
同じ通貨同士の交換はレート1として仮定される。
通貨の交換レートが
1.0 0.8 1.2
0.9 1.0 0.8
1.3 1.2 1.0
なら表は対角線上の数字が消えた
3
0.8 1.2
0.9 0.8
1.3 1.2
が実際に与えられる表となる。
どれかの通貨から開始してレートに従って通貨を交換していき(手数料は取られないとする)最終的に最初の通貨に戻ったとき利益が1％以上になる交換手順を求めたい。
通貨の交換回数が最小かつｎ回以下の交換でこの条件を満たすものがあれば交換した通貨の順番を表示せよ。
条件を満たす答えが複数あるならどの答えを出力しても良い。
できない場合はno arbitrage sequence existsと１行に表示せよ。
通貨は交換表の上から1番、２番、、、ｎ番と設定されている。
答えは通貨の交換手順で表示する。
2 3 4 3 4 2
なら通貨2から初めて通貨３に交換し、それを４に交換し３に戻しまた４に交換し最終的に２に戻ってきたことをあらわす。
----
*UVa 105 - The Skyline Problem
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=41
平面上にｙ＝0を床としてその上に長方形がえがかれている。
一番ｘの値が小さい方から見ていきその地点での一番高い長方形の位置に変化があった場所を順番に出力せよ。
解説するよりも図をみた方が問題です。
1 5 11
というデータがあればｘ範囲1～11までの範囲に高さ5の長方形が置かれているとなります。
1 5 11
3 7 10
なら
1 5 3 7 10 5 11 0
と出力する。
これは1の地点で高さが５になり、３の地点で高さが7と変化し、10の地点で高さが5になり、11の地点で高さが0になったとします。
長方形は重なっても良いとします。
----
*106 - Fermat vs. Pythagoras
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=42
数字ｎが与えられるので。
x^2+y^2=z^2,z<=nをみたす原始ピタゴラス数の組の数と。
原始ピタゴラス数でないピタゴラス数も考えた時z<=nとなるピタゴラス数の組に出てこない数の個数を答えよ。
例えば
10
入力されたら
1 4と答える。
これは
z<=10となる原始ピタゴラス数は(3,4,5)の一種類だけなので1、原始でないピタゴラス数も考えると(6,8,10)。
z<=10以下のピタゴラス数の組ででて来る数は3,4,5,6,8,10
でてこない数は1,2,7,9の４種類なので答えが1 4となるわけである。
----
*107 - The Cat in the Hat
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=43
猫の帽子の中に小さなｒ匹の猫がいて、ｒ匹の猫それぞれの帽子の中にも同じくそれより小さなｒ匹の猫がいてこれが連鎖する。
猫の中の猫の関係はｒ分木となる。
この連鎖において一番奥の帽子にいる一番小さな猫のサイズは必ず１で終了する。
猫を帽子にいれている猫は、帽子の中の猫より必ずｒ+1倍大きいという規則がある。
一番大きな猫のサイズと、一番小さなサイズ１の猫の数が一行に与えられるので一番小さな猫以外の猫の数と全猫のサイズの合計を答えよ。
----
*108 - Maximum Sum
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=44
入力の一行目はｎでｎ*ｎのマス目が与えられる。
その後ｎ*ｎマスのマス目に入ってる数字が左上から順に与えられていく。
マス目を適当な長方形で囲み、長方形内の数字の合計が最も大きくなるように囲んだときの長方形内の合計値を答えよ。
*109 SCUD Busters
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=45
平面上に複数の国がありどの国内にも発電施設がある。
国は外壁で囲まれすべての施設を含む最小の長さの外壁で囲まれている。
外壁は太さ0で国と国は重ならない仮定してよい。
インプットデータは国の施設の数ｎが与えられ、その後その国施設の座標n個が整数で与えられてこれが複数回続く。
-1が施設データの入力の終わりを示す。
続いて降り注ぐミサイルの着弾座標が与えられる。
ミサイルが国内に降り注いだ国はどこに着弾しても停電してしまう。
外壁に降り注いだ場合も停電すると仮定してよい。
ミサイルの入力終了はＥＯＦとなる。
全ミサイル着弾後。
停電した国の面積の総計を小数点以下２桁までで答えよ。
*110 - Meta-Loopless Sorts
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=46
ｍ個の数字の変数を読み込み、小さい順にソートした結果を返すphytonプログラムを自動生成したい。
ただし生成されるコードで使っていい命令は
if,else if,else,readln,writelnそれと < (比較演算子)だけである。
使っていい変数はa,b,c,d,e,f,g,hだけとなる。
最初にデータセットの数ｎが与えられる。
そのあとにｎ個データセットが続く。
データセットの中身は変数の数1<=ｍ<=8一つだけであり一行ずつ与えられる。
ｍにあったohytonコードを生成するプログラムを書くこと。
答えの間には一行間隔を空けること。
m=3ならa,b,cに数字を順番に読み込み、
m=4ならa,b,c,dに数字を順番に読み込みソートできる処理を書くこと。
出力しなくてはいけないのはphytonコードとなる。
例えばインプットが
2
2
3
なら
答えの例
----
program sort(input,output);
var
a,b : integer;
begin
readln(a,b);
if a < b then
writeln(a,b)
else
writeln(b,a)
end.
program sort(input,output);
var
a,b,c : integer;
begin
readln(a,b,c);
if a < b then
if b < c then
writeln(a,b,c)
else if a < c then
writeln(a,c,b)
else
writeln(c,a,b)
else
if a < c then
writeln(b,a,c)
else if b < c then
writeln(b,c,a)
else
writeln(c,b,a)
end.
----
となる、答えはコードそのものである。
UVa問題日本語意訳100～110
UVaオンラインジャッジの個人による非公式意訳です。
英語が出来ない人のために翻訳しております。
公式から抗議があった場合このページは即座に消す予定です。
抗議はこちらへお願いします。
sinapusu2002@yahoo.co.jp
----
*UVa 100 - The 3n + 1 problem
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=36
数字ｎに対して以下のような操作を繰りかえすと最終的に1になる。
nが２の倍数ならn=n/2
それ以外ならn=3n+1
である。
入力として範囲i,jが与えられる.
i<=n<=jの範囲のどれか一つでｎを始めた時、上記操作を繰り返して１になるまでの数列の長さはそれぞれ違うが、この中でもっとも長くなる場合の長さを答えよ。
j<=n<=iである場合もあるので注意せよ。
入力が
4 2
なら
n=2で始めた時数列は 2,1
n=3で始めた時数列は 3,10,5,16,8,4,2,1
n=4で始めた時数列は 4,2,1
で3から始めた場合の長さ8が答えとなるので
答えは入力で与えられた範囲4と２それと答えである8を合わせて
4 2 8を一行に出力せよ。
入力の終わりはＥＯＦで与えられる。
入出力の詳細は原文を参照すること。
----
*UVa 101 - The Blocks Problem
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=37
0からｎ-1までの地点にブロック一つずつが入っている。
初期状態では0の地点に0のラベルが貼られたブロックが、１の地点には１のラベルが張られたブロックが、、、ｎ-1の地点にはn-1のラベルの張られたブロックが入っている。
アームロボットがこれらのブロックを移動した。
ロボットに与えられた命令が与えられるので移動後のブロックの状態を出力せよという問題。
命令は以下の４種類である
ブロックは地点の上で垂直に積み上げていくものとする。
move a onto b
aのブロックがある山でaが出てくるまでブロックを取り除く。
取り除いたブロックはブロックのラベル番号と同じ地点に移動する。
ｂのブロックがある山でも同様の操作を行い。
その後aの上にｂをのせよ。
move a over b
現在bのブロックがある山の上にaを追加せよ。
aの地点があった場所はaが出てくるまでブロックを取り除き、取り除いたブロックはブロックのラベル番号と同じ地点に置くこと。
pile a over b
aとaの上に乗ってるブロック全てをｂのラベルの貼られたブロックのある山の上にのっけよ。
pile a onto b
ｂのブロックのある山でまずｂがでてくるまでブロックを上から順に取り除き、取り除いたブロックはブロックのラベル番号と同じ場所に置くこと。
後はaとaの上に乗っているブロックすべてをｂの上に乗っけよ。
入力は最初のｎは地点の数。
その後命令が与えられる。
命令の終わりはquitで与えられる。
出力は
地点番号: その地点に乗ってるブロックを下から表示。
、、、
として表示する。
詳しくは原文のサンプルデータを参照すること。
----
*UVa 102 - Ecological Bin Packing
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=38
一つのデータセットが一行で与えられる問題。
３つの箱に３色のビンが入っている。
第一の箱のデータは最初の３つの数字で青(B)、緑(G)、透明色(C)のビンの数。
第２の箱のデータは4個目から～6個目までの数字で青、緑、透明色のビンの数。
第３の箱のデータは7～9個目までの数字で青、緑、透明色のビンの数が与えられる。
一つのビンを手に取り別の箱に入れる作業を１回の操作と定義する。
どの箱も同じ色の瓶しか入ってないようにビンの入れ替え作業をした時最小の操作回数は何回になるか答えよ。
答えは一つ目、２つ目、３つ目の箱を何色のビンを集めることに決めたかのＢＧＣの組み合わせと、最小の操作回数を一行に出力せよ。
何通りか答えがあるならＢＧＣがアルファベット順になる物が優先される。
----
*UVa103 - Stacking Boxes
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=39
小さなボックスを大きなボックスの中にいれてその大きなボックスをより大きなボックスにいれていく作業を繰り返していく。
この時もっともたくさんボックスが入れ子になる入れ方をどれか一つ答えよ。
入力はボックスの数ｎと次元数ｄが最初の行に与えられる。
その後ボックスの各辺の長さがｎ行与えられる。
ボックスはｄ次元直方体として与えられる。
例えば次元数が３次元ならボックスの縦横高さの３つの長さが与えられる。
ボックス回転してもよいがどのボックスも必ず回転後、全ての辺がどれかの次元の軸と平行にならなくてはいけない。
例えば３次元ならどのへんもＸ軸、Ｙ軸、Ｚ軸のどれかと平行になる回転しか許されない。
入力例
4 2
5 3
2 4
6 6
1 9
なら
2 4の長方形を、5 3の長方形の中に入れ5 3 の長方形を6 6の中に入れればよいので答えは
3
2 1 3
となる。
これは２番目の箱を１番目の箱に入れ、１番目の箱を３番目の箱に入れて箱は３重入れ子になったということを表している。
答え候補が複数ある場合はどれを出力しても良い。
入れる場合箱の辺は必ず大きくなくてはいけない。
例えば入力データが以下のようなものなら
2 2
1 3
2 3
だと３と３が同じ長さであるために(2 3)の箱に入れることが出来ない点に注意が必要。
箱の数は最大30、次元は１０次元までとなる。
----
*UVa 104 - Arbitrage
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=40
通貨売買を行って利益を得る問題。
通貨の種類ｎ＜=20までと通貨の交換レートの表が与えられる。
表は同じ通貨同士の交換は歯抜けで与えられる。
同じ通貨同士の交換はレート1として仮定される。
通貨の交換レートが
1.0 0.8 1.2
0.9 1.0 0.8
1.3 1.2 1.0
なら表は対角線上の数字が消えた
3
0.8 1.2
0.9 0.8
1.3 1.2
が実際に与えられる表となる。
どれかの通貨から開始してレートに従って通貨を交換していき(手数料は取られないとする)最終的に最初の通貨に戻ったとき利益が1％以上になる交換手順を求めたい。
通貨の交換回数が最小かつｎ回以下の交換でこの条件を満たすものがあれば交換した通貨の順番を表示せよ。
条件を満たす答えが複数あるならどの答えを出力しても良い。
できない場合はno arbitrage sequence existsと１行に表示せよ。
通貨は交換表の上から1番、２番、、、ｎ番と設定されている。
答えは通貨の交換手順で表示する。
2 3 4 3 4 2
なら通貨2から初めて通貨３に交換し、それを４に交換し３に戻しまた４に交換し最終的に２に戻ってきたことをあらわす。
----
*UVa 105 - The Skyline Problem
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=41
平面上にｙ＝0を床としてその上に長方形がえがかれている。
一番ｘの値が小さい方から見ていきその地点での一番高い長方形の位置に変化があった場所を順番に出力せよ。
解説するよりも図をみた方が問題です。
1 5 11
というデータがあればｘ範囲1～11までの範囲に高さ5の長方形が置かれているとなります。
1 5 11
3 7 10
なら
1 5 3 7 10 5 11 0
と出力する。
これは1の地点で高さが５になり、３の地点で高さが7と変化し、10の地点で高さが5になり、11の地点で高さが0になったとします。
長方形は重なっても良いとします。
----
*106 - Fermat vs. Pythagoras
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=42
数字ｎが与えられるので。
x^2+y^2=z^2,z<=nをみたす原始ピタゴラス数の組の数と。
原始ピタゴラス数でないピタゴラス数も考えた時z<=nとなるピタゴラス数の組に出てこない数の個数を答えよ。
例えば
10
入力されたら
1 4と答える。
これは
z<=10となる原始ピタゴラス数は(3,4,5)の一種類だけなので1、原始でないピタゴラス数も考えると(6,8,10)。
z<=10以下のピタゴラス数の組ででて来る数は3,4,5,6,8,10
でてこない数は1,2,7,9の４種類なので答えが1 4となるわけである。
----
*107 - The Cat in the Hat
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=43
猫の帽子の中に小さなｒ匹の猫がいて、ｒ匹の猫それぞれの帽子の中にも同じくそれより小さなｒ匹の猫がいてこれが連鎖する。
猫の中の猫の関係はｒ分木となる。
この連鎖において一番奥の帽子にいる一番小さな猫のサイズは必ず１で終了する。
猫を帽子にいれている猫は、帽子の中の猫より必ずｒ+1倍大きいという規則がある。
一番大きな猫のサイズと、一番小さなサイズ１の猫の数が一行に与えられるので一番小さな猫以外の猫の数と全猫のサイズの合計を答えよ。
----
*108 - Maximum Sum
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=44
入力の一行目はｎでｎ*ｎのマス目が与えられる。
その後ｎ*ｎマスのマス目に入ってる数字が左上から順に与えられていく。
マス目を適当な長方形で囲み、長方形内の数字の合計が最も大きくなるように囲んだときの長方形内の合計値を答えよ。
*109 SCUD Busters
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=3&page=show_problem&problem=45
平面上に複数の国がありどの国内にも発電施設がある。
国は外壁で囲まれすべての施設を含む最小の長さの外壁で囲まれている。
外壁は太さ0で国と国は重ならない仮定してよい。
インプットデータは国の施設の数ｎが与えられ、その後その国施設の座標n個が整数で与えられてこれが複数回続く。
-1が施設データの入力の終わりを示す。
続いて降り注ぐミサイルの着弾座標が与えられる。
ミサイルが国内に降り注いだ国はどこに着弾しても停電してしまう。
外壁に降り注いだ場合も停電すると仮定してよい。
ミサイルの入力終了はＥＯＦとなる。
全ミサイル着弾後。
停電した国の面積の総計を小数点以下２桁までで答えよ。
*110 - Meta-Loopless Sorts
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=46
ｍ個の数字の変数を読み込み、小さい順にソートした結果を返すphytonプログラムを自動生成したい。
ただし生成されるコードで使っていい命令は
if,else if,else,readln,writelnそれと < (比較演算子)だけである。
使っていい変数はa,b,c,d,e,f,g,hだけとなる。
最初にデータセットの数ｎが与えられる。
そのあとにｎ個データセットが続く。
データセットの中身は変数の数1<=ｍ<=8一つだけであり一行ずつ与えられる。
ｍにあったohytonコードを生成するプログラムを書くこと。
答えの間には一行間隔を空けること。
m=3ならa,b,cに数字を順番に読み込み、
m=4ならa,b,c,dに数字を順番に読み込みソートできる処理を書くこと。
出力しなくてはいけないのはphytonコードとなる。
例えばインプットが
2
2
3
なら
答えの例
----
program sort(input,output);
var
a,b : integer;
begin
readln(a,b);
if a < b then
writeln(a,b)
else
writeln(b,a)
end.
program sort(input,output);
var
a,b,c : integer;
begin
readln(a,b,c);
if a < b then
if b < c then
writeln(a,b,c)
else if a < c then
writeln(a,c,b)
else
writeln(c,a,b)
else
if a < c then
writeln(b,a,c)
else if b < c then
writeln(b,c,a)
else
writeln(c,b,a)
end.
----
となる、答えはコードそのものである。
