Вверх ↑
Этот топик читают: Гость
Ответов: 5446
Рейтинг: 323
#1: 2010-07-17 23:21:10 ЛС | профиль | цитата
== Младшая Лига HiAsm Contest ==
Для тех, кто к нам недавно присоединился, поясняю: HiAsm Contest - это соревнование по составлению схем, решающих поставленную задачу: этакая олимпиада по программированию, только на Hiasm-е.

Задачи Младшей Лиги проще, чем Старшей, и потому (надеюсь) доступнее новичкам.

Напомнинаю основные правила:

0. Цель сего мероприятия - развитие алгоритмического мышления у участников.
1. Решения принимаются в виде фрагмента схемы, заключённого в MultiElementEx заданного вида (для каждой задачи свой). В комментарии к элементу должен быть указано имя участника, номер задачи, название лиги (Старшая либо Младшая) и (по желанию) порядковый номер версии решения.
2. В решении разрешается использовать элементы следующих вкладок:
  • Строки
  • Логика
  • Массивы
  • Инструмены (кроме группы "Языки" и компонента FTCG_Tools)
  • MT-потоки
  • Помощники (кроме вкладки "Среда")
  • Работа с типами
  • Кабели
Возможен приём схем с InlineCode и FTCG-компонентами на внеконкурсной основе.
3. Призы: +4 в рейтинг за правильное решение; 50ћ, 30ћ и 10ћ за I, II и III место соответственно; дополнительные призы (5ћ) за оригинальность решения.
4. Сроков у конкурса нет: по мере нахождения интересных задач они будут выкладываться.
5. Решения принимаются через личные сообщения (ЛС). На каждую задачу даётся неограниченное число попыток, в зачёт идёт первое правильное решение.
6. Решения будут оцениваться по:
  • Времени работы
  • Элегантности решения / оформления
7. Если в течении двух недель подряд на какую-либо из задач не поступило ни одного решения, то все присланные верные решения выкладываются на всеобщее обозрение (если автор решения не выскажет явного запрета). Решения таких задач больше не принимаются.
Задача №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) описывает следующий мир:
+---+---+---+
| С | К | К |
+---+---+---+
| С | К | С |
+---+---+---+
| К | С | С |
+---+---+---+
Во входном массиве такой мир описывается тремя числами: двоичным 011 (дес. 3), 010 (дес. 2) и 100 (дес. 4)

На вход программы подаются: целое число 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
Задача №2

== Горизонт Мурсии ==
Вводная
Мурисия быстро растёт. С 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).
Задача №3

== Старый маг ==
Постановка задачи
Есть у старого мага любимый фокус: он помещает в свою шляпу 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
Задача №4

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

Недавно родители этого мальчика подарили ему несколько наборов, каждый из которых состоит из двенадцати спичек. Мальчик начал собирать из них различные геометрические фигуры. Он уже собрал много различных фигур, но теперь ему стало интересно: из каких наборов возможно склеить каркас параллелепипеда при помощи двенадцати спичек из набора и клея? Ломать спички нельзя и ни одна из спичек не должна выступать за каркас.

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

Вход
Входные данные содержат в себе описание набора спичек — двенадцать целых положительных чисел не превышающих 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
Задача №5

== Кирпичная стена ==
Вводная
Возьмём обычные кирпичи, длина каждого из которых равна 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
Задача №6

== Ключ к шифру ==
Вводная
Все те сотни лет, в течении которых существуют государства, границы и периодически возникающие конфликты между странами, существует и система шпионажа. Агент, нелегально или легально проживающий в одной стране, отправляет донесения, содержащие в себе государственную тайну, в другую страну. Способы передачи донесений непрерывно меняются. Сто лет назад это были бумажные письма, пятьдесят лет назад — радиограммы, сейчас же есть возможность отправить донесение даже по электронной почте. Однако, одна характерная черта всех донесений не изменилась и не изменится никогда — любое информационное сообщение можно перехватить. Чтобы застраховаться от такой возможности, донесения шифруются так, чтобы прочитать их мог только тот, кому они предназначены. При этом обычно используется некоторый ключ — сравнительно небольшая строка, часто не имеющая смысла, с помощью которой донесение можно расшифровать. А чтобы, в случае поимки агента, он не мог сообщить ключ заинтересованным лицам, каждому донесению соответствует свой ключ, который отправляется вместе с донесением, тоже зашифрованный, но не очень сложным способом. Вам предстоит научиться получать этот ключ по его зашифрованной версии для некоторого алгоритма шифрования.

Чтобы зашифровать непустой ключ 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.2059.62 + 43.25--
tig-rrr ------92.20 + 9.3854.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 ОТКРЫТА

карма: 1

0
файлы: 4p11786.png [12KB] [785], p11790a.jpg [27.7KB] [1306], p11790b.png [2.2KB] [1310], p900.gif [2KB] [1213]
vip
#1.1контекстная реклама от партнеров
Гость
Ответов: 17029
Рейтинг: 0
#2: 2010-07-18 18:51:50 правка | ЛС | профиль | цитата


Редактировалось 4 раз(а), последний 2017-06-21 01:39:35
карма: 0

0
Ответов: 5446
Рейтинг: 323
#3: 2010-07-18 19:03:00 ЛС | профиль | цитата
г. KisL()R()[)!,
1. i-й элемент массива c
2. 2 в степени n
3. для задания начального состояния мира
карма: 1

