Задача в неделю (стр. 7 )

Эта система вначале была с радостью принята жителями острова. Когда первые восторги рассеялись, очевидны стали, однако, некоторые недостатки новой системы. Оказалось, что сторонники партии, предложившей систему, смогли оказать некоторое влияние на формирование групп избирателей. Благодаря этому, они получили возможность проводить некоторые решения, не обладая при этом реальным большинством голосов.

Пусть, например, на острове были сформированы три группы избирателей, численностью в 5, 5 и 7 человек соответственно. Тогда партии достаточно иметь по три сторонника в каждой из первых двух групп, и она сможет провести решение всего 6-ю голосами "за", вместо 9-и, необходимых при общем голосовании.

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

Технические требования:

Входной файл: INPUT. TXT

Выходной файл: OUTPUT. TXT

Ограничение по времени тестирования: по 5 секунд на один тест.

Формат входных данных:

Входной файл INPUT. TXT состоит из двух строк. В первой строке записано натуральное число K<1001 - количество групп избирателей. Во второй строке через пробел записаны K натуральных чисел, которые задают количество избирателей в группах. Население острова не превосходит 30000 человек.

Формат выходных данных:

В выходной текстовый файл OUTPUT. TXT записывается найденное число.

Пример файла входных данных:

3

5 5 7

Пример файла выходных данных (для приведенного выше входного файла):

6

 Разбор задачи № N

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

var

a : array [1..1000] of integer;

n, i, j, k, min : integer;

begin

assign(input,'input. txt'); reset(input);

assign(output,'output. txt'); rewrite(output);

readln(n);

for i:=1 to n do read(a[i]);

for i:=1 to n div 2+1 do

begin

k:=i; min:=a[i];

for j:=i+1 to n do

if a[j]<min then begin min:=a[j]; k:=j end;

a[k]:=a[i]; a[i]:=min

end;

k:=0;

for i:=1 to n div 2+1 do

k:=k+a[i] div 2 +1;

write(k)

end.

Задача O. "ЧТО ТУТ СЧИТАТЬ?" (20 баллов)

Задано натуральное десятичное число N (N£1.000.000.000).

Требуется написать программу вычисления количества принадлежащих диапазону от 1 до N чисел, в двоичном представлении которых содержится ровно K значащих нулей. Например, для N=18 и K=3 таких чисел — 3 (8, 17, 18).

Технические требования:

Входной файл: INPUT. TXT

Выходной файл: OUTPUT. TXT

Ограничение по времени тестирования: 5 секунд на один тест.

Формат входных данных:

В текстовом файле INPUT. TXT в первой строке записано число N, а во второй - K.

Формат выходных данных:

Вывести в текстовый файл OUTPUT. TXT полученное количество.

Пример файла входных данных:

18

3

Пример файла выходных данных (для приведенного выше входного файла):

3

Задача P. "Коррозия металла" (20 баллов)

Для хранения двух агрессивных жидкостей A и B используется емкость с многослойной перегородкой, которая изготавливается из имеющихся N листов. Для каждого листа i (i = 1, …, N) известно время его растворения жидкостью A — ai  и жидкостью B — bi. Растворение перегородки каждой из жидкостей происходит последовательно лист за листом, с постоянной скоростью по толщине листа.

Требуется написать программу проектирования такой перегородки, время растворения которой было бы максимальным.

Технические требования:

Входной файл: INPUT. TXT

Выходной файл: OUTPUT. TXT

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

Формат входных данных:

В первой строке входного файла записано число N (1£N£256). В каждой из последующих N строк содержатся два положительных вещественных числа ai и bi, разделенные пробелом.

Формат выходных данных:

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

Пример файла входных данных:

4

1 2

1 2

0.5 1.5

7 3.5

Пример файла выходных данных

(для приведенного выше входного файла):

6.000

4 2 1 3

Задача Q. "Факториал" (20 баллов)

Факториалом натурального числа N (обозначается N!) называется произведение всех натуральных чисел от 1 до N включительно: N! = 1×2×3×…×N.

Требуется написать программу, которая определит, каким количеством цифр «0» заканчивается запись числа N! в K-ричной системе счисления.

Технические требования:

Входной файл: INPUT. TXT.

Выходной файл: OUTPUT. TXT.

Ограничение времени: 5 секунд на тест.

Формат входных данных:

Во входном файла содержится два числа: N и K (1£N£2×109, 2£K£5000). Оба числа записаны в десятичной системе счисления.

Формат выходных данных:

В выходной файл вывести количество нулей, которыми в K-ричной системе счисления оканчивается число N!. Число вывести в десятичной системе счисления.

Пример файла входных данных:

10000 10

Пример файла выходных данных (для приведенного выше входного файла):

2499

Задача R. "Палиндром" (20 баллов)

Палиндром – это симметричная строка, т. е. она одинаково читается как слева направо, так и справа налево.

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

Технические требования:

Входной файл: INPUT. TXT.

Выходной файл: OUTPUT. TXT.

Ограничение времени: 5 секунд на тест.

Формат входных данных:

Файл INPUT. TXT состоит из двух строк. Первая строка содержит одно число – длину N входной последовательности (3£N£5000). Вторая – строку длины N, которая состоит из прописных букв от ‘A’ до ‘Z’, строчных букв от ‘a’ до ‘z’, цифр от ‘0’ до ‘9’. Прописные и строчные буквы считаются различными.

Формат выходных данных:

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

Пример файла входных данных:

5

