【頭脳試し】Imagine Cupアルゴリズム【ﾈﾀﾊﾞﾚ】

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

出される質問は以下の分野のもの。
アルゴリズム分析
幾何学
確率と統計
帰納 (再帰)
離散数学
集合論
代数
組み合わせ理論
頭の体操問題
有限オートマトン

サンプル問題A (実際の問題は英語で出題される)

次のアルゴリズムの実行時間計算量は以下のうちのいずれか?
For X = 1 to N
For Y = 1 to X
/* ここに計算式を入れる */
Next Y
Next X

a) O(N) b) O(log N) c) O(N log N) d) O(N2) e) O(√N)

サンプル問題B

次の帰納関数定義があるとする。
fun f(a, 0) = 1 | f(a, n) = a * f(a, n-1)

f(3,4) は以下のうちのいずれか?
a) 0 b) 12 c) 27 d) 64 e) 81

サンプル問題C

箱が 2 つあります。1 つ目の箱には立方体が 8 つと球体が
6 つ入っていて、2 つ目の箱には立方体が 6 つと球体が 12 個
入っています。1 つ目の箱からランダムに物体を 1 つ選んで
2 つ目の箱に移します。2 つ目の箱から選ばれた物体が立方体で
ある確率はいくらになりますか?

a) 7/19 b) 46/133 c) 67/133 d) 156/133 e) 1/2

サンプル問題D

あるクラスに 30 人の男子生徒がいて、野球、ホッケー、
フットボールのいずれか 1 つあるいはそれらのうちの
いくつかをしているとします。野球しかしない生徒が 3 人、
ホッケーしかしない生徒が 3 人、フットボールしかしない
生徒が 2 人います。3 つともする生徒は 4 人います。
フットボールと野球をする生徒は 11 人、フットボールと
ホッケーをする生徒は 10 人います。
野球とホッケーはするがフットボールはしない生徒は何人ですか?

a) 1 b) 2 c) 3 d) 5 e) 8

サンプル問題E

ある列車の車両には、5 人掛けの座席 2 列が向かい合わせに
並んでいる。4 人が進行方向に向いて座ることを望んでおり、
3 人が進行方向とは反対に向いて座ることを望んでいる。
その他の人たちはどちらでもよいと思っている。乗客 10 人が
自分の好みに合わせて座る方法は何種類あるか？

a) 120 b) 720 c) 14400 d) 43200 e) 86400

サンプル問題F

2 台の列車が、20 マイル離れて同じ線路上を互いの方向に向かって
走っている。各列車は時速 10 マイルで走っている。時速 15 マイル
で飛ぶハエが 1 台の列車の前からもう 1 台の列車へ向かって飛ぶ
ことにする。ハエは向かいの列車に到着するとすぐさま振り返って
最初の列車に戻る。ハエは、間に挟まれるまで列車の間を行ったり
きたり飛び続けるものとする。最後までにハエが飛ぶ距離は
何マイルか？

a) 10 b) 15 c) 20 d) 25 e) 30

現在の上位ランキングされている人の国
1位：フランス
2位：インド
3位：インド
4位：中国
5位：中国
6位：アメリカ
7位：中国
8位：中国
9位：アメリカ
10位：ブルガリア

日本人は100位にも入っていないぞ。

実際の問題1

Suppose that the ratio between the work done by (x - 1)
people in (x + 1) days to the work done by (x + 2) people
in (x - 1) days is 9:10. What is x?

7
8
9
10
11
------------
(x - 1) 人が (x + 1) 日間行った仕事量と、(x + 2) 人が
(x - 1) 日間に行った仕事量の比率が 9:10 のとき、x は何？

実際の問題2

Mrs. James works in a book store. She has been assigned
the task of rearranging all information technology books
on a particular shelf in proper order at the end of each
day. What would be her best choice for a sorting algorithm?

Bubble Sort
Insertion Sort
Selection Sort
Heapsort
None of these
-------------
ジェームス婦人は書店で働いている。彼女は毎日終業時まで、
特定の本棚のIT関連の本を適切な順番に並びかえる仕事を
している。下記のうち、どのアルゴリズムを使って並びか
えるのが最適か？

実際の問題3

20 passengers are to travel on a train which can accommodate
13 in the upper berth and 7 in the lower deck. How many ways
can they be assigned berths if 5 refuse to be booked in the
upper berth and 8 refuse to be booked in the lower berth?

25
21
18
15
None of these
--------------
20人の乗客が乗っている寝台列車がある。上の寝台が13、
下の寝台が7つ空いている。しかし、20人のうち5人は
上の寝台に寝るのが嫌で、8人は下の寝台が嫌な場合、
希望の寝台を割り振ると何通りの組み合わせがあるか。

実際の問題4

Two squares are chosen at random on an 8 x 8 chessboard.
What is the probability that they have a side in common?

1/9
2/7
1/18
5/7
None of these

--------
8 x 8 のチェス版上で、ランダムに2つの四角を選んだとする。
その2つの四角が隣り合わせになる確率は？

実際の問題5

If my professor likes the number pair 1198911 and 1168611,
which of the following number pairs does he also like?

1689 and 6891
19 and 91
190 and 160
1981 and 1891
None of the above
------------
うちの教授は 1198911 と 1168611 の数字の組み合わせが好きだ。
以下の中で彼が好きだと思われる組み合わせは？

俺は解けません

挑戦した人は、問題を上げてくれ。訳はあってもなくても構わない。
解答方法がわかった人もどんどん書き込んでくれ。

変なところで改行されてしまったが、これが正しい。

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

何か、この問題、センス悪くね？

問題1の答え
この文章を計算式に置き換えると、
(x - 1) * (x + 1) * 10 = (x + 2) * (x - 1) * 9
これをまとめると、
x�A - 9x + 8 = 0 (�Aは2乗のこと)
となり、
x = -1 または x = 8　となる。
x は負の数にはなりえないので、答えは x = 8

問題２の答え

proper order の説明なし。
本の冊数の指定無し（数が少ない場合、Bubble や Insert の方が速かったりする）。
”本屋”という物理的な条件も考慮するべきか否かの記述無し。

これだけの条件で回答が出せるか。ヴォケ

問題2の答え

バブルソートは隣同士の比較を順に行い、それを繰り返す。
挿入ソート(Insertion sort)は、最初のものから順番に、本来あるべき位置に挿入していく。
選択ソート(Selection sort)は、一番小さいものから順に並べていく。
ヒープソートは、2分木構造を使用したソート。

日常生活じゃ選択ソートだろ。本の冊数が分からなくても、バブルやヒープは
使わない。挿入は、本来あるべきところが分からないと並べられない。

すまん。
良く考えたら、挿入ソートが正解かも。
本屋や図書館は、本来その本を置く位置が決まってるから、
挿入ソートになる。

問題３の答え

マンドクセ。誰かやれ。

学生じゃなくても登録して挑戦できるぞ

問題４の答え

配置できる組み合わせ→ (8*8)*(8*8-1)=4032
隣り合う組み合わせ=枡の間の罫線の本数→ (8*7)*2=112
枡を選ぶ組み合わせ→ 2

2*112/4032=1/18

問題５の答え

２ｃｈ向けのネタだな。

問題４
((2*7+1)*7+7)/(64*63/2)=1/18
かな？

実際の問題6

John travels to Gotham everyday for his work. His wife picks him up at the train
station each evening at exactly 6 PM. One day, he left work early, and arrived at
the train station at 5 PM. He started walking home, but he met his wife en route
to the station and got into the car. They drove home and arrived 10 minutes
earlier than usual. How long did the man have to walk before he was picked up
by his wife?

55 minutes
45 minutes
35 minutes
25 minutes
57 minutes
-----------------
まさしは日暮里に毎日出勤している。かわいい奥さんは毎日午後6時きっかりに駅に
迎えに行く。ある日、まさしは仕事が早く終わり、5時に駅についてしまった。家に向かって
歩き始めたが、途中で迎えに来た奥さんにばったり会って車に乗って戻り、家に着いた
時間はいつもより10分早かった。まさしは、奥さんに会うまで何分歩いたか。

実際の問題7

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
-------------------
お皿をテーブルの上に並べるとする。テーブルの直径はお皿の直径の15倍。
何枚のお皿を並べられるか？ お皿は重ねられないし、テーブルのふちにも置けない。
たぶん、テーブルもお皿もまん丸なんだろうな。

>>28
>家に着いた時間はいつもより10分早かった。

？？？

いつもより１時間も早く駅に着いたのに、
実際に家にたどり着いた時間はたった１０分しか
縮まらなかったの？

>>30
家から駅まで遠いんじゃない?
少なくとも、駅から家まで徒歩60分以上かかると見た。

実際の問題8

Let S be the set of strings defined by the regular expression (abb*c)* .
Which of the following regular expressions defines a set of strings
which is a subset of S?

a*b*c*
(a*b*c*)*
(aabb*cc)*
(aabb*c)*
None of the above
---------------
Sは正規表現 (abb*c)* という文字列だ。下記のうち、Sのサブセットとして
定義される正規表現の文字列は？

実際の問題9

From a pack of 52 cards with 4 suits, cards are drawn until a king appears.
What is the probability that a king is not drawn in first 26 cards?

46 / 153
23 / 27
109 / 153
1/2
None of these
---------
52枚組のトランプを良くきって、キングが出るまで引いていくとする。最初の26枚を
引いた段階でキングが出ない確率は？

※ 4suit は、スペード、ハート、ダイヤ、クラブのことなので、普通のババなしの
52枚組トランプと思われ。

実際の問題10

20 prisoners escape from jail. Each day after that,
half of those that are free are recaptured. How
many are still free at the end of the second day?

9
10
5
0
15
----------
20人の (　´∀｀) が逃げ出した。次の日から毎日半分の
(　´∀｀) を捕まえたとして、2日めが終わっても捕まって
いない (　´∀｀) は何人？

実際の問題11

What is the next number of the following
sequence: 1, 3, 4, 9, 10, 12, 13,...?

14
23
27
28
25
--------------
1, 3, 4, 9, 10, 12, 13 の次に来る数は？

【緊急】ネット投票の協力
CNNのネット投票に協力してください。
今回の台湾総統選挙は公正と思いますか
ぜひ台湾に「Yes」を
http://www.cnn.com/2004/WORLD/asiapcf/03/20/taiwan.elections/index.html
QUICKVOTE
Was Taiwan's presidential vote fair?
Yes ●
No
宋楚瑜氏が先程、このネット投票の結果を利用して、選挙無効を群衆に訴えて
います。宋氏に悪用されないようにしましょう。
「台湾の声」編集長 林建良（りんけんりょう）拜