0
Гость
Ответов: 17029
Рейтинг: 0
#4: 2010-07-18 19:47:05 правка | ЛС | профиль | цитата


Редактировалось 4 раз(а), последний 2017-06-21 01:39:35
карма: 0

0
Ответов: 3464
Рейтинг: 233
#5: 2010-07-18 19:47:56 ЛС | профиль | цитата
Вопрос:
Муравей двигается только вперед?
iarspider писал(а):
конфигурации мира, и (ii) начальнрой

карма: 0

0
Гость
Ответов: 17029
Рейтинг: 0
#6: 2010-07-18 19:56:35 правка | ЛС | профиль | цитата


Редактировалось 4 раз(а), последний 2017-06-21 01:39:36
карма: 0

0
Ответов: 3464
Рейтинг: 233
#7: 2010-07-18 20:18:31 ЛС | профиль | цитата
iarspider писал(а):
pi/2

Это что по диагонали получается?
------------ Дoбавленo в 20.18:
Куда начально направлен муравей?
карма: 0

0
Ответов: 534
Рейтинг: 5
#8: 2010-07-18 20:26:28 ЛС | профиль | цитата
iarspider, всё понятно и вроде даже просто, но я не понял, муравей может двигаться по диагонали? Если нет, то как понять pi/2?
------------ Дoбавленo в 20.22:
Ivann писал(а):
Куда начально направлен муравей?
Полагаю, что вперёд (90 градусов).
------------ Дoбавленo в 20.26:
Ещё непонятка: если код чётный (состоит из 2,4,6 чисел...), то мир принимает форму
+---+---+
| С | К |
+---+---+
| С | С |
+---+---+
А если нечётный (3,6,9), то такой:
+---+---+---+
| С | К | К |
+---+---+---+
| С | К | С |
+---+---+---+
Если нет, то как определить, сколь битов использовать в одной строке, а после этого начинать новую строку?
карма: 0

0
Ответов: 3464
Рейтинг: 233
#9: 2010-07-18 21:09:35 ЛС | профиль | цитата
iarspider писал(а):
Мир муравья - плоскость n*n

То есть настоящий квадрат
карма: 0

0
Гость
Ответов: 17029
Рейтинг: 0
#10: 2010-07-18 21:29:34 правка | ЛС | профиль | цитата


Редактировалось 4 раз(а), последний 2017-06-21 01:39:37
карма: 0

0
Ответов: 5446
Рейтинг: 323
#11: 2010-07-19 02:36:35 ЛС | профиль | цитата
Из школьного курса планиметрии (8-9 класс) известно, что угол pi/2 соответствует углу 90 градусов (а не 45!).

Муравей может двигаться только вперёд: ни по диагонали, ни боком, ни задом он двигаться не может.

Начальное положение муравья соответствует углу -90 градусов (направление на север). Замечу также, что ось Y в данной задаче направлена вниз.

Уточнил описание входных данных в части содержимого массива. Продублирую здесь:
Задача 1 писал(а):
Конфигурация n*n мира может быть закодирована набором из n^2 двоичных бит. Значение "0" соответствует синему цвету, значение "1" - красному. Ячейки описываются справа налево от младшего бита к старшему, сверху вниз. Например, двоичное число 0100 (десятичное 4) описывает следующую конфигурацию:
+---+---+
| С | К |
+---+---+
| С | С |
+---+---+

Во входном массиве такой мир описывается двумя числами: двоичным 01 (дес. 1) и 00 (дес. 0)

Аналогично, 011010100 (десятичное 212) описывает следующий мир:
+---+---+---+
| С | К | К |
+---+---+---+
| С | К | С |
+---+---+---+
| К | С | С |
+---+---+---+

Во входном массиве такой мир описывается тремя числами: двоичным 011 (дес. 3), 010 (дес. 2) и 100 (дес. 4)

На вход программы подаются: целое число n (1 < n < 16) определяющее размер мира; массив (Array) целых чисел c, каждый элемент которого 0 < c_i < 2^n; целые числа x и y, задающие начальное положение муравья (1 < x, y < n).

Каждая строка массива c описывает один ряд клеток мира.

карма: 1

0
Гость
Ответов: 17029
Рейтинг: 0
#12: 2010-07-19 06:34:40 правка | ЛС | профиль | цитата


Редактировалось 4 раз(а), последний 2017-06-21 01:39:38
карма: 0

0
Ответов: 1379
Рейтинг: 86
#13: 2010-07-19 07:11:32 ЛС | профиль | цитата
[flood]Подождите меня чуть-чуть (2 недели)
Просто я сейчас уезжаю, вернусь только так. И сразу начну. [/flood]
карма: 0

0
Гость
Ответов: 17029
Рейтинг: 0
#14: 2010-07-19 10:09:07 правка | ЛС | профиль | цитата


Редактировалось 4 раз(а), последний 2017-06-21 01:39:39
карма: 0

0
Гость
Ответов: 17029
Рейтинг: 0
#15: 2010-07-19 10:48:12 правка | ЛС | профиль | цитата


Редактировалось 4 раз(а), последний 2017-06-21 01:39:39
карма: 0

0
Сообщение
...
Прикрепленные файлы
(файлы не залиты)