Головоломки Tech Monsters Night

Совсем недавно М.Видео-Эльдорадо в рамках хакатона Tech Monsters Night предложили всем желающим стать участниками интеллектуальной битвы, решив серию головоломок.

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

Под катом серия предложенных участникам Tech Monsters Night задач. Таким образом, у вас есть чудесная возможность провести наступившие выходные за решением этих головоломок. Есть предложение: в начале мы публикуем задания, вы в комментариях размещаете варианты решений. А через пару дней в обновлениях к данному посту мы разместим правильные ответы.

1. Унести с места

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

Входные данные: строка распределения весов в ряду
Пример входных данных: «1,2,0» — введенные веса грузов в каждом ряду.

Подряды:
«2,0»: 2+0 = 2 — количество цифр
«1»: 1 = 1 — количество цифр
“1,2,0”: 1+ 2 + 0 = 3 — количество цифр

Выходные данные: количество рядов подходящих под условие

Пример ответа: 3
Тестовые пары:?

2. Мультиварки

Условие:
В магазине есть мультиварки k видов. Дано количество мультиварок каждого вида и их цена за штуку. Покупателю нужно купить t мультиварок.
Необходимо продать мультиварки, чтобы суммарная стоимость была максимальна.

Входные данные: Строка, в которой пары чисел разделены точкой с запятой (";"). Первая пара чисел содержит значения [t,k], а последующие — количество мультиварок каждого вида n, и их стоимость p. [n,p]. Все пары чисел разделены запятой (",")

Пример входных данных: “7,3;5,10;2,5;3,6”

Три вида мультиварок:

• первый вид 5 штук, стоимостью по 10,
• второй вид 2 штуки стоимостью по 5,
• третий вид 3 штуки стоимостью по 6.

Выходные данные: суммарная максимальная стоимость

Пример ответа: 62
Тестовые пары:?

3. Наушники

Условие:
Нужно предсказать возможно ли при условиях, описанных ниже, чтобы в магазинах бытовой техники “Tune 66” в наличии всегда было от a до b штук наушников. Известно, что их покупают ровно t штук ежедневно.

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

Входные данные: Строка, содержащая параметры: «h,a,b,s,t, k». Числа в строке разделены запятой (",")

Ответ: “1” если да, “0” если нет
Тестовые пары:?

4. Акция

Условие
При покупке любого телефона проводится интересная акция. Покупатель может выиграть баллы на следующую покупку. Для этого было приготовлено k банок, в каждой банке находятся монеты. В каждой банке разное количество монет от 1 до k, количество монет в банке, соответствует номеру банки. Покупатель выбирает две баночки, он не знает сколько конкретно монет в них.

Покупатель получает половину, округленное в меньшую сторону содержимого выбранных баночек и уносит, вместе с одной из банок. Остальные монеты складываются в оставшуюся банку и она дальше участвует в розыгрыше, совместно с оставшимися. Найдите сколько максимум в ходе розыгрышей выиграют все покупатели за k-1 шагов.

Пример: пусть k = 4, тогда изначально есть баночки с [1,2,3,4] монетами, сначала берем 4 и 2 баночку. Покупатель уносит 3 монеты, а оставшиеся 3 монеты оставляет на месте 2 баночки. Тогда остается [1,3,3]. Следующий покупатель выбирает 2 и 3 банку, забирает половину их содержимого, т.е 3 монеты, и оставляет на месте 2 банки, вторую половину, то есть ещё 3 монеты. Тогда остается [1,3]. Дальше разыгрывается первая и вторая банка, покупатель забирает 2 монеты, и остается 2, т.е [2].

Входные данные: число k
Ответ: сколько максимум выиграли в сумме все покупатели?
Пример ответа: 8
Тестовые пары:?

5. Мероприятие

Условие
На рекламное мероприятие требуется организовать t участков квадратной формы. Есть несколько стен, длин h1, h2, h3… hn

У этих стен будут ставить ограждения для мероприятий, у одной стены могут организовать несколько участков. При этом вся стена должна быть задействована участками. Найдите такое разбиение, чтобы общая площадь участков была минимальной.



Пример разбиения, тут три стены, указаны зеленым, и 6 участков, указаны красным

Входные данные: Строка, разделенная точкой с запятой (";") на 2 части: первое число — количество участков t, а далее, список длин всех стен через запятую (",").