問題10は簡単に見えるけど、ほんとに簡単なの？
ウラある？

>>35って「任意の解が認められる」問題の典型だよな。
アルゴリズムの出題としてありなのか？

34は単純なひっかけが目的だったらツマランなあ。

>>38
ワケワカメなんでググったよ
ttp://rec-puzzles.org/sol.pl/series/25 (ネタバレ注意)
何がしたいのかよくわからん・・・パズルと言われればそれまでだけど。

問題６、マジでわからんのですが・・・

実際の問題12

60 students take tests in French and Astrology. 40 pass in French
and 30 in Astrology. If X is the number of students who pass in both
subjects then what is the range of possible values of X ?

10 ≦ X ≦ 30
X = 10
X ≧ 10
X < 60
30 ≦ X ≦ 40
-------------
60人の生徒が英語と保健体育のテストを受けている。40人が英語の
テストに受かり、30人が保健体育のテストに受かった。Xは英語と
保健体育の両方に受かった人数とすると、Xのとりうる範囲は？

実際の問題13

A box contains 2 green, 3 red and 4 yellow marbles. If after each
selection the marble is replaced, what is the probability of drawing
a green, a red and then a yellow marble (in order)?

8/243
4/27
8/247
1/729
Can't be determined
----------
箱の中に緑玉2個、赤玉3個、黄玉4個が入っている。そこから玉を抜き取っていった
とき、緑、赤、黄色の順で取り出す確率は？

4月1日までなら何度でも挑戦可。最後の点数が、その人の点となる。

採点方法は、問題の難易度にEasy, Medium, Hardの3種類があり、
Easy正解で4点、不正解で-1点、Medium正解で8点、不正解で-2点、
Hard正解で12点、不正解で-3点。問題をスキップすれば、加点も
減点もされない。

今のトップは240点中225点。今なら、100点取ればベスト200に入れるぞ。

2の答え
選択ソートか、挿入ソート

3の答え
7C2 = 21

なんか、ただの算数の問題のような気がする。

問題6
55分

正規表現のサブセットって何?

問題6
35分ってなった。

>>46
ほんと?55分で結構自信あるけど。

>>47
計算間違えてた。

駅から家までの距離 x (km)
奥さんの移動速度 A (km/h)
まさしの移動速度 B (km/h)
家からまさしと奥さんのあった場所までの距離 y (km)

奥さんとまさしが会った時刻 6 - x/A + y/A = 5 + (x-y)/B
(x-y)/A + (x-y)/B = 1

いつもより10分早く家についた (6 + x/A) - (5 + (x-y)/B + y/A) = 1/6
(x-y)/B - (x-y)/A = 5/6

(x-y)/B - (1 - (x-y)/B) = 5/6
2*(x-y)/B = 11/6
(x-y)/B = 11/12

11/6のところの11が汚くて7と読み間違えてたみたいだった。

実際の問題14

In a certain factory, there are 100 workers who have 3 commuting
options: their own vehicle, company bus, and public transport.
50 workers use the company bus, 70 use their own vehicle, and
60 use the public transport. 10 workers use only the company bus
or their own vehicle and avoid the public transport. 5 workers
do not have their own vehicle and hence use the other two only,
while 25 workers do not live on the route of the company bus and
hence use either the public transport or their own vehicle.
20 workers use all forms of transportation. How many workers
commute by own vehicle?

12
3
4
11
15
------------
キゴ工場では、100人が3つの方法で通っている。自家用車、会社のバス、
公共の乗り物の3種類だ。50人が会社のバスを使用し、70人が自家用車を
使い、60人が公共の乗り物で通っている。10人は会社のバスか自家用車
しか使わず、公共の乗り物には乗らない。5人は自家用車を持っていなくて
その他の2種類の方法を使用する。25人は会社のバスルートの近くに住んで
いないため公共の乗り物か自家用車を使っている。20人がすべての方法を
使用している。さて、自家用車だけで通っている人は何人？

実際の問題15

An insurance company has written 2 fire insurance policies of
$50,000, 4 of $25,000, and 9 of $10,000. If the probability of
a fire is 1/1000 per year, how much can the company expect
to pay during the first year of the policies?

$85
$290
$1275
0
None of these
-----
ある保険会社は50000ドルの火災保険を2件、25000ドルの火災保険を4件、
10000ドルの火災保険9件を請け負っている。もし火災が起きる確率が1年に
1/1000だったとすると、保険会社は最初の1年に払わなければならない
期待値はいくらか？

ここまでのまとめ

