Несколько олимпиадных задач

[MooNDeaR]

Сегодня сходил на олимпиаду. Результат средний.
Хочу поделится задачами, которые не решил.

Задание 1:
Ограничение по времени: 1с
Ограничение по памяти: 64 МБ

Задача:
Жил был Чудак (на букву М). Однажды этот чудак, прогуливаясь по чудному городу, увидел два чудных числа a и b, он был так поражен этими числами, что сломя голову побежал домой. Дома он сразу же начал составлять множество чисел. Множество составляется по такому алгоритму:
• 1. Берем пустое мн-во
• 2. Добавляем в множество числа a и b
• 3. Выбираем из множества два любых различных числа и добавляем во множество их произведение, повторяем шаг новер 3 (неоднократно)

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

Входной файл:
Даны три числа через пробел a,b,d (1 <= a,b,d<= 1E16; a != b)/

Выходной файл:
Если число d находится во множетсве чудака, то выведите YES, иначе выведите NO
*********************************** ***********************

P.S.
Писать можно почти на всем стандартном:
• java
• C#
• C
• C++
• Basic
• Pascal
• Delphi

[MooNDeaR]

Задание 2:
H. Дерево NEXUS

Ограничения те же.

Задача:
Жил был Чудак. Чудак любит деревья NEXUS. Деревом NEXUS он называет любое (необязательно сбалансированное) бинарное дерево, в котором только в листах дерева лежат числа и сумма по всем листам A[i] * P[i] минимальна, где A[i] - число в i-ом листе, P[i] - длина пути от i-го листа до корня дерева. ваша задача для данных N чисел найти дерево NEXUS.

Входной файл:
В первой строке дано N - кол-во чисел (1 <= N <= 20). Во второй строке через пробел даны сами числа A[i] (1 <= A[i] <= 1000).

Выходной файл:
Для дерева NEXUS построенного на данном наборе чисел, вывести его сумму A[i] * P[i].

Пример:
test.in:
4
7 10 5 10

test.out
64
*********************************** ******************
Остальное не буду выкладывать, т.к. там рисунки нужны, да и задачи решабельные, просто много времени бы ушло. У меня не было столько.

[Alexandr555]

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

[anyx]

Сообщение от MooNDeaR

P.S.
Писать можно почти на всем стандартном:
• java
• C#
• C
• C++
• Basic
• Pascal
• Delphi

А где Haskell? Или хотя бы Python?

[Corus]

Первая задача:
В беск. цикле делим d на то из чисел a и b, на которое оно делится без остатка. Рез-т присваиваем d. Если на каком-то шаге:
1). d ни на a, ни на b не делится: NO.
2). d равно a или b: YES.

[Juffin]

Ну первая задача вроде несложная. Если d можно разложить в произведение a*a*...*a*b*b*...*b, то тогда оно входит в множество.

[_PROGRAMM_]

Писать можно почти на всем стандартном

Нет самого главного. Assembler'а. На моей олимпиаде кроме паскаля вообще ничего не проверялось.