2-я командная олимпиада
Задача A. Последовательность Кеане
(Время: 1 сек. Память: 16 Мб)
Бесконечная последовательность битов, предложенная Кеане, равна 001001110001001110110110001… и формируется следующим алгоритмом: вначале записывается 0, потом 001, далее 001001110, то есть, для получения следующего члена, предыдущий записывается дважды, а справа приписывается его отрицание. Элементы этого ряда являются начальными подпоследовательностями Кеане.
Требуется написать программу, которая по заданному n определит N-й бит этой последовательности.
Входные данные
Входной файл INPUT. TXT содержит число N (N ≤ 10200).
Выходные данные
В выходной файл OUTPUT. TXT должен содержать найденный бит.
Примеры
№ | INPUT. TXT | OUTPUT. TXT |
1 | 3 | 1 |
2 | 18 | 0 |
Решение
Каждый раз длина последовательности увеличивается в три раза. При этом только в третьей части происходит перемена 0 на 1 и 1 на 0. Таким образом, надо подсчитать для заданного n количество таких перемен. Так как число может быть 201-значным, то для его хранения и операций с ним надо использовать «длинную» арифметику. Подробности приведены в программе.
Программа
var
n : longint;
k, m, i, p : integer;
s : string;
a : array [0..201] of integer;
begin
assign(input,'input. txt'); reset(input);
assign(output,'output. txt'); rewrite(output);
readln(s);
m:=length(s); a[0]:=1;
for i:=1 to m do a[m+1-i]:=ord(s[i])-48;
p:=-1; i:=1;
while p<0 do begin
p:=a[i]+p; if p<0 then a[i]:=9 else a[i]:=p;
i:=i+1 end;
while a[m]=0 do m:=m-1;
k:=0;
while m>0 do begin
p:=0;
for i:=m downto 1 do begin
p:=p*10+a[i];
a[i]:=p div 3;
p:=p mod 3
end;
if p mod 3=2 then k:=1-k;
while a[m]=0 do m:=m-1;
end;
write(k)
end.
Задача B. Подарки
(Время: 1 сек. Память: 16 Мб)
Приближался Новый год и отец купил своим детям по подарку. Оказалось, что в них разное количество конфет. Тогда отец купил еще конфет и стал их раскладывать по подаркам следующим образом: брал один из подарков с наименьшим количеством конфет и добавлял в него одну конфету.
Требуется написать программу, которая найдет наименьшее количество конфет, оказавшихся в одном из подарков после завершения раскладывания всех конфет.
Входные данные
Входной текстовый файл INPUT. TXT содержит в первой строке N – количество детей и M – количество купленных конфет. Числа записаны через пробел, 1 ≤ N ≤ 10 000, 1 ≤ M ≤ 1 000 000. Далее в N строках записаны числа в диапазоне от 1 до 30000 – количество конфет в подарках.
Выходные данные
Выходной файл OUTPUT. TXT должен содержать одно найденное число.
Пример
№ | INPUT. TXT | OUTPUT. TXT |
1 | 2 4 | 3 |
Решение
Упорядочим массив по возрастанию методом выбора. Теперь добавляем к первому подарку столько конфет, чтобы их стало столько же, сколько во втором подарке. После этого добавляем к первым двум подаркам столько конфет, чтобы их стало как и в третьем подарке. Эту процедуру продолжаем до тех пор, пока имеются конфеты. После этого легко вычислить требуемое в задаче число конфет.
Программа
var
a : array [1..10001] of longint;
n, i : integer;
m : longint;
procedure sort;
var i, j, x, k : integer;
begin
for i:=1 to n-1 do begin
x:=a[i]; k:=i;
for j:=i+1 to n do
if a[j]<x then begin x:=a[j]; k:=j end;
if i<>k then begin a[k]:=a[i]; a[i]:=x end
end
end;
begin
assign(input,'input. txt'); reset(input);
assign(output,'output. txt'); rewrite(output);
read(n, m);
for i:=1 to n do read(a[i]);
sort;
a[n+1]:=1000000;
i:=1; while a[i+1]=a[i] do i:=i+1;
while m div i +a[i]>a[i+1] do begin
m:=m-(a[i+1]-a[i])*i;
i:=i+1; while a[i+1]=a[i] do i:=i+1 end;
write(a[i]+m div i)
end.
Задача C. Нить Ариадны
(Время: 1 сек. Память: 16 Мб)
Тезею из лабиринта Минотавра помог выйти клубок ниток. Вы можете вместо клубка использовать персональный компьютер.
Требуется написать программу, которая вводит маршрут Тезея в лабиринте и находит обратный путь, по которому Тезей сможет выйти из лабиринта, не заходя в тупики и не делая петель.
Входные данные
Входной файл INPUT. TXT содержит маршрут Тезея, который представлен строкой, состоящей из букв: N, S, W, E и длиной не более 200.
Буквы означают:
N - один "шаг" на север,
S - один "шаг" на юг,
W - один "шаг" на запад,
E - один "шаг" на восток.
Выходные данные
В выходной файл OUTPUT. TXT записывается аналогично входному файлу найденный обратный путь. Если маршрут неоднозначен, то следует выбирать согласно следующему приоритету: N, E, S, W.
Пример
№ | INPUT. TXT | OUTPUT. TXT |
1 | EENNESWSSWE | NWW |
Решение
Будем считать, что вначале находимся в точке с координатами (0; 0). В массив будем записывать координаты следующей точки маршрута Тезея, при этом каждый раз проверяем пересечение маршрута. Если пересечение было, то удаляем часть массива.
Программа
var
s, t : string;
a : array [1..2,0..200] of integer;
i, j, k : integer;
begin
assign(input,'input. txt'); reset(input);
assign(output,'output. txt'); rewrite(output);
readln(s); t:='';
k:=0; a[1,k]:=0; a[2,k]:=0;
for i:=1 to length(s) do begin
k:=k+1;
if s[i]='N' then begin a[1,k]:=a[1,k-1]; a[2,k]:=a[2,k-1]+1; t:=t+'S' end;
if s[i]='E' then begin a[1,k]:=a[1,k-1]+1; a[2,k]:=a[2,k-1]; t:=t+'W' end;
if s[i]='S' then begin a[1,k]:=a[1,k-1]; a[2,k]:=a[2,k-1]-1; t:=t+'N' end;
if s[i]='W' then begin a[1,k]:=a[1,k-1]-1; a[2,k]:=a[2,k-1]; t:=t+'E' end;
j:=0;
while (a[1,j]<>a[1,k]) or (a[2,j]<>a[2,k]) do j:=j+1;
if j<k then begin
delete(t, j+1,k-j);
k:=j
end
end;
for i:=length(t) downto 1 do write(t[i])
end.
Задача D. Выборы
(Время: 1 сек. Память: 16 Мб)
В одном из государств все решения традиционно принимались простым большинством голосов на общем собрании граждан, которых, к счастью, было не очень много. Одна из местных партий, стремясь прийти к власти как можно более законным путем, смогла добиться некоторой реформы избирательной системы. Главным аргументом было то, что население острова в последнее время значительно возросло, и проведение общих собраний перестало быть легкой задачей.
Суть реформы состояла в следующем: с момента введения ее в действие все избиратели острова делились на K групп (необязательно равных по численности). Голосование по любому вопросу теперь следовало проводить отдельно в каждой группе, причем считалось, что группа высказывается "за", если "за" голосует более половины людей в этой группе, а в противном случае считалось, что группа высказывается "против". После проведения голосования в группах подсчитывалось количество групп, высказавшихся "за" и "против", и вопрос решался положительно в том и только том случае, когда групп, высказавшихся "за", оказывалось более половины общего количества групп.
Эта система вначале была с радостью принята жителями острова. Когда первые восторги рассеялись, очевидны стали, однако, некоторые недостатки новой системы. Оказалось, что сторонники партии, предложившей систему, смогли оказать некоторое влияние на формирование групп избирателей. Благодаря этому, они получили возможность проводить некоторые решения, не обладая при этом реальным большинством голосов.
Пусть, например, на острове были сформированы три группы избирателей, численностью в 5, 5 и 7 человек соответственно. Тогда партии достаточно иметь по три сторонника в каждой из первых двух групп, и она сможет провести решение всего 6-ю голосами "за", вместо 9-и, необходимых при общем голосовании.
Требуется написать программу, которая по заданному разбиению избирателей на группы определит минимальное количество сторонников партии, достаточное для принятия любого решения.
Входные данные
Входной файл INPUT. TXT состоит из двух строк. В первой строке записано натуральное число K < 1001 - количество групп избирателей. Во второй строке через пробел записаны K натуральных чисел, которые задают количество избирателей в группах. Население острова не превосходит 30000 человек.
Выходные данные
В выходной файл OUTPUT. TXT выведите ответ на задачу.
Примеры
№ | INPUT. TXT | OUTPUT. TXT |
1 | 3 | 6 |
2 | 5 | 5 |
Решение
Хотя и условие задачи довольно длинное, но решение достаточно простое. Упорядочим массив количества избирателей в каждом в округе по возрастанию. Как следует из условия для победы в округе необходимо набрать более половины голосов в каждом округе и победить в более половины округов. Из этого следует, что для победы с минимальным общим количеством избирателей надо победить в округах с наименьшим количеством избирателей. Так как надо победить только в половине округов, то и сортировать массив надо только до середины. Подробности реализации приведенных аргументов смотрите в программе.
Программа
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.
Задача E. Слон
(Время: 1 сек. Память: 16 Мб)
На шахматной доске 8*8 клеток стоит слон (фигура, которая ходит по диагонали).
Требуется написать программу, которая определит: сможет ли слон дойти до заданной клетки (x, y). Если сможет, то указать за какое наименьшее количество ходов. Если количество ходов больше одного, то указать через какие промежуточные клетки он должен пройти. Если таких маршрутов несколько, то указать любой из них.
Входные данные
Входной файл INPUT. TXT содержит четыре числа m, n, x, y. (m, n) – координаты клетки, на котором находится слон, (x, y) – координаты клетки, на которую надо попасть. Числа m, n, x, y задаются в диапазоне от 1 до 8 и записываются через пробел.
Выходные данные
Выходной файл OUTPUT. TXT должен содержать в первой строке k – минимальное количество ходов, а далее в k-1 строках по 2 числа через пробел – координаты посещенных клеток. Если слон не может попасть на заданную клетку, то вывести 0.
Примеры
№ | INPUT. TXT | OUTPUT. TXT |
1 | 1 1 3 1 | 2 |
2 | 1 1 3 3 | 1 |
3 | 1 1 4 1 | 0 |
Решение
Слон попадает с одного поля на другое, если эти поля одного цвета. Если это так, то проверяем не находятся ли эти поля на одной диагонали. Если это так, то требуется один ход, иначе - два хода, при этом вычисляем координаты промежуточного поля.
Программа
var m, n, x, y, i, j : integer;
begin
assign(input,'input. txt'); reset(input);
assign(output,'output. txt'); rewrite(output);
read(m, n,x, y);
if ((m+n) mod 2<>(x+y) mod 2) or ((m=x)and(n=y)) then write(0)
else
if (m+n=x+y) or (m-n=x-y) then write(1)
else begin
writeln(2);
i:=(m-n+x+y) div 2;
j:=(x+y-m+n) div 2;
if (0<i)and(i<9)and(0<j)and(j<9) then write(i,' ',j)
else write((m+n+x-y)div 2,' ',(m+n-x+y)div 2)
end
end.
Задача F. Салаты
(Время: 1 сек. Память: 16 Мб)
Как-то раз, придя домой со школы, Света обнаружила записку от мамы, в которой она просила сделать салат. Света знала, что салат – это смесь двух или более ингредиентов, поэтому ей не составило труда выполнить мамину просьбу.
Но Света хочет стать математиком, поэтому, для тренировки, решила посчитать, сколько различных салатов она сможет сделать из имеющихся продуктов (майонез, огурцы, помидоры). После небольших расчетов она получила ответ: 4.
Зная, что вы любите интересные задачки, и хотите стать программистами, Света попросила вас написать программу, которая определяет количество различных салатов для произвольного числа ингредиентов.
Входные данные
Входной файл INPUT. TXT содержит натуральное число N – количество имеющихся ингредиентов (N < 32).
Выходные данные
В выходной файл OUTPUT. TXT выведите количество различных салатов.
Примеры
№ | INPUT. TXT | OUTPUT. TXT |
1 | 3 | 4 |
2 | 4 | 11 |
Решение
Два продукта из n можно выбрать 
способами, три - 
и так далее. Так как сумма всех сочетаний равна 2n, а 
и 
, то количество различных салатов равно 2n-1-n. Вначале вычислим степень 2, а потом вычтем два числа.
Программа
var n, i : integer; p : longint;
begin
assign(input, 'input. txt'); reset(input);
assign(output, 'output. txt'); rewrite(output);
read(n); p:=1;
for i:=1 to n do p:=p*2;
write(p-1-n);
close(output)
end.
