Programming
13 September 2011

Праздничный биатлон

Programmers' dayС днем программиста, коллеги!

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

Алгоритмы. Задача №1, разминочная


Напишите код, который находит количество подчисел числа n, на которые это число делится без остатка.

Для числа n, подчисло — это такое число, запись которого является подстрокой записи числа n. К примеру, если n равняется 1938, то его подчислами будут являться: 1, 9, 3, 8, 19, 93, 38, 193 и 938. Без остатка 1938 делится на четыре из этих подчисел: 1, 3, 19 и 38. Соответственно, результатом работы программы должно быть число 4.
Если подчисла повторяются, каждое из них считается. Например, 101 делится без остатка на 1, 1 и 01, значит, ответ — 3.

Так как задача несложная, в решениях ценится краткость или нестандартный подход.

Алгоритмы. Задача №2, посложнее


Руководство финансовой пирамиды решило присвоить числовой рейтинг каждому из участников пирамиды. Если участник до сих пор никого не привел в пирамиду, то его рейтинг равняется 1. Если у участника уже есть подчиненные участники, то его рейтинг равняется 1 + сумма рейтингов его прямых подчиненных.
Задача: найти сумму рейтингов всех участников финансовой пирамиды.

Исходные данные подаются в виде массива из n строк, где каждая строка содержит n символов. Каждый символ — либо '0', либо '1'.
j-й символ i-й строки указывает на то, является ли участник под номером j прямым подчиненным участника i.
j-й символ j-й строки всегда равен '0'. Дерево участников никогда не имеет циклов. Каждый участник всегда является прямым подчиненным максимум одного другого участника. У дерева участников всегда только один корневой участник.

Пример исходных данных:

"0110"
"0000"
"0001"
"0000"

Корневым элементом в данном случае является участник 0. У него двое подчиненных: участники 1 и 2. У 1 подчиненных нет, у 2 есть подчиненный участник 3.
Рейтинг 3-го: 1.
Рейтинг 1-го: 1.
Рейтинг 2-го: 1 + 1 = 2.
Рейтинг 0-го: 1 + 1 + 2 = 4.

Результатом работы кода должна являться сумма рейтингов всех участников, в данном случае это: 1 + 1 + 2 + 4 = 8.

SQL. Задача №1, попроще


Дано: две (ненормализированные) таблицы:
Categories(Id, Name)
Books(Id, CategoryId, Name)

В будущем вы, конечно же, хотите добавить третью таблицу-связку Book_Category, но пока что в таблице Books может существовать несколько записей с одинаковым значением поля Name, но разными CategoryId.

Задача: написать запрос, который выбирает все книги, которые есть в категории с Id = 1, но которых нет в категории с Id = 2.
Небольшое уточнение: СУБД, которую вы используете, не знает, что такое подзапросы :)

SQL. Задача №2, посложнее


Есть таблица Players(Id, Name, Score), где Score — количество очков игрока. Чем больше очков, тем выше место игрока в зачетной таблице.
Задача: написать запрос, который выбирает игроков, занимающих (делящих) 3-е место.

UPD: Так как задача оказалась проще, чем ожидалось, вводится ограничение: нельзя использовать подзапросы. Для интереса, попробуйте обойтись джоинами :)

Пример данных:

Players

Как видно, 1-2 место делят Stepan и Svetlana, а 3-4 — Vladimir и Valentin, которых и должен вернуть запрос.

Скрипт для создания таблицы и тестовых данных можно скачать.

Напоследок


Те, у кого нет аккаунта, могут слать решения мне на почту: dmitrii.shevchenko@gmail.com. Инвайтов не обещаю (нет их у меня), а вот в комментарии самые интересные решения выложу.

Надеюсь, вам понравится :)

+36
1.1k 19
Comments 83
Top of the day