実際の問題01 - 回答済
実際の問題02 - 回答済
実際の問題03 - 。｡･ﾟ･(ﾉД`)･ﾟ･｡
実際の問題04 - 回答済
実際の問題05 - 。｡･ﾟ･(ﾉД`)･ﾟ･｡
実際の問題06 - 回答済
実際の問題07 - 。｡･ﾟ･(ﾉД`)･ﾟ･｡
実際の問題08 - 。｡･ﾟ･(ﾉД`)･ﾟ･｡
実際の問題09 - 。｡･ﾟ･(ﾉД`)･ﾟ･｡
実際の問題10 - 。｡･ﾟ･(ﾉД`)･ﾟ･｡
実際の問題11 - 。｡･ﾟ･(ﾉД`)･ﾟ･｡
実際の問題12 - 。｡･ﾟ･(ﾉД`)･ﾟ･｡
実際の問題13 - 。｡･ﾟ･(ﾉД`)･ﾟ･｡
実際の問題14 - 。｡･ﾟ･(ﾉД`)･ﾟ･｡
実際の問題15 - 。｡･ﾟ･(ﾉД`)･ﾟ･｡

11は回答でてるだろ

問題14やってみたけど分からない

問題9の答え

１枚めでキングを引かない確率は48/52。
２枚めでキングを引かない確率は47/51。
３枚めでキングを引かない確率は46/50。
……
26枚めでキングを引かない確率は23/27。

ということは、
48x47x46x ... 23 26x25x24x23 46
---------------- = ----------- = -----
52x51x50x ... 27 52x51x50x49 833

ずれた。鬱。
48x47x46x ... 23
---------------- ＝
52x51x50x ... 27

26x25x24x23
----------- ＝
52x51x50x49

46
---
833

もっとおもしろい問題欲しい。
算数レベルじゃねーかよ。
日本人がランクインしてなくてよかった気もする。

>>48
いつもより10分だけ早い -> 片道5分早い -> 5:55についた ->
まさしは55分歩いた

問題14意味がわからん。

50人がバスを使っていて残りの50人はバスを使えない。
25人はバスを使えない。
この25は役に立つ情報なのか?

70 use their own vehicle.
How many workers commute by own vehicle?
答えは70じゃないのか?

今のところ、111点取れば入賞するみたい。
日本人も入ってきたぞ。締め切りまであと10日くらいだから、
目標は150点かな。

>>58
use と commute が持つニュアンスに違いがあるのかな…
commute には「だけ」って意味も含まれるのかもしれん…そうじゃないと問題にならんし。
これはネイティブに聞かんとわからん。
49さんの訳には「だけ」って入ってる。

>>60
useとcommuteにはそれほど違いはないみたい。文脈をみると、
最初の50人、70人、60人はその乗り物を使うことがある人の
数で、その後の10人、5人、25人は2種類の乗り物を使う人、
最後の20人が3種類とも使ってる人だから、答えは意外に簡単。

問題3

21じゃない？

20人中
　上に乗りたい奴（下が嫌な奴）→8人　残りの上の寝台→5
　下に乗りたい奴（上が嫌な奴）→5人　残りの下の寝台→2
　どっちでもいい奴　　　　　　　 →7人

この7人の割り振り方は、７*6/2=21

ひょっとして既出？　

むしろ数学版のほうがいいような気がする。

問題5の解答
1689 and 6891

>>63
なるほど。さかさにするのね。

65 名前： デフォルトの名無しさん ： 投稿日： 04/03/25 (木) 14:19
問題8。
*は直前の正規表現の0回以上の繰り返しでいいのかな？
Sの部分集合になるような文字列集合を定義してる正規表現は
ないんじゃない？

66 名前： デフォルトの名無しさん ： 投稿日： 04/03/25 (木) 14:23
どうやってさんかすんの？

67 名前： デフォルトの名無しさん ：sage 投稿日： 04/03/25 (木) 14:25
SWくらいの難易度かな

68 名前： デフォルトの名無しさん ： 投稿日： 04/03/25 (木) 14:41
>>41 問題12
普通にX=10だよね？

69 名前： 68 ：sage 投稿日： 04/03/25 (木) 15:02
あ、ほんとは時間制限があるのか。
回答する問題の選別が点数を左右するね。

70 名前： デフォルトの名無しさん ： 投稿日： 04/03/25 (木) 15:55
英語の数式で出てくる★はどういう意味ですか？

71 名前： デフォルトの名無しさん ：sage 投稿日： 04/03/25 (木) 16:26
>>68
おぬしあほか。10 <= x <= 40だろ。

72 名前： デフォルトの名無しさん ：sage 投稿日： 04/03/25 (木) 16:27
10 <= x <= 30でした。

73 名前： デフォルトの名無しさん ：sage 投稿日： 04/03/25 (木) 16:28
>>65
ですよね。選択肢の正規表現はどれもaaにマッチしちゃうからね。

74 名前： 68 ： 投稿日： 04/03/25 (木) 20:19
>>72
しまった、まちがいた！
そうですな、うううう・・・訂正さんくすです。

75 名前： デフォルトの名無しさん ： 投稿日： 04/03/25 (木) 20:52
これ世界大会に行けるの世界で５人だけ？

ジョーカーを除いたトランプ５２枚の中から１枚のカードを抜き出し、
表を見ないで箱の中にしまった。
そして、残りのカードをよく切ってから３枚抜き出したところ、
３枚ともダイアであった。
このとき、箱の中のカードがダイヤである確率はいくらか。

76 名前：デフォルトの名無しさん[] 投稿日：04/03/25 22:55
more than って≦、＜のどっち？

77 名前：デフォルトの名無しさん[sage] 投稿日：04/03/26 00:11
>>76
<じゃないかな。

78 名前：デフォルトの名無しさん[] 投稿日：04/03/26 01:07
実際の問題16
A bag contains 5 brown and 4 white socks. A man pulls
out two socks. What is the probability that they are
the same color?

5/108
1/6
5/18
4/9
None of these
------
かばんの中に5足の茶色い靴下と4足の白い靴下が入っている。
この中から2つの靴下を取り出したとき、それらが同じ色である確率は？

79 名前：デフォルトの名無しさん[] 投稿日：04/03/26 01:11

実際の問題17

There are 25 stations on a railroad line. At each of
the 25 stations the passengers can get tickets for
any of the other 24 stations. How many different kinds
of tickets do you think have to be printed?

600
500
450
460
650
----------
ある電車の路線上に25の駅がある。25駅ともその他の24駅行きの
切符を買うことができる。印刷された切符の種類は何種類？
※ 行き先の駅名が書かれている切符なんだろうな。


80 名前：デフォルトの名無しさん[] 投稿日：04/03/26 01:18
実際の問題18
Which of the following is not true?

The set of rational numbers is an abelian group under addition.
The set of rational integers is an abelian group under addition.
The set of rational numbers form an abelian group under multiplication.
The set of rational integers form an abelian group under multiplication.
None of these
-------------
どれがウソ？

81 名前：デフォルトの名無しさん[sage] 投稿日：04/03/26 01:20
何回か挑戦してると、同じ問題がちらほら出てくる。
全体の問題数は意外に少ないかも。

ちなみに3回チャレンジして、同じ問題が4問あった。
全体の問題数は何問くらいと予想できる？

82 名前：デフォルトの名無しさん[sage] 投稿日：04/03/26 01:26
>>66
Imagine Cupのページに行って登録してチームを作ったあと、
アルゴリズムのページに行ってサインインすると左上に
Take the algorithm quiz!
というリンクが表示されるから、それをクリック。

登録方法：
http://www.gotdotnet.com/japan/student/contest/ImagineCup2004/regist.aspx

アルゴリズム部門のページ：
http://www.imaginecup.com/algorithm.aspx

83 名前：デフォルトの名無しさん[] 投稿日：04/03/26 09:03
問題うｐしたいけど、２乗とか３乗とかついてる式はどうすればいいの？

84 名前：デフォルトの名無しさん[] 投稿日：04/03/26 09:08
(x^2) (x^3) でも x**2 x**3 でも pow(x,2)でも

85 名前：hoge ◆WGlV2Dh//2 [sage] 投稿日：04/03/26 11:27
>>80
まず、アーベル郡からググらなければならなかった。

>The set of rational numbers is an abelian group under addition.
>The set of rational integers is an abelian group under addition.

これは、trueですよね。

答えは、None of theseだと思います。

でも、
>The set of rational numbers form an abelian group under multiplication.
も気になるな。

86 名前：デフォルトの名無しさん[sage] 投稿日：04/03/26 11:55
>>79
切符を買った駅と、行き先の駅との組み合わせが、何通りあるかってことですか？　切符を買う駅を含めないのだから、
25 * 24 == 600
だと思います。

>>78
えーと、
(5C2 + 4C2) / 9C2 == (10 + 6) / 36 == 2 / 9

それともこうだっけ？
(5P2 + 4P2) / 9P2 == (20 + 12) / 72 == 4 / 9

答えは、4 / 9

>>50

( 50000 * 2 + 25000 * 4 + 10000 * 9) * (1 / 1000) == 290000 / 1000 == 290

答えは、$290

>>67
(13-3)/(52-3)
=10/49

//スレの趣旨と微妙に違う問題のような気もするが・・・

とりあえず、英語が正確に日本語化できないい。
しかも、問題の答えをセットするのとか反応が遅くて
時間がもったいない

ついに全問正解者現る。
http://www.imaginecup.com/leaguetable.aspx
まけちゃおられん。どしどし問題と答をあげてくれ。

実際の問題19
How many squares can be formed on an 8 x 8 chessboard?

64
160
224
204
None of these
-----------
8 x 8 のチェス版の中に正方形をいくつ作ることができる？

実際の問題20
A daughter, a Mom, and a grandmother were asked about
their ages. Mom answered "our ages are prime numbers
in which i) the average of ANY TWO of the numbers is
a prime and ii) the average of all three of the numbers
is a prime." What were their ages?

11,29,61
11,47,71
7,29,71
13,37,79
none of the above
-------------
娘、母、祖母がいて、年齢を聞いてみた。母の答えは、
「私たちの年齢は素数よ。しかも、どの2人の年齢の平均を
とっても素数になるし、3人の年齢の平均も素数だわ」
彼女らの年齢は？

実際の問題21
A and B are two different sets of real numbers,
A = {a, b, c} and B= {e, f}. What is A × B ?

{(a, c), (a, b), (a, e), (a, f), (b, e), (b, f)}
{(a, f), (b, e), (b, f), (a, b), (a, e), (c, f)}
{(e, a), (e, b), (e, c), (f, a), (f, b), (f, c)}
{(e, a), (f, a), (e, b), (f, b), (e, c), (f, c)}
{(a, e), (a, f), (b, e), (b, f), (c, e), (c, f)}
-------
AとBは違った数の真の数である。
A = {a, b, c} で B= {e, f} のとき A × B は？

実際の問題22
A large tank with volume V is full of milk. Nine gallons
are drawn from the tank and it is then filled with water.
Again, nine gallons of liquid are drawn from the tank and
it is again filled up with water. If the ratio of milk to

water is 16/9 at this stage, what is the value of V?

18 gallons
45 gallons
27 gallons
5 gallons
None of these
--------
でかいタンクに牛乳が満タン入っている。9リットルをタンクから
抜き出し、その分、水で薄める。さらに、そこから9リットル取り
出して、その分、水で薄める。もし、そのときのミルクと水の
割合が16:9だとすると、このタンクの容量は？

実際の問題23
Say f(x) = x/(x +1) and g(x) = 2/x. What is (f o g)(x),
where o is the composite mapping operator?

2 / (2 + x)
2 / (x + 1)
(x + 1) / 2
(x + 2) / x
2x / (1 + 2x)
---------　
f(x) = x/(x + 1) かつ g(x) = 2/x だとする。(f o g)(x)
という式がある場合、"o" はどれに該当する？

実際の問題24
How many triangles can be formed by choosing the vertices
from a set of 10 points, 4 of which lie on the same
straight line?

116
120
180
117
115
----------
10個の点があるとする。そのうち3点を結んで三角形を作るとすると、
いくつ作れる？ただし、そのうち4つの点は、同じ直線上にあるものとする。

※ ガロンはリットルに変えちゃいました。ちなみに1ガロン＝3.785リットル。

>>78
real numbers => 実数
>>80
o が合成演算子であるとき、(f o g)(x) はなんぼ？

>>83
thanks

締め切りまであと1日。しかし、時差があるから4月2日になっても
しばらくは挑戦できるはず。
まだ日本人が一人も入ってないぞ。みんな頑張れ！
俺も頑張って問題を訳すぞ。

実際の問題25
If repetition of digits is not allowed, what is the sum of
all the five-digit numbers that can be formed using the

digits 5, 4, 2, 3 and 1?

360000
66660
366000
180000
3999960
------------
5、4、3、2、1の5つの数字で作成される5桁の数値を全部足すと
いくつになる? ただし、5桁の中に同じ数字は使わないものとする。

実際の問題26
Which grammar will generate {(ab)^n | n ≧ 1} ∪ {(ba)^n | n ≧ 1}?

S→S1,S1→abS1,S1→ab,S→S2,S2→baS2,S2→ba
S→S1,S1→aS1,S1→ab,S→S2,S2→bS2,S2→bc
S→S1,S1→S2,S2→S1a,S1→ab,S2→ba
None of these
Can't be determined
---------
どの文法が {(ab)^n | n ≧ 1} ∪ {(ba)^n | n ≧ 1} を作成する?

実際の問題26
Bill threw a party and borrowed 100 glasses from his
friend. He sent his son John to pick up the glasses
from his friend's place. Just to give an extra incentive,
he offered John 3 cents for every glass brought safely
and told him he would deduct 9 cents for every glass he
broke. After John returned, Bill gave him $2.40. How
many glasses did John break ?

10
2
8
6
5
---------
ビルはパーティで友達から100個のグラスを借りた。ビルは息子
のジョンに友達のところからグラスを持って来させた。そのとき
の約束として、もしグラスを安全に持って来れたらグラス1個
あたり3万円あげて、もし壊してしまったら9万円取り上げる約束
をした。ジョンが戻ってきたとき、ビルはジョンに240万円払った。
さて、何個のグラスを壊したでしょう?

間違えた。27だ...
実際の問題27
Bill threw a party and borrowed 100 glasses from his
friend. He sent his son John to pick up the glasses
from his friend's place. Just to give an extra incentive,
he offered John 3 cents for every glass brought safely
and told him he would deduct 9 cents for every glass he
broke. After John returned, Bill gave him $2.40. How
many glasses did John break ?

10
2
8
6
5
---------
ビルはパーティで友達から100個のグラスを借りた。ビルは息子
のジョンに友達のところからグラスを持って来させた。そのとき
の約束として、もしグラスを安全に持って来れたらグラス1個
あたり3万円あげて、もし壊してしまったら9万円取り上げる約束
をした。ジョンが戻ってきたとき、ビルはジョンに240万円払った。
さて、何個のグラスを壊したでしょう?

>>89
5個

実際の問題28
In an election for the class leader, half the number of
students voted for Janet and two-thirds voted for Mary.
10 voted for both and 6 did not vote for either.
How many students were there in all?

60
24
36
18
None of these
-------
学級委員を決めるのに、半分の生徒がジャネットに、2/3の生徒が
メリーに投票した。10人は両方に投票し、6人はどちらにも投票
しなかった。何人の生徒がいる？
※ 昨日のThe Student Dayで複数のチームに投票した人っている?

実際の問題29
Which of the following statements is true?

An acyclic graph is a directed graph with no cycles.
An acyclic graph is a weighted graph with cycles.
An acyclic graph is a directed graph with cycles.
An acyclic graph is neither wieghted nor directed.
None of the above.
------------
どれがホント？

実際の問題30
John and Jack play a game where each is asked to select
a number from 1 to 30. If the two numbers match, both of

them win a prize. What is the probability that they will
not win a prize in a single trial?

1/30
29/30
1/15
None of these
Can't be determined
---------
ジョンとジャックは、それぞえれ1から30までの数の中から1つ
選ぶゲームをしている。もし二人が選んだ数字が同じなら勝ち。
1回の挑戦で勝つ確率は?

実際の問題31
What is the next term of the following sequence: 1, 4, 3, 16, 15, 12, 13,...?

14
4
11
64
25
---------
1, 4, 3, 16, 15, 12, 13, に続く数は？

実際の問題32
In a family there are several children. Each boy has
as many sisters as brothers but each girl has twice
as many brothers as sisters. How many brothers and
sisters are in that family?

3 brothers, 4 sisters
2 brothers, 2 sisters
4 brothers, 3 sisters
3 brothers, 5 sisters
None of these
----------
ある家族は子沢山だ(こざわやまじゃねーぞ)。男の子たちには
兄弟(男限定ね)と同じ数の姉妹がいて、女の子たちには姉妹の
人数の倍の兄弟がいる。この家族の中の男の子と女の子の数は?

実際の問題33
In a local soccer league, this year's participation
increased 10% over last year. The number of men
increased by 5% and the number of women increased
by 20%. What is the ratio of female participation
to total participation?

1/3
4/11
2/5
4/9
1/2
------
あるサッカーリーグがあり、そこへの参加者は昨年より10%
増えている。男性は5%増えていて、女性は20%増えている。
全体のうち、女性の割合は？

とある情報筋によれば、時差の関係で4月2日まるまるいっぱい
挑戦できるそうだ。

問題30の答
これは簡単。1/30

問題33の答
昨年の男の数をX、女の数をYとすると、
(X + Y) * 1.1 = X * 1.05 + Y * 1.2
1.1X + 1.1Y = 1.05X + 1.2Y
0.05X = 0.1Y
X : Y = 1 : 2
答は1/3

問題32の答
4 brothers, 3 sisters
男から見ると兄弟3人、姉妹3人。
女から見ると兄弟4人、姉妹2人。

まだ日本人ランクインしない....
http://www.imaginecup.com/leaguetable.aspx
中国人半分超えた....

今、解けてない問題ある？

まとめますた。答があってるかどうかは知らぬ。

実際の問題01 - 回答済 8
実際の問題02 - 回答済 挿入ソート
実際の問題03 - 回答済 21
実際の問題04 - 回答済 1/18
実際の問題05 - 回答済 1689 and 6891
実際の問題06 - 回答済 55分
実際の問題07 - 。｡･ﾟ･(ﾉД`)･ﾟ･｡
実際の問題08 - 。｡･ﾟ･(ﾉД`)･ﾟ･｡
実際の問題09 - 回答済 46/833
実際の問題10 - 。｡･ﾟ･(ﾉД`)･ﾟ･｡
実際の問題11 - 回答済 27
実際の問題12 - 回答済 10
実際の問題13 - 。｡･ﾟ･(ﾉД`)･ﾟ･｡
実際の問題14 - 。｡･ﾟ･(ﾉД`)･ﾟ･｡
実際の問題15 - 回答済 $290
実際の問題16 - 回答済 4/9
実際の問題17 - 回答済 600
実際の問題18 - 。｡･ﾟ･(ﾉД`)･ﾟ･｡
実際の問題19 - 。｡･ﾟ･(ﾉД`)･ﾟ･｡
実際の問題20 - 。｡･ﾟ･(ﾉД`)･ﾟ･｡

実際の問題21 - 。｡･ﾟ･(ﾉД`)･ﾟ･｡
実際の問題22 - 。｡･ﾟ･(ﾉД`)･ﾟ･｡
実際の問題23 - 回答済 None of these
実際の問題24 - 。｡･ﾟ･(ﾉД`)･ﾟ･｡
実際の問題25 - 。｡･ﾟ･(ﾉД`)･ﾟ･｡
実際の問題26 - 。｡･ﾟ･(ﾉД`)･ﾟ･｡
実際の問題27 - 回答済 5
実際の問題28 - 。｡･ﾟ･(ﾉД`)･ﾟ･｡
実際の問題29 - 。｡･ﾟ･(ﾉД`)･ﾟ･｡
実際の問題30 - 回答済 1/30
実際の問題31 - 。｡･ﾟ･(ﾉД`)･ﾟ･｡
実際の問題32 - 回答済 4 brothers, 3 sisters
実際の問題33 - 回答済 1/3

>>91
(x/2)+(2x/3)-10+6=xから

x=24か？

>>77
実際計算してみると

答え　11,47,71

実際の問題20 - 回答済 11,47,71
実際の問題28 - 回答済 24

>>49
問題になるのは自家用車を使ってる人だから

x+35+20=70より

x=15

問題25の答
15 * (4! * 10000 + 3! * 4 * 1000 + 2! * 12 * 100+ 1! * 24 * 10 + 1! * 24 * 1) = 3999960

ぬ？漏れ3/31が締め切りなんだとてっきり勘違いしていた。
でも本当は4/1が締め切りで、日本は時差のおかげで
4/2くらいまでいけちゃうんだよね

ﾔｯﾃﾓｳﾀ orz

終わっちゃったね。
結局日本人はダメだったぽ。

今年のはいつからだっけ？再利用

VisualGamingSDK落としました。

詳細
Adnan G.El Shukrijumahは、現在アメリカに対するテロリスト脅威の１人です。

報酬
アメリカ国務省は、Adnan G.El Shukrijumahの
捕獲に直接結びつく情報には上限500万ドルの報酬を提供します。

http://www.fbi.gov/terrorinfo/adnan.htm

もう始まった？

マダダヨ
アルゴリズムは2/1から

はやく始まらないかなぁ
ﾜｸﾜｸ

始まったぞ！

やってみたけど英語の壁の厚さを感じた orz

ていうか何処から入れるの？

登録はしたけど
コンテストへの入り方が分からない。

これさ、一体どこでやってるの？

登録したら、
http://www.thespoke.net にアクセスして、右上のボタンからログイン
右下の、暗い青の背景で空手をやってる絵をクリック
//TEAM & EVENT TOOLS をクリック

これでImagineCupの入り口に入れる。

しまった。h抜き忘れた。
一応、こちらで

ttp://www.thespoke.net

群とかわかんねー．．．
文章題は多少きついね
専門用語はわかりやすいけど

結果はどこにでんの？

>>125

//TEAM & EVENT TOOLS をクリックしていける画面の
Algorithm のところの View Leaderboard で順位がわかる

あと、チャレンジしてから24時間後に、点数を教えてくれるメールが届く

これって自分でプログラム作って使ってもいいの？

これって、何回でも挑戦可能？？

>>128
何回でもできるけど
最後に挑戦したスコアが最終スコアになる
だから普通は前回のスコアを知るまで再挑戦はしないわけで
問題解いてからスコアが分かるまで24時間かかる
だから実際10から20回くらい挑戦できるのかな？

>>93の
問題３０なんだけど、
これって勝つ確率でいいの？
負ける確率と思って答えてたんだが

>>130
負ける確率でしょ？

>>128
純粋に経験値を貯めて点数アップを図りたければ、1日に何回でもチャレンジしていいと
思う。ただ、届くメールが1時間に1回で、MSから送られてから届くまでの順番が
その1時間の中でぐちゃぐちゃになっちゃうから、チャレンジの間隔が1時間未満だと
届くメールに書かれている点数がどのチャレンジの結果なのかわからなくなる恐れがある。

>>131
あ、やっぱそれでいいのか
上の方で正解は1/30って書いてあったから・・・
にしても、去年と同じ問題もでるのね。

3回やってみたけど、問題の数少なすぎ。
何回も同じのが出るよ。
ここで問題を公開していくとネラーが上位入賞の悪感

海外のblogerがとっくに全問公開してそうな悪寒

今年の一次通過点は幾らくらいになるんだろう。
去年の問題と同じ物が出てたりするところを見ると点数インフレが起こりそうな予感。

わかんねー・・・

n^3-8(n^2)+20n-13
が素数になるようなnの数はいくつか

どうやってやるんだろ

>>137
因数分解すると
(n-1)(n^2-7n+13)=0
これが素数になるためには、
n-1=1 または n^2-7n+13=1
でなければならない。前者の条件(n=2)の場合、n^2-7n+13=3になるのでこれは解。
後者の条件の場合、二次方程式の解はn=3,4。両方ともn-1が素数になるので、
解はn=2,3,4。

>>137
n=3

因数分解した式の=0いらね。

強引にやるとか
int i, j, n;
for (n = 2; n < 1000; n++) {
j = f(n);
for (i = 2; i < j; i++) {
if (j%i==0) break;
}
if (i == j) {
printf("%d : %d\n", n, j);
}
}

>>141
そういうのもありだなぁ。
数式で考えるのとプログラムで考えるののどちらが速いかだね。

プログラムで考えるってなんだそれorz

今の暫定日本一位は高校生なのか。やるな。

>>144
どの情報？

>>145
Leaderboardで国籍にJapanを選択すれば、日本人だけのランキングが出るよ。

>>146
ありがとう。世界は広いね

>> 142
ただ、2^500の下二桁を求めろ、みたいな問題には対応できない。
（いや、やりゃできるんだけど）

>>148
言いたいことはわかるんだけど、その問題は自分なら迷わずプログラムで解くなぁ。
周期求めるの面倒だから。

そうそう、この前出てきた問題に、隣り合う桁の数が全部素数になってる数のうち一番大きい数は
何桁かって問題が出たんだけど、どう解くんだろう？
選択肢は9〜13桁くらいだったと思うんだけど。

>>149
ま、下二桁だけ残して計算させればいいんだから、
500乗程度は、余裕だしな

ちなみに、回答は、
21^2=441
41*21=861
61*21=1281
81*21=1701
1*21=21
で、巡回。
答えは、なので「01」
ま、41*21の時点で予想はつくけど。

>>148
問題の意味がわからん

すまん。
>>149
だった

ひょっとして、素な素数のことか？？
73939133（右から桁を落としていっても残りは素数）
357686312646216567629137（左から桁を落として素数）
とか？？

>>152
多分237とか(23,37は素数)だと思うんだけど…
うーん、ごめん。その問題は飛ばしちゃったもんで記憶に少し残ってる程度だから、
間違ってるかもしれない。

でもそれだったら23737373737…とかありだよなぁ。とふと思った。
ごめん、また同じ問題が出てきたら報告する。

>>155
確かに、それだったら、111111111111111111（1が19個は素数）も
OKになるし何より、「一番大きい数」が無限大だから間違いだろう。
素な素数なら、73939133と357686312646216567629137が最大というのは、
確かに証明されていたような・・・

素な素数の話でしょ，多分．

っていうか知識問題はやめて欲しいよ．

>>138
そっか。１×素数＝素数だよな。ありがとう。
因数分解も考えようとしたんだけど因数分解できたら素数じゃないじゃないか！って考えて思考停止してた。
>>141のはやろうとしたけど大きな数字の時の証明ができないっぽいからやめた。

和訳に時間かかりすぎ・・・orz

満点キター！
1 John Dethridge Australia 240 Melbourne University
日本勢も満点目指してがんばろう！

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
------------
格子点の配列が与えられて、その中点も格子点であるならばそれを表示する。
そのような中点は入力には含まれていないとする。
効率的なアルゴリズムは次のオーダーで動く。

>>160
普通にO(n^2)じゃないのか？

anyって、出力する点はどれか一つでいいってことかな？
そうならO(constant)なんだけど。

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

------------
問題の意味がわからん・・・。へるぷみー

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

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)

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つの虚数解を求めたんだけど、こんなもん時間内に解けるか！？

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スティック）。最も大きい２つのスティックが違うグループに
分けられている可能性は？
----------------------------------------

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

>>163
10の異なったfurbiesの1つは手当たりしだいに何人かのタイプの穀物の各箱の中に置かれました。
母が、彼女が少なくともそれぞれの10の異なったfurbiesの1つを得るまで彼女の子供のためにこの穀
物を買うと決めたなら、彼女が購入すると予想される穀物の箱の数はどのくらいですか?

exciteな翻訳でｽﾏｿ

>>164
1

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

>>168
２台の車は９０ｋｍはなれている。片方は１５ｋｍ/ｈで、もう一方は２５ｋｍ/ｈで
お互いのほうに向かって走り出した。そのときに遅いほうの車から鳥が飛び立った。
鳥は４０ｋｍ/ｈで速いほうの車へ向かう。その鳥が車に到達した瞬間に反転する。
それを繰り返して２台の車がぶつかり、鳥は潰れた。それまでに鳥が飛んだ距離はいくらか？

90miles

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

>>167はどうやってとくの？

>>169
なぜ1？
x=y=zだなんて、誰が決めた？
それなら、0でもいいじゃないか。x=y=z=0。

>>163
-------------------------------
おまけにリカちゃん人形の入ったお菓子がある。リカちゃん人形は全部で10種類だ。
そこで、お前は、全種類コンプするぞと頑張るわけだ。
お前は、いったいどれだけのお菓子を買えば、全部集められると期待する？
---------------------
かな？確率も英訳も苦手だ。

>>167について
2番目に大きな棒が、もっとも大きい棒のグループに入る確率はn/(2n-1)だから

>>174
x^(abc) = y^(bc) = z^c = x
よってabc = 1

>>174納得した

ばんばん問題あげていこうや
というわけで


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人である。
また、女の赤ん坊が生まれる割合はどちらも５０％程度であるが、
その割合は日によって違う。
一年のうち、女の赤ん坊が生まれる割合が60%を超える日が多いのはどちらか？

>>173
>>169
ありがとう。これ答えでるのか？わからん・・・。

>>176
50%じゃないの？
大きい方では、45人のうち、だいたい50%が女
小さい方は、15人のうち、だいたい50%が女
結局、どっちも60%を超えるのは、似たり寄ったりな確率では？

>>176
極端にしてみる。
生まれても一人という田舎の病院と地球全体を比べる。
田舎の病院では60%を超えることなど頻繁だが、世界全体ではまずありえない。
よって小さい病院のほうが60%を超える日が多いだろう

>>169
>>167 は逆じゃない？
同じグループに入る確率は(n-1)/(2n-1)だから、答は n/(2n-1)

>>163
期待値は 29.29 らしい。
tp://www.kjps.net/user/kakuritsu/omake2.html

コテハンでわかね？
どんどん問題上げようぜ

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の確率は？

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がすべて異なった部からあるという確率はどのくらいですか?

>>180
私が間違ってました。そうだと思います。

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

>>183
2*3*4 / 9C3 = 2/7
よってNone of these

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はどんな提案をするべきですか?

>>185
普通に199じゃないの？

>>185
ステージが進んで残り２人という状況になると、
(2)が何を提案しても必ず(1)が反対して、提案は過半数を得られず、
1000枚を(1)が独占する。

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

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

よって、あと５人という状況で(4)は必ず反対するが、
(3)は次のステージに行ったら＄０しかもらえないので、＄１で賛成。
(1)(2)は＄２で賛成。
(5)は、自分と、(3)と、(1)(2)のうち一方を味方につければよいので、
「2:0:1:0:997」あるいは「0:2:1:0:997」という提案で過半数の賛成が得られる。

なるへそ

中国強いな。俺今問題集めてるんだが　こういうやり方は微妙かね？

>>189
あんまし役にたたないかもね。
おれの読みだと100点くらいが限界だと思うよ。

>>190
そうかぁ。ただひたすら本番をといたほうがいいのか

>>191
無駄という分けではないと思うけど。
ただ集めるだけじゃなくて、実際に解いてみたら実力がついていくとおもうふ

２００問程度、問題集めたんだが答えがわからぬ。

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、*)に、以下の声明のどれが本当ですか?

エキサイトな翻訳ですまん

>>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 だと思う

>>194
None of theseの予感。
工房の漏れに即答は不可能。

>>195
>Zの集合の中の最小の数をmとすると、
Zに最小値はありません

Zは無限だから最小値が定義できないってこと？
言われてみれば確かにそんな気がするorz

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

>>195
monoidは、モノイド。
gourpは、群。
Abelian groupは、可換群。

>>194
難しいな。俺にも即答はできない。

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

>>201
(goh)^(-2) = g^2 o h^2 for every g,h ∈G
だと思う。

日本も地味に得点あがってきたな。
頑張ろうぜ

オレの限界は100点くらいだと判明

中国つええな

↓のような問題は英語が苦手だと厳しい。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 .

国内196点ｷﾀｰ
9 Kazuhiro Inaba  Japan 196 The University of Tokyo

さすが稲葉・・・

東大の人、200弱　ｷﾀ――(ﾟ∀ﾟ)――!!
漏れも頑張らねば。

今年のラインは190前後かなぁ。

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

>>211
2(x^2)-1
なお、cos(x)はcos(x)=xの解に、sin(x)は0に収束し、1/xとx^2-1は簡単な振動に向かう。

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番目の数があるという条件付き確率はどのくらいですか?

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

>>213
条件付確率などではなく、a<bのとき
abc
cab
acb
の3通りが等しい確率なので1/3

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
------------
ジョンは静止した車の中に座っている。車の中にはヘリウムの風船があり、
天井の中心付近で漂っている。ジョンは急発進して前方に加速した。
ジョンはその勢いで座席の後ろに飛ばされ、風船は前方へ飛んでいった。
風船の移動にはどの物理現象がかかわっているでしょうか？

濃度

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組の夫婦がいて、混合ダブルスのチームわけを混ぜて選ぶ。
夫婦でプレーしないのならどれだけチームを編成できるか？

>>217
求めるのめんどくさい
None of theseだろ
13の倍数じゃないし

>>217
普通に84じゃないのか？

>>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))

>>217
再帰プログラムを組んでムリヤリ全通り求めたら
1854通りになったから
None of these

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

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

>>223
0

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.

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

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

>>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

>>227はどうやって解くんだ？
ご丁寧に計算したが時間がかかる

中心が正三角形を作るようにして
面積で計算すると204ぐらいだから200だろうけど
実はNone of theseだったりとか

>>229
お皿の直径を1として，テーブルの直径を15とする．
テーブルを水平方向に，1ずつ15分割して考える．
そうすると，テーブルの中心を通る水平方向の領域に，お皿を15枚おける．
その領域の上下2つの領域は，幅が14になる（と思う）ので，14*2で28枚おける．
これを同様に繰り返すと，
(1+2+3+ ... + 14) * 2 + 15となるので，
225が答え　　かな？

答えは187だよ。ただ5分以上かかって本番じゃ解けない

解法は231のようにいちいち計算
ただ重ならないように230のような置き方で
という感じ

231はまずいところあるのか？

>>234
とりあえず２２５が答えになることはならないんじゃない？
あとはわからん

>>234
> 231はまずいところあるのか？
直径15の円の面積はpi*(15/2)^2=pi*225/4
直径1 の円の面積はpi*(1/2)^2 =pi*1 /4
きっちり隙間なく置けたとして、225枚。
もちろんそんな芸当は絶対できっこないから>>230も言うように、225枚よりはずっと少ない。

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くらいかな？

>>236
ネタ？
そんな芸当ができっこないからといって，それが答えにならないの？
理論値でいいんでない？

>>238
冗談だろ。皿は円形だぜ。

>>238
大丈夫。
理論的に考えて225枚は無理だから。

>>238
ネタ？
不可能なものは「理論値」とは言わんよ

>>239-241
>>238は英語が読めないに32bit。

3人が6月の同じ日に生まれない確率は？
203/225
201/225
115/450
None of these
Can't be determined

訳が間違ってるのかな
英文をのせておく

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?

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)

だれか問題文の意味教えてください。

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

>>245
衝突回避をしながら、y個の配列をx種類のハッシュテーブルで管理する。
検索のさいにかかる最悪の時間は？
T(y)

訳はできんが説明は出来る。
仮にy個全部おんなじハッシュになるとする。
すると衝突しまくって最悪でy回の回避処理が必要になる。
なのでT(y)

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

>>247
y個の要素を持った大きさxのハッシュテーブルじゃないか？
同じことであるならすまん。説明がよくわからなくて混乱してしまった

俺32歳の学生なんだが参加していいのか？

>>250
ttp://www.microsoft.com/japan/msdn/student/imaginecup/2005/rules/

f:X→Y
Xのサイズがx
Yのサイズがy

でいいの？

>>248
一番小さいのを見つけるのに1023回
一番大きいのを見つけるのに1023回
合計2046回

・・・もっと少ない方法があるのか

>>249
そういう意味です。
日本語が下手なので伝えきれないです。


類問をひとつ
What is the load factor of a hash table of size x which contains y elements?

y
x
y/x
x/y
xy

>>253
一番小さいのがわかってるから大きい方は１０２２回ってそんなもんじゃないなｗ

>>253
一番小さい方を記憶（逆でも可）して、もしそれより小さければ最小にして大きければ最大と比較で
回数を削れると思ったけど最悪の場合だと変わらんか…

>>256
それは比較してることになる＞もしそれより小さければ

>>248
答えは1536だな。
２個ごとに大小をつける。ここで512回。
最大値は大きいとされた512個の中にしかないので512回
最小値も同じく512回
計1536回

>>257
そうではなく、小さいのと大きいのと２回比較を防ぐために最小より小さい場合は
最大と比較を行わないと言いたかった
結局最悪の場合は最大と最小２回比較を行うから変わらない

>>258
> 最大値は大きいとされた512個の中にしかないので512回
511回じゃないの？

>>260
そうですねぇ、どうしよう。

貼った人のミスだとおもわれ

俺も問題集めてるけど選択肢は
1024
1280
1536
1792
2048
だった。

How many ways can 10 different flowers be strung together so that 5
particular flowers are never separated?
5!5!
10!/5!
288
(1/2)5!5!
None of these

>>222の問題が出てきました。
まったく意味がわかりません。
関数の定義しか書いてないようにみえるのですが・・・・

>>265
貼ったやつが間違えてたと思っていたがまさかほんとにそんな問題だったとは…
俺は定義が途中で終わっていて意味不明の問題にあたった

>>237
これわかりません
8回じゃないんでしょうか

>>237
6くらいじゃないか？

12manabu saito Japan205

また高校生か

The number of steps executed by an algorithm is given by
the recurrence T(n)=4T(n/4)+n^2.
What is this alogrithm's time complexity?
Θ(n^2)
Θ(n^2 log n)
Θ(n^3)
Θ(n^3 log n)
None of the above

Consider the following mystery function:
int MysteryFunc(unsigned char val)
{
　if (!(val >> 1))
　　return val;
　return (val (val & 0xFE)) + MysteryFunc((val & 〜1)-(val >> 1));
}
What does it return?

The value of the most significant bit in val
The number of bits set to 0 in val
The number val divided by two
The number of consecutive bits in val set to 0
The number of bits set to 1 in val

>>271
Θ(n^2)
T(n) = n^2 + n^2 /4 + n^2 /16 ・・・・ -> Θ(n^2)

Consider four ropes of different lentgh. Their average length is 74
inches and the difference in lengths amongst the first three ropes is 2
inches. The difference between the third and the fourth rope is six
inches. What is the length of the fourth rope?
80 inches
75 inches
82 inches
78 inches
90 inches

4本のロープは
78 76 74 68
で68が答えに見えるのですがありません。
何が違うのでしょう？

なんか変な問題ばっかだな

>>274
70 72 74 80

>>272
return (val-(val & 0xFE)) + MysteryFunc((val & 〜1)-(val >> 1));
ならbits set to 1 in valなんだけども・・・

Suppose you have a graph that is 3-colorable; that is, you can assign each vertex a color,
red,blue, or green, such that no two adjacent vertices have the same color.
Which of the following can you conclude?

The graph is bipartite
The graph is planar
The graph is 2-colorable
The graph is 4-colorable
Both b and d
----------------------
３色で塗り分けられるグラフがある。塗り分けられるとは頂点に３種類の色を割り当て、
つながっている頂点には同じ色を使わないということが可能という意味である。
それでは次のどれが結論付けられるか？

For an undirected graph G we call a path a sequence of vertices v1,.....vn
such that vi is connected to vi+1 for all i=1,........n-1.
The path is called simple if all vertices v1,........vn are distinct.
A graph is called connected when for each two vertices there is at least one path connecting them.
A set of simple paths of G is called a path cover if each vertex of G belongs to at least one of these paths.
Let pc(G) be the smallest number of paths in a path cover of G(i.e. there is a path cover with pc(G) paths
and every path cover has at least pc(G) paths).
Let log denote the logarithm of base 2 and sqrt denote the square root.
Consider these statements, which are the correct ones?

For all connected graphs G with n>1 vertices we have.........

1) pc(G)>=log(n)
2) pc(G)<=log(n)
3) pc(G)<=sqrt(n)
4) pc(G)<=n/2

1
1 and 4
2,3, and 4
3 and 4
4

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.

正四面体がある。それの同じ頂点から3匹の目の見えない蜘蛛は出発する。
蜘蛛は賢い虫である私より少し足が速い。私を含めてみな、知られた方法で動く。
また、辺の上しか移動できない。蜘蛛はいつでも私を捕まえることが出来るか？

わかりません。教えてください。

A chauffeur always arrives at the train station at five o'clock sharp to
pick up his boss and drive him home. One day, the boss arrives an
hour early, starts walking home, and is eventually piocked up. he is
home 20 minutes earlier than usual. How long did the boss walk
before he was picked up by hte chauffeur?
20 minutes
30 minutes
40 minutes
45 minutes
50 minutes

>>282
車--------------->駅に
　<---------------６時
のはずが・・・
車-------->出会う
　<--------

往復２０分の短縮なので片道１０分の短縮。
ということは５時５０分に出会うわけ。
５時に駅を出た人は５０分歩いて、車にであったわけ。

John travels to Gotham everyday for his work.
His wife picks him up at the train station each evening at exactly 6 PM. One day, he left work early, and arrived at the train station at 5 PM.
He started walking home, but he met his wife en route to the station and got into the car.
They drove home and arrived 10 minutes earlier than usual
. How long did the man have to walk before he was picked up by his wife?
55 minutes
45 minutes
35 minutes
25 minutes
57 minutes

日本語訳ｷﾀｰ
ttp://jp.thespoke.net/MessageBoard/MessageBoard_ViewThread.aspx?postid=696

∩( ・ω・)∩ばんじゃーい


でも問題の答え合わせはここでつづける

3000個のバナナをラクダに乗せて1000マイル運ぶ
ただしラクダは1000個までしか同時には乗せられず
1マイルごとに1個食べてしまう

みたいな問題にあたった人いる？
答えがどうみても0にしか思えないんだけど・・・・

What is the 90th term of a recursive sequence which is defined as
a_n=a_{2n-1}-|a_{n-2}|
a_0=1
a_1=0 ?

-1
0
1
2
None of these

マジわかりません。助けて。

>>287
There are 3000 bananas but you need to move them a 1000 miles
across a desert. There is a camel but it eats 1 banana every mile,
and can carry only 1000 bananas at a time. What is the max # of
numbers of bananas that you can get to the final destination?

0
200
466
534
1000

だね。答えは534です。
途中にバナナを置いて、いったん引き返すんだよ


>>288
a_{2n-1}ではなくて、(a_{n-1})^2ですよ。

６００問ほど集めたけど半分も正解できない漏れって・・・ｗｗｗっうぃうｑｈうぃうｈｗｗ

>>289
最初の１０００個を６６７ｍ運んで３３３個置く
これを３回繰り返すと６６７ｍ地点に９９９個のバナナがある
これを最後まで運ぶと９９９−３３３＝６６６個余る

よくわからないけど答えは１０００じゃないか？

>>290
UPしてください

In the United States, how many times will a car wheel typically rotate
in 1 minute of travel at freeway (60 miles per hor) speeds?
100
300
1000
3000
10000

知識問題ですか・・・？これ

たぶん全問集まった850問くらいか？

>>291
引き返す分の消費考えてないだろ

>>289
俺466だと思うんだが、どうやったのか詳細plz

>>291,296
まず２００マイル地点まで２往復と片道歩くと残り２０００本。
そこから５３３マイル地点まで１往復と片道で１００１本
１本手に持って歩くと５３４本持って到着。

>>293
１マイル１８００ｍとすると１分間で１８００ｍ車は走るわけだ。
円周率を３、車の直径をｘ(ｍ)、タイヤの回転回数をｙとすると
３*ｘ*ｙ＝１８００
x*y＝６００
直径は５０ｃｍ程度なのでｘ≒0.5
よってｙ≒1000

>>278
The graph is 4-colorable
３色でぬれるなら４色でもぬれる。

>>279
4
ある一頂点のみが全ての頂点とつながっているグラフを考えるとpc(G)<=n/2である

>>280
NP完全のような希ガス


>>284
>>283

>>288
1
1,0,-1,1,0,-1・・・なので

>>280
spiderはbugより速いんだから
同じ道をたどって行けばいつかは必ず追いつくだろう

>>298>>278
planerってどういう意味かわかりません


英和辞典 [ planer ]の前方一致での検索結果 1件
plan・er
━━ n. 鉋をかける人; 機械鉋.

>>299
blind spiderですから目が見えないんです。

>>300
planar
平面的であるという意味です。

Given a standard telephone keypad (2-ABC, 3-DEF, 4-GHI, 5-JKL, 6-MNO, 7-PRS, 8-TUV, 9-WXY),
what is the maximum number of letter combinations of 3 to 7 letters inclusive that can be made from a standard 7 digit telephone number?
327
4024
4833
63215
None of the above

>>302
ADGJMPTWの８文字から出来うる７文字文字列だけでも
8*7^6=941192なのでNone of the above
これ自信ない

>>303
8*7!になるだろ

あとから同点になった人の方がLeaderboardで高順位につく件

Nine chairs are numbered 1 to 9.
Two women and three men each want to sit down in a chair.
First the women choose chairs from amongst the chairs marked 1 to 5. Afterwards, the men select chairs from those remaining.
How many possible seating arrangements are there? Recall that xCy means x!/(y!(x-y)!) and xPy means x!/(x-y)!.
4C3 x 5C2
5P2 x 7P3
5P2 x 4P3
5C2 x 6P3
None of these

>>304
同じ文字使ってもいいんじゃないでしょうか？

>>306
5P2 * 7P3だと思う

>>303
＾6はどっからでてきた？

>>278は
グラフの頂点が３つの場合はどうするんだろ
４色で塗れるって言ってしまっていいのかな

>>309
正解

>>304
３点でも４色あれば、そのうち何色かをつかって塗り分けられます。
それがcolorableの意味だと思っていたのですが、間違っていますか？

締め切り迫る

Can you find the next three terms in the series shown below?
23, 31, 41, 59, 71, 83, 97, 109, ?, ?, ?, ...
A 119, 131, 149
B 117, 129, 131
C 131, 157, 173
D 131, 173, 199

>>313
難しいな。この手のやつは苦手だ

>>314
簡単だよ。こたえはD。

>>315
理由を教えてくれ。

>>316
やだ。でもヒントはあげよう。素数だよ。

"23, 31, 41, 59, 71, 83, 97, 109"でぐぐれ。

Can you find the next three terms in the series shown below?

23, 31, 41, 59, 71, 83, 97, 109, ?, ?, ?, ...

Answer:
131, 173, 199

Why? The series is only those prime numbers that can be expressed as the sum of three consecutive prime numbers.

23 = 5 + 7 + 11
31 = 7 + 11 + 13
41 = 11 + 13 + 17
59 = 17 + 19 + 23
71 = 19 + 23 + 29
83 = 23 + 29 + 31
97 = 29 + 31 + 37
109 = 31 + 37 + 41
131 = 41 + 43 + 47
173 = 53 + 59 + 61
199 = 61 + 67 + 71
And so on...

ボーダー何点くらいだと踏んでる？

去年のペースと比べて、190弱じゃないかと思う。

Say you have a traditional binary heap with n elements. How much
time is required to perform the "DecreaseKey" operation
corresponding to Dijkstra's algorithm?
O(1)
O(log log n)
O(log n)
O(n)
O(n log n)

Dijkstra's algorithmってダイクストラ法とは関係ないですよね？
DecreaseKey ってなんですか？

締め切りまであと何時間？

なんでプログラム板にこのスレがあるんだ？
理系板か数学板行けよ。

>>324
いまさらすぎじゃね？去年からあるのを再利用してるだけだし・・・。

今夜あたり150点のラインこえるねぇ

人減ったな。みんな必死か？

漏れは３ﾏｿほぼ確定なので余裕

>>328
３万って何？

ttp://www.microsoft.com/japan/msdn/student/imaginecup/2005/guide/prize.aspxより

その他日本向け賞金

--------------------------------------------------------------------------------

ソフトウェア デザイン部門以外の世界大会予選通過者にもそれぞれ独自の賞金を提供します。
オフィス デザイナー部門・レンダリング部門・ショート フィルム部門・テクニカル ビジネス プラン部門・Web 開発部門は、1 次予選突破で 1 チーム 10 万円を贈呈。(Web 開発の高校生部門は 3 万円)
アルゴリズム部門・IT 部門 は 1 次予選突破で 1 チーム 3 万円贈呈。
ビジュアル ゲーミング部門 は 2 次予選突破で 1 チーム 3 万円贈呈。
更に、各部門において世界大会出場で 10 万円贈呈。

>>329
後二日くらいだが、がんばれ。

>>331
俺は180↑いってるから大丈夫だとは思うが、３万もらえるなんて知らなかった。
３万ってどうやってくれるんだ？

>>332
メールで送られてくるのだろうｗ

正直ここの答え役に立ったのが結構あったぜ('A*`)
thx

