Страницы

Уроки 63, 64 Решение олимпиадных задач

Задание 1. Номер автобусного билета - шестизначное число ( первый билет 000000, второй 000001 и т.д.). Подсчитать число всех "счастливых" билетов ("счастливым" называется билет, у которого сумма первых трех цифр равна сумме трех последних).


output.txt
Число счастливых билетов

Указание: Решение задачи перебором всех шестизначных чисел превысит время тестирования.
Разделим число на две части по три цифры. организуем перебор всех цифр первой части от 000 до 999. Для каждого из этих чисел найдем сумму цифр и добавляем   1 в элемент массива А с номером, равным сумме цифр. В результате массив А заполнится количествами сумм цифр, где суммы цифр и соответственно номера элементов массива А принимают значения от 0 до 27.
Например, а[2] принимает значение, равное 6 (т.е. сумма цифр, равных 2, будет 6: 002, 011, 020, 101, 110, 200).
Если i - это сумма цифр трехзначного номера, то a[i] - количество всех трехзначных номеров с суммой цифр i. Тогда количество "счастливых" билетов с суммой первых трех цифр i для шестизначного номера составит a[i]*a[i], так как каждому из a[i] билетов первой тройки цифр найдется ровно a[i] билетов с суммой цифр i во второй тройке цифр.
Просуммировав все количества "счастливых" шестизначных билетов, для каждого i от 0 до 27 найдем общее количество "счастливых" билетов.


      Посмотреть решение        



Задание 2. Натуральное число из N цифр является числом Армстронга, если сумма его цифр, возведенных в N-ую степень, равна самому числу (как, например, 153=13+53+33). Получить все числа Армстронга, состоящие из двух, трех и четырех цифр.


output.txt
...
153
...

Указание: 
Рассмотреть три отдельных фрагмента программы для поиска двузначных, трехзначных и четырехзначных чисел Армстронга.
Двумя циклами по a и b сформируем все двузначные числа и выведем на экран те, для которых с1*с1+с2*с2=i, где двузначное число i составляется из цифр с1 и с2 по формуле i:=с1*10+с2. Аналогично для трехзначных и четырехзначных чисел.


        Посмотреть решение       


Задание 3. Из одномерного массива, состоящего из N элементов, удалить те, которые встречаются только один раз. Массив сжать, т.е. на освободившиеся места передвинуть оставшиеся элементы массива, соблюдая порядок их первоначального расположения. Разрешается использовать только один массив (для исходных данных). Все числа натуральные <=100.

Ввод:
1 строка – N - количество элементов в массиве
2 строка – элементы массива

Вывод: 
оставшиеся элементы массива
Пример:


Input.txt
Output.txt
4
2  5  2  7
2  2


Указание: Просматриваем элементы массива, пока не находим элемент. который не повторяется (a[i]). все элементы массива, находящиеся правее найденного, сдвигаем на один шаг влево. Количество элементов уменьшаем на 1 и с оставшимися элементами совершаем аналогичные действия с места последней остановки по индексу i.


    Тесты     Посмотреть решение    


Задание 4. Дано натуральное число N (N<=999). Записать это число русскими словами (семнадцать, двести пятьдесят три).

Ввод:
1 строка – N - число

Вывод: 
число словами

Пример:


Input.txt
Output.txt
25
двадцать пять


Указание: найдем количество сотен (s), количество десятков (d)  и количество единиц (e), а также число. содержащее две последние цифры (p) в заданном числе N. 
Если p принадлежит промежутку 11..19, то нет необходимости выводить количество десятков и единиц и d=p, е=0.
Использовать команду case для сотен, десятков и единиц ( в команду выбора по десяткам добавить и числа от 11 до 19). 
В зависимости от значений s, d, e находим части строки, из которых затем легко можно составить все название числа.

     Тесты     Посмотреть решение      


Задание 5. В последовательности цифр а1, а2, а3,... каждый член, начиная с четвертого, равен последней цифре суммы трех предыдущих. Написать программу, которая по заданным а1, а2, а3 определяет aN для введенного N (n<=2000).

Ввод:
1 строка – три числа а1, а2, а3
2 строка - число N
Вывод: 
аN

Пример:


Input.txt
Output.txt
2  4  9
5
8

Комментариев нет:

Отправить комментарий