Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 114
Стрельнуть по последнему окопу, потом по первому, потом по предпоследнему и так далее, солдат будет смещаться к середине.
С таким же успехом можно слева направа стрелять, или справа налево.
Ну и вообще я немного не понял: если я не вижу ни Билла, ни его перебежек, ни результатов, то чтобы быть уверенным, что я его убил - мне стопудово надо выстрелить в каждый из 1000 окопов.
Ну и вообще я немного не понял: если я не вижу ни Билла, ни его перебежек, ни результатов, то чтобы быть уверенным, что я его убил - мне стопудово надо выстрелить в каждый из 1000 окопов.
Проскочить легко. Стрельнул по, например, 995 - Билл был в 994 и после выстрела в это же укрытие и убежал (995). А потом побежал в >995 и там бегает. Слева направо все перестрелять уже лучше.
Пронумировать окопы числами от 1 до 1000. Предполагая, что в момент первого выстрела Билл сидит в окопе с нечетным номером. Мы стреляем в окоп номер 1. Если не попали, то Билл перешел в окоп с четным номером. Выстрелим во второй окоп. Если не попали, то Билл перешел в окоп с нечетным номером, не меньшим 3. Выстрелим в окоп номер 3, и так далее. Оттесняя Билла, мы таким образом поразим его. Если же вначале он находился в окопе с четным номером, то после тысячного выстрела он находится в окопе с четным номером. Теперь опять стреляем в 1000-й окоп, а потом в 999-й, 998-й, ... 1-й.
Задача не имеет алгоритмического решения, потому что солдат может перебежать как в сторону выстрела, так и в противоположную, мы можем выстрелить в окоп, а на следующий ход он окажется в нём. Мы убьём его с вероятностью 1/1000, больше никаких данных нам не известно, оптимальным вариантом будет стрелять всё время в один окоп, но не факт, что рано или поздно его убьём.
А если он переместится в обстреленный окоп, после Вашего второго выстрела?
Только что придумал такое же решение независимо от вас)
и, к сожалению, оно не верное(
сколько бы мы не стреляли в одну ячейку, никто не гарантирует, что после последнего выстрела Билл, находящийся в соседней ячейке, не переместится в "зачищенную".
сколько бы мы не стреляли в одну ячейку, никто не гарантирует, что после последнего выстрела Билл, находящийся в соседней ячейке, не переместится в "зачищенную".
если все окопы от 1 до n зачищены, то бишь в них известно отсутствие билла, то n+1 и n+2 зачищаются тремя последовательными выстрелами "n+2, n+3, n+1"
то есть начало стрельбы такое: 2, 3, 1, 4, 5, 3...
так можно зачистить до 98, потом делаем два выстрела в 99 и биллу капец
то есть начало стрельбы такое: 2, 3, 1, 4, 5, 3...
так можно зачистить до 98, потом делаем два выстрела в 99 и биллу капец
творчески облажался, такие три выстрела зачищают n+2 при условии зачищеных предыдущих n+1 окопов. Но билла это все равно не спасет.
ЗЫ выстрелов получается 998*3 + 2
ЗЫ выстрелов получается 998*3 + 2
нет, таки идея о возможности сделать серию таких выстрелов, что в дальнейшем билл никак не доберется до какой-то части окопов, не проходит. Пусть даже есть серия, которая не оставляет биллов в первых n окопах. После такой серии билл вполне может сделать ход n-1 -> n, а значит, первые n не зачищены.
если все окопы от 1 до n зачищены, то бишь в них известно отсутствие билла
по условиям задачи неизвестно где Билл и убил или не убил
по условиям задачи неизвестно где Билл и убил или не убил
Похоже, что самым оптимальным решение будет стрелять рандомно. И задача получается на теорию вероятности)
Похоже, что вы правы
Имеется в виду, что сначала нужно бострелять нечетные окопы, а потом четные?
если изначально билл был в нечетном окопе, то после каждого четного выстрела он оказывается в нечетном окопе. При указанном методе прохождения окопов если Билла не убили до выстрела в 998 окоп (998 выстрел), то Билл должен обязательно находиться в 999 окопе. То есть первый проход будет состоять из 999 выстрелов.
Далее. Если изначально Билл сидел в четном окопе, обстрел начинаем со второго окопа (первый выстрел - второй окоп - число выстрелов на 1 меньше, чем номер окопа, в который производится выстрел). Если Билла там не было, то и в первом он оказаться не мог после выстрела, а переместился наверняка в нечетный окоп. То есть после каждого нечетного выстрела Билл будет в нечетном окопе (после четного - в четном). То есть, когда мы сделаем выстрел в окоп номер 998 (выстрел номер 997), то Билл (если мы не убили его до этого) наверняка будет находиться в 999 окопе (единственный оставшийся нечетный). Стреляем туды, получаем 998 выстрелов.
998+999 = 1997. А у товарища ниже получилось 1996. Судя по вему, олимпиада в Днепре проводилась в 1996 году ))
Далее. Если изначально Билл сидел в четном окопе, обстрел начинаем со второго окопа (первый выстрел - второй окоп - число выстрелов на 1 меньше, чем номер окопа, в который производится выстрел). Если Билла там не было, то и в первом он оказаться не мог после выстрела, а переместился наверняка в нечетный окоп. То есть после каждого нечетного выстрела Билл будет в нечетном окопе (после четного - в четном). То есть, когда мы сделаем выстрел в окоп номер 998 (выстрел номер 997), то Билл (если мы не убили его до этого) наверняка будет находиться в 999 окопе (единственный оставшийся нечетный). Стреляем туды, получаем 998 выстрелов.
998+999 = 1997. А у товарища ниже получилось 1996. Судя по вему, олимпиада в Днепре проводилась в 1996 году ))
если в каждый окоп бить по два раза (1000*2 - 1 выстрел), то
1) Билл теряет возможность проскочить зону обстрела (ибо хотя бы на один ход он должен стать под боем)
2) т.о. прочесываются все окопы
3) в последний окоп можно второй раз не стрелять :)
чистая эвристика, ибо после работы
1) Билл теряет возможность проскочить зону обстрела (ибо хотя бы на один ход он должен стать под боем)
2) т.о. прочесываются все окопы
3) в последний окоп можно второй раз не стрелять :)
чистая эвристика, ибо после работы
Бомбить в одну и ту же ячейку миллион раз.
Условие неясное.
"Сразу после того, как вы делаете выстрел, рядовой перебегает в соседний окоп" — непонятно, снаряд долетает до окопа моментально, или у солдата есть время, чтобы перебежать?
Если мы стреляем в окоп A, а солдат сидит в окопе A + 1 или A - 1, может ли он после выстрела перебежать в окоп A? Останется ли он при этом жив?
"Сразу после того, как вы делаете выстрел, рядовой перебегает в соседний окоп" — непонятно, снаряд долетает до окопа моментально, или у солдата есть время, чтобы перебежать?
Если мы стреляем в окоп A, а солдат сидит в окопе A + 1 или A - 1, может ли он после выстрела перебежать в окоп A? Останется ли он при этом жив?
По-моему, условие понятное. Подразумевается очерёдность ходов. То есть снаряды летят мгновенно, а в промежутках между выстрелами солдат совершает перебежки. Естественно, что возвращаться в поражённый окоп он может.
Солдат перебегает после выстрела. Впрочем, если он все время будет перебегать до выстрела, то его тоже можно убить.
Миром правят не законы математики а законы мерфи.
Если какость может может случиться - она случиться.
Именно в кваке как только вы вылетаете из-за поворота - получаете ракеты в лоб.
И именно по этому у вас никак не получается отомстить противнику - вы либо мажете, ну либо ракета в лоб :)
Итак дорогие мои математики не надо думать за сколько итераций вы замочите беднягу.
Главное выснить для кого работают законы мерфи.
Учитывая что бил НЕ отстреливается то
1.либо он над вами просто издевается, и вы НИКОГДА по нему не попадете
2.либо ракета в лом. С первой итерации.
Законы мерфи, законы жизни, законы обыкновеной подлости :)
Если какость может может случиться - она случиться.
Именно в кваке как только вы вылетаете из-за поворота - получаете ракеты в лоб.
И именно по этому у вас никак не получается отомстить противнику - вы либо мажете, ну либо ракета в лоб :)
Итак дорогие мои математики не надо думать за сколько итераций вы замочите беднягу.
Главное выснить для кого работают законы мерфи.
Учитывая что бил НЕ отстреливается то
1.либо он над вами просто издевается, и вы НИКОГДА по нему не попадете
2.либо ракета в лом. С первой итерации.
Законы мерфи, законы жизни, законы обыкновеной подлости :)
Задачка была на Днепропетровской областной олимпиаде, которую я благополучно выиграл. :)
Ответ: 1996.
printf("%d", 2*N-4);
for (i=2; i 1; i--)
printf(" %d", i);
Ответ: 1996.
printf("%d", 2*N-4);
for (i=2; i 1; i--)
printf(" %d", i);
Извините, исправил код.
printf("%d", 2*N-4);
for (i=2; i<N; i++)
printf(" %d", i);
for (i=N-1; i>1; i--)
printf(" %d", i);
printf("%d", 2*N-4);
for (i=2; i<N; i++)
printf(" %d", i);
for (i=N-1; i>1; i--)
printf(" %d", i);
А что вы делаете, если окопов всего 2? Не стреляете совсем? =)
Жаль, что вы на человеческом не разговариваете. Не все смогут оценить правильный ответ.
=)
Стреляю от 2-го до 999-го и обратно.
Стреляю от 2-го до 999-го и обратно.
шайтан!
я не учёл, что ему нельзя оставаться в одном окопе :)
я не учёл, что ему нельзя оставаться в одном окопе :)
Не совсем понятно. Допустим, Билл сидит в 3-м окопе, в стреляете во 2-й. Затем Билл переползает во 2-й, Вы идёте чёсом до 999-го, Билл ползёт за вами и, после выстрела в 999-й, переползает в него из 998-го, ситуация повторяется. Я что-то в условии пропустил?
по моему можно стрелять в каждый окоп па два раза (последовательно с 2 по 999), тогда Билл гарантировано будет смещаться от "линии огня", где и будет зажат
<возможно>
маятником от центра к краям, стреляя дважды в каждую клетку
вроде бы получается
</возможно>
вот только считать кол-во выстрелов вечером тяжко
маятником от центра к краям, стреляя дважды в каждую клетку
вроде бы получается
</возможно>
вот только считать кол-во выстрелов вечером тяжко
максимум 501 выстрелов
я прав ?
я прав ?
задача не решаема. Есть шанс что вообще не попадете никогда. Есть тока вероятность, причем очень облачная. Нехватает какого нибудь ограничительного условия для билла, например, если б он не мог перебежать в только что пораженный окоп.
Точно можно за 1996 ходов. Нужно стрелять в следующем порядке: 2, 3, 4, ..., 996, 997, 998, 998, 997, 996, ..., 4, 3, 2.
Можно строго доказать по индукции, но это муторно — проще нарисовать на бумажке.
Но вот оптимальность не очевидна.
Можно строго доказать по индукции, но это муторно — проще нарисовать на бумажке.
Но вот оптимальность не очевидна.
вероятность одного попадания из тысячи по теореме Бернулли примерно равна 0,368 и она мало изменяется при увеличении количества выстрелов, но, надо помнить что солдат реальный и после первой сотни он устанет бегать по окопам, после тысячи уснет (какая скорость стрельбы кстати, если выстрел в минуту, то 1000 выстрелов это 16 часов, не один марафонец не выдержит :) ) и тогда останется провести еще тысячу выстрелов чтобы наверняка его уснувшего убить :)
чудится мне, что это задача с турнира им. А.П.Савина журнала квант. рыбинск, 1999 год, 3-й матбой
Пока тока могу сказать, что если стрелять по два раза первый и последний окопы обстреливать не надо... =)
Удача! Я выстрелил и попал с первого раза!
А вот код, выстреливающий от начала и до конца по 2 раза подряд в один окоп:
(если кому интересно попробовать, после копипаста замените дефисы на два минуса)
Этот вариант предложил и
coldFlame
А вот код, выстреливающий от начала и до конца по 2 раза подряд в один окоп:
(если кому интересно попробовать, после копипаста замените дефисы на два минуса)
#!/usr/bin/php
define ('Rows', 1000);
echo "\nСидел ",
$Bill = rand (1, Rows);
$Weapon = 0;
$Strike = 0.5;
while (true) {
if (strike ())
break;
else
move_bill ();
};
echo "\nПоймал ", $Bill, "\nХодов ", $Weapon, "\n";
function strike () {
global
$Weapon,
$Strike,
$Bill;
++$Weapon;
$Strike += 0.5;
return (intval ($Strike) == $Bill ? true : false);
}
function move_bill () {
global $Bill;
$Bill == Rows ?
$Bill — :
$Bill == 1 ?
$Bill ++ :
rand (0, 1) ?
$Bill ++ :
$Bill — ;
}
Этот вариант предложил и
coldFlameНемного длиннее, чем у Oleksandr :)
Oleksandr
Ответ: 1998 - необходимое количество выстрелов для того, чтобы наверняка попасть в билла.
Решение: Стрелять необходимо следующим образом: начиная с первого окопа подряд до предпоследнего, (повторить 2 раза).
Обоснование: если при первом проходе при первом выстреле билл находиться в четном окопе, то попасть в него просто невозможно, т.к. он будет находиться в четном окопе когда мы будем стрелять по нечетному, и наоборот. Для этого необходим второй проход, который наверняка синхронизирует четность окопов. И в этом случае, билл уже никак не сможет уйти от попадания.
Теперь почему не надо стрелять в последний окоп. Дело в том, что убить билла в последнем окопе просто невозможно т.к. он может туда перебежать только из предпоследнего окопа, в который мы только что стрельнули.
Решение: Стрелять необходимо следующим образом: начиная с первого окопа подряд до предпоследнего, (повторить 2 раза).
Обоснование: если при первом проходе при первом выстреле билл находиться в четном окопе, то попасть в него просто невозможно, т.к. он будет находиться в четном окопе когда мы будем стрелять по нечетному, и наоборот. Для этого необходим второй проход, который наверняка синхронизирует четность окопов. И в этом случае, билл уже никак не сможет уйти от попадания.
Теперь почему не надо стрелять в последний окоп. Дело в том, что убить билла в последнем окопе просто невозможно т.к. он может туда перебежать только из предпоследнего окопа, в который мы только что стрельнули.
Прочитал "опкодов" вместо "окопов"...
с первого раза завалил, сидел в окопе N 567 засранец;)
А если начать стрелять с 1 го и так через один стрелять? То есть будет шанс, что он не сможет перебежать в другой окоп. В этом случае он нарушит закон своей вселенной и его уничтожат высшие силы.
Самый практичный вариат стрелять в один и тот же окоп пока задача не будет выполнена =)
Я знаю одну похожую задачку!
Кому первая понравилась, попробуйте эту!
Задача в целых числах (это важно!)
Невидимая лягушка начинает прыгать по дорожке с неизвестного места.
Убежать с дорожки она не хочет.
Дорожка бесконечна.
Лягушка прыгает в только в одну и ту же сторону.
Длина прыжка лягушки постоянна, но никак не ограничена.
Каждый раз, мы хотим ее замочить и стреляем базукой по выбранной координате. Если она была на этой координате, то мы попали, и лягушке - кирдык (уж это мы это заметим). Если нет, она снова прыгает. И так далее.
Вопрос: как убить лягушку за конечное число выстрелов?
Кому первая понравилась, попробуйте эту!
Задача в целых числах (это важно!)
Невидимая лягушка начинает прыгать по дорожке с неизвестного места.
Убежать с дорожки она не хочет.
Дорожка бесконечна.
Лягушка прыгает в только в одну и ту же сторону.
Длина прыжка лягушки постоянна, но никак не ограничена.
Каждый раз, мы хотим ее замочить и стреляем базукой по выбранной координате. Если она была на этой координате, то мы попали, и лягушке - кирдык (уж это мы это заметим). Если нет, она снова прыгает. И так далее.
Вопрос: как убить лягушку за конечное число выстрелов?
Если дорожка бесконечная, и, допустим, лягушка прыгает все время вперед, то куда бы мы не стрельнули, легушка может быть впереди выстрела как угодно далеко.
В условии нет ошибки? =)
В условии нет ошибки? =)
Абсолютно верно и тем не менее нет ошибки, я решил эту задачу. Просто мое решение этой задачи сильно отличается от идеи решения первой задачи. Надо про нее думать по-другому.
Можно слегка упростить и предположить, что лягушка может прыгать только в одну сторону принципе(только увеличивать свою координату, а не уменьшать).
Можно слегка упростить и предположить, что лягушка может прыгать только в одну сторону принципе(только увеличивать свою координату, а не уменьшать).
Наверно дорожка замкнута?
нет, дорожка прямая и бесконечная.
Есть решения для замкнутой дорожки, но если она прямая и бесконечная, то, похоже, что задача нерешаемая. Поскольку куда бы мы не шмальнули (например, координата N), у лягушки может оказаться в координате N+infinity, таким образом, задача заключается в том чтобы догнать лягушку огнем (если она движется от зоны обстрела) и одновременно не дать ей проскочить, если она движется навстречу. Одно другое исключает, так как пытаясь заградить лягушке движение на встречу (например, двумя выстрелами в одну точку) невозможно её догнать.
Сначала лягушка находилась в конкретном месте, потом она движется с конечной скоростью, значит она "достигнет" бесконечности через бесконечное число ходов. То есть её позиция после конкретного хода всегда конкретное число!
"Конкретное место" имеет смысл, если это известное место (координата N). Тогда все просто - первый выстрел делаем по N-1, второй по N+2, саёнара лягушка(:
Но если я правильно понял, имеется в виду конкретный известный отрезок прямой? То есть, известно, что лягушка вначале находится на отрезке (N, M), для наглядности (0, 1000). Алгоритм такой: по очереди стреляем в минус- и плюс-бесконечность (N-1, M+2, N-2, M+3...). Таким образом, лягушка в конце концов "догонит" точку обстрела.
Эксперимент. Отрезок (0,5) лягушка на координате 3, движется в плюс-бесконечность:
она фауст-патрон
4 -1
5 7
6 -2
7 8
8 -3
9 9
Но если я правильно понял, имеется в виду конкретный известный отрезок прямой? То есть, известно, что лягушка вначале находится на отрезке (N, M), для наглядности (0, 1000). Алгоритм такой: по очереди стреляем в минус- и плюс-бесконечность (N-1, M+2, N-2, M+3...). Таким образом, лягушка в конце концов "догонит" точку обстрела.
Эксперимент. Отрезок (0,5) лягушка на координате 3, движется в плюс-бесконечность:
она фауст-патрон
4 -1
5 7
6 -2
7 8
8 -3
9 9
Отличная задачка!
Лягушка движется равномерно и прямолинейно по целочисленной прямой, допустим, её скорость равна a, а координата в момент 0 равна b - т.е. уравнение движения лягушки - аt+b, где a и b - неизвестные целые числа.
Целочисленные точки на плоскости (a,b) можно пронумеровать, например, обходом по спирали: (0,0), (0,1), (1,1), (1,0), (1,-1), (0,-1), (-1,-1), (-1,0), (-1,1), (-1,2), (0,2) и т д
Формулу a(t), b(t) здесь писать не буду, так как поля слишком малы ;)
Ну а теперь тупо стреляем в момент t по точке a(t)*t+b(t)...
Лягушка движется равномерно и прямолинейно по целочисленной прямой, допустим, её скорость равна a, а координата в момент 0 равна b - т.е. уравнение движения лягушки - аt+b, где a и b - неизвестные целые числа.
Целочисленные точки на плоскости (a,b) можно пронумеровать, например, обходом по спирали: (0,0), (0,1), (1,1), (1,0), (1,-1), (0,-1), (-1,-1), (-1,0), (-1,1), (-1,2), (0,2) и т д
Формулу a(t), b(t) здесь писать не буду, так как поля слишком малы ;)
Ну а теперь тупо стреляем в момент t по точке a(t)*t+b(t)...
Чтобы понятнее было, программка:
void hunt() {
int x=0, y=0, t=0;
for(t=0;;++t) {
if(fire(x*t+y)) return; /* если попали, выход */
if (x+y>0) {
if (x>y) ++y; else --x;
} else {
if (x>=y) ++x; else --y;
}
}
}
непонятно, к чему тут плоскоть (a,b), если задача о "целочисленной прямой"? (:
Ага. Точно!
А если допустить упрощение, что a>0, b>0, то можно пронумеровать "вьющейся из нуля змейкой" и значит |N| = |N^2| = "алеф ноль".
А если допустить упрощение, что a>0, b>0, то можно пронумеровать "вьющейся из нуля змейкой" и значит |N| = |N^2| = "алеф ноль".
Какие вы злые :( Зачем кого-то убивать? Можно же, например, придумать такую же задачку про кроликов в непрозрачных клетках и доставать их оттуда.
Жестокость заразна, изначально, у меня предлагалось найти лягушку, а не убить))
Задача злая. Вспоминается анекдот.
Профессор расхаживает по аудитории:
- На веревке подвешен деревянный брусок массой 20кг, в него попадает пуля, массой 16 г. Вопрос - какова скорость пули, если после попадания брусок отклонился на 30 гра...
Замечает поднятую женскую руку:
- Да?
- А у вас нет чего-нибудь мирного, про орешки, белочек?
- Есть. Итак, на веревке висит белочка...
Профессор расхаживает по аудитории:
- На веревке подвешен деревянный брусок массой 20кг, в него попадает пуля, массой 16 г. Вопрос - какова скорость пули, если после попадания брусок отклонился на 30 гра...
Замечает поднятую женскую руку:
- Да?
- А у вас нет чего-нибудь мирного, про орешки, белочек?
- Есть. Итак, на веревке висит белочка...
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Kill Bill