2017-2018 учебного года. A. Колода карт. Для. игры число карт в колоде должно быть кратно количеству игроков. У Никиты есть колода из N карт.


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
Разбор задач т
ренирово
чной олимпиады №
6

для

подготовки к школьному и муниципальному этапам
Вс
е
российской олимпиады школьников по инф
о
рматике
2017
-
2018 учебного года


A
.
Колода карт

(
Время

-

1
сек
.,
память

-

16
Мб
)

Каждые выходные к
Никит
е приходят друзья,
чтобы поиграть в карты. Для
игры число карт в колоде должно быть кратно количеству игроков.

У
Никиты

есть колода из

N

карт. Он решил, что для каждой новой игры он
будет выбирать такое количество карт, которым не играли ранее. В карты он
и
и
г
рают либо вдвоѐм
, либо втроѐ
м. Помогите
Никите

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

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

В единственной строке входного файла INPUT.TXT
записано натуральное
число

N

(1



N



10
9
)



количество карт в колоде.

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

В единств
енную строку выходного файла
OUTPUT
.
TXT

нужно вывести одно
натуральное число


количество игр, которые можно сыграть этой кол
о
дой
.

Пример
ы



input.txt

output.txt

Пояснения

1

5

3

Мож
но играть колодами из 2, 3, 4
к
арт

2

6

4

Мож
но играть колодами из 2, 3, 4
, 6
к
арт

Разбор

Число игр вдвоѐм равно [n/2], а число игр втроѐм


[n/3], где [x] обозначает
целую часть выражения x. При этом игры, в которых количество карт кратно 6,
подсчитаны два раза. В итоге имеем, что требуемое количество игр равно
[n/2]+[n/3]
-
[n/
6].

Программа на Паскале

var


n

:
longint
;

begin




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


read(n);


write(n div 2 + n div 3
-

n div 6);


close(output)

end.

B
. Хорошая таблица

(
Время

-

1
сек
.,
память

-

16
Мб
)

Имеется прямоугольная целочисленная таблица размером
N

M
. ©Путѐмª в
этой таблице назовѐм последовательность на
N
+
M
-
1
клеток, которая начинается
из клетки (1, 1), заканчивается клеткой (
N
,
M
)
и любые две идущие подряд клетки
в этой последовательности

имеют общую сторону. Назовѐм таблицу ©хорошейª,
если сумма чисел в клетках каждого пути в этой таблице одна и та же.
Опред
е
лить, является ли данная таблица ©хорошейª.

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

Во входном файле
INPUT
.
TXT

записаны не более 10 таблиц. Запись каждой
таб
лицы содержит в первой строке два числа


количество строк
N

и количество
столбцов
M

(1



N
, 1



M
,
N

M



30000).
В следующих
N

строках содержатся по
M

чисел


значения элементов таблицы


целые числа от
-
32000 до 32000.
После
д
няя строка входного файла сод
ержит значения 0 0.

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

В единственную строку выходного файла
OUTPUT
.
TXT

нужно вывести
стр
о
ку из символов
Y

и
N
. Длина строки равна количеству таблиц во входном
файле. Символ
Y

обозначает что соответствующая таблица ©хорошаяª,
N

-

ин
а
че.

Пример



input.txt

output.txt

1

2 2

1 2

2 3

2 2

1 2

1 2

0 0

YN

Разбор

Из определения ©хорошейª таблицы легко получить, что в ней должны быть
равны элементы стоящие в одной побочной диагонале. Всего побочных
диагон
а
лей n+m
-
1. Это и подсказывает способ хранения
©хорошихª таблиц.
Например, достаточно хранить первую строку и последний столбец, а все
остальные элеме
н
ты сравнивать с ними по мере вв
о
да.

Программа на Паскале

{
Autor

-

A
.
Alexeev
,
date

-

22.10.13}

var


n, m, i, j, b : integer;


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


t : boolean;

begin




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


readln(n,m);


�while n+m0 do begin


t:=true;


for j:=1 to m do read(a[j]);


for i:=2 to n do begin


for j:=1 to m
-
1 do

begin


read(b);


t:=t and (b=a[i+j
-
1])


end;


read(b);


a[m+i
-
1]:=b


end;


if t then write('Y') else write('N');


readln(n,m)


end;


close(output)

end
.

C
.
Покраска

забора

(Время
-

2 сек., память
-

16 Мб)

Однажды Том решил покрасить свой забор. Так как Том очень занятой
чел
о
век, то он решил нанять рабочих, чтобы они выполнили работу за него. Для
этого он подал объявление в газету и в ответ получил
m

предложен
ий от рабочих.
В к
а
ждом из них была указана пара чисел (
a
,
b
),
где
a



номер первой доски,
b



номер последней доски того участка, который будет покрашен.

Требуется определить, может ли Том покрасить весь забор с помощью этих
предложений рабочих?

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

В первой строке входного файла
INPUT
.
TXT

записано два натуральных
чи
с
ла:
n



количество досок в заборе
(1



n



2000000
000)

и
m



количество
предл
о
жений от рабочих (
1



m



10
000
). В каждой из следующих
m

строк
записана пара натуральных чисел
a

и
b
,

где
a



номер первой доски,
b



номер
последней доски того участка, который определѐн в предложении на покраску
(
1



a



b



n
).

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

