Chuck Norris

A task from codingame.com

Task

Binary with 0 and 1 is good, but binary with only 0, or almost, is even better! Originally, this is a concept designed by Chuck Norris to send so called unary messages.

Write a program that takes an incoming message as input and displays as output the message encoded using Chuck Norris’ method.

Here is the encoding principle:

  • The input message consists of ASCII characters (7-bit)
  • The encoded output message consists of blocks of 0
  • A block is separated from another block by a space
  • Two consecutive blocks are used to produce a series of same value bits (only 1 or 0 values):
    — First block: it is always 0 or 00. If it is 0, then the series contains 1, if not, it contains 0
    — Second block: the number of 0 in this block is the number of bits in the series

Input

Line 1: the message consisting of N ASCII characters (without carriage return)

Output

The encoded message

Tests

[su_table]

Input
Output
C 0 0 00 0000 0 00
CC 0 0 00 0000 0 000 00 0000 0 00
%

00 0 0 0 00 00 0 0 00 0 0 0
Hello

0 0 00 00 0 0 00 000 0 00 00 00 0 0 00 0 0 000 00 0 0 00 00 00 0 00 00 0 0 00 00 00 0 00 00 0 0 0000

[/su_table]

Code

Solution

First, we create a so called mask, which takes the symbol, transform it to a binary 7-bit number and return string. Then we add this string to another one, while transforming every symbol in the cin.  Then we create a loop, where we check either symbol is 0 or 1 and add them to another string in the right order according to the encoding principle. In order to escape mistakes with ‘1’ in the first loop, we create another loop, where we change all ‘1’ to ‘0’.

 

ASCII ART

Task

In stations and airports you often see this type of screen:

Have you ever asked yourself how it might be possible to simulate this display on a good old terminal? We have: with ASCII art!

Your mission is to write a program that can display a line of text in ASCII art in a style you are given as input.

Input

Line 1: the width L of a letter represented in ASCII art. All letters are the same width.
Line 2: the height H of a letter represented in ASCII art. All letters are the same height.
Line 3: the line of text T, composed of N ASCII characters.
Following H lines: the string of characters ABCDEFGHIJKLMNOPQRSTUVWXYZ? Represented in ASCII art.

[latex]0 < [/latex] L[latex] < 30[/latex]
[latex]0 < [/latex] H[latex] < 30[/latex]
[latex]0 < [/latex] N[latex] < 200[/latex]

Output

The text T in ASCII art.
The characters a to z are shown in ASCII art by their equivalent in upper case.
The characters that are not in the intervals [a-z] or [A-Z] will be shown as a question mark in ASCII art.

Tests

Input Output
1
1
Encoding using ASCII? Hah!
?ZYXWVUTSRQPONMLKJIHGFEDCBA
WNYMXSNUAGISNUA?IYSSAAT?TA

Codes of the program

Solution of the task

After saving the string, we can convert the task to «semi-stream processing». After we read and save the first line of ASCII characters into alphabet array, we start to print the tops of the ASCII letters. Then the same procedure is repeated on the following lines, and new parts of ASCII letters are read over the old ones into alphabet.

Links

There is no Spoon — Episode 1

Task

The Goal

The game is played on a rectangular grid with a given size. Some cells contain power nodes. The rest of the cells are empty.

The goal is to find, when they exist, the horizontal and vertical neighbors of each node.

Rules

To do this, you must find each [latex]\left( x1, y1 \right)[/latex] coordinates containing a node, and display the [latex]\left(x2, y2\right)[/latex] coordinates of the next node to the right, and the [latex]\left(x3, y3\right)[/latex] coordinates of the next node to the bottom within the grid.

If neighbor does not exist, you must output the coordinates [latex]\left(-1, -1\right)[/latex] instead of [latex]\left(x2, y2\right)[/latex] and/or [latex]\left(x3, y3\right)[/latex].

You lose if:

  • You give an incorrect neighbor for a node.
  • You give the neighbors for an empty cell.
  • You compute the same node twice.
  • You forget to compute the neighbors of a node.

Game input

The program must first read the initialization data from standard input. Then, provide to the standard output one line per instruction.

Initialization input

Line 1: one integer width for the number of cells along the x axis.

Line 2: one integer height for the number of cells along the y axis.

Next height lines: A string line containing width characters. A dot . represents an empty cell. A zero 0 represents a cell containing a node.

[latex]0 <[/latex] width[latex]\le 30[/latex]
[latex]0 <[/latex] height[latex]\le 30[/latex]

Output for one game turn

One line per node. Six integers on each line: x1 y1 x2 y2 x3 y3
Where:

  • ( x1, y1) the coordinates of a node.
  • ( x2, y2) the coordinates the closest neighbor on the right of the node.
  • ( x3, y3) the coordinates the closest bottom neighbor.