冗談はともかく貧乏学生にはありがたい。
両親とすしでも食べにいくべ

にしても日本レベル低いな。
３万って餌つけてもこれか。
お前ら他の部門も頑張ろうぜ。

190は行かないと大丈夫とは言えないと思うぞ。
俺も180後半だがどきどきだ。
締め切りってUTCで3/1の0:00でいいんだっけ？

>>337

>>332だが、個人特定されそうだから180↑って表現にした。
たぶん大丈夫な点数なはず。

数人に1人程度に絞れたなｗ

中国のランキング　すごいな。
169〜223だ。

>>337
たぶんいいとおもう。

あと二日でボーダーが180まであがるんだろうか？

漏れは240でつ

急に書き込み加速したなｗ

>>342
お前が誰だかわかｔｔ

>>342
一人に絞れたなｗ

正直、全部自作自演・・・なんて思ってしまいそうな速さだ

この速さなら貼れる


To number all the pages of a book took 582 digits.
How many pages are there in the book?

200
210
220
230
240
----------
全ページに番号を割り振るために582個の数字を書き込んだ。
この本は何ページですか？

>>346
230

>>346
たぶん5番。これEasyだな。難易度。

>>346
4だった。ｽﾏｿ

もういっちょ

In a custom microchip processing plant, workers shape 1 gram packages
of Silicon semiconductor material into custom microprocessor wafers.
During the manufacturing process, not all the Silicon is used.
For every five wafers the plant fabricates, there is enough extra Silicon
to make one additional wafer. Suppose a worker is presented with 25 grams
of Silicon. What is the maximum number of wafers she can make?

