Как стать автором
Обновить

Комментарии 114

Стрельнуть по последнему окопу, потом по первому, потом по предпоследнему и так далее, солдат будет смещаться к середине.
С таким же успехом можно слева направа стрелять, или справа налево.

Ну и вообще я немного не понял: если я не вижу ни Билла, ни его перебежек, ни результатов, то чтобы быть уверенным, что я его убил - мне стопудово надо выстрелить в каждый из 1000 окопов.
Хотя нет, здесь в любом случае подвох: может случится так, что я выстрелю в окоп, в который он после этого переместится. И то же самое с вариантом cst.
Проскочить легко. Стрельнул по, например, 995 - Билл был в 994 и после выстрела в это же укрытие и убежал (995). А потом побежал в >995 и там бегает. Слева направо все перестрелять уже лучше.
Пронумировать окопы числами от 1 до 1000. Предполагая, что в момент первого выстрела Билл сидит в окопе с нечетным номером. Мы стреляем в окоп номер 1. Если не попали, то Билл перешел в окоп с четным номером. Выстрелим во второй окоп. Если не попали, то Билл перешел в окоп с нечетным номером, не меньшим 3. Выстрелим в окоп номер 3, и так далее. Оттесняя Билла, мы таким образом поразим его. Если же вначале он находился в окопе с четным номером, то после тысячного выстрела он находится в окопе с четным номером. Теперь опять стреляем в 1000-й окоп, а потом в 999-й, 998-й, ... 1-й.
Если я правильно вас понял, то если он вначале находился в окопе с нечетным номером, то вторая тысяча выстрелов не нужна, так?
НЛО прилетело и опубликовало эту надпись здесь
Задача не имеет алгоритмического решения, потому что солдат может перебежать как в сторону выстрела, так и в противоположную, мы можем выстрелить в окоп, а на следующий ход он окажется в нём. Мы убьём его с вероятностью 1/1000, больше никаких данных нам не известно, оптимальным вариантом будет стрелять всё время в один окоп, но не факт, что рано или поздно его убьём.
Задача таки имеет алгоритмическое решение ибо Биллу запрещено отсиживаться. Не очень жизненная задачка, ну и что?
Ну и что, что ему запрещено отсиживаться, можно бесконечно стрелять, но так и не попасть в него. Задача имела бы решение, если бы за один ход мы могли сделать, хотя бы, 2 выстрела.
НЛО прилетело и опубликовало эту надпись здесь
А если он переместится в обстреленный окоп, после Вашего второго выстрела?
Только что придумал такое же решение независимо от вас)
и, к сожалению, оно не верное(
сколько бы мы не стреляли в одну ячейку, никто не гарантирует, что после последнего выстрела Билл, находящийся в соседней ячейке, не переместится в "зачищенную".
Имхо не переместится. Ему же запрещено отсиживаться, верно? Ну и вот, после первого выстрела он либо переберется в обстреливаемый окоп и погибнет, либо отойдет от него на один окоп и не сможет забраться в обстреливаемый из-за ограничения на длину перехода.
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Все можно сделать проще.
НЛО прилетело и опубликовало эту надпись здесь
после второй нет смысла стрелять в первую, потому что если он был там, то он должен переместится во вторую.
если все окопы от 1 до n зачищены, то бишь в них известно отсутствие билла, то n+1 и n+2 зачищаются тремя последовательными выстрелами "n+2, n+3, n+1"
то есть начало стрельбы такое: 2, 3, 1, 4, 5, 3...
так можно зачистить до 98, потом делаем два выстрела в 99 и биллу капец
НЛО прилетело и опубликовало эту надпись здесь
творчески облажался, такие три выстрела зачищают n+2 при условии зачищеных предыдущих n+1 окопов. Но билла это все равно не спасет.
ЗЫ выстрелов получается 998*3 + 2
НЛО прилетело и опубликовало эту надпись здесь
я уже написал о несостоятельности комментом ниже
ЗЫ высрел - это сильно
нет, таки идея о возможности сделать серию таких выстрелов, что в дальнейшем билл никак не доберется до какой-то части окопов, не проходит. Пусть даже есть серия, которая не оставляет биллов в первых n окопах. После такой серии билл вполне может сделать ход n-1 -> n, а значит, первые n не зачищены.
если все окопы от 1 до n зачищены, то бишь в них известно отсутствие билла
по условиям задачи неизвестно где Билл и убил или не убил
Похоже, что самым оптимальным решение будет стрелять рандомно. И задача получается на теорию вероятности)
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Похоже, что вы правы
НЛО прилетело и опубликовало эту надпись здесь
Логика довольно спорная, но решение правильное.
Такое впечатление, что ответ вы списали, а доказать не можете :)
НЛО прилетело и опубликовало эту надпись здесь
Согласен. Просто нужно внимательно вчитаться.
Имеется в виду, что сначала нужно бострелять нечетные окопы, а потом четные?
если изначально билл был в нечетном окопе, то после каждого четного выстрела он оказывается в нечетном окопе. При указанном методе прохождения окопов если Билла не убили до выстрела в 998 окоп (998 выстрел), то Билл должен обязательно находиться в 999 окопе. То есть первый проход будет состоять из 999 выстрелов.
Далее. Если изначально Билл сидел в четном окопе, обстрел начинаем со второго окопа (первый выстрел - второй окоп - число выстрелов на 1 меньше, чем номер окопа, в который производится выстрел). Если Билла там не было, то и в первом он оказаться не мог после выстрела, а переместился наверняка в нечетный окоп. То есть после каждого нечетного выстрела Билл будет в нечетном окопе (после четного - в четном). То есть, когда мы сделаем выстрел в окоп номер 998 (выстрел номер 997), то Билл (если мы не убили его до этого) наверняка будет находиться в 999 окопе (единственный оставшийся нечетный). Стреляем туды, получаем 998 выстрелов.
998+999 = 1997. А у товарища ниже получилось 1996. Судя по вему, олимпиада в Днепре проводилась в 1996 году ))
если в каждый окоп бить по два раза (1000*2 - 1 выстрел), то
1) Билл теряет возможность проскочить зону обстрела (ибо хотя бы на один ход он должен стать под боем)
2) т.о. прочесываются все окопы
3) в последний окоп можно второй раз не стрелять :)

