Паскаль, несколько задач.

Отменен
Раздел: Программирование
Предмет: Pascal
Тип работы: Задача
Срок сдачи: Не определен
11 Ноя 2015 в 02:40
Цена: Договорная
Блокировка: 10 дней
Заказчик:
Номер заказа: 429773
Размещен: 11 Ноя 2015 в 11:47
Просмотров: 67
Антиплагиат:

Описание работы

Задача 2. Необычное развлечение
Когда Георгию становится скучно на уроках математики, он развлекает себя следующим образом: берет натуральное число n и получает из него единицу с помощью последовательных делений без остатка. На каждом шагу Георгий делит текущее число на любой его натуральный делитель, отличный от единицы.
Например, если n=30, то существует несколько способов получить из него единицу. Например, 30→10→1 или 30→6→3→1, или 30→1. Всего это можно сделать 13 способами.
Георгий просит вас помочь подсчитать количество способов, которыми он может получить из числа n единицу. Два способа n→x1→…→xk→1 и n→y1→…→ym→1 считаются различными, если k≠m или существует i такое, что xi≠yi.
Вход: файл input.txt, в первой строке записано натуральное число n.
Ограничения: 1≤N≤2*109
Выход: файл output.txt, содержащий единственное число – количество способов получить из числа n единицу по модулю (109+7) (т. е. вывести остаток от деления количества способов получить единицу на 109+7).
Примеры:
input.txt
output.txt
1
1
9
2
30
13
Задача 3. Конструктор
Помимо математики Георгий любит собирать замки из конструкторов. В магазин завезли n конструкторов. Конструкторы пронумерованы числами от 1 до n.
У Георгия есть 2 способа получить нравящийся конструктор:
Купить его. Конструктор с номером i стоит ci рублей;
Купить и объединить два конструктора, получив из них другой конструктор. Возможные способы компоновки конструкторов заданы тройками чисел (x, y, z). Купив конструкторы с номерами y и z, можно их объединить и получить один конструктор с номером x. Всего есть m доступных троек (x, y, z)
Георгий ограничен в средствах и просит вас помочь ему найти минимальную сумму денег, которую нужно будет потратить, чтобы собрать конструктор, из которого можно будет построить замок номер 1.
Вход: файл input.txt, в первой строке записаны два целых числа n и m. Во второй строке содержатся n чисел ci – стоимости конструкторов. В следующих m строках содержится по 3 числа xi, yi, zi – это означает, что конструктор номер xi может быть скомпонован из конструкторов yi и zi.
Ограничения: 1≤ n≤ 104, 0≤ m≤ 105, 0 ≤ ci ≤ 109, 1 ≤xi,yi,zi≤ n
Выход: файл output.txt, содержащий единственное число – минимальная сумма денег, которую потратит Георгий.
Примеры:
input.txt
output.txt
4 2
8 1 1 3
4 2 3
1 2 4
3
4 2
2 1 1 3
4 2 3
1 2 4
2

Примечание:
В первом тестовом примере, можно купить конструкторы номер 2 и 3, собрать из них детали для конструктора номер 4, затем купить ещё один конструктор номер 2 и собрать из имеющихся конструкторов конструктор номер 1. На это будет затрачено 1+1+1=3 рубля.
Нужна аналогичная работа?
Оформи быстрый заказ и узнай стоимость
Гарантированные бесплатные доработки
Быстрое выполнение от 2 часов
Проверка работы на плагиат

Рекомендуемые заказы

Хотите выполнять заказы? Стать экспертом
Хотите заказать работу? Разместить заказ
Доверьте свою работу экспертам
Разместите заказ
Наша система отправит ваш заказ на оценку 31 626 авторам
Первые отклики появятся уже в течение 10 минут