25
26
30
31
32
-------------
マイクロチップを作る工場では作業員が1個当たり1gのシリコンを削って作ります。
この工程ではシリコンの削りかすが発生します。
5つ製造するごとに1gのシリコンが余ります。
25gのシリコンから何個作れるでしょう？

>>350
31

What is the identity element of the group if it is defined on a set of
integers Z with the binary operation "*" such that a*b = a+b+1
for a,b ∈ Z ?

0
1
12
[-1]
None of these
------------
整数の集合Zが次の演算*に対して定義されている。
a*b = a+b+1
それでは単位元はどれか？

>>350
ちなみにそれもEasyだ。
30問中、Easy、Medium、Hardがそれぞれ10問で30問。
点数の重みが違うから気をつけろ。

>>353
Easy,Medium,Hardって問題の出る順番とは関係ないですよね？
友人は最後は決まって簡単なのが出るとかいってましたけど、どうなんでしょう。

>>352
答えに括弧ついてるよ

>>354
そこまでは調べてない。
たぶん関係ないと思う。Hard(３段階中一番難しいやつ)間違えると-24

>>356
ルール読み間違えてない？

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!
-------------
5つの要素(同不順)の中点を決定するために必要とされる比較は最大何回か？

>>357
240を基準にして考えてるから。
それを付け加えるの忘れてた。

