トップページ⇒tech
566コメント165KB

【頭脳試し】Imagine Cupアルゴリズム【ネタバレ】

■ このスレッドは過去ログ倉庫に格納されています
0001デフォルトの名無しさんNGNG
Imagine Cup アルゴリズム部門開催中!

30分で30問の質問に答える。学生のみ参加可能。
上位200名が第2ラウンドに進み、第2ラウンドの上位5名が世界大会進出。

締切は4月1日
賞金:1位 5,000ドル、2位 2,500ドル、3位1,000ドル

ここで出た質問の答えを話し合い、日本から上位を狙おう。
質問は英語で出るので、日本語訳も募集!英語の得意な人はどんどん訳してくれ。

Imagine Cup アルゴリズム部門
http://www.gotdotnet.com/japan/student/contest/ImagineCup2004/algorithm/default.as

px
Imagine Cup 参加登録方法
http://www.gotdotnet.com/japan/student/contest/ImagineCup2004/regist.aspx
Imagine Cup コンテストルール
http://www.gotdotnet.com/japan/student/contest/ImagineCup2004/contestrules.aspx

現在の上位200位
http://www.imaginecup.com/leaguetable.aspx
015315205/02/05 20:32:06
ひょっとして、素な素数のことか??
73939133(右から桁を落としていっても残りは素数)
357686312646216567629137(左から桁を落として素数)
とか??
015414905/02/05 20:54:57
>>152
多分237とか(23,37は素数)だと思うんだけど…
うーん、ごめん。その問題は飛ばしちゃったもんで記憶に少し残ってる程度だから、
間違ってるかもしれない。
0155デフォルトの名無しさん05/02/05 21:56:05
でもそれだったら23737373737…とかありだよなぁ。とふと思った。
ごめん、また同じ問題が出てきたら報告する。
0156デフォルトの名無しさん05/02/06 00:39:24
>>155
確かに、それだったら、111111111111111111(1が19個は素数)も
OKになるし何より、「一番大きい数」が無限大だから間違いだろう。
素な素数なら、73939133と357686312646216567629137が最大というのは、
確かに証明されていたような・・・
0157デフォルトの名無しさん05/02/06 01:06:21
素な素数の話でしょ,多分.

っていうか知識問題はやめて欲しいよ.
015813705/02/06 01:19:31
>>138
そっか。1×素数=素数だよな。ありがとう。
因数分解も考えようとしたんだけど因数分解できたら素数じゃないじゃないか!って考えて思考停止してた。
>>141のはやろうとしたけど大きな数字の時の証明ができないっぽいからやめた。

和訳に時間かかりすぎ・・・orz
0159デフォルトの名無しさん05/02/06 12:11:28
満点キター!
1 John Dethridge Australia 240 Melbourne University
日本勢も満点目指してがんばろう!
0160デフォルトの名無しさん05/02/06 15:55:12
A point(x,y) is an integer point if both x and y are integers. Given an
array of integer points, print any two point such that their mid-point is
an integer point. The mid-point may not belong to the input.
The best algorithm runs in

O(n^2)
O(n) with a storage of O(n)
O(constant) with a storage of O(n)
O(constant)
O(n) with no storage
------------
格子点の配列が与えられて、その中点も格子点であるならばそれを表示する。
そのような中点は入力には含まれていないとする。
効率的なアルゴリズムは次のオーダーで動く。
0161デフォルトの名無しさん05/02/06 16:05:08
>>160
普通にO(n^2)じゃないのか?
0162デフォルトの名無しさん05/02/06 16:23:12
anyって、出力する点はどれか一つでいいってことかな?
そうならO(constant)なんだけど。
0163デフォルトの名無しさん05/02/06 18:09:56
One of ten different furbies was randomly placed into each box of some type of cereal.
If a mother decided to buy this cereal for her children until she obtained at least one of each of the ten different furbies,
what is the number of boxes of cereal that she is expected to purchase?

12
17
19
20
30

