Сегодня рассмотрим очередную задачу алгоритмического характера с сайта 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.
Если правильных ответов несколько, выведите любой.
|
1 |
2 |
|
1 2 |
3 2 1 2 |
- Можно сбросить 1 бомбу строго в 1 клетку
- Танки перемещаются в соседние клетки ТОЛЬКО при попадании. Плюс очевидное условие для крайних клеток поля, так как танки не могут выходить за пределы поля.
- Танк считается уничтоженным после 2-х попаданий.
С условием мы расправились, перейдем к цели. Задача: уничтожить все танки минимальным количеством бомб. Начинаем думать. Условие минимальной траты бомб сразу же отрезает вариант “коврового” бомбометания, ну или переводя на нашу игру последовательно сбросить бомбы с точки 1 до n и с n до 1. Возможно такие затраты на боеприпасы может позволить армия России, но не Слава на своем бомбардировщике. Очевидная стратегия нам не подходит, продолжаем искать оптимальную.
Углубимся в поведение танков, при попадании в них бомбы. Они перемещаются в ЛЮБУЮ соседнюю клетку. Например если танк стоит в клетке 3, то после попадания он переместиться в клетку 2 или 4. В какую точно мы не знаем. Если танк находится в клетке 4, то его маршрутом могут быть клетки 3 или 5. В общем случае танк в клетке k (k<n) направится в k-1 и k+1. Посмотрите внимательно на цифры, подумайте, ответ уже где-то рядом. Несмотря на то, что мы точно не знаем (оно и понятно, ведь с высоты полета бомбардировщика этого не увидеть) в какую именно точку переместиться танк со своей текущей, мы точно может выделить инвариант для нашего будущего алгоритма:
Если танк находится в “четной” позиции, то он переместиться только в “нечетную”. Если же танк находится в “нечетной” позиции, он переместиться в “четную”
И действительно, если вы посмотрите чуть выше на рисунок поля, то увидите эту зависимость. Благодаря этому замечанию предлагаю следующую стратегию: сначала сбрасываем бомбы во все четные позиции, танки из них перемещаются в нечетные. После бомбим нечетные позиции, танки перешедшие из четных уничтожены, а оставшиеся в живых перемещаются в четные. Снова бомбим четные позиции и все таки уничтожены. Вашему вниманию реализация нашего алгоритма на языке Java. Код лишен комментариев, и написан так, чтобы вы поняли суть его работы. Так же предлагаю в комментариях писать идеи своих оптимальных стратегий по уничтожению танков, а так же по улучшению реализации алгоритма.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Solution { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); int countBombs = 0; List<Integer> cells = new ArrayList<>(); int cell = 2; do { cells.add(cell); cell += 2; countBombs++; } while (cell <= n); cell = 1; do { cells.add(cell); cell += 2; countBombs++; } while (cell <= n); cell = 2; do { cells.add(cell); cell += 2; countBombs++; } while (cell <= n); System.out.println(countBombs); cells.forEach(c -> System.out.print(c + " ")); } } |