Hardだと正解で+12、不正解で-3だね

-15だよね。つか、>>346と>>350がEasyだというのも>>356の妄想？

-3いれてなかった。すまん。
>>361
パケットから見てるからそれは確か。

>>358
5!/2なら確実なんだが、6も胡散臭い。

>>362
パケット見てわかるんですか

今やってるのが調子いいので助けてください。

Mark tosses a coin until 2 tails appear and then he stops.
What is a recurrence relation for the number of tosses that end on the nth flip or sooner ?

an = an-1+ 2(n -1)
an = an-1+ (n -1)
an = an-1+ n
an = an+ (n -1)
Can be determined

日本語化されてませんでした。

>>364
an=a(n-1)+(n-1)

>>364
2chに書き込む暇があるのか
俺なんか30分じゃ短すぎてとても駄目だ

調子はどうだい？

これ時間止められるバグは既出？

>>368
まじかよ・・・

>>364と>>366はそういう意味だったのか

>>368
クライアント側で時間止めたとしても
サーバ側の問題発行時間と解答提出時間の差を見れば
不正と見なされて無効になるぞ。








もちろんチェックしてるよね？>MS

してればね

さすがにＭＳでも、してるだろう

締め切りって日本時間で何時でしょうか？

>>374
15°で1h違うよ。