Ответ: минимальная площадь
Пример ответа: 15
Тестовые пары:?

6. Поиск подходящих складов

Условие:
Магазин ищет места для хранения бытовой техники. Чтобы она не портилась, нужно создать особые условия. Были разработаны специальные пластины, благодаря которым бытовая техника не портится и соблюдаются условия хранения, такие как влажность воздуха, температура и т.д.

Склад размером 2 на k, разделен на ячейки размером 1 на 1, при этом некоторые ячейки свободны и именно это пространство предназначено для складирования бытовой техники. Можно ли поместить пластины, размером 2 на 1 так, чтобы они занимали всё свободное пространство, и при этом не накладывались друг на друга?



Пример с пластинами, где пластины розовые, зеленые, синие.

Входные данные: строка, в которой первое число — длина склада k, а остальные символы — это пары чисел, разделённые точкой с запятой (";“), которые обозначают координаты занятых точек. Координаты между собой разделены запятой (”,").

Пример входных данных: “5;2,2;1,4”
Выходные данные: “1” если можно, “0” если нет.
Тестовые пары:?

7. Организация консультантов

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

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

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

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



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

Пример входных данных: “0,0,2,1,1,2”

Выходные данные: Строка, состоящая из 0 и 1, разделённых запятой, соответствующая входной, в которой 0 — если консультант смотрит влево, и 1, если смотри вправо.

Если это невозможно, нужно вывести строку “NO”.
Пример выходных данных в примере: «1,1,0,0,1,0»

Тестовые пары:?

8. Единая команда

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

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



Входные данные: Строка, которая разделена точкой с запятой (";"), в которой первая часть — это подстрока t,n, описывающий количество сотрудников t и количество отделов n. Вторая часть — подстрока, в которой указано, какой из сотрудников (по порядку) в каком отделе находится (числа разделены запятой). Последующие части — пары людей, знакомых друг с другом (порядковые номера сотрудников разделены запятой).

Пример входных данных: “6,3;1,1,2,2,3,3;1,3;1,5;1,6;2,5;2,6;3,4;3,5;5,6”

Выходные данные: количество способов выбрать две команды.

Пример ответа: 2
Тестовые пары:?

9. Найдите местоположение

Условие:
Решается вопрос, где оптимально было бы разместить новые магазины бытовой техники. Один из факторов — это пути доставки бытовой техники от различных складов. Каждый магазин должен быть расположен в одной из данных вершин, рядом с каким-то складом.

Каждый тип склада обозначается своей цифрой. Нужно найти вершины m, на которых следует разместить магазины и которые удовлетворяют условиям:
— при движении от этой вершины до любой другой, типы складов не повторяются в рамках одного пути;
— на разных путях, типы складов могут повторяться;

Посчитайте количество вершин m на графе.



Пример графа [[2,5,1,1,4],[1,2],[1,3],[2,4],[2,5]], при этом исконные вершины отмечены голубым

Входные данные: Строка, разделённая точкой с запятой (";"), в которой первая часть содержит типы складов по порядку (разделённых запятой). Остальные части являются доступными путями, которые записываются двумя числами (разделёнными запятой), где показывается, между какими складами существует дорога.

Пример входных данных: “2,5,1,1,4;1,2;1,3;2,4;2,5”

Выходные данные: количество подходящих вершин m

Пример ответа: 3
Тестовые пары:?

10. Роботизация рекламы

Условие:
В магазине расставлены товары. Вокруг товаров должен ходить рекламный робот. Магазин застеклен, и покупатели могут видеть робота привлекающего внимание снаружи. Для упрощения задачи пол магазина представлен в виде квадратной сетки, где в узлах сетки лежат товары.

Робот может проезжать или по стороне квадрата, длина которой равно 1, или по диагонали. Робот должен объезжать всё содержимое магазина снаружи, чтобы его было видно. Найдите длину кратчайшего пути, по которому должен пройти робот.



Пример минимального маршрута, при обходе трех точек.

Входные данные: Строка, содержащая координаты предметов. Каждый предмет разделён точкой с запятой (";"), а каждая координата в нём — запятой (",")
Пример входных данных: “1,2;3,4;4,1”

Пример ответа: 3
Тестовые пары:?