В первую строку выходного файла OUTPUT.TXT нужно вывести

Yes
‖,
если
весь забор можно покрасить, или

No

, если

это сделать невозможно. В случае
п
о
ложительного ответа во второй строке нужно вывести 0, если все доски забора
б
у
дут покрашены по одному разу, иначе надо вывести наименьший номер доски,
к
о
торая будет выкрашена более одного раза. Если забор не удастся покрасить, то
во второй строке выходного файла вывести наименьший номер доски, которая не
б
у
дет покрашена.

Примеры



input.txt

output.txt

1

3 1

1 3

Yes

0

2

2 1

1 1

No

2

Разбор

Задача из книг
и С.Г. Волчѐнкова с соавторами ©Ярославские олимпиады по
информатике. Сборник задач с решениямиª, изданной издательством ©БИНОМ.
Лаборатория знанийª в 2010 году. Она предлагалась в 2008
-
2009 учебном году
участникам городской олимпиады на практическом туре.

Условие усложнено,
д
о
бавлены дополнительные ответы.

Введѐм характеристики для чисел каждой заявки. Первое число в заявке
им
е
ет характер
и
стику 1 (один), а второе


-
1 (минус один). Отсортируем все числа
в заявках в порядке возрастания, не забывая их характ
еристик (отсортируем
масс
и
вы c и d). Необходимым (но недостато
ч
ным) условием покраски забора
является условие, что c[1]=1. Теперь последовательно просма
т
риваем
отсортированные массивы чисел из заявок и их характеристик. При просмотре
очере
д
ного элемента сч
итаем суммарную характеристику как сумму
характеристик уже просмотре
н
ных элементов. Если эта суммарная
характеристика всегда положительна, то это озн
а
чает, что каждую доску (включая
данную) есть кому красить. Если же суммарная характеристика оказалась
нуле
вой, то следующий номер должен отличаться не более чем на 1, иначе
следующую доску красить некому. Если просмотр заве
р
шился на предпоследнем
элементе массива, то надо проверить, что c[2m]=n
.

Программа на Паскале

var


m
,
i
,
j
,
b

:
integer
;


n, a, kt :
longint;


c : array [1..20000] of longint;


d : array [1..20000] of integer;


t : boolean;

begin




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


readln(n,m);


for i:=1 to m do begin


read(c[2*i
-
1], c[2
*i]);


d[2*i
-
1]:=1; d[2*i]:=
-
1


end;


for i:= 1 to 2*m
-
1 do


for j:=1 to 2*m
-
i do


�if c[j]c[j+1] then begin


a:=c[j]; c[j]:=c[j+1]; c[j+1]:=a;


b:=d[j]; d[j]:=d[j+1]; d[j+1]:=b


end;


�if c[1]1 then begin writeln('No'); wr
ite(1); close(output) end


else begin


b:=0; t:=true; i:=1;


while i2*m do begin


b:=b+d[i];


�if t and (b1) then begin t:=false; kt:=c[i] end;


if t and (b=0) and (c[i]=c[i+1]) then begin t:=false; kt:=c[i]
end;


if (b=0) and (
�c[i+1]c[i]+1) then begin writeln('No');
write(c[i]+1); close(output); exit end;


i:=i+1


end;


if c[2*m]n then begin writeln('No'); write(c[2*m]+1);
close(output) end


else begin


writeln('Yes' ); if t then write(0) else write(kt);
clo
se(output)


end


end

end
.

D
.
Пила

(
Время

-

1
сек
.,
память

-

16
Мб
)

Пилой
высоты x
называется

ломанная, проходящая через точки (0, 0)
-
(x, x)
-
(2x, 0)
-
(3x, x)
-
(4x, 0)
-


(смотрите рисунок)
. Найдите пилу наименьшей высоты,
проходящую через точку с заданными

координатами (a, b)
, либо, определите
, что
такую пилу построить невозможно.


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

В единственной строке входного файла
INPUT
.
TXT

записаны два
натурал
ь
ных числа a и b



координаты точки

(1



a



10
6
,
1



b



10
6
).

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

В единственную

строку выходного файла
OUTPUT
.
TXT

нужно вывести одно
вещественное
число
x



высоту найденной пилы
. Число выводить с шестью
знак
а
ми после запятой. Если пилу построить нельзя, то вывести
-
1
.

Пример
ы



input.txt

output.txt

1

3 1

1.000000

2

1 3

-
1

3

4 1

1.
250000

Разбор

Если точка лежит выше биссектрисы первой координатной четверти, то пилу
построить невозможно, проверяем условие a-
1.
Рассматриваем два случая: точка лежит на правой стороне некоторого зуба пилы,
точка лежит на

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

Программа на Паскале

var


a
,
b
,
k
1,
k
2 :
longint
;

begin




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


read(a,b);


if ab then write('
-
1') else begin


k1:=(a+b) div b; if odd(k1) then k1:=k1
-
1;


�if a=3*b then begin


k2:=(a
-
b) div b; if odd(k2) t
hen k2:=k2
-
1;


�if (a+b)*k2(a
-
b)*k1 then begin


b:=
-
b; k1:=k2


end


end;


writeln((a+b)/k1:0:6)


end

end.


Приложенные файлы

  • pdf 47879117
    Размер файла: 355 kB Загрузок: 0

Добавить комментарий