Chuck Norris

Антон Куперман
Антон Куперман

Latest posts by Антон Куперман (see all)

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

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

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

Вустянюк Ігор Дмитрович
Вустянюк Ігор Дмитрович

Latest posts by Вустянюк Ігор Дмитрович (see all)

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

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

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

Условия

Разбор

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

Horse-racing Duals

Вустянюк Ігор Дмитрович
Вустянюк Ігор Дмитрович

Latest posts by Вустянюк Ігор Дмитрович (see all)

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

Вустянюк Ігор Дмитрович
Вустянюк Ігор Дмитрович

Latest posts by Вустянюк Ігор Дмитрович (see all)

Задача

Бэтмен

Речь пойдёт о первой задаче уровня 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