------------
問題の意味がわからん・・・。へるぷみー
0164デフォルトの名無しさん05/02/06 18:12:42
If x^a=y, y^b=z, and z^c=x, then what is the value of abc?
> 0
> 1
> 2
> 3
> None of these
0165デフォルトの名無しさん05/02/06 18:14:29
Consider a forest of disjoint sets on which one is able to perform
typical "find" and "union" operations. If the sets contain a total of m
members, what best describes the worst-case time for a sequence of
s find and union operations?
> T(m)
> T(s)
> T(m log s)
> T(s log m)
> T(ms)
0166デフォルトの名無しさん05/02/06 18:19:13
Consider the equation: x^4 - 9(x^3) + 33(x^2) + 14x + 24 = 0
Which of the following is true?
> The equation has four real solutions.
> The equation has three real solutions and one imaginary solution.
> The equation has two real solutions and two imaginary solutions.
> The equation does not have any real solution.
> None of these
----------------------------------------
結局、普通にフェラーリの解法で、
2つの実数解と2つの虚数解を求めたんだけど、こんなもん時間内に解けるか!?
0167デフォルトの名無しさん05/02/06 18:40:01
2n sticks of different sizes are randomly divided into two subgroups
containing n stick each. What is the probability that the two biggest
sticks are in different groups?
> n/(2n-1)
> (n-1)/(2n-1)
> (2n-1)/4(n^2)
> None of these
> Can't be determined
----------------------------------------
サイズの異なる2nのスティックが、無作為にふたつのグループに分けられている
(それぞれnスティック)。最も大きい2つのスティックが違うグループに
分けられている可能性は?
----------------------------------------
0168デフォルトの名無しさん05/02/06 18:46:25
Two cars are 90 miles apart, and start driving towards each other.
One at a speed of 15 miles pr. Hour and the other at 25 miles pr.
Hour. At the same time a fly starts from the slower car, flying 40
miles an hour towards the faster car. At the moment when the fly
reaches the other car it turns around (instantly - no speed loss) and
flies back towards the first car. Every time the fly reaches a car it turns
around. By the time the cars drive into each other, the fly is crushed.
What is the distance the fly put back on his last journey?
> 90 miles
> 45 miles
> 60 miles
> 15 miles
0169デフォルトの名無しさん05/02/06 19:50:39
>>163
10の異なったfurbiesの1つは手当たりしだいに何人かのタイプの穀物の各箱の中に置かれました。
母が、彼女が少なくともそれぞれの10の異なったfurbiesの1つを得るまで彼女の子供のためにこの穀
物を買うと決めたなら、彼女が購入すると予想される穀物の箱の数はどのくらいですか?

exciteな翻訳でスマソ

>>164
1

>>167
(n-1)/(2n-1)

>>168
2台の車は90kmはなれている。片方は15km/hで、もう一方は25km/hで
お互いのほうに向かって走り出した。そのときに遅いほうの車から鳥が飛び立った。
鳥は40km/hで速いほうの車へ向かう。その鳥が車に到達した瞬間に反転する。
それを繰り返して2台の車がぶつかり、鳥は潰れた。それまでに鳥が飛んだ距離はいくらか?

90miles
0170デフォルトの名無しさん05/02/06 20:06:00
You are dealt these four cards from a deck of fifty-two playing cards: 3
4 5 and 6. What are the chances that one more card will give you a
pair (two of a kind) ?

1 out of 2
1 out of 3
2 out of 7
4 out of 13
None of above
0171デフォルトの名無しさん05/02/06 20:22:01
>>167はどうやってとくの?
017216405/02/06 20:27:20
>>169
なぜ1?
x=y=zだなんて、誰が決めた?
それなら、0でもいいじゃないか。x=y=z=0。
0173デフォルトの名無しさん05/02/06 20:39:23
>>163
-------------------------------
おまけにリカちゃん人形の入ったお菓子がある。リカちゃん人形は全部で10種類だ。
そこで、お前は、全種類コンプするぞと頑張るわけだ。
お前は、いったいどれだけのお菓子を買えば、全部集められると期待する?
---------------------
かな?確率も英訳も苦手だ。
017416905/02/06 20:41:32
>>167について
2番目に大きな棒が、もっとも大きい棒のグループに入る確率はn/(2n-1)だから

>>174
x^(abc) = y^(bc) = z^c = x
よってabc = 1
017517205/02/06 20:54:43
>>174納得した
017616905/02/06 21:12:00
ばんばん問題あげていこうや
というわけで


A certain town is server by two hospitals. In the large hospital, about
45 babies are born each day. In the smaller one, about 15 babies are
bone each day. Althought they overall proportion of girls is about 50%,
the actual propotion at either hospital may be greater or less on any
day. At the end of a year, which hospital will have the greater number
od days on which more than 60% of the babies born were girls?