чистая эвристика, ибо после работы
НЛО прилетело и опубликовало эту надпись здесь
Почему вы всё время пишете "высрел"? Для справки: выстрел
НЛО прилетело и опубликовало эту надпись здесь
Ваш второй шедевр написания слов почему-то наводит на мысль о возможном заболевании насморком.
Бомбить в одну и ту же ячейку миллион раз.
НЛО прилетело и опубликовало эту надпись здесь
Условие неясное.

"Сразу после того, как вы делаете выстрел, рядовой перебегает в соседний окоп" — непонятно, снаряд долетает до окопа моментально, или у солдата есть время, чтобы перебежать?

Если мы стреляем в окоп A, а солдат сидит в окопе A + 1 или A - 1, может ли он после выстрела перебежать в окоп A? Останется ли он при этом жив?
НЛО прилетело и опубликовало эту надпись здесь
По-моему, условие понятное. Подразумевается очерёдность ходов. То есть снаряды летят мгновенно, а в промежутках между выстрелами солдат совершает перебежки. Естественно, что возвращаться в поражённый окоп он может.
Солдат перебегает после выстрела. Впрочем, если он все время будет перебегать до выстрела, то его тоже можно убить.
Миром правят не законы математики а законы мерфи.
Если какость может может случиться - она случиться.
Именно в кваке как только вы вылетаете из-за поворота - получаете ракеты в лоб.
И именно по этому у вас никак не получается отомстить противнику - вы либо мажете, ну либо ракета в лоб :)

Итак дорогие мои математики не надо думать за сколько итераций вы замочите беднягу.
Главное выснить для кого работают законы мерфи.
Учитывая что бил НЕ отстреливается то
1.либо он над вами просто издевается, и вы НИКОГДА по нему не попадете
2.либо ракета в лом. С первой итерации.
Законы мерфи, законы жизни, законы обыкновеной подлости :)
Задачка была на Днепропетровской областной олимпиаде, которую я благополучно выиграл. :)


Ответ: 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);
А что вы делаете, если окопов всего 2? Не стреляете совсем? =)
В формулировке автора количество окопов дано и равно 1000.
В самой задаче частные случаи конечно-же рассмотрены.
Когда 2 окопа, то дважды стреляю в один из них. =)
Жаль, что вы на человеческом не разговариваете. Не все смогут оценить правильный ответ.
=)
Стреляю от 2-го до 999-го и обратно.
шайтан!
я не учёл, что ему нельзя оставаться в одном окопе :)
Не совсем понятно. Допустим, Билл сидит в 3-м окопе, в стреляете во 2-й. Затем Билл переползает во 2-й, Вы идёте чёсом до 999-го, Билл ползёт за вами и, после выстрела в 999-й, переползает в него из 998-го, ситуация повторяется. Я что-то в условии пропустил?
это задача про чёт-нечет, чтобы гарантированно его убить нужно чесать в два прохода с первого по последний, причём в последний дважды бить, перед тем как пойти обратно.
НЛО прилетело и опубликовало эту надпись здесь
ага, прострелял, стало понятно, главное дважды в предпоследний тогда и его ловим и 4 выстрела экономим
по моему можно стрелять в каждый окоп па два раза (последовательно с 2 по 999), тогда Билл гарантировано будет смещаться от "линии огня", где и будет зажат
Было опровергнуто выше: если Вы стреляете по N-му окопу, а Билл в N+2'м окопе, то за два выстрела он как раз переместится к N-му окопу, а Вы перейдете на N+1'й.
<возможно>
маятником от центра к краям, стреляя дважды в каждую клетку
вроде бы получается
</возможно>
вот только считать кол-во выстрелов вечером тяжко
Какой смысл стрелять дважды? Например вы стреляете в клетку 8,а солдат в клетке 6. Выстрел - он в 7. Выстрел, он в 8. вы выстрелили 2 раза а он в 8 клетки и жив здоров. Будет гулять по траектории 1-8 клетка пока вы будете по два раза оставшуюся тысячу бомбить.
если маятником простреливать все клетки, то никуда он не убежит, вот только не оптимально это
мда, хрень написал я :( согласен
максимум 501 выстрелов

я прав ?
задача не решаема. Есть шанс что вообще не попадете никогда. Есть тока вероятность, причем очень облачная. Нехватает какого нибудь ограничительного условия для билла, например, если б он не мог перебежать в только что пораженный окоп.
НЛО прилетело и опубликовало эту надпись здесь
условие есть, читайте внимательнее :)
Точно можно за 1996 ходов. Нужно стрелять в следующем порядке: 2, 3, 4, ..., 996, 997, 998, 998, 997, 996, ..., 4, 3, 2.

