Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
Муниципальный
этап
2016
-
2017
уч
.
года
, 9
-
11
классы
1
.
Встреча друзей
(Время
-
1 сек., память
-
16 Мб, баллы
-
100)
Два бизнесмена, бывшие в школьные годы друзьями, давно не общались и
решили встр
е
титься в кафе нового бизнес
-
центра. Первый указал, что может
быть
с l
1
минуты включительно до r
1
минуты включительно. А второй указал, что может
быть с l
2
минуты включительно до r
2
минуты включительно и будет занят тел
е-
фонным разговором на k
-
й минуте. Определите в теч
е
нии какого времени друзья
смогут пообщаться.
Вх
одные данные
В единственной строке входного файла INPUT.TXT записаны пять натурал
ь-
ных чисел
l
1
,
r
1
,
l
2
,
r
2
,
k
(1
≤
l
1
,
r
1
,
l
2
,
r
2
,
k
≤
32767, l
1
≤
r
1
, l
2
≤
r
2
).
Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести одно
натуральное
число
–
время общения друзей в минутах. Если друзья не смогут п
о-
общаться, то вывести 0.
Примеры
№
INPUT.TXT
OUTPUT.TXT
1
1 2 1 3 2
1
2
1 10 10 20 10
0
Разбор
Вначале определим возможный интервал встречи друзей
.
Его начало равно
максимуму из начал интер
валов каждого, а окончание
–
минимуму из концов и
н-
тервалов каждого из друзей.
Потом опреде
ляем, встретятся ли друзья и
если да, то
попадает ли время телефонного разговора в этот и
н
тервал.
Программа
var
l1, r1, l2, r2, k, l, r : integer;
begin
assign(in
assign(output,'output.txt'); rewrite(output);
read(l1,r1,l2,r2,k);
�if l1l2 then l:=l1 else l:=l2;
if r1r2 then r:=r1 else r:=r2;
�if lr then write(0) else
if (l=k)and(k=r) then write(r
-
l) else write(r
-
l+1)
end.
2
.
Сумма трёх чисел
(Время
-
1 сек., память
-
16 Мб, баллы
-
100)
Три числа, записанных в системе счисления с основанием n, сложили в
«столбик», как пок
а
зано ниже.
A
A
A
+
B
B
B
C
C
C
D
D
D
2
В этой записи разные буквы означают разные цифры используемой
системы
счисления. Сколько возможно вариантов решения этого числового ребуса?
Входные данные
В единственной строке входного файла INPUT.TXT записано одно натурал
ь-
ное число n
-
о
с
нование системы счисления (6
Выходные данные
В единственную строку вы
ходного файла OUTPUT.TXT нужно вывести одно
натуральное число
–
количество вариантов.
Пример
№
INPUT.TXT
OUTPUT.TXT
1
7
6
Разбор
П
ервое наблюдение
-
п
ри сложении в столбик
нет переноса в старший разряд
.
Второе наблюдение
–
если a+b+c=d, то и b+
a
+
c
=
d
и ве
рны ещё 4 равенства.
Таким
образом, достаточно рассмотреть случай, что a, b, c, d имеют значения в возра
с-
тающем порядке и полученный результат умножить на 6. Организуем цикл по
возрастающим значениям a, b, c, d, суммируя количество выполненных условий
a+b+
c=d.
Программа
var
a, b, c, d, n : integer;
k : longint;
begin
assign(output,'output.txt'); rewrite(output);
read(n);
k:=0;
for d:=6 to n
-
1 do
for c:=3 to d
-
1 do
for b:=2 to c
-
1 do
fo
r a:= 1 to b
-
1 do
if a+b+c=d then k:=k+1;
write(6*k)
end.
3
.
Число
(Время
-
1 сек., память
-
16 Мб, баллы
-
100)
Никита написал на доске n целых неотрицательных чисел. Его старший брат
Слава хочет придумать такое натуральное число x, которое мо
жно прибавить к
некоторым написанным числам или вычесть из некоторых написанных чисел и
получить в результате на доске все одинаковые числа. П
о
могите ему.
Входные данные
В первой строке входного файла INPUT.TXT записано одно натуральное чи
с-
ло n
-
количеств
о написанных чисел (1
≤
n
≤
100000). Во второй строке через пр
о-
бел записаны n натуральных ч
и
сел от 1 до 1000000.
3
Выходные данные
В первую строку выходного файла OUTPUT.TXT нужно вывести сообщение
“Yes” (без к
а
вычек), если можно найти требуемое натуральное
число x, во вторую
строку вывести найденное x. Если условию задачи удовлетворяют несколько зн
а-
чений, то вывести наименьшее из них. Если такого значения не существует, то в
ы-
вести в единственную строку сообщение “No” (без к
а
вычек).
Примеры
№
INPUT.TXT
OUTPUT
.TXT
1
5
1 1 2 2 3
Yes
1
2
5
1 1 1 1 1
Yes
1
3
5
1 2 3 4 5
No
Разбор
Последовательно
обрабатывая числа, считаем
количество разных чисел и
храним
их значения
.
Если разных чисел стало больше трёх, то прекращаем ввод и
выдаём сообщение, что искомого числа
не существует. Если все числа одинак
о-
вые, то по условию задачи искомое число равно 1. Если последовательность с
о-
стоит из двух чисел, то вычисляем разность большего и меньшего, если она дели
т-
ся на 2, то ответом будем половина этой разности, иначе сама разн
ость. Если же в
п
о
следовательности три разных числа b,
c
,
d
(
в порядке возрастания
)
, то надо ещё
проверить
условие
b
+
d
=2
c
, которое обеспечивает существование р
е
шения.
Программа
var
n
,
i
,
k
,
a
,
b
,
c
,
d
:
longint
;
begin
assign
(
input
,'
input
.
txt
');
(
i
nput
);
assign
(
output
,'
output
.
txt
');
rewrite(output);
read(n); k:=0; i:=0;
while (i4)and(kn) do begin
k:=k+1; read(a);
case i of
0: begin i:=i+1; b:=a end;
1: if ab then begin c:=b; b:=a; i:=i+1 end else
�if ab then beg
in c:=a; i:=i+1 end;
2: if ab then begin d:=c; c:=b; b:=a; i:=i+1 end else
�if (ab)and(ac) then begin d:=c; c:=a; i:=i+1 end else
�if ac then begin d:=a; i:=i+1 end;
���3: if (ab)and(ac)and(ad) then i:=i+1
end
end;
if i=4 then write('No') else
if i=1 then begin writeln('Yes'); write(1) end else
if i=2 then begin writeln('Yes');
d:=c
-
b;
if odd(d) then
write(
d
)
else write(d div 2)
end
else
if (2*c=b+d) then begin writel
n('Yes'); write((d
-
b)div
2) end
else write('No')
4
end.
4
.
Клумбы
(
Время
-
1
сек
.,
память
-
16
Мб
,
баллы
-
100)
На школьной аллее в ряд расположены n клумб. В начале лета на клумбы
школьникам надо высадить по f
i
цветов. На посадку каждого цветка каждому уч
е-
нику требуется по
2 минуты. Для выполнения этой работы приглашены n учен
и-
ков и за каждым из них закре
п
лена клумба. Для более быстрого окончания работ
двум ученикам, закреплённым за сосе
д
ними клумбами, можно вначале засадить
одну клумбу, потом другую. При этом вторую клумбу
эти ученики начинают з
а-
саживать только после посадки всех цветов на первую клумбу. Н
а
пример, если на
соседние клумбы надо посадить 5 и 2 цветов, то школьникам лучше объед
и
ниться,
тогда они справятся с работой за 8 минут (6 минут на первую грядку и 2 минуты
на вторую). При этом первый ученик высаживает на первой клумбе 3 цветка за 6
минут, а второму остаётся 2 цветка и 2 минуты он ждёт первого. Если бы они з
а-
саживали каждый свою клу
м
бу, то потребовалось бы 10 минут (10 первому и 4
второму).
Помогите школьник
ам как можно быстрее справиться с порученным задан
и-
ем.
Входные данные
В первой строке входного файла INPUT.TXT записано одно натуральное чи
с-
ло n
–
количес
т
во клумб и количество учеников (1
≤
n
≤
100000). Во второй строке
через пробел заданы n натуральных ч
исел
–
количество цветов на клумбах. Эти
числа не превышают значения 100000.
Выходные данные
В первую строку выходного файла OUTPUT.TXT нужно вывести одно нат
у-
ральное число
–
время выполнения работы школьниками. Во вторую строку ну
ж-
но вывести через пробел
n чисел 1 или 2. Если i
-
ю грядку засаживает один ученик,
то вывести 1, иначе 2.
При этом количество учеников, которые засаживают по о
д-
ной клумбе, должно быть максимально возможным. Если существует несколько
таких решений, выведите любое
.
Примеры
№
INPUT.TX
T
OUTPUT.TXT
1
2
1 1
2
1 1
2
2
2 5
8
2 2
3
3
2 2 1
4
1 1 1
Разбор
Применим метод динамического программирования.
Обозначим через t
i
м
и-
нимальное время, за которое можно высадить цветы в i клумб. Легко найти
t
0
=0,
t
1
=2
f
1
. Пусть мы уже выч
и
слили
эту велич
ину до некоторого i. Вычислим её при
добавлении i+1 клумбы. Эту клумбу может посадить (i+1)
-
й школьник и всего б
у-
дет затрачено время max(t
i
, 2
f
i+1
) минут. Е
сли i
-
ю и (i+1)
-
ю клумбы будут высаж
и-
5
вать двое, то всего будет потрачено max(
t
i
-
1
,
f
i
+
f
i
mod
2+
f
i
+1
+
f
i
+1
mod
2
)
минут
. Из
этих двух вариантов выбираем наименьший. Ответом будет вычисленное значение
t
n
. Так как при вычислениях используются только два предыдущих значения, то
можно обойтись простыми переменными и не использовать массив.
В задаче также треб
уется назначить школьников на клумбы. Для этого будем
в массиве хранить номера клумб, которые позволили найти лучший ответ. После
определения наименьшего времени выполнения работы обратным просмотром
массива найдём массив ответов.
Программа
var
n, i, t,
t1, t2, f, g, u, v : longint;
a, otv : array [1..100000] of longint;
begin
assign(output,'output.txt'); rewrite(output);
read(n);
t1:=0; read(f); t2:=2*f; a[1]:=f; otv[1]:=0;
for i:=2 to n do begin
r
ead(g);
a[i] := g;
�u:=2*g; if t2u then u:=t2;
�v:=f+f mod 2+g+g mod 2; if t1v then v:=t1;
if u=v then begin t:=u; otv[i]:=i
-
1 end
else begin t:=v; otv[i]:=i
-
2 end;
t1:=t2; t2:=t; f:=g
end;
writeln(t2);
i:=n;
while
�i0 do
if otv[i]=i
-
1 then begin otv[i]:=1; i:=i
-
1 end
else begin
otv[i]:=2; otv[i
-
1]:=2;
if (a[i]*2=t2) and (a[i
-
1]*2=t2) then
begin otv[i]:=1; otv[i
-
1]:=1 end;
i:=i
-
2
end;
for i:=1 to n
-
1 do write(otv[i],' ');
write(otv[n])
end.
Приложенные файлы