the large hospital
the small hospital
neither -- the number of these days will be about the same
neither -- the number of these days will be exactly the same
------------
二つの市立病院があり、それぞれの病院で一日に生まれる赤ん坊は、
大きいほうはおよそ45人、小さいほうはおよそ15人である。
また、女の赤ん坊が生まれる割合はどちらも50%程度であるが、
その割合は日によって違う。
一年のうち、女の赤ん坊が生まれる割合が60%を超える日が多いのはどちらか?
017716305/02/06 22:15:23
>>173
>>169
ありがとう。これ答えでるのか?わからん・・・。
0178デフォルトの名無しさん05/02/06 22:26:19
>>176
50%じゃないの?
大きい方では、45人のうち、だいたい50%が女
小さい方は、15人のうち、だいたい50%が女
結局、どっちも60%を超えるのは、似たり寄ったりな確率では?
0179デフォルトの名無しさん05/02/06 22:56:38
>>176
極端にしてみる。
生まれても一人という田舎の病院と地球全体を比べる。
田舎の病院では60%を超えることなど頻繁だが、世界全体ではまずありえない。
よって小さい病院のほうが60%を超える日が多いだろう
0180デフォルトの名無しさん05/02/07 05:06:40
>>169
>>167 は逆じゃない?
同じグループに入る確率は(n-1)/(2n-1)だから、答は n/(2n-1)

>>163
期待値は 29.29 らしい。
tp://www.kjps.net/user/kakuritsu/omake2.html
0181デフォルトの名無しさん05/02/07 12:43:10
コテハンでわかね?
どんどん問題上げようぜ
0182デフォルトの名無しさん05/02/07 13:04:40
P and Q are two independent events. The probability that both P and Q occur is 1/6
and the probability that neither of them occurs is 1/3. What is the probability of P?

a 1/2
b 1/3
c 0
d 1
e Either a or b

===========
PとQは2つの独立した事象。PかつQの確率は1/6でPでもQでもない確率は1/3。
ではPの確率は?
0183デフォルトの名無しさん05/02/07 13:33:47
A student committee at a university consists of 2 students from the math department, 3 from the english department, and 4 from the history department.
The president of the university wants to reduce the committee size by 3 and chooses 3 committee members at random to remove.
What is the probability that the three chosen are all from different departments?
1/24
1/8
1/4
None of these
Can be determined
-----------------------------
-----------------------------
大学の学生委員会は数学部からの2人の学生、英語部からの3、および歴史部からの4から成ります。
大学の学長は、委員会のサイズを3つ減少させたくて、取り外すために無作為に3人の委員を選びます。
選ばれた3がすべて異なった部からあるという確率はどのくらいですか?
018416905/02/07 21:27:52
>>180
私が間違ってました。そうだと思います。

>>182
実際に試すと、Either a or b

>>183
2*3*4 / 9C3 = 2/7
よってNone of these
0185デフォルトの名無しさん05/02/07 22:22:22
A pirate ship capture a treasure of 1000 golden coins.The treasure
has to be split amoung the 5 pirates: 1,2,3,4,and 5 in order of rank.
The lowest ranking pirate (5) can make a proposal on how to split up
the treasure.This proposal can eather be accepter or the pirate is
thrown overboard. A proposal is accsepted if and only if a majority of
pitrate agrees on it. If 5 is thrown overboard, the next lowest ranking
pirate (4) can make a propoasal.
The pirate have the following important characteristics:(i) infinitely
smart; (ii) bloodthirsty; (iii) greedy.
What proposal should pirate 5 make?

999
997
500
499
199
------------
海賊は1000枚の金貨をみつけました。海賊は宝物を分けようとしました。
海賊は5人いて、順位は1,2,3,4,5と5段階あります。
最もランクの低い海賊(5)はどう宝を分割しようという提案をだせます。
提案は多数決で決まりますが、この提案が受け入れられなければ
その海賊は海へ投げられてしまいます。すると次は海賊(4)が提案をします。
海賊は以下の性質を持つ: (i)無限に賢い; (ii) 残忍である; (iii) 貪欲である。
海賊5はどんな提案をするべきですか?
0186デフォルトの名無しさん05/02/07 22:32:27
>>185
普通に199じゃないの?
0187デフォルトの名無しさん05/02/07 23:51:38
>>185
ステージが進んで残り2人という状況になると、
(2)が何を提案しても必ず(1)が反対して、提案は過半数を得られず、
1000枚を(1)が独占する。

