Уничтожаем танки! Разбор задачи “Слава и Танки”

Сегодня рассмотрим очередную задачу алгоритмического характера с сайта Codeforces. Не буду томить вас, поэтому сразу условие:

Слава играет в свою любимую игру «Peace Lightning». Сейчас он играет на бомбардировщике на одной специфической карте.

Более формально, карта представляет из себя клетчатое поле 1 × n, клетки которого пронумерованы от 1 до n, в каждой клетке может находиться один или несколько танков. Слава не знает количество танков и их расположение, так как летит очень высоко, но при этом он может сбросить бомбу в любую клетку. Все танки, находящиеся в этой клетке, получат урон.

Если танк получает урон в первый раз, то он мгновенно перемещается в одну из соседних клеток (танк из клетки номер n может переместиться только в клетку номер n - 1, танк из клетки номер 1 может переместиться только в клетку номер 2); если же танк получил урон второй раз, он считается уничтоженным и никогда больше не движется. За время игры танки перемещаются только тогда, когда в них попали в первый раз, самостоятельно они не перемещаются.

Помогите Славе гарантированно уничтожить все танки, использовав минимальное число бомб.

Входные данные

В единственной строке содержится одно целое положительное число n (2 ≤ n ≤ 100 000) — размер карты.

Выходные данные

В первой строке выведите число m — минимальное количество бомб, которое потребуется, чтобы уничтожить все танки.

Во второй строке выведите m чисел k1, k2, …, km. Число ki обозначает, что i-ю бомбу нужно бросить в клетку номер ki.

Если правильных ответов несколько, выведите любой.

Примеры
входные данные

выходные данные

Пойдем по порядку и разберем условие. Как обычно в формулировках подобных задач много воды, которая способна сбить мысль и отвести фокус внимания от сути. Хотя от этого даже интереснее. У нас есть только число n – верхняя граница множества [1,n]. Это наше игровое поле с клетками, в каждой из которых находится любое количество танков. Оно выглядит так: (хотя с высоты полета бомбардировщика думаю что не факт)
Перед нами пример поля размером от 1 до 6. Представили, двигаемся дальше. Разберем правила игры:
  1. Можно сбросить 1 бомбу строго в 1 клетку
  2. Танки перемещаются в соседние клетки ТОЛЬКО при попадании. Плюс очевидное условие для крайних клеток поля, так как танки не могут выходить за пределы поля.
  3. Танк считается уничтоженным после 2-х попаданий.

С условием мы расправились, перейдем к цели. Задача: уничтожить все танки минимальным количеством бомб. Начинаем думать. Условие минимальной траты бомб сразу же отрезает вариант “коврового” бомбометания, ну или переводя на нашу игру последовательно сбросить бомбы с точки 1 до n и с n до 1. Возможно такие затраты на боеприпасы может позволить армия России, но не Слава на своем бомбардировщике. Очевидная стратегия нам не подходит, продолжаем искать оптимальную.

Углубимся в поведение танков, при попадании в них бомбы. Они перемещаются в ЛЮБУЮ соседнюю клетку. Например если танк стоит в клетке 3, то после попадания он переместиться в клетку 2 или 4. В какую точно мы не знаем. Если танк находится в клетке 4, то его маршрутом могут быть клетки 3 или 5. В общем случае танк в клетке k (k<n) направится в k-1 и k+1. Посмотрите внимательно на цифры, подумайте, ответ уже где-то рядом. Несмотря на то, что мы точно не знаем (оно и понятно, ведь с высоты полета бомбардировщика этого не увидеть) в какую именно точку переместиться танк со своей текущей, мы точно может выделить инвариант для нашего будущего алгоритма:

Если танк находится в “четной” позиции, то он переместиться только в “нечетную”. Если же танк находится в “нечетной” позиции, он переместиться в “четную”

И действительно, если вы посмотрите чуть выше на рисунок поля, то увидите эту зависимость. Благодаря этому замечанию предлагаю следующую стратегию: сначала сбрасываем бомбы во все четные позиции, танки из них перемещаются в нечетные. После бомбим нечетные позиции, танки перешедшие из четных уничтожены, а оставшиеся в живых перемещаются в четные. Снова бомбим четные позиции и все таки уничтожены. Вашему вниманию реализация нашего алгоритма на языке Java. Код лишен комментариев, и написан так, чтобы вы поняли суть его работы. Так же предлагаю в комментариях писать идеи своих оптимальных стратегий по уничтожению танков, а так же по улучшению реализации алгоритма.

Оставить комментарий:

Ваш email не будет опубликован.