Результат (файл sms.out)

Олимпиадные задания 2 этапа Всеукраинских ученических олимпиад по информатике.

Задача №1. Число (30 баллов)

Задано натуральное десятичное число N (N<= 1 000 000 000). Написать программу вычисления количества принадлежащих диапазону от 1 до N чисел, в двоичном представлении которых содержится ровно K значащих нулей.

Входные данные.

Первая строка входного файла NUMBER.DAT содержит числа N и K.

Выходные данные.

Первая строка выходного файла NUMBER.SOL содержит количество чисел.

Пример входных и выходных данных.

NUMBER.DAT	NUMBER.SOL
18 3

 

Замечание.

Например, для N=18 K=3 таких чисел 3 (8, 17, 18)

 

Задача №2. Делители числа. (40 баллов)

Определить какую цифру нужно дописать справа к числу 250, чтобы образованное четырехзначное число, имело два простых делителя, оканчивающиеся дописанной цифрой.

 

Выходные данные.

Первая строка выходного файла DIVIDED.SOL содержит значения простых делителей, удовлетворяющих условию задачи. Вторая строка выходного файла DIVIDED.SOL содержит дописанную цифру.

 

Задача №3. Троллейбусы. (50 баллов).

Троллейбусы одного маршрута проходят через остановку каждые K (1≤K≤500) минут. Известно время прихода каждого из N (1≤N≤100000) жителей города на остановку (N,K-целые числа). Если человек приходит на остановку в момент прихода троллейбуса, то он так же успевает войти в этот троллейбус. Необходимо написать программу определения времени прибытия первого троллейбуса на остановку ( это число от 0 до K-1) такого, чтобы :

- суммарное время ожидания троллейбуса для всех граждан было минимально;

- максимальное время ожидания троллейбуса было минимально.

Входные данные.

В первой строке файла INPUT.TXT записано число K, во второй – N, а затем N строк, в которых указано время прихода каждого человека на остановку (числа от 0 до 100 000).

Выходные данные.

В файл OUTPUT.TXT записывается два числа, каждое в отдельной строке, являющиеся ответами на первый и второй вопросы задачи соответственно.

Пример входных и выходных данных.

INPUT.TXT	OUTPUT.TXT

 

 

Олимпиадные задания 3 этапа Всеукраинских ученических олимпиад по информатике.

Задание № 1.

Поезд

 

Ограничение времени: 1 секунда

Входной файл: train.inp

Выходной файл: train.out

(20 баллов)

Иногда на старых железнодорожных станциях можно встретить поворотный круг –специальное устройство, позволяющее менять местами два соседних вагона в поезде. Предположим, что некоторый поезд был составлен L вагонов пронумерованных в случайном порядке. Поворотный круг позволяет переставлять местами в этом поезде только два соседних вагона. Какое минимальное количество перестановок нужно сделать, чтобы вагоны оказались расположены в возрастающем порядке от 1 до L.

Исходные данные (файл train.inp)

Входной текстовый файл train.inp состоит из двух строк. В первой строке содержится единственное целое число L (1 <= L <= 50) – количество вагонов в поезде. Во второй строке содержится ровно L различных целых чисел в диапазоне от 1 до L, то есть некоторая перестановка чисел от 1 до L.

Результат (файл train.out)

Выходной текстовый файл train.out должен содержать единственное число – минимальное количество перестановок соседних вагонов, необходимое для того, чтобы расположить вагоны в возрастающем порядке от 1 до L.

ВНИМАНИЕ! Число выводить с переводом строки!

Примеры исходных данных и результатов

Файл train.inp	Файл train.out
3 1 3 2
4 4 3 2 1
2 2 1
4 4 1 2 3

 

 

Задание № 2

 

SMS
Ограничение времени: 0.5 секунды

Входной файл: sms.inp

Выходной файл: sms.out

(50 баллов)

SMS-спам – это перспективная технология массовой рассылки рекламных текстов в виде SMS сообщений. Очень удобно, очень эффективно, очень просто. Впрочем, не совсем просто. Вся проблема в том, что длина одного SMS сообщения ограничена, а рекламные тексты могут быть весьма длинными. К счастью, рекламный текст может быть разбит на несколько частей, каждая из которых будет отправлена в виде отдельного SMS сообщения. Но за каждое отправленное SMS сообщение нужно платить. Поэтому рекламный текст необходимо отправить благодарному получателю в виде минимально возможного количества SMS сообщений.

Для желающих сэкономить ушлые операторы придумали забавную фишку. SMS сообщение, содержащее только латинские буквы и пробелы, может достигать целых M символов в длину, в то время как длина SMS сообщения, содержащего произвольные символы, ограничена всего N символами.

Исходные данные (файл sms.inp)

Первая строка входного текстового файла sms.inp содержит целые числа N и M (1<=N<=M<=1000). Вторая строка содержит рекламный текст. Рекламный текст имеет длину от 1 до 10000 символов и содержит только латинские буквы, пробелы, цифры и знаки препинания "." (точка), "," (запятая), ";" (точка с запятой), ":" (двоеточие), "!" (восклицательный знак), "?" (вопросительный знак), "-" (дефис) и """ (двойные кавычки). Рекламный текст заканчивается переводом строки.

Результат (файл sms.out)

В текстовый файл sms.out вывести единственное число - минимальное количество SMS сообщений, в виде которых можно отправить исходный рекламный текст.

ВНИМАНИЕ! Число выводить с переводом строки!