よって、あと3人という状況で(2)はいかなる提案をも承諾せざるを得ず、
(3)は、「0:0:1000」という分割を提案し、過半数の賛成を得ることになる。

よって、あと4人という状況で(3)は必ず反対するが、(1)も(2)ともに$1でも
もらえるなら賛成してくれるので、
(4)は「1:1:0:998」と提案すれば過半数の賛成が得られる。

よって、あと5人という状況で(4)は必ず反対するが、
(3)は次のステージに行ったら$0しかもらえないので、$1で賛成。
(1)(2)は$2で賛成。
(5)は、自分と、(3)と、(1)(2)のうち一方を味方につければよいので、
「2:0:1:0:997」あるいは「0:2:1:0:997」という提案で過半数の賛成が得られる。
0188デフォルトの名無しさん05/02/08 00:02:23
なるへそ
0189デフォルトの名無しさん05/02/08 04:10:37
中国強いな。俺今問題集めてるんだが こういうやり方は微妙かね?
0190デフォルトの名無しさん05/02/08 06:53:14
>>189
あんまし役にたたないかもね。
おれの読みだと100点くらいが限界だと思うよ。
0191デフォルトの名無しさん05/02/08 08:09:04
>>190
そうかぁ。ただひたすら本番をといたほうがいいのか
0192デフォルトの名無しさん05/02/08 13:32:25
>>191
無駄という分けではないと思うけど。
ただ集めるだけじゃなくて、実際に解いてみたら実力がついていくとおもうふ
0193デフォルトの名無しさん05/02/08 20:31:30
200問程度、問題集めたんだが答えがわからぬ。
0194デフォルトの名無しさん05/02/08 21:27:09
Let (Z,*) be an algebraic structure, where Z is the set of integers and the operation * is defined by p*q = max (p,q).
Which of the following statements is true for (Z,*)?


(Z,*) is a monoid
(Z,*) is an non-abelian group
(Z,*) is a group
(Z,*) is an abelian group
None of these

----------------------------------------
----------------------------------------
代数構造であることをさせます(Z、*)。そこでは、Zが整数のセットであり、p*q=最大(p、q)によって操作*は定義されます。
(Z、*)に、以下の声明のどれが本当ですか?

エキサイトな翻訳ですまん
0195デフォルトの名無しさん05/02/08 22:43:57
>>194
(Z,*)をある代数系とする。ただし、Zは整数の集合で、演算子*は p*q=max(p,q)と定義される。
(Z,*)が真となるものは以下のどれか。

代数系なんて言葉今初めて知ったし、以下は調べながらやったからちょっと自信ない

a,b,c∈Z として
結合則 (a*b)*c = a*(b*c)
max(max(a,b),c) = max(a,max(b,c)) は成り立つ

aは Zの中の任意の数ってことにして・・・

単位元 (1) a*1=a, 1*a=a
Zの集合の中の最小の数をmとすると、
max(a,m)=a, max(m,a)=a だから、単位元は存在する
逆元 (b) a*b=1, b*a=1
Zの集合の中の最小の数mが単位元で max(a,b) とかやっていつもmがでる
ようなbはありえないから、逆元は存在しない

結合則を満たして単位元を持っているものは monoid
monoidでかつ逆元をもっているのが group
group でかつ交換則を満たすのが Abelian group

ってことで monoid だと思う


019616905/02/08 22:46:54
>>194
None of theseの予感。
工房の漏れに即答は不可能。
019716905/02/08 22:49:36
>>195
>Zの集合の中の最小の数をmとすると、
Zに最小値はありません
019819505/02/08 22:56:36
Zは無限だから最小値が定義できないってこと?
言われてみれば確かにそんな気がするorz

だとすると None of these になるのか・・・

0199デフォルトの名無しさん05/02/09 00:30:06
>>195
monoidは、モノイド。
gourpは、群。
Abelian groupは、可換群。
0200デフォルトの名無しさん05/02/09 08:00:59
>>194
難しいな。俺にも即答はできない。
0201デフォルトの名無しさん05/02/09 19:02:41
Which of the following is true for G if(G,0) is Known as abelian?