[latex]0 \le[/latex] x1[latex]<[/latex] width
[latex]0 \le[/latex] y2[latex]<[/latex] height
[latex]-1 \le[/latex] x2, x3[latex]<[/latex] width
[latex]-1 \le[/latex] y2, y3[latex]<[/latex] height
Alloted response time to first output line [latex]\le 1[/latex]s.
Response time between two output lines [latex]\le 100[/latex]ms.

Tests

Input Output
2 2
00
0.
0 0 1 0 0 1
1 0 -1 -1 -1 -1
0 1 -1 -1 -1 -1
4 4
.0..
.000
000.
..0.
1 0 -1 -1 1 1
1 1 2 1 1 2
2 1 3 1 2 2
3 1 -1 -1 -1 -1
0 2 1 2 -1 -1
1 2 2 2 -1 -1
2 2 -1 -1 2 3
2 3 -1 -1 -1 -1

The code of the program

Solution of the task

First of all, we must pay attention, that we have to find the closest neighbor. It doesn’t mean, that if there is no neighbor on adjacent cells, then the answer will be negative, because the neighbor may be further. This leads to the fact, that the task can not be completed without memorization of the whole list of cells.

After storing every string in array, the task becomes simple: we go using the cycle through every cell, and if the cell contains a node, then we launch two cycles from it in two directions (to the right and to the bottom), and assume there are no neighbors with assigning value -1 to both variables ansX and ansY. If there will be no nodes found, the value will remain the same, otherwise variables will take values of the node coordinates. In any case, the result will be correct.

This process is optimized by usage of the following: the [latex]x[/latex] coordinate of the closest right neighbor (or the value of width) is saved in a variable x2. Whether we find a neighbor or no, we can start the further horizontal search right from the coordinate x2, because empty cells must be skipped anyway.

Links

Разбор Proggy-Buggy Contest

5 декабря компанией DataArt проводилась международная  юмористическая олимпиада по программированию Proggy-Buggy Contest.

Задачи на ней не были сложными, но решать их нужно было очень быстро: на 13 задач отводилось 42 минуты времени.

В Одесском офисе DataArt было рекордное количество команд-участинков среди всех городов, принимавших мероприятие. Среди участников была команда ONU_Rabid_Pandas (Марченко, Илларионова, Вустянюк), которая подготовила разбор задач соревнования:

Условия

Разбор

Пожалуйста, сообщайте в комментариях обо всех найденных очепятках и непонятках. Мы исправим и ответим на вопросы.

Horse-racing Duals

Horses2

Задача

Рассмотрим последнюю задачу уровня Easy с сайта codingame.com. Некоторое количество лошадей участвует в скачках и у каждой есть некая характеристика, выраженная целым числом. Формат скачек — парные заезды — и организаторы хотят, чтобы в заезде участвовали две лошади, различие между которыми (т.е. разность их характеристик) минимальна.

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

Первая строка: число  n  — количество лошадей.

Следующие  n  строк — в каждой указано одно целое число — характеристика соответствующей лошади.

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

Наименьшая положительная разность характеристик.

Решение

Пусть задана конечная последовательность целых чисел  a. В исходной формулировке задачи, без каких-либо оптимизаций, от нас требуют найти  [latex] D = \min_{1 \leq i < j \leq n} \left| a_{i} — a_{j} \right|[/latex]. Если решать задачу  в лоб, нам понадобятся два цикла: один пробегает все значения по   i, а другой — все значения по  [latex] j > i [/latex]. На каждом шаге внешнего цикла будет проделано  [latex] n — i [/latex] шагов внутреннего. Итого получаем приблизительную оценку сложности такого алгоритма:  [latex] n\left( n — i \right)[/latex], что асимптотически эквивалентно  [latex] n^2 [/latex].

