Для тех, кто к нам недавно присоединился, поясняю: HiAsm Contest - это соревнование по составлению схем, решающих поставленную задачу: этакая олимпиада по программированию, только на Hiasm-е.
Задачи Младшей Лиги проще, чем Старшей, и потому (надеюсь) доступнее новичкам.
Напомнинаю основные правила:
0. Цель сего мероприятия - развитие алгоритмического мышления у участников.
1. Решения принимаются в виде фрагмента схемы, заключённого в MultiElementEx заданного вида (для каждой задачи свой). В комментарии к элементу должен быть указано имя участника, номер задачи, название лиги (Старшая либо Младшая) и (по желанию) порядковый номер версии решения.
2. В решении разрешается использовать элементы следующих вкладок:
- Строки
- Логика
- Массивы
- Инструмены (кроме группы "Языки" и компонента FTCG_Tools)
- MT-потоки
- Помощники (кроме вкладки "Среда")
- Работа с типами
- Кабели
3. Призы: +4 в рейтинг за правильное решение; 50ћ, 30ћ и 10ћ за I, II и III место соответственно; дополнительные призы (5ћ) за оригинальность решения.
4. Сроков у конкурса нет: по мере нахождения интересных задач они будут выкладываться.
5. Решения принимаются через личные сообщения (ЛС). На каждую задачу даётся неограниченное число попыток, в зачёт идёт первое правильное решение.
6. Решения будут оцениваться по:
- Времени работы
- Элегантности решения / оформления
Задача №1== Муравей Лэнгтона ==
Постановка задачи
Муравей Лэнгтона, названный так по имени математика Кристофера Лэнгтона, является клеточным автоматом с очень простым набором правил, но очень интересным результирующим поведением; это поведение в днастоящее время является предметом исследований нескольких математиков. Аналогия между муравьями и клеточным автоматом Лэнгтона происходит из того, что можно ассоциировать произвольно выбранное состояние автоматона с муравьём, а динамику автомата - со способностью муравья перемещаться в специальном мире.
Мир муравья - плоскость n*n, разбитая на одинаковые клетки размером 1*1. Каждая клетка (ячейка) мира окрашена либо в синий, либо в красный цвет. Число n называют размером мира. Клетки обозначаются парой чисел (i; j) (1 < i, j < n). Жизнь и перемещения муравья определяются следующими простыми правилами:
- Если он находится на синей клетке, он "переворачивает" цвет клетки, поворачивается на угол pi/2 влево, и передвигается на одну клетку вперед;
- Если он находится на красной клетке, он "переворачивает" цвет клетки, поворачивается на угол pi/2 вправо, и передвигается на одну клетку вперед;
- Если перемещение невозможно (муравей не может выйти за пределы мира), он погибает.
Пусть, например, муравей находится на красной клетке, лицом на восток. Если к югу от текущей позиции нет клетки, то муравей погибает. Если же к югу от него есть клетка, то он перемещается на неё, и цвет покинутой ячейки меняется на синий. После этого муравей попытается совершить следующий шаг, и так далее.
Ваша задача состоит в том, чтобы выяснить, сможет ли муравей достигнуть ячейки с координатами (n; n), исходя из (i) конфигурации мира, и (ii) начальной позиции муравья.
Вход
Конфигурация n*n мира может быть закодирована набором из n^2 двоичных бит. Значение "0" соответствует синему цвету, значение "1" - красному. Ячейки описываются справа налево от младшего бита к старшему, сверху вниз. Например, двоичное число 0100 (десятичное 4) описывает следующую конфигурацию:
+---+---+
| С | К |
+---+---+
| С | С |
+---+---+
Во входном массиве такой мир описывается двумя числами: двоичным 01 (дес. 1) и 00 (дес. 0)
Аналогично, 011010100 (десятичное 212) описывает следующий мир:
+---+---+---+
| С | К | К |
+---+---+---+
| С | К | С |
+---+---+---+
| К | С | С |
+---+---+---+
На вход программы подаются: целое число n (1 < n < 16) определяющее размер мира; массив (Array) целых чисел c, каждый элемент которого 0 < c_i < 2^n; целые числа x и y, задающие начальное положение муравья (1 < x, y < n).
Каждая строка массива описывает один ряд клеток мира.
Выход
В выходном потоке программа должна вернуть сторку "Yes", если муравей может достигнуть ячейки с координатами (n; n); либо "Kaputt!", если муравей умирает не достигнув ячейки (n; n).
Шаблон оформления
Add(MultiElementEx,3557107,525,210)
{
@Hint=#8:задача 1|9:iarspider|12:Младшая Лига
}
BEGIN_SDK
Add(EditMultiEx,7593973,21,21)
{
WorkCount=#8:doAnt|
EventCount=#8:onAnt|
DataCount=#1:n|1:c|1:x|1:y|
}
END_SDK
== Горизонт Мурсии ==
Вводная
Мурисия быстро растёт. С XV века, в её высотном контуре доминировал собор в стиле "барокко". Но в последнее время на землях Мурисии сторится всё больше и больше небоскрёбов.
Некоторые говорят, что если просматривать контур слева направо, то высота зданий повышается. Другие говорят, что она понижается.
Постановка задачи
Если просматривать контур слева направо, то мы увидим N зданий. У каждого здания своя высота и ширина. Ваша задача выяснить, возрастает ли высота, или нет.
Высота считается "возрастающей" (increasing), если "длина" самой длинной возрастающей подпоследовательности больше или равна "длине" убывающей. В противном случае, такая подпоследовательность называется "убывающей" (decreasing). "Длина" в данном случае - это сумма ширин элементов.
Пусть, например, у нас есть шесть зданий, высоты которых: 10, 100, 50, 30, 80, 10; а их ширины - 50, 10, 10, 15, 20, 10; тогда у нас есть "возрастающая" подпоследовательность из трёх зданий длиной 85, и убывающая подпоследовательность из 1 здания длиной 50 (и другая убывающая подпоследовательность из 4 зданий длиной 45). Ниже представлено графическое изображение этого примера:
Вход
На вход схемы подаются два массива целых чисел: массив H высот зданий и массив W ширин зданий
Выход
На выходе ожидается строка вида
Increasing (A). Decreasing (B).
Decreasing (B). Increasing (A).
Числа A и B - длины (самых длинных) возрастающей и убывающей подпоследовательностей.
Примеры
Вход:
10 100 50 30 80 10
50 10 10 15 20 10
Increasing (85). Decreasing (50).
Вход:
30 20 20 10
20 30 40 50
Decreasing (110). Increasing (50).
Вход:
80 80 80
15 25 20
Increasing (25). Decreasing (25).
== Старый маг ==
Постановка задачи
Есть у старого мага любимый фокус: он помещает в свою шляпу W белых и B чёрных шаров. После этого,
он выбирает одного из зрителей проделывать следующие операции до тех пор, пока в шляпе не останется один шар:
1. Достать из шляпы два шара
2. Если шары одного цвета, поместить белый шар в шляпу, иначе - чёрный.
Когда в шляпе останется только один шар, зритель просит волшебника угадать цвет этого шара. Излишне говорить, что маг не видел, какие шары и в каком порядке извлекались и помещались в шляпу.
Проблема в том, что наш маг, как и многие его коллеги, уже стар, и иногда забывает, как делать этот фокус. Будучи добрым человеком, вы собираетесь помочь магу.
Для каждой пары чисел (W, B), верните:
- "WHITE" - если последний шар в шляпе будет белым
- "BLACK" - если последний шар в шляпе будет чёрным
- "UNKNOWN" - если определить цвет последнего шара затруднительно
Вход
На вход программы подаются количество чёрных (B) и белых (W) шаров. Ограничения: W + B > 0.
Выход
В выходном потоке программа должна вернуть строку.
Оформление
Шаблон оформления решения:
Add(MultiElementEx,3557107,525,210)
{
@Hint=#8:задача 3|9:iarspider|12:Младшая Лига
}
BEGIN_SDK
Add(EditMultiEx,7593973,21,21)
{
WorkCount=#8:doMagic|
EventCount=#8:onMagic|
DataCount=#1:W|1:B|
}
END_SDK
== Параллелепипед ==
Вводная
Вопреки известной поговорке «спички детям не игрушка», один мальчик очень любит играть со спичками. Но он не балуется ими, не разжигает огонь, а решает различные головоломки. Например, он умеет приравнивать число девять к числу одиннадцать, переложив только одну спичку.
Недавно родители этого мальчика подарили ему несколько наборов, каждый из которых состоит из двенадцати спичек. Мальчик начал собирать из них различные геометрические фигуры. Он уже собрал много различных фигур, но теперь ему стало интересно: из каких наборов возможно склеить каркас параллелепипеда при помощи двенадцати спичек из набора и клея? Ломать спички нельзя и ни одна из спичек не должна выступать за каркас.
Ваша задача состоит в том, чтобы по известным длинам спичек для каждого набора проверить, можно ли из них склеить каркас параллелепипеда.
Вход
Входные данные содержат в себе описание набора спичек — двенадцать целых положительных чисел не превышающих 10^9
Выход
Для каждого набора спичек выведите «yes», если из него возможно склеить каркас параллелепипеда, и «no» в обратном случае.
Примеры
Вход:
1 1 1 1 2 2 2 2 3 3 3 3
yes
Вход:
1 1 1 1 2 2 2 2 3 3 3 4
no
Шаблон оформления решения:
Add(MultiElementEx,3557107,308,182)
{
@Hint=#8:задача 4|9:iarspider|12:Младшая Лига|
}
BEGIN_SDK
Add(EditMultiEx,7593973,21,21)
{
WorkCount=#5:doBox|
EventCount=#5:onBox|
DataCount=#1:a|1:b|1:c|1:d|1:e|1:f|1:g|1:h|1:i|1:j|1:k|1:l|
}
END_SDK
== Кирпичная стена ==
Вводная
Возьмём обычные кирпичи, длина каждого из которых равна 2 ед., а ширина - 1 ед., и посторим из них стену высотой 2 ед. Если подойти к процессу творчески, то окажется, что для заданной длины стены существует несколько вариантов укладки кирпичей:
- для стены длины 1 есть только один способ - поставить киприч "на попа"
- для стены длины 2 есть два способа - либо два кирпича, поставленных "на попа", либо два кирпича, положенных друг на друга
- для стены длины 3 - три способа
Сколько способов существует для стены длины 4? А для длины 5?
Постановка задачи
Ваша задача - по заданной длине стены определить, сколько существует способов её постройки
Вход
Входом является натуральное число L - длина стены, причём L < 46
Выход
На выходе ожидается целое число N - число способов постройки стены
Примеры
Вход:
1
1
Вход:
2
2
Вход:
3
3
Оформление
Шаблон оформления решения:
Add(MultiElementEx,3557107,308,182)
{
@Hint=#8:задача 5|9:iarspider|12:Младшая Лига|
}
BEGIN_SDK
Add(EditMultiEx,7593973,21,21)
{
WorkCount=#5:doWall|
EventCount=#5:onWall|
DataCount=#1:L|
}
END_SDK
== Ключ к шифру ==
Вводная
Все те сотни лет, в течении которых существуют государства, границы и периодически возникающие конфликты между странами, существует и система шпионажа. Агент, нелегально или легально проживающий в одной стране, отправляет донесения, содержащие в себе государственную тайну, в другую страну. Способы передачи донесений непрерывно меняются. Сто лет назад это были бумажные письма, пятьдесят лет назад — радиограммы, сейчас же есть возможность отправить донесение даже по электронной почте. Однако, одна характерная черта всех донесений не изменилась и не изменится никогда — любое информационное сообщение можно перехватить. Чтобы застраховаться от такой возможности, донесения шифруются так, чтобы прочитать их мог только тот, кому они предназначены. При этом обычно используется некоторый ключ — сравнительно небольшая строка, часто не имеющая смысла, с помощью которой донесение можно расшифровать. А чтобы, в случае поимки агента, он не мог сообщить ключ заинтересованным лицам, каждому донесению соответствует свой ключ, который отправляется вместе с донесением, тоже зашифрованный, но не очень сложным способом. Вам предстоит научиться получать этот ключ по его зашифрованной версии для некоторого алгоритма шифрования.
Чтобы зашифровать непустой ключ s, агент сначала выбирает такую строку t, что строка s является префиксом строки t, а развернутая строка s — суффиксом строки t. При этом в строке t могут быть символы, не имеющие отношения к строке s. После этого слева к строке t дописывается некоторое случайное (возможно, нулевое) количество случайных символов, справа же дописывается точно такое же количество, возможно других, случайных символов. Теперь строка t представляет из себя зашифрованный ключ s.
Понятно, что при попытках восстановить сам ключ, то есть исходную строку s, вариантов может получиться несколько. Поэтому было принято решение, что ключ должен быть самой длинной строкой из всех возможных вариантов, а в случае, если и таких строк несколько — то такой строкой, что количество случайно дописанных слева и справа символов было минимально, то есть строка t имеет максимальную длину. Вам необходимо реализовать алгоритм восстановления ключа s по его зашифрованной версии.
Вход
На вход подаётся строка t, содержащая зашифрованную версию искомого ключа. Каждая зашифрованная версия содержит только строчные буквы латинского алфавита.
Гарантируется, что для каждой зашифрованной версии существует хотя бы один подходящий непустой ключ.
Выход
На выходе ожидается строка s - расшифрованный ключ
Примеры
Вход:
ababc
bab
Вход:
ababa
ababa
Вход:
cxbaydzabxe
xba
Оформление
Шаблон оформления решения:
Add(MultiElementEx,3557107,308,182)
{
@Hint=#8:задача 6|9:iarspider|12:Младшая Лига|
}
BEGIN_SDK
Add(EditMultiEx,7593973,21,21)
{
WorkCount=#5:doRecover|
EventCount=#5:onRecover|
DataCount=#1:t|
}
END_SDK
| Участник | Время (#1) | Время (#2) | Время (#3) | Время (#4) | Время (#5) | Время (#6) |
| tomas | -- | -- | 30.49 + 64.31 | -- | -- | -- |
| Ex_ | -- | -- | -- | 36.44 + 5.20 | 59.62 + 43.25 | -- |
| tig-rrr | -- | -- | -- | 92.20 + 9.38 | 54.54 + 35.32 | -- |
| nesco (*) | -- | -- | -- | 47.49 + 7.54 | -- | -- |
| samakacd | -- | -- | -- | 65.91 + 11.66 | -- | -- |
| foksov | -- | -- | -- | -- | 198.726 + 186.357 | -- |
| ivann | -- | -- | -- | -- | 37.21 + 21.46 | -- |
(*) Решение не участвует в конкурсе
Для задачи №3 "время" определяется как среднее время для 1000 заданий.
Для задачи №4 "время" определяется как среднее время для 975 заданий.
Для задачи №5 "время" определяется как среднее время для 1000 случайных заданий.
Для задачи №6 "время" определяется как среднее время для 1000 случайных заданий.
| Задача | Дата окончания приёма решений |
| 1 | ЗАКРЫТА |
| 2 | ЗАКРЫТА |
| 3 | ЗАКРЫТА |
| 4 | ЗАКРЫТА |
| 5 | ЗАКРЫТА |
| 6 | ОТКРЫТА |
[/flood]
Поиск
Друзья
Администрация