g = g^(-1) for every g∈G
g = g^2 for every g∈G
(goh)^(-2) = g^2 o h^2 for every g,h ∈G
G is of finite order.
None of these
0202デフォルトの名無しさん05/02/09 22:36:42
>>201
(goh)^(-2) = g^2 o h^2 for every g,h ∈G
だと思う。
0203デフォルトの名無しさん05/02/10 17:08:28
日本も地味に得点あがってきたな。
頑張ろうぜ
0204デフォルトの名無しさん05/02/10 19:18:22
オレの限界は100点くらいだと判明
0205デフォルトの名無しさん05/02/10 19:19:19
中国つええな
0206デフォルトの名無しさん05/02/10 19:57:17
↓のような問題は英語が苦手だと厳しい。For exampleが(無駄に?)多い。
Consider a war game in which each player controls an individual soldier unit on the battle field.
Each soldier's accuracy is measured by anumber in the range[2-12].when the soliderfires,
twoevenly weighted six-sided dice are rolled, and their individual results are added together.
If the total result isless than or equal to the solider's accuracy score, the shot hits the intended target.
For example, if asolider with an accuracy of 8 fires, arollof (2,4) will hit his target (2+4=6),
and a roll of(4,5) will miss(4+5=9).
In this context of game, a player with an accuracy rating of 6 is offerred the choice of two improvements to his solider.
The first improvement will subtract a fixed inteeger,n,from the result of every attack roll total.
For example,if n=1,the player would still hit his target with a roll of(4,3).
The second improvement will allow the player to roll three dice instead of two on every attack,
and choose only the lowest two dice to compute his attack roll total.
For example ,a solider with this improvement rolling(4,5,2) would have an attack roll total of 6.
For what values of n does the first improvement offer a greater benefit to the player than the second improvement .
0207デフォルトの名無しさん05/02/11 00:50:58
国内196点キター
9 Kazuhiro Inaba  Japan 196 The University of Tokyo
0208デフォルトの名無しさん05/02/11 04:08:51
さすが稲葉・・・
0209デフォルトの名無しさん05/02/11 07:58:03
東大の人、200弱 キタ――(゚∀゚)――!!
漏れも頑張らねば。
0210デフォルトの名無しさん05/02/11 20:40:23
今年のラインは190前後かなぁ。
0211デフォルトの名無しさん05/02/12 15:05:16
For values 0<x<1, only one function applied recursively shows chaotic behavior (does not converge or cycle). Which is it?

1/x
Cos(x) (x in radians)
Sin(x) (x in radians)
x^2-1
2(x^2)-1
021216905/02/12 18:28:19
>>211
2(x^2)-1
なお、cos(x)はcos(x)=xの解に、sin(x)は0に収束し、1/xとx^2-1は簡単な振動に向かう。
0213デフォルトの名無しさん05/02/14 22:31:03
Three numbers are selected at random without replacement from the set of numbers { 1, 2, ..., N}.
What is the conditional probability that the third number lies between the first two numbers
if the first number is known to be smaller than the second ?

1/6
1⁄3
1⁄2
None of these
Can be detertmined

---------------------------
---------------------------
3つの番号が数{1、2、…、N}のセットから交換なしで無作為に選択されます。
1番目の数が2番目より小さいのが知られているなら最初の2つの番号の間には、
3番目の数があるという条件付き確率はどのくらいですか?

条件付確率忘れてしまった。へるぷみー


021416905/02/14 23:23:20
>>213
条件付確率などではなく、a<bのとき
abc
cab
acb
の3通りが等しい確率なので1/3
0215デフォルトの名無しさん05/02/15 00:17:31
John is sitting in a stationary car. In the car there is a helium-filled
balloon, which is resting up against the cars ceiling somewhere near
the middle. John hits the pedal and the car accelerates forward. John
is thrown back into his seat and the balloon floats towards the front of
the car. What physical phenomenon would you attribute the balloon's
movement to?

Inertia
Buoyancy
Gravity
Frictional Force
None of these
------------
ジョンは静止した車の中に座っている。車の中にはヘリウムの風船があり、
天井の中心付近で漂っている。ジョンは急発進して前方に加速した。
ジョンはその勢いで座席の後ろに飛ばされ、風船は前方へ飛んでいった。
風船の移動にはどの物理現象がかかわっているでしょうか?
0216デフォルトの名無しさん05/02/15 00:24:47
濃度
0217デフォルトの名無しさん05/02/15 22:59:48
How many mixed-double tennis teams can be formed from seven married couples
if no husband and wife play on the same team?
210
420
840
None of these
Can be determined