Оказывается, можно решить задачу «проще». Как утверждают авторитетные источники, сложность встроенного в стандартную библиотеку алгоритма сортировки составляет  [latex] O(n \cdot \log \left( n \right) [/latex], что при больших значениях  n  лучше, чем  [latex] n^2 [/latex]. Пусть  b  —  конечная последовательность, в которой элементы последовательности  a  расположены по возрастанию. Поскольку множество значений у этих последовательностей одинаково, имеем: [latex] D = \min_{1 \leq i < j \leq n} \left| a_{i} — a_{j} \right| [/latex]. Однако нам уже не нужен двойной цикл. Благодаря монотонному возрастанию последовательности  b,  при любом   [latex] i [/latex]   имеем  [latex] b_{i+1} — b_{i} > 0 [/latex] и при любых  [latex] i,j [/latex]  если  [latex]i < j[/latex], то  [latex] b_{j} — b_{i} \geq b_{i+1} — b_{i}[/latex].

Значит, [latex] D = min_{1 \leq i \leq n} \left( b_{i+1} — b_{i} \right) [/latex], а эту проверку можно провести за  n  действий. Таким образом, новая сложность составит примерно  [latex] n \cdot log(n) + n [/latex], что асимптотически эквивалентно  [latex] n \cdot log(n) [/latex]  и, значит, для больших значений лучше «безоптимизационного» подхода.

Код на С++

Код на Java

Подтверждение

Horses3

Horses

 

Heat Detector

Задача

Бэтмен

Речь пойдёт о первой задаче уровня Medium на сайте  codingame.com. По сюжету Бэтмен должен отыскать бомбу в многоэтажном доме. Ему известно количество этажей  и количество окон на каждом этаже. Ему также известно направление, в котором находится бомба. Бэтмену нужно как можно быстрее её найти. Процесс поиска выглядит следующим образом: Бэтмен заглядывает в какое-то окно и затем на каждом игровом шаге он перепрыгивает в какое-то другое окно — так до тех пор, пока не отыщет бомбу.

Инциализация

В первой строке заданы числа  W  и  H  —  соответственно количество окон на каждом этаже (оно для всех этажей одно и то же) и количество этажей в здании.

Во второй строке задано количество переходов, которые Бэтмен может сделать до взрыва. Это число нам не понадобится.

В третьей строке заданы два целых числа — x  и  y  —  координаты окна, с которого Бэтмен начинает свой поиск. Первая координата задаёт номер окна на этаже (начиная с нуля), вторая — номер этажа (также начиная с нуля). Нулевой этаж — верхний, нулевое окно на каждом этаже — левое.

Входные данные для одного игрового хода

Одна строка  DIR, задающая направление, в котором следует искать бобму:

Бэтмен3

Выходные данные для одного игрового хода

Одна строка, в которой заданы два целых числа, разделённых одним пробелом, — координаты окна, которое должен проверить Бэтмен.

Решение

Игровой цикл продолжается до тех пор, пока либо бобма взорвётся, либо Бэтмен её обезвредит. Т.е. либо нам не хватит шагов, либо мы угадаем обе координаты. На каждом шаге игрового цикла будем перемещать Бэтмена с учётом направления, в котором находится бомба, и при этом «сжимать» область игрового поля, в которой он может прыгать. Однажды этот промежуток ужмётся в ондну точку — ту самую, абсцисса которой соответствует координате бомбы.

Обозначим координаты бобмы через  BX  и  BY  и введём четыре вспомогательных параметра: l, r, u, b  —  «динамические границы», левая, правая, верхняя и нижняя соответственно. Идея состоит в том, чтобы на каждом шаге выполнялись неравенства  [latex] l \leq BX \leq r [/latex]  и  [latex] d \leq By \leq u [/latex].

Зададим начальные значения [latex] l = 0 [/latex],  [latex] r = W — 1 [/latex],   [latex] u = 0 [/latex]  и  [latex] d = H — 1 [/latex]. Тогда после инициализации игры указанные выше неравенства справедливы тривиальным образом (это просто заданные по условию ограничения на возможные значения  Bx  и  By). Переходим к первому ходу, он же первый шаг игрового цикла. Мы считали строку  DIR, указавшую нам направление, в котором следует искать бомбу.

Для оси абсцисс имеет место один из трёх случаев:

  • [latex] BX < x [/latex] (если DIR — одна из строк «L», «DL», «UL»). В этом случае справедливо неравенство  [latex] l \leq BX \leq x — 1 [/latex]. Положим  [latex] r = x — 1 [/latex]. Тогда будет справедливо неравенство  [latex] l \leq BX \leq r [/latex]. Отметим, что новый промежуток  [latex] l \ldots r [/latex]  в этом случае будет на единицу короче предыдущего.
  • [latex] BX = x [/latex] (если DIR — одна из строк  «U»  и  «B»). В этом случае всё хорошо.
  • [latex] BX > x [/latex] (если  DIR — одна из строк  «R», «DR», «UR»). В этом случае справедливо неравенство  [latex] x + 1 \leq BX \leq r [/latex]. Положим  [latex] l = x + 1 [/latex]. Тогда будет справедливо неравенство  [latex] l \leq BX \leq r [/latex].  Отметим, что новый промежуток  [latex] l \ldots r [/latex]  в этом случае будет на единицу короче предыдущего.

Если  [latex] BX = x [/latex], то всё хорошо — мы уже знаем абсциссу бомбы. А что делать в остальных двух случаях? Как эффективнее искать бомбу? Можно просматривать все значения из промежутка [latex] l \ldots r [/latex] поочерёдно слева направо, но что если бомба расположена у правого края? Можно просматривать все значения поочерёдно справа налево, но что если координата бомбы равна  l, а промежуток большой? Остаётся один естественный вариант — «прыгнуть» в середину промежутка, т.е. в точку с абсциссой  [latex] \left \lfloor \frac{l + r}{2} \right \rfloor[/latex]. На следующем шаге цикла надо повторить приведённые выше рассуждения, изменения границ и «прыжок». Таким образом, либо мы случайно наткнётся на абсциссу бомбы, либо промежуток [latex] l .. r [/latex], уменьшаясь каждый раз на одно число,  ужмётся в точку, т.е. мы тоже найдём абсциссу бомбы! Осталось применить те же рассуждения к ординате бомбы. Надеюсь, код ответит на оставшиеся вопросы.

Код

Код на Java

 

Подтверждение

Бэтмен2

Heat Detector

Conway Sequence


Conway Sequence


Conway Sequence — седьмая по счету игра уровня сложности medium, основанная на свойствах последовательности Конвея (правильнее было бы назвать её look-and-say sequence). Последовательность рекурсивна, но в более широком понимании: предыдущая строка полностью характеризует текущую. Изучение последовательности Конвея приводит к занятным открытиям, включая так называемую космологическую теорему, но лучше меня об этом расскажет лично Джон Хортон Конвей. Но начиная с определенного номера получить новую строку становится непросто даже на бумаге. Авторы просят нас помочь математикам и составить программу, которая по заданным значениям выводит определенную строку последовательности.

Алгоритм вывода следующей строки уместно проиллюстрировать на примере:
Sequence seed: 3
Строка №1 имеет вид: «3»
В ней записана одна тройка.
Следовательно, строка №2 запишется как: «1 3».
В ней записаны одна единица и одна тройка
Следовательно, строка №3 выглядит так: «1 1 1 3».
В ней содержатся три единицы и одна тройка,
потому строка №4 имеет вид: «3 1 1 3» et cetera.

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

  • [latex]R[/latex] — основание последовательности («sequence seed»)
  • [latex]L[/latex] — номер последней строки

Выходные данные:
Строка №[latex]L[/latex], все элементы которой разделены пробелами.

Код программы:

Алгоритм решения:

  1. Начать просмотр содержимого строки слева направо. Если подряд идут несколько одинаковых чисел, запомнить их количество.
  2. Если следующее число в строке отлично от предыдущего записать в новую строку количество повторов предыдущего числа и само это число.
  3. Если строка подошла к концу, дописать к новой строке количество повторений последнего элемента и сам этот элемент.
  4. Если номер полученной строки меньше [latex]L[/latex], повторить процедуру для новой строки.

Эффективность алгоритма:
Программа успешно проходит все данные тесты.

conway_result

Технические детали реализации:

  • Для удобства работы с строками произвольной длины использована библиотека vector, в частности функции .clear(), .push_back(), .size(), .swap()
  • Так как принципиальное значение имеют только три факта: значение текущего элемента последовательности, значение предыдущего и количество подряд идущих одинаковых элементов, стоящих за ним — достаточно завести три переменные типа int для их хранения.
  • На каждой итерации вектор [latex]next\_line[/latex] копируется в вектор [latex]current\_line[/latex] и очищается. Переменной [latex]previous[/latex] присваивается значение первого элемента вектора [latex]current\_line[/latex].

Puzzle — Temperatures

Задача взята с этого сайтаБезымянный

В этой задаче необходимо проанализировать значения температуры, дабы найти ближайшее к нулю.

Ввод:

Строка 1: [latex]N[/latex], количество значений температуры.

Строка 2: собственно говоря, сами значения температуры, выраженные целыми числами в диапазоне от -273 до 5526.

Вывод:

Вывести 0 в том случае, если не введено ни одного значения.

Если введено хотя бы одно, то вывести на экран значение ближайшее к 0. Отметить, что если есть 2 значения, одинаково близкие к нулю, но с разными знаками, то на экране должно отобразиться положительное число.

[latex]N[/latex] Ввод Вывод Комментарий.
Простой тест 5 1 -2 -8 4 5 1 Пройден.
Сложный тест 10 -5 -4 -2 12 -40 4 2 18 11 5 2 Пройден.
Без температур 0 0 Пройден.
Дополнительный тест 14 7 -10 13 8 4 -7 -12 -3 3 -9 6 -1 -6 7 -1 Пройден.

Код программы (C++):

Для первого теста нужно было найти ближайшее к нулю значение, когда все числа по модулю были попарно различными. Для этого достаточно было завести переменную типа int и положить в неё значение, которое заведомо больше всех возможных (это 5527, так как по условию задачи значения температур не выходят за пределы [-273;5527]). И в цикле сделать проверку того, что же больше — модуль нашего текущего значения или модуль только что введённого.

[su_spoiler title=»Задача 1.» icon=»arrow-circle-2″]

[/su_spoiler]

Для того, чтобы пройти второй тест необходимо было ввести такое условие, при котором отметалось бы отрицательное значение температуры при наличии такого же по модулю положительного. Для этого мы сравниваем модуль текущего значения температуры со значением введённым (уже не по модулю, так как нам нужно убрать отрицательные числа), и если они равны, то текущее ближайшее значение изменится на положительное, если до этого оно было с минусом.

[su_spoiler title=»Задача 2.» icon=»arrow-circle-2″]

[/su_spoiler]

Java:

И для последней задачи, конечно, достаточно было ввести условие, что [latex]N[/latex] не равно нулю. В противном случае программа выведет на экран 0. Конечный код указан первым.

 

Skynet: the Virus

Skynet


SKYNET FINALE — LEVEL 1


Вирус

Los Angeles 2029 — Resistance HQ — Review of facts:

В минувшую субботу, сотни отважных бойцов рисковали своей жизнью, чтобы уничтожить Skynet. СТОП

Используя зараженных мото-терминаторов, им удалось привить смертельный вирус к Skynet. СТОП

Проблема: Skynet борется. СТОП

Джон, ещё раз,  нам нужна ваша помощь. СТОП


Задача:

У нас в распоряжении целый граф узлов. Некоторые из них названы шлюзами. Шлюзы надо защищать от злобного Skynet агента, который способен передвигаться по связям между узлами. Способ защиты очень прост: каждый ход можно навсегда заблокировать одну связь, тем самым, через некоторое количество ходов, полностью закрыть шлюз от нежелательных гостей.

Первичная инициализация:

Первая строка: 3 целых числа N L E

  • N — Количество узлов, включая шлюзы
  • L — Количество связей
  • E — Количество шлюзов

Следующие L строк: по два числа на строку (N1, N2), означающие, что между узлами с индексами N1 и N2 присутствует связь.
Следующие E строк: по одному числу на строку, означающие индексы шлюзов.

Инициализация за каждый игровой тик:

Одно число — индекс связи, на которой находится Skynet агент.

Вывод за каждый игровой тик:

Одна строка в которой присутствует два числа C1 и C2. C1 и C2 — это индексы двух узлов, между которыми мы хотим заблокировать переход. Если между ними нет связи, возникает ошибка. В конце строки обязательно должен стоить символ перехода на новую строку.

Программа:

Идея решения: Всё предельно просто: Если агент находится вблизи одного из шлюзов, закрываем переход между агентом и этим шлюзом. Иначе закрываем переход между шлюзом и ближайшим узлом.

Переходы между узлами занесены в двумерный массив N1, далее этот массив был своеобразно отсортирован (для удобства). В игровом цикле объявляем булевую переменную AgentIsNear — агент вблизи шлюза.

Первый цикл: Проверяем каждую клетку вокруг каждого шлюза на присутствие там агента. И если он таки там есть, блокируем переход, меняем первую переменную (отвечающую за шлюз) в массиве переходов (N1) на -1 (значение, которое никогда не встретится), изменяем AgentIsNear на true и прерываем цикл.

Второй цикл: так как агент гуляет где-то далеко, то мы блокируем любой свободный проход любого шлюза.

Второй цикл выполняется только тогда, когда за весь первый цикл условие внутри него ни разу не стало истинным.

Программа проходит все тесты на MEDIUM и, что удивительно, половину тестов на HARD! Взято с CodinGame

 

Temperatures

Температуры

Задача взята с сайта codingame.com

Задача.

Задан набор целых чисел (значения температуры за различные моменты времени). Нужно вывести из них ближайшее к нулю.

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

Задан набор целых чисел (значения температуры за различные моменты времени). Нужно вывести из них ближайшее к нулю.

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

Вывести нуль, если  [latex] N = 0[/latex]. В противном случае вывести число, ближайшее к нулю, причём если два числа разных знаков одинаково близки к нулю, нужно вывести положительное.

Решение.

Сначала отфильтруем случай, когда  [latex] N = 0[/latex]. В этом случае, как от нас и требуют, напечатаем нуль.

Если же  [latex] N > 0 [/latex], прибегнем к уже знакомому нам приёму. Введём новую переменную — min — и присвоим ей первое число. Затем в цикле for будем эту переменную менять, если наткнёмся число, более близкое к нулю, чем хранящееся в min. Вот основной вопрос: когда нам нужно менять min? «Число  [latex] a [/latex]  ближе к нулю, чем число  [latex] b [/latex]»  означает, что  [latex] a [/latex] по модулю меньше, чем   [latex] b [/latex]. Значит, если число, прочитанное на текущем шаге цикла, по модулю строго меньше, чем число, хранящееся в min, переменную min нужно обновить. Но есть ещё один случай, когда переменную min следует обновить — это тот случай, когда текущее число положительно и столь же близко к нулю, как и число, хранящееся в min. Это действие даёт нам гарантию того, что если два числа разных знаков одинаково близки к нулю, будет выведено положительное.

Код на С++

Код на Java

 

P.S.. Возможно, усложнив оператор ветвления можно сделать алгоритм более эффективным за счёт уменьшения числа сравнений или присваиваний.

Ragnarök — Power of Thor

 Рагнарёк

Задача

Есть Тор. А у Тора был источник силы. Больше нет. Тор движется по прямоугольному полю и ему известны его координаты и координаты источника. Наша задача: за наименьшее количество ходов привести Тора к источнику. Допустимые варианты движения приведены на картинке ниже:

Рагнарёк-2

Инициализация

Одна строка, в которой даны четыре целых числа:  LX, LY, TX, TY — соответственно абсцисса и ордината источника, абсцисса и ордината начального положения Тора.

Инициализация

Одна строка, в которой даны четыре целых числа:  LX, LY, TX, TY — соответственно абсцисса и ордината источника, абсцисса и ордината начального положения Тора.

Входные данные для одного игрового хода

Уровень энергии Тора. Нам он не понадобится.

Выходные данные для одного игрового хода

Одна из следующих строк: «N», «NE», «E», «SE», «S», «SW», «W», «NW», указывающая в каком направлении Тору нужно переместиться.

Решение

Поскольку Тор движется по прямоугольному полю, на котором нет преград, кратчайший путь получится, если на каждом шаге сравнивать положение Тора с положением источника по каждой из осей и направлять Тора в соответствующую сторону (так, чтобы скомпенсировать различие в координатах). Подробно этот процесс ниже описан в комменатариях к коду. Здесь сделаем только две ремарки.

Во-первых, нужно учесть, что ордината растёт в южном, а не в северном направлении, как обычно:

 Рагнарёк-3

Во-вторых, если бы поле не было прямоугольным (или на нём были бы преграды, не позволяющие двигаться в том или ином направлении), то наш метод пришлось бы серьёзно модифицировать.

 

Код на С++

Код на Java

 

The Descent

Задача

Мы летим на падающем космическом корабле над горами. Наша задача  — запрограммировать пушки корабля так, чтобы уничтожить горы, тем самым не дав кораблю в них врезаться.

Гор имеется 8 штук. Корабль летает кругами над горами: сначала слева направо, потом справа налево, и так далее. Один полный «пролёт» состоит из восьми игровых ходов. За один пролёт мы можем выстрелить только один раз и только по горе, над которой находимся. При этом высота горы уменьшится на случайное число.

Чтобы благополучно приземлиться нам нужно уничтожить все горы. Создатели игры дали ценную подсказку: если стрелять на каждом пролёте по самой высокой горе, посадка будет безопасной.

Входные данные для одного игрового хода

В первой строке введены два числа (SX и SY) — соответственно горизонтальная и вертикальная координаты нашего корабля. Горизонтальная меняется слева направо от нуля до семи. Вертикальная, как показал опыт, нам не понадобится.

Следующие восемь строк содержат каждая по одному целому числу от нуля до девяти — высоту соответствующей горы. Высоты перечислены слева направо.

Выходные данные для одного игрового хода

Одна строка: «FIRE», чтобы выстрелить, и «HOLD», если на текущем ходе стрелять не нужно.

Решение

Считаем SX и SY. После этого в цикле for считаем высоты гор. Нам нужно стрелять на каждом пролёте по самой высокой горе. Для этого мы применим приём, уже опробованный нами на практических занятиях: введём новую переменную max_height, в которую поместим высоту первой горы (точнее, нулевой). А в цикле будем обновлять эту переменную, если наткнёмся на более высокую гору. Всё? Нет, не всё. Стрелять мы можем только по горе, которая находится под нами. Чтобы знать, когда стрелять, введём переменную max_position, которая будет хранить координату самой высокой горы. Вначале присвоим ей нулевое значение. А в цикле будем обновлять эту переменную, вместе с переменной max_height.

Когда цикл for завершится, останется только проверить находимся ли мы на текущем ходу над самой высокой горой: для этого будем каждый раз сравнивать текущую координату корабля (SX) с координатой самой высокой горы, которая после цикла for хранится в переменной max_position. В случае совпадения — стреляем, в противном случае — ждём.

Код на С++

Код на Java

 

Skynet: The Chasm

Вторая по списку игра на сайте codingame.com проверяет умение примата пользоваться условными операторами, интуицией и программой по физике за десятый класс. По легенде, на постапокалиптических просторах Земли будущего раскинулась зловещая империя враждебных человеку роботов, но инженерный гений непокоренных программистов-взломщиков дает человечеству шанс на выживание. Подрывная деятельность начинается с малого: под дистанционный контроль удалось взять кремниевые мозги скоростного робота, внешностью и повадками напоминающего модифицированный мотоцикл. Наша задача — создать алгоритм управления, позволяющий машине преодолевать препятствия.

Инициализация:
Каждый уровень поделен на три этапа:

  1. Движение по стартовой площадке.
  2. Прыжок через пропасть.
  3. Торможение на финишной прямой.

До начала игрового цикла программа считывает данные о длине каждого из элементов уровня и сохраняет соответственно в переменные [latex]R, G, L[/latex].

Игровой цикл
На каждой итерации входной поток содержит:

  1. Координату мотоцикла [latex]X[/latex].
  2. Мгновенную скорость мотоцикла [latex]S[/latex].

В выходной поток необходимо вывести одну из четырех команд:

  1. JUMP — совершить прыжок.
  2. SPEED — увеличить скорость на единицу.
  3. SLOW — уменьшить скорость на единицу.
  4. WAIT — ждать следующего хода.

Прежде чем приступить к решению, проанализируем и формализуем задачу.
Continue reading

Ragnarök — Power of Thor

Четвертая по счету игра на сайте называется Ragnarök — Power of Thor, где нам посчастливилось быть Великим Воином Тором. Тору необходимо самым кратчайшим путем добраться до источника энергии, которая придаст ему еще больше сил и уверенности в дальнейших сражениях.

Пока еще не всемогущий Тор ждет указаний

Пока еще не всемогущий Тор ждет указаний

Инициализация

В начале нам сообщают положение на карте источника и самого персонажа (их координаты по X и Y) (int LX, LY) (int TX, TY) соответственно.

Игровой цикл

Бесконечно (до конца игры) повторяемый игровой цикл состоит из любого количества кода, который читает входной поток и выводит команду в выходной поток.

Вход

В самом игровом цикле нам сообщают величину энергии Тора (int E), которая уменьшается на 1 с каждым последующим ходом.

Выход

В выходной поток необходимо вывести одну строку. Нам представлено всего 8 возможных вариантов дальнейшего передвижения Тора. Screenshot_2222

 

Движение возможно только как показано на картинке (т.е. по компасу). Например, если мы хотим, чтобы персонаж двигался вправо (на восток) мы выведем буквочку E и т.д.

Перевод строки на новую обязателен.

 

Тест 1

Запуская программу впервые, Тор будет сам не свой, двигаясь совсем не по направлению к источнику.

Пройти первый и второй тесты, кажется просто, якобы написать в какую сторону мальчику бежать и только наблюдать за процессом, но не тут то было. Третий тест показывает нам, что все-таки придется подумать об адекватном решении.

[su_spoiler title=»Адекватное решение» icon=»arrow-circle-2″]

Немного подумав вспоминаем, что нам даны начальные координаты как источника так и энергии. Сразу же приходит в голову мысль, что их надо сравнивать.

Если равны координаты Тора и источника энергии по X, то тут мы находим разность координат источника и Тора по Y, если LY — TY > 0 (Источник находится выше Тора по оси Y), то идем на юг (вверх), в противном случае на север (вниз). Аналогично и с движением по Y,  что дает нам силы пройти первые два теста.

[/su_spoiler]

Дважды заряженный энергией боец рвется подзарядиться и в третий раз, но вдруг остается стоять на месте. Обескураженный обстоятельствами Тор замечает, что источник уже находится не ровно по оси движения, а под каким-то определенным углом. Оставаясь на месте, Тор принимает обет молчания (не выводит ничего на экран) и погружается в свои мысли.

[su_spoiler title=»Цикл for идет на помощь» icon=»arrow-circle-2″]

Конечно, мы могли бы высчитывать конечное число выводов команд на экран или подбивать все это проваливая тесты раз за разом. Но Тор нам подсказывает, что этого делать не надо, ведь он вспомнил могучее заклинание под названием цикл, которое спасает в очень многих ситуациях и эта не исключение.

Код на C++:

Код на Java:

 

Получается вот такой вот симпатичный код, описывающий все возможные ситуации по передвижению Тора (переносит Тора к источнику из любой точки карты). Разбивая на два возможных случая, движение в правой половине карты и в левой половине карты, получается, что программа охватывает любую ее точку. В самом цикле возьмем модуль между разностью (т.к. источник может находиться и ниже Тора). Сравниваем LX и TX, для того, чтобы узнать в какой половине карты находится источник. Если LX — TX > 0, то в цикле будем отнимать от LX, в противном случае — от TX, дабы не получить отрицательные значения. В конечном счете переменная E (энергия) там так и не понадобилось, так как воин и так находил кратчайшее расстояние.

[/su_spoiler]

Пройдя все тесты, наш довольный рыцарь полон сил и энергии. Пожелаем удачи ему в дальнейших приключениях.

Skynet — The Chasm

Вторая по счету игра на сайте называется Skynet — The Chasm. В игре мы будем управлять мотоциклистом, который изо всех сил пытается попасть на другую сторону пропасти и остановиться на конечной платформе.

Ни о чем не подозревающий мотоциклист

Ни о чем не подозревающий мотоциклист

Инициализация

В начале нам сообщают всевозможные данные о будущем пути: расстояние от мотоциклиста до пропасти (int R), длину пропасти (int G), длину платформы для приземления (int L).

Игровой цикл

Бесконечно (до конца игры) повторяемый игровой цикл состоит из любого количества кода, который читает входной поток и выводит команду в выходной поток.

Вход

Каждый новый ход (т.е. после каждого следующего выполненного действия в самом цикле while) нам сообщают скорость мотоциклиста (int S) и его позицию на дороге (int X).

Выход

В выходной поток необходимо вывести одну строку. Тут разработчики представляют нам 4 варианта:

  • ускоряться (SPEED);
  • тормозить (SLOW);
  • ехать вперед без ускорения (WAIT);
  • прыгать (JUMP).

Перевод строки на новую обязателен.

Тест 1

В начале нам представлен базовый код программы.

 

Запуская первый тест наш несчастный мотогонщик, постоянно ускоряясь, уже в который раз падает в пропасть. Но мы, всячески пытаемся его выручить и, наконец, пишем спасательный код.

[su_spoiler title=»Спасательный код» icon=»arrow-circle-2″]

Мы, с чувством выполненного долга, наблюдаем как мотоциклист, с улыбкой на лице, наконец перепрыгивает первую пропасть, а затем и вторую и третью. Понимая, что мотоциклист должен прыгнуть в момент, когда пропасть будет перед ним (т.е. за 1 шаг до нее), приказываем ему ускоряться до того момента (пока расстояние до пропасти не станет равным 1 (X == R — 1)). То есть пока положение мотоциклиста Х меньше, чем расстояние до пропасти R минус длинна пропасти G (X < R — G) мотоциклист будет ускоряться. После прыжка нам нужно затормозить, то есть если положение мотоциклиста X будет уже за пропастью (X > R — G), но меньше чем конец самой дороги (X < R + G + L), он будет тормозить.

[/su_spoiler]

Подходя к 4 тесту сталкиваемся с новой проблемой. Длинна платформы для приземления очень мала и наш бессмертный каскадер вылетает за окончание дороги. Что же делать?

[su_spoiler title=»Еще более спасательный код» icon=»arrow-circle-2″]

И тут вступает в игру переменная, которую до этого момента нам не приходилось использовать в программе, а именно, скорость мотоциклиста S.

После тысячи непройденых тестов начинаешь понимать, что ты что то упустил. Вот тут то и вступает в игру всеми любимый «любимый» magic number равный, в данном случае, единице. И вправду, для того, чтобы перелететь пропасть нам потребуется скорость всего лишь на 1 больше, чем длинна этой пропасти. То есть если скорость будет равна длине пропасти + 1, то мы будем ехать с этой постоянной скоростью, в противном случае будем ускоряться. С этим замечанием программа позволяет с легкостью останавливаться на конечной платформе любой длинны.

[/su_spoiler]

Кажется, что мы предусмотрели все варианты развития событий, но не тут то было. Разработчики устанавливают новую, увлекательную задачу. Что будет, если начальная скорость будет не равна 0, спрашивают они? И мы пускаемся в глубокие размышления.

[su_spoiler title=»Код дающий, в прямом смысле, крылья» icon=»arrow-circle-2″]

Из которых тут же выходим с новой идеей. Нам всего лишь надо тормозить до тех пор, пока скорость не станет достаточной для прыжка.

На С++:

На Java:

 

[/su_spoiler]

В конце-концов мы получаем рабочий «крылатый» вариант программы. Все довольны, в том числе и мотоциклист, которому больше не придется падать в пропасть и выбираться из нее.