Можно строго доказать по индукции, но это муторно — проще нарисовать на бумажке.

Но вот оптимальность не очевидна.
Ой, то есть так: 2, 3, 4, ..., 997, 998, 999, 999, 998, 997, ..., 4, 3, 2
Да, я к такому же выводу пришел )
Только в конце надо два раза по 2 стрелять, иначе, если он перемещается на окоп впереди от выстрела, то стреляй последний раз по второму окопу, Билл переместится из первого окопа во второй, где мы его и прибьем вторым ударом по 2.
Вот иллюстрация для случая 10-ти окопов:
http://img161.imageshack.us/img161/2341/solutionnu4.png

Черными клетками обозначены наши выстрелы, крестиками — окопы, в которых не может оказаться противник.
вероятность одного попадания из тысячи по теореме Бернулли примерно равна 0,368 и она мало изменяется при увеличении количества выстрелов, но, надо помнить что солдат реальный и после первой сотни он устанет бегать по окопам, после тысячи уснет (какая скорость стрельбы кстати, если выстрел в минуту, то 1000 выстрелов это 16 часов, не один марафонец не выдержит :) ) и тогда останется провести еще тысячу выстрелов чтобы наверняка его уснувшего убить :)
НЛО прилетело и опубликовало эту надпись здесь
если солдат не передвигается
чудится мне, что это задача с турнира им. А.П.Савина журнала квант. рыбинск, 1999 год, 3-й матбой
Пока тока могу сказать, что если стрелять по два раза первый и последний окопы обстреливать не надо... =)
Удача! Я выстрелил и попал с первого раза!
А вот код, выстреливающий от начала и до конца по 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 :)
Ответ: 1998 - необходимое количество выстрелов для того, чтобы наверняка попасть в билла.
Решение: Стрелять необходимо следующим образом: начиная с первого окопа подряд до предпоследнего, (повторить 2 раза).
Обоснование: если при первом проходе при первом выстреле билл находиться в четном окопе, то попасть в него просто невозможно, т.к. он будет находиться в четном окопе когда мы будем стрелять по нечетному, и наоборот. Для этого необходим второй проход, который наверняка синхронизирует четность окопов. И в этом случае, билл уже никак не сможет уйти от попадания.
Теперь почему не надо стрелять в последний окоп. Дело в том, что убить билла в последнем окопе просто невозможно т.к. он может туда перебежать только из предпоследнего окопа, в который мы только что стрельнули.
По первому окопу стрелять не надо. Можно свести к четырём окопам и проверить:
2, 3, 3, 2 - так или иначе снаряд башка попадет... =)
Точно, тогда поправка. 1996 стрелять в этом случае надо от 2 до N-1, от N-1 до 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
Отличная задачка!

Лягушка движется равномерно и прямолинейно по целочисленной прямой, допустим, её скорость равна 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| = "алеф ноль".
Более того, |N|=|Z^2| ;) А у тебя было кардинально другое решение?
Нет. Точно такое же решение))
Остается лишь заметить, что также верно, что |N| = |Q| ))
Какие вы злые :( Зачем кого-то убивать? Можно же, например, придумать такую же задачку про кроликов в непрозрачных клетках и доставать их оттуда.
Жестокость заразна, изначально, у меня предлагалось найти лягушку, а не убить))
Задача злая. Вспоминается анекдот.
Профессор расхаживает по аудитории:
- На веревке подвешен деревянный брусок массой 20кг, в него попадает пуля, массой 16 г. Вопрос - какова скорость пули, если после попадания брусок отклонился на 30 гра...
Замечает поднятую женскую руку:
- Да?
- А у вас нет чего-нибудь мирного, про орешки, белочек?
- Есть. Итак, на веревке висит белочка...
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории