Mathemat>>: Одинаковые они по прочности. Цвета имеют принципиальнейшее значение: их перекрашивать никак нельзя, т.к. это эксклюзивный каприз заказчика для кодера. Шарика только два. P.S. Задачка действительно серьезная. Я и не подозревал, что подобные задачки дают в качестве испытательных.
Prival>>: правильно ли я понял, что самый худший вариант. перебор. бросаем шарик на 1, 2 и т.д. этаже, пока он не разобьется. и в принципе 2-й шарик не нужен. Да ?
MetaDriver>>: Уговорил. Вот вариант с 14 бросками. Красный: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 98 // последний ход (98 вместо 99) позволяет сэкономить один худший бросок, в случае если с 95 не разбит Синий: заполняет последний неразбитый промежуток красного, как и в прошлый раз.
Одинаковые они по прочности. Цвета имеют принципиальнейшее значение: их перекрашивать никак нельзя, т.к. это эксклюзивный каприз заказчика для кодера. Шарика только два.
P.S. Задачка действительно серьезная. Я и не подозревал, что подобные задачки дают в качестве испытательных.
100階建て、ボール2個」の場合、最悪の場合16投で可能
// 最初は19個かかると思っていたのですが、皆さんの強烈な待ち伏せのヒントで、「選択肢がある」ことに気づきました...。:)
戦略
赤いボールを先に投げる(プログラマーの気まぐれ):
階数:16、31、45、58、70、81、91、100
赤い風船がどの階でクラッシュしても、青い風船を「赤いリストで生き残ったもの+1」から順に投げ、「赤いものがクラッシュしたもの-1」まで投げ続けるのです。
最悪の場合の合計==16。
// 一般的なケースについては、誰かに先を越されなければ、目が覚めたときに計算式を考えておきます。
あなたは薪割りをする人を雇いました。1週間(7日間)刻むそうです。あなたは7グラムの金塊を持っていて、毎日 きっかり1グラムを支払わなければなりません。でも、ピースを刻めるのは2回まで。支払いはどうするんだ?
しかし、問題は測定器なしでどうやってここまで精密に刻むかということです。また、そのような装置があれば、1~2本のチョッパーで7gに切り分け、あらかじめ細断しておき、切り株の上で曲げるという方法もあります :)
-
数理さん、 優勝パレードの印象はいかがですか?
1階で風船を投げれば割れるし、それなら他のところへ行く意味がない。最大100個(壊れない)。
2つ目の風船は、半分に割って使うチャンスです。 割れるまで、最大数を減らして、1つ目は50階に投げます。Brokenは1~49まであります。壊れなければ25へ、といった具合です。
最小で2ステップ、最大で3ステップになります。50.
条件がなければ、色に意味があるとは思えません。赤いボールが壊れないのは何階までか、とか。
もちろん、問題の条件が悪いのですが、「7本の鎖があり、1本しか切れない」と書いてあれば、より確定的だったのですが......。
правильно ли я понял, что самый худший вариант. перебор. бросаем шарик на 1, 2 и т.д. этаже, пока он не разобьется. и в принципе 2-й шарик не нужен. Да ?
最悪なのは、2つのフロアをまたいでボールを投げることで、下から上へ、壊れるまで移動し、2つ目のフロアより下のフロアを投げる。
リッチー 刻み方を考えるヒントがないのに、なぜ作業を複雑にするのでしょうか?ある種の切り株、熱。私たちは、1つのピースを任意の2つのピースに任意の精度で2回切り分ける能力を持っています。この問題は、すでにあなたによって解決されています。
MetaDriver правильно движется. Просто найденный вариант еще не оптимален.
赤:14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 98 // 最後の手(99の代わりに98)は、95の不成立の場合、最悪の出目を1つ減らすことができる。
青:前回と同じ、最後の切れ目のない赤のギャップを埋める。
リッチー 刻み方を考えるヒントがないのに、なぜ作業を複雑にするのですか?ある種の切り株、熱。私たちは、1つのピースを任意の2つのピースに任意の精度で2回切り分ける能力を持っています。この問題は、すでにあなたによって解決されています。
Уговорил. Вот вариант с 14 бросками.
Красный: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 98 // последний ход (98 вместо 99) позволяет сэкономить один худший бросок, в случае если с 95 не разбит
Синий: заполняет последний неразбитый промежуток красного, как и в прошлый раз.
はい、面白いですね。私が見つけた解答では、最適な書き方はほぼ同じ(99で)、それでも14と出ています。 問題は証明にあります。なぜ、どんなケースでも13ステップで解決できないのか?
ここでは証明は好まれないようですが(特にVolodya さん)、私にはこれが最適解のように思えます。しかし、何かが足りない。なぜ、このアルゴリズムが最適なのか?
追伸:このアルゴリズムを使えば、14が最小であることを証明するのは難しいことではありません。よし、やったぞ。一般的なケースで解くのか、そうでないのか?