Задача в неделю. Олимпиадные задачи по информатике. Задание U-го занятия
Югорский НИИ информационных технологий
Югорский государственный университет
Институт развития образования ХМАО-Югры
Телекоммуникационный проект "Задача в
неделю"
Занятие № U (18 мая 2009 года)
Задания проекта в этом учебном году выбираются на сайте <Олимпиады по информатике (ХМАО-Югра)>.
Для работы с этим ресурсом надо на нём зарегистрироваться. После этого
вы сможете не только сдавать задания нашего проекта, но и самостоятельно решать
задачи из <Архива задач> и
принимать участие в соревнованиях (раздел <Олимпиады>). На выполнение
сегодняшнего задания отводится одна неделя - до 10 часов московского времени 25
мая.
535. Неправильное сложение
(Время:
1 сек. Память: 16 Мб Баллы: 100)
Володя написал
программу, которая складывает в столбик два числа. К сожалению, он не
разобрался, как правильно переносить единицу из одного разряда в следующий. Поэтому программа стала выполняться следующим
образом. Сначала она складывает последние цифры обоих чисел и записывает
результат, как в случае, если он однозначный, так и в случае, если он
двузначный. Затем программа складывает предпоследние цифры обоих чисел и результат сложения приписывает слева к результату
предыдущего сложения. Далее процесс повторяется для всех разрядов. Если в одном
числе цифр меньше, чем в другом, то программа размещает нули в соответствующих
разрядах более короткого числа.
Федя хочет доказать
Володе, что его способ сложения не обладает свойством ассоциативности. В
частности, Федя утверждает, что существуют три числа, для которых важен порядок,
в котором их складывают (при этом разрешается складывать числа в любом порядке,
например можно сначала сложить первое число и последнее, а затем прибавить к
ним среднее). Федя привел даже пример трех таких чисел.
Требуется написать
программу, которая поможет Феде и Володе определить, верно
ли утверждение, что, складывая заданные три числа в разном порядке, можно
получить разные суммы.
Входные данные
Входной файл INPUT.TXT
содержит в одной строке три целых числа a, b и c (1≤a,b,c≤106). Все
числа в строке разделены пробелом.
Выходные данные
В первую строку
выходного файла OUTPUT.TXT необходимо вывести слово YES, если данные три числа
можно сложить разными способами и получить разные суммы. В противном случае,
необходимо вывести слово NO.
В последующих строках
необходимо вывести все возможные суммы, которые можно получить, складывая числа
a, b и c.
Суммы следует выводить по одной на строке и в порядке их возрастания.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
30
239 566
YES
7945
71215
2
643
733 553
NO
18129
536. Числа - 2
(Время: 1 сек.
Память: 16 Мб Баллы: 100)
Решая задачу по
информатике, Вова в очередной раз допустил ошибку. Он снова вывел в выходной
файл числа, забыв разделить их пробелами. Увидев полученный результат, Вова сначала огорчился, а потом задумался над следующим
вопросом: сколько существует различных последовательностей неотрицательных
целых чисел, таких что, если выписать их без пробелов, то получится тот же
результат, что и у него. Он вспомнил также, что его программа смогла вывести не
произвольные числа, а только те, что не превосходят C и не имеют ведущих нулей.
Чтобы ответить на
поставленный вопрос, Вова решил написать программу, которая позволит ему найти
число различных последовательностей неотрицательных целых чисел, в каждой из
которых любое число не превосходит C. Он понимал, что такое число могло быть
достаточно большим, поэтому ограничился поиском только последних k цифр этого числа.
Требуется написать
программу, которая покажет Вове, как можно правильно решить поставленную им
задачу.
Входные данные
Первая строка входного
файла INPUT.TXT содержит три целых числа - N, C и K (1≤N≤50000, 1 ≤ C ≤ 108,
1 ≤ K ≤ 18). Во второй строке этого файла содержится результат работы
Вовиной программы, состоящий из N цифр.
Выходные данные
В выходной файл
OUTPUT.TXT выведите последние K цифр искомого количества последовательностей
без ведущих нулей.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
3
11 2
111
3
2
19
9 1
0123456789876543210
1
3
1
8 3
9
0
Сдать решения этой задачи можно в разделе <Олимпиады> в указанное там время. Для
этого выберите олимпиаду <Занятие U
проекта> и подайте заявку на участие в ней. После сдачи задачи прошу прислать на
мой электронный адрес описание результатов вашей работы (оформляйте это одним
файлом, содержащим ваши персональные данные, описание алгоритма и текст вашей программы).
На основе результатов сдачи и присланных материалов будет
подготовлен разбор задачи.