>>375
聞き方が悪かったか
日にちは書いてあるんだけど時間が書いてないんだよ
そもそもアメリカ時間で何時？

>>376
>>337

日本勢がごっそり落ちてきたな

締め切りまで後7時間切ったけどここから本当にボーダー180まで上がるのか？
去年を全然知らないのでなんともいえないけど。

なんでこんなに人が少ないの？
みんな必死なのか？
もう締め切りだぞ？

後３時間ですよ〜♪

後２時間です〜♪
４回しかチャレンジできませんよ〜♪

現在のボーダー　１６８

日本人予選通過人数　１２人

現在のランキング

170/240 177位
175/240 165位
180/240 140位
185/240 112位
190/240 80位

日本頑張れ！
目指せ入賞15人！
チャンスは残りあと僅か！

後1日ありますよｗ

現在のランキング

170/240 182位
175/240 165位
180/240 143位
185/240 113位
190/240 81位
195/240 59位

人がいないな・・・。

結局いつまでなんだ。まだ問題みえるけど実はもう終わってるのか？

24時間延長になったらしい。
"締め切りは、GMTで3月3日12：00 AMなので、日本時間で3月3日9：00AMまでの延長となります。
とのこと"

マジ？ソースｷﾎﾞﾝ

ネタじゃないか？
GMTで3月3日12:00なら日本では21:00になるはずだぞ。

ttp://jp.thespoke.net/MessageBoard/MessageBoard_ViewThread.aspx?postid=729
に有る通りだが、たぶん12:00AM = 00:00(24時制)のことだと思う

たまに時計でもあるよねAM12:00とかいう表現
AM12:00 = PM0:00と解釈したくなるんだけど…

みんな、STUDENT DAYって行くの?

当選したよ

落選した人っている？

落選したよ

わざわざ東京行くのはﾒﾝﾄﾞｲ。
大阪までならいけるんだが

411317197379

>>401
それ、どういう数ですか？

>>402
たぶん教授の好きな数字

>>402
復活の呪文

予定通り遅れたけど結果出たね。
ボーダーは185か。思ったより延びなかったね。
で、3万円はどこ経由でやってくるのかな。

>>405
どこに結果でてる？

トップページからリンクあるよ。
ttp://www.thespoke.net/MessageBoard/MessageBoard_ViewThread.aspx?postid=2525

>>407
ありがとう

>>405
> で、3万円はどこ経由でやってくるのかな。
メールで送られてきます

6 Conan Edogawa Teitan Highschool Japan 230

これどうよ？

本当に実在してればありなんじゃね？
ただ江戸川コナン・・・ありえないな

他にもRitsumeikan Universityにはありえないような名前が…

ありえなさそうな名前は
6 Conan Edogawa Teitan Highschool Japan
13 Mika Nakashima Ritsumeikan University Japan
69 Square Enix Ryukoku University Japan
69 Nanako Matsushima Ritsumeikan University Japan
149 Demento Capcom Japan
こんなもんかなぁ…芸能人と同姓同名は可能性として否定はしないが
Square Enixて。

あんまり多いと繰り上げ合格になるのかな
俺には関係のない話だが

なぜ偽名をわざわざ使うのかがわからん。それでも３万もらえるとおもってるのかな

>>413
3 Miyabi Natsuyaki Ritsumeikan University Japan 235
33 Risako Sugaya Ritsumeikan University Japan 215
も芸能人と同姓同名だね。

>>415
ただの荒らしじゃない？3万円なんか狙ってなくて。

ベストスコアを最終日に自分の名前に変更すればいいのか
頭いいな

なるほどな。マイクロソフトもそこまで馬鹿じゃないだろう

>>417
どうせなら知り合いの名前借りまくった方が頭いいぞ。馬鹿だけど。

江戸川コナンの本名は工藤新一ですから・・・・
残念！！！

メールきたけどなんも問題ないよ？

２次予選は面白そうだね。
ほかの人の点数は見ることが出来るのかな？

２次のほうが断然面白そうだね。

>>422
there will be a leader list provided at the end of the round showing
name, country, school, and score, similar to what was provided at the
end of the first round.
we are not planning to have an ongoing leaderboard or a level-wise leaderboard however.