7組の夫婦がいて、混合ダブルスのチームわけを混ぜて選ぶ。
夫婦でプレーしないのならどれだけチームを編成できるか?
0218デフォルトの名無しさん05/02/15 23:57:27
>>217
求めるのめんどくさい
None of theseだろ
13の倍数じゃないし
0219デフォルトの名無しさん05/02/16 00:05:45
>>217
普通に84じゃないのか?
0220デフォルトの名無しさん05/02/16 04:39:19
>>215
Buoyancy
>>217
javascript:alert((function(n){return n==1?0:n==2?1:(n-1)*(arguments.callee(n-1)+arguments.callee(n-2))})(7))
0221デフォルトの名無しさん05/02/16 20:11:14
>>217
再帰プログラムを組んでムリヤリ全通り求めたら
1854通りになったから
None of these
0222デフォルトの名無しさん05/02/16 20:42:07
Consider the following function:
F(x,y) = xyF(x-1,y-1), if x is even,
F(x,y) = [1/(x+1)^y]F(x-1,y-1), if x is odd,
F(0,y) = y, where x

8
42
24
2
None of these
0223デフォルトの名無しさん05/02/16 23:53:05
Consider an arithmetic progression that starts at zero. If the sum of this progression is the same for n as for m terms (where n ≠ m), then what will be the sum of (n + m) terms?
0
n+m
2n + m
1
None of these
0224デフォルトの名無しさん05/02/16 23:58:56
>>223
0
0225デフォルトの名無しさん05/02/17 00:01:44
Given a regular tetrahedron (6 equal edges, 4 faces, 4 vertices),
3 blind spiders and I smart bug. All spiders start from
the same vertex and follow a known (to all spiders and the bug)
algorithm. Spiders are slightly faster then the bug.
One can only travel on the edges.
Can the spiders always catch the bug?

No, because this reduces to NP complete problem.
No. There is no deterministic solution. It is not NP complete.
Yes, because it can be reduced to a simple loop with one spider
    chasing the bug and the spider is faster than the bug.
It is not possible to tell since we do not know how slow the
    bug is as compared to spiders.
Yes, if and only if the bug is along any edge that starts with
    the vertex from which spiders start.
0226デフォルトの名無しさん05/02/17 12:09:46
Eighteen guys are to manage two tasks, clearing the coffee cups and scrubbing the snack bar.
They put slips numbered 1 to18 in a hat and decide that anyone who draws a number divisible by 3 will be assigned the coffee cup task and anyone who draws a number divisible by 5 will be assigned to the snack bar cleaning.
The first person draws a 4, the second a 3, and the third a 11.
What is the probability that the fourth person to draw will be assigned to clearing the coffee cups?
1/5
1/6
1/3
2/15
4/18
0227デフォルトの名無しさん05/02/17 17:26:53
How many plates can be placed on a table where the diameter of the table is 15 times that of the plates? The plates can not overlap each other or the edge of the table.
187
225
200
150
None of these
0228デフォルトの名無しさん05/02/17 18:02:32
>>226
問)
18人のバイト君達は皿洗いと床掃除をしなければなりません。
彼らは1〜18の番号がついたクジ引きで仕事の担当を決めることにしました。
番号が3の倍数なら皿洗い、5の倍数なら床掃除です。(15引いたら最悪ですなワラ)
一人目は4,二人目は3,三人目は11を引きました。
このとき4人目が皿洗いの仕事をする羽目になる確率はいくらでしょう?

解)
残ってるクジは1,2,5,6,7,8,9,10,12,13,14,15,16,17,18の15枚。
そのうち3の倍数は6,9,12,15,18の5枚なので、当たる確率は
5/15=1/3
0229デフォルトの名無しさん05/02/17 18:47:59
>>227はどうやって解くんだ?
ご丁寧に計算したが時間がかかる
0230デフォルトの名無しさん05/02/17 21:39:28
中心が正三角形を作るようにして
面積で計算すると204ぐらいだから200だろうけど
実はNone of theseだったりとか
0231デフォルトの名無しさん05/02/18 01:08:41
>>229
お皿の直径を1として,テーブルの直径を15とする.
テーブルを水平方向に,1ずつ15分割して考える.
そうすると,テーブルの中心を通る水平方向の領域に,お皿を15枚おける.
その領域の上下2つの領域は,幅が14になる(と思う)ので,14*2で28枚おける.
これを同様に繰り返すと,
(1+2+3+ ... + 14) * 2 + 15となるので,
225が答え  かな?