Ab3Bd

Пример файла выходных данных

(для приведенного выше входного файла):

2

Задача S. "Гири" (20 баллов)

На левой чашке весов лежит груз в N грамм, где N - натуральное число. Имеется по одной гире в 1, 3, 9, 27, 81, ... грамм.

Требуется написать программу, которая укажет, какие гири и на какую чашку весов надо поставить, чтобы уравновесить груз.

Технические требования:

Входной файл: INPUT. TXT.

Выходной файл: OUTPUT. TXT.

Ограничение времени: 5 секунд на тест.

Формат входных данных:

Файл INPUT. TXT состоит из одной строки, в которой содержится число N (1£N£1000000000).

Формат выходных данных:

В выходной файл OUTPUT. TXT вывести номер гири (0 – 1 грамм, 1 – 3 грамма, 2 – 9 грамм, …) и через пробел символ ‘L’ если гиря ставится на левую чашку весов или ‘R’ иначе. Используемые гири выводить в порядке возрастания номеров.

Пример файла входных данных:

2

Пример файла выходных данных (для приведенного выше входного файла):

0 L

1 R

Задача T. "Числа" (20 баллов)

Задано натуральное число N.

Требуется написать программу, которая находит количество натуральных чисел, не пре­вышающих N и не делящихся ни на одно из чисел 2, 3, 5.

Технические требования:

Входной файл: INPUT. TXT.

Выходной файл: OUTPUT. TXT.

Ограничение времени: 3 секунды на тест.

Формат входных данных:

Файл INPUT. TXT состоит из одной строки, в которой содержится число N (1£N£1000000000).

Формат выходных данных:

В выходной файл OUTPUT. TXT вывести найденное число.

Пример файла входных данных:

10

Пример файла выходных данных (для приведенного выше входного файла):

2

Задача V. "Числа" (20 баллов)

Для натуральных чисел X и Y будем говорить, что X входит в Y, ес­ли дво­ичную запись числа X можно получить из двоичной записи Y вычерки­ванием нуле­вого, единичного или большего количества цифр. Например, X=1010 входит в Y=1001100.

Требуется написать программу, которая для двух данных натуральных чисел A и B найдет максимальное число C, входящее как в A, так и в B.

Технические требования:

Входной файл: INPUT. TXT.

Выходной файл: OUTPUT. TXT.

Ограничение времени: 3 секунды на тест.

Формат входных данных:

Файл INPUT. TXT состоит из одной строки, в которой через пробел записаны числа A и B (1£A, B£1000000000).

Формат выходных данных:

В выходной файл OUTPUT. TXT вывести найденное число C.

Пример файла входных данных:

3 6

Пример файла выходных данных (для приведенного выше входного файла):

3

Задача W. "Сумма" (20 баллов)

Рассмотрим сумму

Требуется написать программу, которая находит по заданному n (2<n<1000) сто десятичных цифр дробной части числа Sn.

Технические требования:

Входной файл: INPUT. TXT.

Выходной файл: OUTPUT. TXT.

Ограничение времени: 3 секунды на тест.

Формат входных данных:

Файл INPUT. TXT состоит из одной строки, в которой записано число n.

Формат выходных данных:

В выходной файл OUTPUT. TXT вывести найденные цифры.

Пример файла входных данных:

3

Пример файла выходных данных (для приведенного выше входного файла):

83333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333333

Задача X. "Цифра на N-ом месте" (20 баллов).

В бесконечную бинарную последовательность выписаны натуральные числа по возрастанию в двоичном виде: 11011100101110111100010011010.... Определить, какая цифра стоит на N-м месте.

Требуется написать программу для решения задачи.

Технические требования:

Входной файл: INPUT. TXT

Выходной файл: OUTPUT. TXT

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

Формат входных данных:

Входной файл INPUT. TXT содержит натуральное число N (1≤N≤1000000000).

Формат выходных данных:

Выходной файл OUTPUT. TXT должен содержать найденную цифру.

Пример файла входных данных:

5

Пример файла выходных данных (для приведенного выше входного файла):

1

Задача Y. "Первая цифра" (20 баллов)

Известно натуральное число k.

Требуется написать программу для определения такого наименьшего натурального число, которое уменьшается в k раз при зачеркивании первой цифры.

Технические требования:

Входной файл: INPUT. TXT

Выходной файл: OUTPUT. TXT

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

Формат входных данных:

Единственная строка входного файла содержит целое число k (1 £ k£ 32767).

Формат выходных данных:

Выходной файл OUTPUT. TXT должен содержать либо значение найденного числа, либо число 0, если такого числа не существует.

Пример файла входных данных:

6

Пример файла выходных данных (для приведенного выше входного файла):

12

Задача Z. "Домино" (20 баллов)

Дан комплект домино (0, 0), (0, 1), ..., (6, 6) (всего 28 штук).

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

Технические требования:

Входной файл: INPUT. TXT

Выходной файл: OUTPUT. TXT

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

Формат входных данных:

Единственная строка входного файла содержит два целых числа SUM (0£ SUM£32767) и N (1£N£28), разделенных пробелом.

Формат выходных данных:

Выходной файл OUTPUT. TXT должен содержать либо найденную правильную раскладку (в файле должно быть N строк, в каждой строке через пробел записываются значения на кости домино), либо число 0, если такая раскладка невозможна.

Пример файла входных данных:

20

4

Пример файла выходных данных (для приведенного выше входного файла):

0 1

1 1

1 6

6 4