と、掲示板にある。

とりあえず、ぐるぐる回るｈプログラム

a(A):rb(A)rb(A)a(A-1)
b(A):sb(A-1)
a(26)

これで全部のボタンを押せるはず。

今年のImagineCupは中止だってさ。
本家に書いてあった。

とりあえずレベル１と２はとけた！

"System.ArgumentNullException"が発生して起動できねぇ・・・＿|￣|○

ということは「ぬるぽ」じゃないんだな？

これ25問解こうとした方がいいのか捨て問作ってできるだけ減らした方がいいのか　どっちなんだろうな？

特殊な規則性の元でがっちり作られた数問を除いて、どれもmaxbyte未満で解けそうだ。
迷路はがんばっても解けそうにないんだが・・・

>>430
暇なら全部とけ、そして日本人として世界大会に出てくれ。

迷路ジャストで解けた。
ここで解けた問題のバイト数報告しあわない？

>>432
それはまずいと思うぞ。
一応ヒントになりうるので。

一次予選の時は誰も何も言わなかったじゃん

じゃレベル１は4byte

奇遇だな　漏れも4byte

4byte未満は無理でしょう。明らかに

24解けたやついる？

24は発想だよ。分かってみればすごく簡単。
24解く前には外に散歩行ったらいいと思う。

だれも話題にしないけど、
Visual Studio .net Academic Version 2003 無料でｹﾞｯﾄｽﾞｻﾞｰ

俺んとこにも届いた。けど使いにくくてかなわん。
結局VC6.0入れなおした。

バカだなぁ、未開封の状態で売ればいいのに…

どうせ売っても３０００円くらいでしょ

最終日。
230000点超えた奴いる？

私のスコアは２０万にもいかなかった。
大学と高校の壁を思い知った。
23,24あたりは考える気すら失せてしまった。

賞状っぽいものとTシャツが来たage

げげ、このスレ、まだ残ってた???
しかもいつのまにか、またはじまってんじゃん。
<http://www.microsoft.com/japan/msdn/student/imaginecup/2006/>
どの部門が狙い目なんじゃ??? この前は日本人も賞金取ったらしいじょ。

ビジアル ゲーミングの攻略本もみつけた。
http://thespoke.net/forums/920088/ShowPost.aspx
これ、かなりいけてる。

世界大会はどこなの？

インド

賞金総額って１５００万円もあるの?

総額だけならね。１位の賞金は部門ごとによって異なるから注意。

おいおい。
http://www.microsoft.com/japan/academic/campaign/default.mspx
こんなのみつけた。ゲームもらえるんじゃん。登録さえすればいいんだな。

>>448
攻略本というほどのものでもない、取扱説明書
round1は簡単にクリアできるようにはなるけどな

>>453
希望のものがもらえるの？
どこにも書いてないみたいだけど。

>>455
>MSN ゲーム http://games.msn.co.jp/ の中からご希望のゲーム 45名様
これじゃないの？

なんか当選のメールが来てたｗ

開始まであと２週間きったか

予選通過でお金貰えるんじゃないなら今年はやらない。

来週の月曜からか、時差で火曜だけど

もう始まってるのか？

専用クライアントの実行に時間がかかりすぎｗ

内容が去年と全然違うのか

いや、去年の２次予選と同じじゃないか？

若干規定変わってるけど、
去年の二次とほぼ同じだね。
後半の難易度上がってる。

初めて起動しようとしたのに、すでに起動してますとかでてくる。謎

こんなんみつけたじょ。
http://www.microsoft.com/japan/msdn/student/imaginecup/2006/aljp/

今年はトップから200人のスコアが見れないのか
みんなどのくらいの点数とってるんだろ…

メル友になってください､アドレスは
[email protected] <[email protected]>です｡
送ってください！！！

灰色のボタンうぜー

後半の問題だとそんな動き方は想定済みですと言わんばかりの場所に灰色のボタンがあるな

今のところ２００位の点数が６７２３らしい。木曜までに７０００越えれば名前が載るかな？

level5むずいよヽ(ﾟ∀ﾟ)ﾉウンコー！

やったー解けたーヽ(ﾟ∀ﾟ)ﾉチンコー！

level5よりlevel3の方が難しそうに見えたｗ

あと1バイトが削れない・・・
せっかくここまできたのにアルゴリズム間違ってるのかぁぁ！！

微妙に削れるところがあるはずだぁぁ！！

この世のものとは思えない美しいコードができたーーぁぁ！！

これってランキング見れないの？

>>479
明日(もう今日と言うべきか)メンテナンスがあるから、それが終わったらランキングが見れるようになる予定らしい

一応2月14日時点での1位と200位のスコアはでてるな
1位が67325、200位が6723だそうだ

>>480
とん

ボーダー60000超えるかな？

40000ぐらいじゃないの？と適当なこと言ってみる
上位１００位なら60000超えてそうな気もするけど

メンテナンスに入ったな、１時間後にランキングが見れるようになってることを祈る

メンテナンスは2時間だろw
さて、日本人が何人入ってるかな

ランキングまだー？

http://www.wildnoodle.com/ic2006/UI/Compete/LeaderBoard.aspx
一日一回更新。
最後の週は更新が止まる。

日本人多いなw
筑駒何人いるんだよw

微妙な位置でも神奈川大学と専修大学が頑張ってるように見えてしまう
どうでもいいことだけどね

なんか嫌味っぽいなw

英語を読める必要が無ければ日本人は強いなw

これ協力すれば、簡単に上位いけるぽいなｗ

ボーダーラインの点数の上がり方がすごいｗ
60000超えるか？ｗ

学校名直らない・・・orz

>>494
Imagine Cupの学校名ってtheSpokeのプロフィールのやつだよね？

そうなんだけど、修正してもなんか反映されない・・・

レベル46が難しい

41、47が見当付かない
他は46含め組み方次第でなんとかなりそうなんだが

１次予選の途中経過・・・日本人が一位だね。これって、すごすぎる。
なんか、ストーンズのチケットとかXBOXが当たる登録キャンペーンもはじまったね。
当たるかもしれないので参加登録だけしてみた。

見るからに東大、筑駒が強いようにも見えるが、岡山とか変なとこもたくさんいるな
よくわからん

41、47は見るからに無理そう
46はできそうなきもするけど無理

よくわからんが>>500は東大か筑駒

僕は文系。でもチケット欲しいので、参加登録だけした。

>>500は岡山だろ

実は>>500は浅野

ボーダーラインの点数が停滞しはじめたか

東大のトップはかわらないな

ボーダーラインが停滞したと思ったらいきなり点数が上がったｗ
50000か60000ぐらいいくかもな

高校生が4位に上がってきたぞ

ランキングに入ってる日本人の数も増えたな

>>500はベトナム

>>511
ベトナムはこの板発見できねーだろw

>>512はベトナム

>>509はnadsuki

>>514はMg9H

>>515はNaCl

ボーダーライン60000越えるか？
最後に急に点数が伸びたりしないかぎり微妙なところだが

>>517は２００位くらい

>>518はビルゲイツ

>>520たん萌えー

>>520は5位くらい

Round 1で上位の方でもRound 2になってから何をやればいいかわからないやつがでてきそう

羊が狐を抜いたぞ

誤爆ですorz

保守

取りあえず一番下の2点って何だろうね

順位がリアルタイムにわかるようになったけど・・・
なかなか解けない問題で悩んでるうちにどんどん順位がさがってく
なんとか解いても現状維持
きついよー(ノД`)

終了直前だしみんな張り切ってんだろｗ

８万越えたのに最後まで４６の壁が・・・

ボーダーラインはすでに60000を超えた
最低でも65000にはなるだろう
下手すりゃ70000？

時間的にもうほとんどあがらんな、１問解くのに２，３時間はかかるような問題しか残ってないだろうから
それに、残ってるやつはできなくて後回しにしたやつだろうしな

微妙に時間が伸びてるのなｗ

46解けたやつおる？

順位一桁入ったけど４６はまだ
なんなんだこの４６

46できず・・・orz

終了

最後に実行してたプログラム
a(A,B):sA(AAA,B-1)
Herbertお疲れ、今までよく逆らわずに回り続けてくれたよ・・・

一日放っておいたら今日に限ってものすごい勢いで順位下がってた件

TextSS　のWindowsXP(Professional)64bit化おながいします

もしくは64bitにネイティブ対応したテキスト置換ソフトありますか？

そういや64bitにネイティブ対応している２ｃｈブラウザてありましたっけ？

もうすぐ結果発表だね
わくわく

もうすぐだね
3/13の順位が全く当てにならない

結果出たぞ
ttp://www.wildnoodle.com/ic2006/UI/Compete/LeaderBoard.aspx

ちょｗジャップ強ええｗｗ

2 monae 85377 Japan The University of Tokyo

外人はきっとモネって読んでることだろう

２次発表されたんだけど、課題読める人いる？
マジで読めません、誰か助けて・・・

>>545
つ Excite

>>545
英語読めなくてもチュートリアル見れば大体わかるだろ？

ぅぇぇん、ぜんぜんわかんなぃょぉ・・・

何がわからないのかがわからない

ようやくわかったｗ　激しい勘違いしてた・・・
とってもありありｗ

漏れRound1落ちたんだけどRound2ってどんな問題？

さめがめをひっくり返したような問題

問題を公開すれ
知恵を貸してやるよ

問題
ttp://www.wildnoodle.com/ic2006r2/Tutorial.aspx

Round2にいってなくてもSDKをダウンロードできるんだなｗ

３万円来るらしいけど、銀行口座ってどこでもいいのか？

>>556
賞金あったの？今年はなさそうな感じだったのに…

うん、３万円らしい
ないと思ってたからびっくりだ

私の胸はImage Cup

？？　Round2 行っただけで３万？



…… VG にはないだろうな(；´Д｀)

工工エエェェ(´Д｀)ェェエエ工工
あると知っていれば頑張ったのに…orz

>>556

俺もRound1クリアしたけど賞金のことは知らなかった。
どこで賞金があるってわかったんだ？

漏れも２次に進んだけど賞金の話は聞かされてないな。
それとも高校生だけが対象とかあるんだろうか。

メールがきたよ
日本人１０人までって聞いたことあるけど、ソースないや

>>564
情報さんくす。すると漏れは対象外ってことだな。
それにしても３万円とは太っ腹な…。

さすがにRound2にいった全員に賞金は厳しいだろうな、人数が多すぎるｗ
VGは簡単だったから賞金をだしたくないだろうね