023222905/02/18 01:50:54
答えは187だよ。ただ5分以上かかって本番じゃ解けない
023322905/02/18 02:00:35
解法は231のようにいちいち計算
ただ重ならないように230のような置き方で
という感じ
0234デフォルトの名無しさん05/02/18 12:01:37
231はまずいところあるのか?
0235デフォルトの名無しさん05/02/18 13:15:35
>>234
とりあえず225が答えになることはならないんじゃない?
あとはわからん
0236デフォルトの名無しさん05/02/18 13:32:31
>>234
> 231はまずいところあるのか?
直径15の円の面積はpi*(15/2)^2=pi*225/4
直径1 の円の面積はpi*(1/2)^2 =pi*1 /4
きっちり隙間なく置けたとして、225枚。
もちろんそんな芸当は絶対できっこないから>>230も言うように、225枚よりはずっと少ない。
0237デフォルトの名無しさん05/02/18 13:41:26
What is the maximum number of comparisons required to determine the median of an (unordered) set of 5 elements?
5
3
5!/2
6
5!

今年のボーターは180くらいかな?
0238デフォルトの名無しさん05/02/18 13:56:15
>>236
ネタ?
そんな芸当ができっこないからといって,それが答えにならないの?
理論値でいいんでない?
0239デフォルトの名無しさん05/02/18 14:23:29
>>238
冗談だろ。皿は円形だぜ。
0240デフォルトの名無しさん05/02/18 14:37:27
>>238
大丈夫。
理論的に考えて225枚は無理だから。
0241デフォルトの名無しさん05/02/18 14:43:52
>>238
ネタ?
不可能なものは「理論値」とは言わんよ
0242デフォルトの名無しさん05/02/18 14:47:35
>>239-241
>>238は英語が読めないに32bit。
0243デフォルトの名無しさん05/02/18 15:14:54
3人が6月の同じ日に生まれない確率は?
203/225
201/225
115/450
None of these
Can't be determined
0244デフォルトの名無しさん05/02/18 15:20:42
訳が間違ってるのかな
英文をのせておく

If three people are chosen at random then what is the probability
that no two of them were born on the same date of the month of June?
0245デフォルトの名無しさん05/02/18 18:29:26
Consider a hash table of size x containing y elements which uses
probing for collision resolution. What is the worst-case time required
to find an element?
T(y)
T(x)
T(y/x)
T(x/y)
T(x+y)

だれか問題文の意味教えてください。
0246デフォルトの名無しさん05/02/18 19:27:17
You are dealt these four cards from a deck of fifty-two playing cards:
3 4 5 and 6. What are the chances that one more card will give you a
pair (two of a kind)?

1 out of 2.
1 out of 3
2 out of 7
4 out of 13
none of the above
0247デフォルトの名無しさん05/02/18 19:29:53
>>245
衝突回避をしながら、y個の配列をx種類のハッシュテーブルで管理する。
検索のさいにかかる最悪の時間は?
T(y)

訳はできんが説明は出来る。
仮にy個全部おんなじハッシュになるとする。
すると衝突しまくって最悪でy回の回避処理が必要になる。
なのでT(y)
0248デフォルトの名無しさん05/02/18 19:57:46
To find out the biggest number and the smallest number in 1024
unsorted numbers, what is the minimum number of comparisons
required in worst case?
1024
1280
1536
1792
2048
0249デフォルトの名無しさん05/02/18 20:03:14
>>247
y個の要素を持った大きさxのハッシュテーブルじゃないか?
同じことであるならすまん。説明がよくわからなくて混乱してしまった
0250デフォルトの名無しさん05/02/18 20:09:46
俺32歳の学生なんだが参加していいのか?
0251デフォルトの名無しさん05/02/18 20:21:14
>>250
ttp://www.microsoft.com/japan/msdn/student/imaginecup/2005/rules/
0252デフォルトの名無しさん05/02/18 20:27:18
f:X→Y
Xのサイズがx
Yのサイズがy

でいいの?
■ このスレッドは過去ログ倉庫に格納されています