book1


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

3


Предисловие


Олимпиадное движение по информатике (т.н.
спортивное пр
о-
граммирование
) приобрело в нашей стране большую популярность как
среди школьников, так и среди студентов. Каждый год проводятся мн
о-
жество соревнований по спортивному программированию в ра
зличных
форматах. Так, республиканская олимпиада по информатике среди
школьников состоит из четырёх этапов: школьный, районный, областной
и республиканский. Эта олимпиада проводится по правилам, принятым
на международных олимпиадах по информатике (
IOI
).

С
оревнования в формате IOI состоят из одного или нескольких т
у-
ров (в настоящее время первый и второй этапы
республиканской
оли
м-
пиады проводятся в один тур, а третий и четвёртый


в два тура). На к
а-
ждом туре участникам олимпиады предлагается для решения неск
олько
задач (от трёх до пяти).

Решением классической задачи (а именно такие задачи предста
в-
лены в предлагаемом пособии) является
исходный текст программы на
одном из языков программирования высокого уровня.
Этот текст комп
и-
лируется членами жюри и проверяе
тся на наборе тестов, неизвестных
участнику.
Каждый тест из набора оценивается своим количеством ба
л-
лов (чаще всего это количество одинаково для всех тестов набора).

Каждый тест из набора оценивается независимо от других, позв
о-
ляет авторам объединить в одн
ом условии несколько задач, указав ра
з-
личные ограничения для различных наборов тестов. Например, для 50 %
тестов могут задаваться меньшие ограничения, которые позволяют и
с-
пользовать более простые (хотя и менее эффективные) алгоритмы. Уч
а-
стник олимпиады мож
ет, таким образом сдать не совсем эффективное
решение, которое, тем не менее, наберёт ненулевое количество баллов.

Сборники олимпиадных задач прошлых лет являются серьёзным
подспорьем при подготовке к будущим олимпиадам. Особенно это п
о-
лезно тогда, когда у
словия задач сопровождаются
авторским разбором,
как это сделано в предлагаемом пособии.

В течение ряда лет авторы составляют задачи для олимпиад ра
з-
личного уровня. В пособии представлены
задачи
для районных школ
ь-
ных олимпиад по информатике (второй этап рес
публиканской олимпи
а-
ды), которые проводились в г. Минске в 2005


2012 годах.
В него вкл
ю-
чена

31 задача;

для каждой из
них

написан разбор решения. Наборы те
с-
тов для каждой задачи можно найти в
и
нтернете по адресу
:


4



https://docs.google.com/file/d/0Bymq5SA5E
B3NRFUUmE1QjVRenc/edit?usp=sharing


Пособие рекомендуется студентам факультета прикладной матем
а-
тики и информатики, школьникам, участвующим в олимпиадном движ
е-
нии по информатике или планирующим прини
мать такое участие, а та
к-
же всем, кто интересуется олимп
иадным движением.

В дальнейшем планируется выпустить еще два сборника олимп
и-
адных задач:



задачи командных чемпионатов школьников г. Минска;



задачи районных олимпиад Минской области.

Авторы благодарят А.Д. Субача, который внимательно прочёл р
у-
копись и сдела
л ряд замечаний и предложений (особенно касающихся
разборов задач), улучшивших её качество.

Выражаем также благодарность доктору физико
-
математических
наук, профессору В.В.Котову

за
рецензировани
е

рукописи.





5


Условия задач

2005/2006 учебный год

Автор зада
ч «Период времени» и «Мат в один ход»


С.И. Кашк
е-
вич. Задача «Правые части» взята из хорватских интернет
-
олимпиад
(
http://hsin.hr/coci
). Решения к задаче «Правые части» писал также С.В.
Гафуров
.



Задача 1: Период времен
и

Ограничения на время и память не задавались

Максимальное количество баллов: 60


Информация о дате и времени наступления какого
-
либо события,
определенных с точностью до секунды, записывается в виде

dd.mm.yyyy hh:nn:ss

где
dd



номер дня (от 01 до послед
него дня месяца),
mm



номер
месяца (от 01 до 12),
yyyy



год (от 1801 до 2100),
hh
,
nn
,
ss



соотве
т-
ственно час (от 00 до 23), минута (от 00 до 59) и секунда (от 00 до 59) н
а-
ступления события. Записи о дате и времени разделяются одним проб
е-
лом. Например,
информация о событии, наступившем в полночь с 1 на 2
февраля 2005 года, будет записана как

02.02.2005 00:00:00

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

Известно, что первое событие наступило не позже
второго. Переходы с летнего времени на зимнее и обратно, а также от
старого стиля к новому следует игнорировать. Для 50 % тестов обе зап
и-
си будут относиться к одной и той же дате.

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

его номер делится на 4.
Однако

если номер года делится на 100, но не делится на 400, год не я
в-
ляется високосным. Так, 2000 год


високосный, а 1900 и 2100 годы


нет.

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

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


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

помещаются в стандартный вывод и содержат
единственную строку с найденной величиной.


6


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


16.08.1980 23:12:40

17.08.1980 09:45:10

37950


Задача 2: Правые части

Ограничения на время и память не задавались

Максимальное количество баллов: 60


Правой частью натурального числа
N

назовем число
K
, полученное
из двоичной записи числа
N

отбрасывани
ем всех цифр, стоящих левее
крайней правой единицы, и преобразованное обратно в десятичную си
с-
тему. Так, правой частью числа 6 является число 2, а правой частью чи
с-
ла 1088


число 16.

Вам требуется определить сумму правых частей всех натуральных
чисел из и
нтервала [
A
,
B
], включая границы этого интервала, где 1

A


B

≤ 10
15
. Гарантируется, что результат будет помещаться в 64
-
битное ц
е-
лое число. Для 50 % тестов 1

A


B

≤ 10
8
, а результат будет помещаться
в 32
-
битное целое число.

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

читаются и
з стандартного ввода и содержат два
числа


значения
A

и
B
.

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

помещаются в стандартный вывод и содержат
десятичное представление найденной суммы.

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


5

9

13


Задача 3:
Мат в один ход

Ограничения на время и па
мять не задавались

Максимальное количество баллов: 100


На квадратной шахматной доске размером
K

×

K

стоят три фигуры:
белые король и ферзь, а также ч
ё
рный король. В начальной позиции ни
один из королей не находится под боем. Следующий ход должны делать
бе
лые. Можете ли Вы, играя за белых, поставить этим ходом мат ч
ё
р-
ным?


7


Следует заметить, что тесты этой задачи разбиты на группы, и уч
а-
стник олимпиады получает ненулевые баллы за группу тестов только в
случае, когда все тесты этой группы пройдены!

Напомним ша
хматные правила, знание которых необходимо для
решения задачи. В шахматы играют два игрока («белые» и «ч
ё
рные»),
которые делают ходы по очереди. Ход заключается в перемещении о
д-
ной из фигур своего цвета на новое место, не совпадающее с первон
а-
чальным. На к
аждой клетке доски в любой момент может находиться не
более одной фигуры.

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

Король может перейти на одну из свободных соседних клеток, ра
с-
положенных по вертикали, горизонтали или диагоналям (за исключен
и-
ем клеток,
находящихся п
од боем
). Король может также снять непр
и-
ятельскую фигуру, стоящую на одной из соседних клеток, встав на ее м
е-
сто (если только после такого хода король не будет
находиться под б
о-
ем
).

С точки зрения одного из игроков, его фигура
находится под боем
,
если его

соперник своим следующим ходом может снять эту фигуру.
Свободная клетка находится под боем, если соперник своим следующим
ходом может занять эту клетку одной из своих фигур.

Игрок получает мат (и проигрывает партию), если при его очереди
хода король этого

игрока находится под боем, и у него нет ходов, выв
о-
дящих своего короля из
-
под боя.

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

находятся в текстовом файле
CHESS
.
IN
, опис
ы-
вающем одну группу тестов и состоящем из нескольких строк. Первая
строка файла содержит величины
N

(1

N

≤ 5)


к
оличество тестов в
группе, и
K

(3

K

≤ 1 000 000,
для 50 % тестов
K

= 8). Каждая из посл
е-
дующих
N

строк описывает один тест группы и содержит положение б
е-
лого короля, белого ферзя и черного короля, разделенные одним проб
е-
лом. Положения фигур задаются двум
я числами, также разделенными
пробелом: номерами вертикали и горизонтали (от 1 до
K
)
.

Вертикали н
у-
меруются слева направо, а горизонтали


снизу вверх.

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

помещаются в текстовый файл
CHESS
.
OUT

и
содержат
N

строк, по одной строке на каждый тест
группы. Если мат в
один ход поставить нельзя, соответствующая строка содержит текст

8



impossible

. В противном случае Вы должны указать один из во
з-
можных ходов белых в формате: обозначение фигуры (
R



король,
Q



ферзь) и номера вертикали и горизонтали, на

которую эта фигура пер
е-
ходит. Данные в строках выходного файла должны разделяться ровно
одним пробелом.

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


2 8

1 5 2 2 4 5

3 3 6 5 3 1

impossible

Q 6 1

2006/2007 учебный год

Автор задач «Игра», «Пустые прямоугольники» и «По
иск анаграмм»


С.И. Кашкевич. Идея задачи «Поиск анаграмм» родилась после чтения
условий задач международной олимпиады по информатике, проходи
в-
шей в Мексике. Задача «Постулат Бертрана» взята из интернет


олимпиад для школьников, проводящихся в Санкт
-
Пете
рбурге
(
http://neerc.ifmo.ru/school/io
). Решения к задачам писал также С.В. Г
а-
фуров.


Задача 1: Игра

Ограничения на время и память не задавались

Максимальное количество баллов: 100


Вася и Петя играют в следующ
ую игру на прямоугольной доске,
имеющей
M

горизонтальных и
N

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

Ограничения на данные: 1

M
,
N

≤ 1

000 000;
M
+
N

> 1. Для 50 %
тестов 1

M
,
N

≤ 10

000.

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

находятся в текстовом файле
GAME
.
IN
, опис
ы-
вающем одну группу тестов и состо
ящем из нескольких строк. Первая
строка файла содержит величину
K

(2

K

≤ 5)


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

9


группе. Каждая из последующих
K

строк описывает один тест группы и
содержит значения
M

и
N
, разделенные одним пробелом.

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

помещаются в текстов
ый файл
GAME
.
OUT

и
содержат
K

чисел, записанных в одной строку через пробел. Каждое чи
с-
ло соответствует одному тесту группы и равно 1, если победить должен
Вася, и 2


если победителем должен быть Петя. Пробелы в начале и
конце строки не допускаются.

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


2

5 3

6 4

1 2


Примечание:

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

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


Задача 2: Постулат Бертрана

Ограничения на время и память не задавались

Максимальное количество баллов: 60


Постулат Бертрана (теорема

Бертрана
-
Чебышёва, теорема Чеб
ы-
шёва) гласит, что для любого
n

≥ 2
най
дётся простое число
p

в интервале
n

<
p

< 2
n
. Такая гипотеза была выдвинута в 1845 году французским м
а-
тематиком Жозе Бертраном (проверившим её до
n

= 3000000) и доказана
в 1850 Пафнутием Чебышёвым. Раманужан в 1920 году нашёл более
простое доказательство,
а Эрдёш в 1932


ещё более простое.

Вы должны решить несколько более общую задачу
-

а именно по
числу
n

найти количество простых чисел
p

из интервала
n

<
p

< 2
n
.

Напомним, что натуральное число называется простым, если оно
делится только само на себя и на
единицу. Единица не считается пр
о-
стым числом.

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

читаются из стандартного ввода и содержат зн
а-
чение числа
n

(2

n

≤ 1

000 000; для 50 % тестов

n

≤ 5000).

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

помещаются в стандартный вывод и содержат
искомое количество простых чисе
л.




10


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


2

1

4

2

8

2


Задача 3:
Пустые прямоугольники

Ограничения на время и память не задавались

Максимальное количество баллов: 80


Задано множество из
N

несовпадающих точек на плоскости (2

N

≤ 1000).
Выберем любую
пару точек из этого множества с координатами
(
x1
,
y1
) и (
x2, y2
). Если
x1


x
2

и
y
1


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

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

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

находятся
в текстовом файле
WIDERECT
.
IN
, состоящем из
нескольких строк. Первая строка
файла содержит величину
N
. В
каждой из последующих
N

строк
через пробел задаются коорд
и-
наты
X

и
Y

одной точки множ
е-
ства


целые числа, не превосходящие по м
одулю 1000000 (в 50 % тестов
координаты не превосходят по модулю 10000).

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

помещаются в текстовый файл
WIDERECT
.
OUT

и содержат единственную строку с найденным числом пустых прям
о-
угольников.

Рис
.

1.

Иллюстрация примера из условия
(пустые прямоугольники выделены)


11


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


5

-
1 4

1
4

1 1

2
1

-
2 2

2


Задача 4: Поиск анаграмм

Ограничения на время и память не задавались

Максимальное количество баллов: 60


Две непустые строки одинаковой длины называются
анаграммами

друг друга, если вторая строка составлена из символов первой, и каждый
символ

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


не являются.

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

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

находятся в текстовом файле
ANAGRAM
.
IN
,
описывающем одну группу тестов и состоящем из нескольких строк.
Первая строка ф
айла содержит величину
K

(2

K

≤ 5)


количество те
с-
тов в группе. Далее следуют
K

пар строк


каждая пара соответствует
одному тесту. Длина одной строки не превосходит 3000 символов (в 50
% групп тестов эта длина не превосходит 200).

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

помещ
аются в текстовый файл
ANAGRAM
.
OUT

и содержат единственную строку из
K

чисел, разделенных одним проб
е-
лом. Каждое число соответствует одному тесту и должно быть равно 1,
если введенные строки являются анаграммами, и 0 в противном случае.
Пробелы в начале и
конце строки не допускаются.




12


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


4

Acad

cAda

AbRa

arBA

duda

adua

termo

1 0 0 1


Примечание:

в группе, соответствующей входному файлу, есть хотя
бы один тест, правильный ответ на который


1, и хотя бы один тест с
правильным

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

2007/2008 учебный год

Автор задач


С.И. Кашкевич. Идея задачи «Экспрессные маршруты» не
нова, в той или иной формулировке её мо
жно найти на любом сайте, где
разбираются задачи по основам динамического программирования. Р
е-
шения к задачам писали также И.Г. Филипович и В.С. Кашкевич.


Задача 1: Экспрессные маршруты

Ограничения на время и память не задавались

Максимальное количество
баллов: 100


Между городом
A

и городом
B

проложена единственная дорога, на
которой построено
N

остановочных пунктов. Обычный автобусный ма
р-
шрут из
A

в
B

предусматривает остановки на каждом из оборудованных
пунктов. Экспрессный маршрут пропускает некоторые
(не менее одного)
остановочных пунктов, но ни один экспрессный маршрут не пропускает
более двух пунктов подряд.

Сколько различных экспрессных маршрутов можно организовать
между городом
A

и городом
B
? Два маршрута считаются различными,
если множества остано
вочных пунктов, которые они пропускают, ра
з-
личны.

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

читаются из стандартного ввода и содержат зн
а-
чение числа
N

(1

N

≤ 70;
для 50 % тестов

N

≤ 20).


13


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

помещаются в стандартный вывод и содержат
искомое количество экспрессных маршр
утов.

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


1

1

2

3

4

12



Задача 2: Отрезки на прямой

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

Ограничения по памяти: 32 мегабайта

Максимальное количество баллов: 80


На числовой прямой задано
N

отрезков [
a
1
;
b
1
], …, [
a
N
;
b
N
], гд
е
a
i



b
i
. Объединение этих отрезков образует
K

новых отрезков [
c
1
;
d
1
], …,
[
c
K
;
d
K
], где 1

K


N
.

Определите величину
K

и длину самого большого отрезка [
c
i
;
d
i
]

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

читаются из текстового файла
SEGMENT
.
IN
.
Первая строка этого файла содержит в
еличину
N

(1

N

≤ 1

000 000; для
50 % тестов

N

≤ 5000).
Каждая из последующих
N

строк содержит вел
и-
чины
a
i

и
b
i
, разделенные одним или несколькими пробелами. Эти числа


вещественные, не превосходят по модулю 100000 и содержат не более
5 цифр в дробной ча
сти.

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

помещаются в файл
SEGMENT
.
OUT
. Единс
т-
венная строка этого файла содержит два искомых числа, разделенные
одним или несколькими пробелами.

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


5

4 4.5

8 11.2

-
3 2

0.00001 0.00001

3 9.1

2 8.2





14


Задача 3: Про
блема Гольдбаха

Ограничения на время и память не задавались

Максимальное количество баллов: 80


Проблема Гольдбаха


одна из самых старых проблем математ
и-
ки, не разрешённых до сих пор. В 1742 году прусский математик Кр
и-
стиан Гольдбах послал Леонарду Эйлер
у письмо, в котором было выск
а-
зано предположение:
любое чётное число, большее двух, можно пре
д-
ставить в виде суммы двух простых чисел
.

Напомним, что простое число


это натуральное число, большее
единицы, имеющее ровно два натуральных делителя: единицу и с
амо с
е-
бя.

К настоящему времени это утверждение ни доказано, ни опровер
г-
нуто, хотя на март
2004

года известно, что оно выполняется для всех
чётных чисел, не превышающих 2
∙ 10
17
.

Вам необходимо предс
тавить заданное
чётное число

N
, большее
двух, в виде суммы двух простых чисел
a
1

и
a
2
. При этом
a
1

должно быть
минимальным из в
озможных чисел, и
a
1


a
2
.

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

читаются из стандартного ввода и содержат зн
а-
чение числа
N

(4

N

≤ 100 000;
для 50 % тестов

N

≤ 5000).

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

помещаются в стандартный вывод и содержат
строку из двух чисел

a
1

и
a
2
, разделенных одним или
несколькими пр
о-
белами.

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


4

2 2

10

3 7

32

3 29


Задача 4: Изменить Строку!

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

Ограничения по памяти: 16 мегабайт

Максимальное количество баллов: 40


Строка
S

состоит из нескольких (не мене
е одного)
слов
, разделе
н-
ных одним или несколькими пробелами. Все другие символы считаются
частями слова. В начале и конце строки также могут быть пробелы.


15


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

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

находятся в текстовом файле
CAPITA
.
IN
. Еди
н-
ственная строка этого файла содержит исходную строку
S
. Длина этой
строки не превосходит 30000 (в 50

% тестов эта длина не превосходит
255).

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

помещаются в текстовый файл
CAPITA
.
OUT

и
содержат преобразованную строку. Длины исходной и преобразованной
строк должны совпадать.

В приведенных далее примерах пробелы для наглядности замен
е-
ны симво
лами ’_’ (подчеркивание).

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

(каждая строка соответс
т-
вует одному примеру)


Wish
_
you
_
were
_
here

___Hello,world!_

shine_on_you_crazy_diamond_(part_1)

__
Превед,_медвед!


Wish
_
You
_
Were
_
Here

___Hello,world!_

Shine_On_You_Craz
y_Diamond_(part_1)

__
Превед,_медвед!


2008/2009 учебный год

Автор задач


С.И. Кашкевич. Решения к задачам писал также С.В. Г
а-
фуров.


Задача 1: Тарабарская грамота

Ограничения по времени:
5

секунд

Ограничения по памяти: 16 мегабайт

Максимальное количест
во баллов:
6
0


Тарабарская грамота, или простая литорея


один из способов
шифрования текстов, применявшийся в древней Руси. Суть его, прим
е-

16


нительно к современному русскому алфавиту, заключается в следующем.
Поставив согласные буквы в два ряда, в порядке:

б

в

г

д

ж

з

к

л

м

н

щ

ш

ч

ц

х

ф

т

с

р

п

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

=
словарь
.

Применим этот же принцип к латинскому алфавиту и расставим
согласные буквы в два

ряда:

b

c

d

f

g

h

j

k

l

m

z

x

w

v

t

s

r

q

р

n

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


строчными. Остальные символы остаются
без изменений.

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

читаются из текстового файла CIPHER.IN, соде
р-
жащего исходный текст. Этот файл состоит из нескольких строк, причем
длина одной строки не превышает 30000 символов (в 50 % те
стов эта в
е-
личина не превосходит 255 символов), а общий объем файла не прево
с-
ходит 5 мегабайт.

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

Зашифрованный текст должен быть помещен в
текстовый файл CIPHER.OUT. Количество строк и размер каждой строки
выходного файла должны соответствов
ать данным входного файла. Если
исходный файл пуст, Вы также должны создать пустой файл. В проти
в-
ном случае последняя строка выходного файла должна заканчиваться
символами перевода строки.

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


Deep Purple

”Who Do We Think We A
re”

Weel ujlpe

”Dso Wo De Gsimq De Aje”



Задача 2: Сглаживание матриц

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

Ограничения по памяти: 32 мегабайт

Максимальное количество баллов: 100


Соседями элемента двумерной матрицы назовем элементы, име
ю-
щие с ним общую сто
рону или угол. Элемент матрицы называется л
о-

17


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

Вып
олните операцию сглаживания для заданной матрицы!

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

читаются из текстового файла
MATRIX
.IN. Пе
р-
вая строка этого файла содержит числа
M

и
N



количество строк и
столбцов матрицы (1

M
,
N

≤ 5000, 1 <
M

×

N

≤ 500000).
Далее следуют
M

строк, кажд
ая из которых содержит
N

действительных чисел и соо
т-
ветствует одной строке матрицы. Элементы матрицы не превосходят по
модулю 100000 и записываются не более чем с тремя цифрами в дробной
части. В 70 % тестов размеры матрицы не превосходят 100.

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

должны быть помещены в текстовый файл
M
A-
TRIX
.
OUT
, содержащий полученную матрицу в том же формате, что и
входной файл. Значения элементов матрицы должны быть выведены с
точностью до 10
-
6
.

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


4 5

1 12.483 5 8 4

0

10 2 9 9

3 11.001 5 7 1

2 10 9 8 9

1.000000
-
0.400000 5.000000 8.000000 4.000000

0.000000
-
10.000000 2.000000 9.000000 9.000000

3.000000 2.625000 5.000000 7.000000 1.000000

2.000000 10.000000 9.000000 8.000000 5.333333


Задача 3: Где
-
то недостаток, а где
-
то


из
быток…

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

Ограничения по памяти: 16 мегабайт

Максимальное количество баллов: 40


Вам, наверное, известно определение совершенного числа (
perfect
number
): совершенное число
-

натуральное число, равное сумме всех
своих собстве
нных делителей (т.

е. всех положительных делителей, о
т-
личных от самого́ числа
). Числа, не являющиеся совершенными, делятся
на две категории: недостаточные и избыточные числа. Избыточное число
(
abundant number
)


положительное целое число
n
, сумма положител
ь-

18


ных делителей (отличных от
n
) которого превышает
n
. Аналогично опр
е-
деляется недостаточное число (
deficient number
). Единица относится к
недостаточным числам.

Число

48, например, является избыточным, поскольку 1 + 2 + 3 + 4
+ 6 + 8 + 12 + 16 + 24 = 76, 76

>

48. Число 45


недостаточное, поскольку
1 + 3 + 5 + 9 + 15 = 33, 33 < 45. Число 28


совершенное, так как 1 + 2 + 4
+ 7 + 14 = 28.

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

Входные

данные

читаются из текстового файла DPA.IN. Первая
строка этого файла содержит величину
K



количество чисел в послед
о-
вательности (1


K

≤ 500).
Каждая из последующих
K

строк соответств
у-
ет одному элементу последовательности и содержит натуральное число,
н
е превосходящее 10
8
.

Сумма элементов последовательности также не
превышает 10
8
. В 50 % входных файлов
K

≤ 250,
а числа
не превосходят
50000.

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

должны быть помещены в текстовый файл
DP
A
.
OUT
, содержащий единственную строку из
K

символов.
i

-

й
символ
(1

i


K
) этой строки должен быть равен прописной латинской букве
'D'
,
'P'

либо
'A'

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

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


3

2
8


4
5

4
8

PDA


Задача 4: Черепаха

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

Ограничения по памяти: 16 мегабайт

Максимальное количество баллов: 80


Тропический остров представляет собой круг радиуса
R

и состоит
из песч
а
ного пляжа и заросшего травой луга. Луг так
же представляет с
о-
бой круг радиуса
P
, и центры этих двух кругов совпадают.


19


Морская черепаха выползла на ос
т-
ров для кладки яиц в точке
A
, распол
о-
женной на берегу. Место для кладки яиц
также расположено на берегу острова в
точке B. Черепаха может ползти тол
ько
по прямой, пр
и
чем скорость ее движения
по песку равна
V
, а по траве


U
.

Определите время, за которое чер
е-
паха доберется из точки A в точку B.

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

находятся в те
к-
стовом файле
TURTE
.
IN
. Первая строка
этого файла содержит четыре целых чи
с-
ла



величины
R
,
P
,
V
,
U

(0

P

<
R


1000; 1

V
,
U

≤ 100).
Во второй строке
записываются азимуты точек A и B, ра
с-
считанные относительно центра острова (целые числа от 0 до 359). Н
а-
помним, что азимутом называется угол между направлением на север и
направл
ением на соответствующую точку. Азимут измеряется в градусах
и отсчитывается по ходу часовой стрелки.

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

помещаются в текстовый файл
TURTE
.
OUT

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


искомое время, рассчитанное с точн
о-
стью до 10
-
4
.

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


10 6 20 17

90 225

1.0054

2009/2010 учебный год

Автор задач


С.И. Кашкевич. Решения к задачам писал также
А.М.

Статкевич.


Задача 1: Литорея

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

Ограничения по памяти: 16 мегабайт

Максимальное количество балл
ов: 100


Рис
.

2
. Иллюстрация приме
ра из
условия задачи


20


Литорея


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

Текст шифруется с помощью ключа, представляющего собой слово
из с
трочных латинских букв. В шифруемом тексте заменяются только
латинские буквы, остальные символы остаются неизменными. Латинские
буквы разделяются на блоки так, что длина всех блоков (кроме, может
быть, последнего) равна длине ключа. Пусть
a
1



номер первой

буквы
блока в латинском алфавите,
b
1



номер первой буквы ключа. Тогда пе
р-
вая буква блока заменяется буквой, чей номер в алфавите равен
a
1
+
b
1

(если
a
1
+
b
1

> 26, то берется величина
a
1
+
b
1
-
26). При этом прописная бу
к-
ва заменяется на прописную, а строчная


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

Пусть шифруемое слово



Crusader

, а ключом является слово

bow

. Тогда первая буква заменяется буквой
’E’

(номер первой буквы
в латинском ал
фавите


3, а номер первой буквы ключа


2; следовател
ь-
но, она заменяется буквой с номером 5). Аналогично, вторая буква зам
е-
няется буквой
’g’

(18+15=33, 33
-
26=7). Зашифрованный текст, таким
образом, выглядит как
”Egrupagg”
. Обратите внимание на то, что в
этом примере одинаковые буквы заменяются одинаковыми, однако это
случайное совпадение


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

Выполните шифрование заданного текста методом литореи.

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

читаются из

текстового файла
ITTERA
.IN, с
о-
держащего хотя бы одну строку. Первая, непустая строка этого файла
содержит ключ шифрования, а остальные строки
-

шифруемый текст
(символы с кодами от 32 до 255). Длина одной строки не превышает
30000 символов (в 50 % тестов

эта величина не превосходит 255 симв
о-
лов), а общий объем файла не превосходит 5 мегабайт. При переходе на
следующую строку шифрование продолжается с позиции ключа, сл
е-
дующей за той, с помощью которой было выполнено шифрование пр
е-
дыдущей части текста (как
показано во втором примере).

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

Зашифрованный текст должен быть помещен в
текстовый файл
ITTERA
.
OUT
. Количество строк и размер каждой
строки выходного файла должны соответствовать шифруемым данным
входного файла, за одним исключением: послед
няя строка выходного
файла должна заканчиваться символами перевода строки, даже если эт
о-

21


го нет во входном файле. Если исходный файл содержит только строку с
ключом, выходной файл должен быть пустым (иметь длину 0 байт).

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


b
ow

Crusader

Egrupagg

rock

Deep Purple

”Who Do We Think We Are”

Vtha Hjuadt

"Zsg Sr Hw Iktfz Zp Sgh"


Задача 2: Две окружности

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

Ограничения по памяти: 16 мегабайт

Максимальное количество баллов: 40


На плоскости расположе
ны две окружности, которые заданы коо
р-
динатами своего центра и радиусами. Определите, сколько общих точек
имеют эти две окружности. Точки считаются совпадающими, если ра
с-
стояние между ними не превосходит 10
-
6
.

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

читаются из текстового файла
CI
RCES
.IN, с
о-
стоящего из двух строк. Каждая строка этого файла соответствует одной
окружности и содержит три числа


координаты центра окружности и её
радиус. Все числа


целые, не превосходящие по модулю 10
8

(в 50 % те
с-
тов эти числа не превосходят 10
5
). Ра
диусы окружностей больше нуля.

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

должны быть помещены в текстовый файл
CI
R-
CES
.
OUT
, единственная строка которого содержит искомое количество
общих точек двух окружностей. Если окружности совпадают, выведите в
качестве результата

1.

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


0 0 10

0 0 20

0

0 5 9

0 4 10

1

0 5 9

0 5 9

-
1





22


Задача 3: Квадраты цифр числа

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

Ограничения по памяти: 16 мегабайт

Максимальное количество баллов: 100


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

число суммой квадратов
его цифр, и последовательно выполним
K

таких замен.

Какое число п
о-
лучится в результате этих операций?

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

находятся в текстовом файле
QUAD
.
IN
, единс
т-
венная строка этого файла содержит значения величин
N

и
K

(1

N
,
K


10
9
, в 50 % тестов эти величины не превосходят 50000).

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

помещаются в текстовый файл
QUAD
.
OUT
.
Единственная строка этого файла должна содержать результат вычисл
е-
ний.

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


5 3

85

912 4

1


Задача 4: ОЖизньП

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

Ограничения по памяти: 16 мегабайт

Максимальное количество баллов: 100



«Жизнь»


компьютерная игра, придуманная английским матем
а-
тиком Джоном Конвеем (ohn Horton Conway). Впервые описание этой
игры было опубликовано в октя
брьском выпуске (1970) журнала
Scientific American
, в рубрике «Математические игры»
Мартина Гардн
е-
ра

(
Martin

Gardner
). Рассмотрим одну из разновидностей этой игры.

Место действия игры



«вселенная»



размеченный на единичные
квадраты (
клетки
) прямоугольник размером
M

строк и
N

с
толбцов. Ка
ж-
дая клетка может находиться в одном из двух состояний: быть живой или
мёртвой. Клетка имеет, в зависимости от ее расположения, от трех до
восьми
соседей

(т.е. клеток, имеющих с ней общую сторону или угол).
Распределение живых клеток в начале иг
ры называется
первым покол
е-
нием
. Каждое следующее поколение рассчитывается на основе пред
ы-
дущего по следующим правилам:


23




вначале наступает фаза рождения. Каждая пустая (мёртвая)
клетка, рядом с которой есть ровно три живые клетки
-
соседки, оживает;



затем нас
тупает фаза смерти. Если у живой клетки есть две
или три живые соседки, то эта клетка продолжает жить; в противном
случае (если соседей меньше двух или больше трёх) клетка умирает от
«одиночества» или «перенаселённости». Клетки, ожившие на фазе ро
ж-
дения эт
ого же поколения, не учитываются при расчёте количества ж
и-
вых соседок.

По карте вселенной с первым поколением клеток определите карту
с
P
-
м поколением.

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

находятся в текстовом файле IFE.
IN
. Первая
строка этого файла содержит три целых числа


величины
M
,
N
,
P

(1



M
,
N

≤ 100, 1 ≤
P

≤ 1000,
в 50 % тестов эта величина не превосходят
100). Далее следуют
M

строк по
N

символов каждая


описание первого
поколения. Символ
'*'

(звёздочка) в этом описании соответствует ж
и-
вой, а символ
'.'

(точка)


м
ёртвой клетке.

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

помещаются в текстовый файл
IFE
.
OUT

и с
о-
держат описание
P
-
го поколения в том же формате, что и во входном
файле. Последняя строка файла должна заканчиваться символами пер
е-
вода строки.

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


10 9
4

.........

.**......

.**......

.......*.

.......*.

.......*.

.........

....*....

....*....

.....*...

.........

.**......

.**......

.........

......***

.........

.........

.........

.........

.........




24


10 10 10

..........

..........

..........

.........
.

....*.....

...***....

..........

..........

..........

..........

..........

..........

...***....

..........

.*.....*..

.*.....*..

.*.....*..

..........

...***....

..........

2010/2011 учебный год

Авторы задач


С.И. Кашкевич и А.А. Толстиков. Идея задачи «Гири и
весы» принадлежит Ю.Г. Стёпину.

Им
ена

входн
ых

файл
ов для всех задач
:
input
.
txt

Имя в
ы
ходн
ых

файл
ов для всех задач
:
output
.
txt


Задача 1: Пвереернуть строку!

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

Ограничения по памяти: 16 мегабайт

Максимальное количество баллов: 50


Задана непустая строка
S

и два целых числа
A

и
B

(1

A


B
,
B

не
превосходит длины строки). Вам требуется «перевернуть» часть строки,
поменяв местами символы с

номерами
A

и
B
,
A
+1 и
B
-
1, …,
A
+
n

и
B

n

до
тех пор, пока
A
+
n

<
B

n
.

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

Входной файл состоит из двух строк.
Первая строка содержит значения
A

и
B
, вторая


строку
S
. Длина строки
не превосходит 30000 (в 50% тестов длина не превосходит 2
55).

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

Единственная строка выходного файла
должна содержать преобразованную строку.

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


2 5

Перевернуть строку!

Пвереернуть строку!

1 10

1234567890

0987654321


25


5 5

abracadabra

abracadabra


Задача 2: Г
ири и весы

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

Ограничения по памяти: 64 мегабайт

Максимальное количество баллов: 100


Комплект гирь состоит из
N

гирь различного веса; в Вашем расп
о-
ряжении имеются два таких комплекта. Сможете ли Вы уравновесить
рычажные вес
ы гирями из этих комплектов, положив на каждую из ч
а-
шек по две гири? При этом гири на левой чашке должны иметь одинак
о-
вый вес, а на правой


разный.

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

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

(1

N

≤ 10000,
для 50% тестов эта
величина не превышает
1000). Вторая строка содержит
N

целых положительных чисел, не пр
е-
восходящих 10
9



веса очередной гири.

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

В первой строке запишите
’Yes’

или
’No’

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


вес одной из гирь, лежащих на левой чашке. Если ответ отрицател
ь-
ный, вторая строка должна содержать наименьший и наиболь
ший вес
гирь из комплекта (в произвольном порядке).

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

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


5

10 20 30 40 50

Yes

20 40

30

7

20 50 1 10 5 2 100

No

100 1


Задача 3: Электронная мишень

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

Ограничения по памяти: 16 мегабайт

Максимальное количество баллов: 100



26


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

покрытую специальным составом,
реагирующим на луч лазера. На мишени отображаются
K

концентрич
е-
ских окружностей различного радиуса. Окружности пронумерованы, н
а-
чиная с единицы, в порядке убывания радиусов. Попадание вовнутрь и
на границу самой маленькой ок
ружности приносит стрелку
K

очков. П
о-
падание в кольцо, ограниченное окружностями
i

и
i
+1 (включая границу
окружности
i
, но исключая границу окружности
i
+1) даёт
i

очков. Нак
о-
нец, если стрелок не попадает в окружность
1
, ему засчитывается промах
и начисляет
ся 0 очков.

Стрельба по таким мишеням ведётся из специального оружия, к
о-
торое вместо пуль выпускает луч лазера.

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

стрельбы.

Вам поручена реализация второй части этой задачи, а именно: по
информации о числе окружностей и их радиусах, а также о координатах
попаданий
N

выстрелов, сделанных одним стрелком, рассчитать колич
е-
ство очков, полученных этим спортсменом.

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

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

и
N

(1

K

≤ 10
4
, 1

N

≤ 10
5
, в 50% тестов
N
,
K

≤ 100,
а в 80%
тестов
K

≤ 100,
N

≤ 1000).
Вторая строка содержит
K

целых чисел
-

р
а-
диусы окружностей
R
1
, …,
R
K
. Ограничения на радиусы: 1

R
K

< … <
R
1
.
Считается, что центры всех окружностей находятся в точке (0, 0).

Затем следуют
N

строк, каждая из которых описывает результаты
одного выстрела и содержат два целых числа


координаты очередного
попадания. Абсолютные величины координат и радиусо
в окружностей
не превосходят 50000 (в 60% тестов они не превосходят 20000).

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

Выведите единственное число


ра
с-
считанный результат стрельбы.




27


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


5 6

10 8 6 4 2

0 0

1 1

2 2

3 3

4 4

5 5

22


Задача 4: Чи
сла
-
близнецы

Ограничения по времени: 2 секунды

Ограничения по памяти: 256 мегабайт

Максимальное количество баллов: 100


Пару чисел
-
близнецов составляют два целых положительных числа
A
1

и
A
2
, удовлетворяющие следующим условиям:



A
1

=
A
2

+ 2;



оба этих числа


простые.

Определите, сколько различных пар чисел
-
близнецов находится в
интервале от
M

до
N
. Пары считаются различными, если их меньшие
элементы не равны. Напомним, что единица не считается простым чи
с-
лом.

Формат входных данных.
Единственная строка содерж
ит величины
M

и
N

(1

M


N

≤ 10
9
,
N

M

≤ 10
$
; для 20% тестов
N

≤ 10
3
, а для 80% те
с-
тов
N

≤ 10
7
).

Формат выходных данных
. Выведите искомое количество чисел
-
близнецов.

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


1 13

3


Пояснение:

результатом будут пары (3, 5), (5,
7), (11, 13).




28


2011/2012 учебный год

Авторы задач


С.И. Кашкевич и А.А. Толстиков
.

Полное решение каждой задачи оценивалось в 100 баллов.

Им
ена

входн
ых

файл
ов для всех задач
:
input
.
txt

Имя в
ы
ходн
ых

файл
ов для всех задач
:
output
.
txt


Задача 1: Метрическо
е время

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

Ограничения по памяти: 16 мебибайт


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

Принято решение для измерения

промежутков времени отказаться
от привычных часов, минут и секунд и ввести новые метрические един
и-
цы измерения. Согласно этому проекту, сутки делятся на 10 равных д
о-
лей


децидней
. Децидень, в свою очередь, делится на сто
миллидней
, а
миллидень


на 100
м
икродней
. Запись времени, прошедшего с начала
суток (полуночи), ведётся в виде a:bb:cc, где a, b, с (0
≤ a ≤ 9, 0 ≤ b,
с

99)


соответственно число деци
-
, милли
-

и микродней. Заметьте, что для
записи величин b и c всегда используются две цифры, например,

3:05:86.

Напомним, что запись времени в «старой» 24
-
часовой системе в
ы-
глядит как dd:mm:ss, где d, m, s


соответственно число часов, минут и
секунд, прошедших с полуночи. Для записи часов, минут и секунд всегда
используются две цифры, например, 05:20:00.

Во время переходного периода необходимо быстро переводить
время из 24
-
часовой в метрическую систему и обратно. Вам поручено
разработать соответствующее программное обеспечение…

Формат входных данных.
Первая строка входного файла содержит
величину
K



колич
ество подтестов (2

K

≤ 10
5
, в 80 % тестов
K

≤ 10
4
, в
50% тестов
K

≤ 100).
Каждая из последующих
K
строк описывает один
подтест и содержит тип системы исчисления времени (1


24
-
часовая, 2


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


29


Формат выходных данных
. Выходной файл должен содержать
K

с
трок, каждая из которых соответствует одному подтесту и содержит р
е-
зультат перевода.

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


4

1 06:04:17

1 00:00:00

2 5:18:71

2 9:99:99

2:52:97

0:00:00

12:26:56

23:59:59


Задача 2: Проверка на нечётность

Ограничения по времени:

2 секунды

Ограничения по памяти: 16 мебибайт


Заданы два целых положительных числа
A

и
B

(
A


B
). Определите,
для скольких целых чисел из интервала [
A
,
B
] их двоичное представл
е-
ние содержит нечётное количество единиц.

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

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



количество подтестов (2

K

≤ 5).
Каждая из последующих
K
строк соответствует одному подтесту и содержит величины
A

и
B

(1

A
,
B

≤ 10
18
). Для 50 % тестов величина
B
-

A

не превышает 10
6
, а для 25 %
тестов


10
5

во всех

подтестах таких тестов.

Формат выходных данных
. Выведите
K

строк, каждая из которых
должна содержать ответ на очередной подтест


искомое количество ч
и-
сел.

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


2

10 16

20 25

4

3

5

1 4

10 40

100 400

1000 4000

10000 40000

3

1
5

151

1500

15001




30


4

10 99

100 999

1000 9999

10000 99999

45

450

4500

45000


Задача 3: Химия, химия…

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

Ограничения по памяти: 16 мебибайт


Названия химических элементов состоят либо из одной прописной
латинской буквы (напр
имер,
H



водород,
K


калий), либо из пары л
а-
тинских букв, первая из которых является прописной, а вторая


стро
ч-
ной (например,
Ca


кальций,
Hg


ртуть).

Задана непустая строка
S
, содержащая названия всех химических
элементов, атомы которых входят в сост
ав молекулы некоего химическ
о-
го вещества. Если в состав молекулы входят несколько атомов одного
химического элемента, название этого элемента повторяется соответс
т-
вующее количество раз, причём не обязательно подряд. Никаких разд
е-
лителей между названиями эл
ементов нет. Так, строка

OKOMnOO

(перманганат калия) означает, что в состав этой молекулы входят четыре
атома кислорода (
O
) и по одному атому калия (
K
) и марганца (
Mn
)
1
.

Определите количество различных химических элементов, атомы
которых входят в состав
описанного вещества.

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

Входной файл содержит единственную
строку
S
. Длина строки не превосходит 30000 (в 50 % тестов длина не
превосходит 255). Кроме того, в 25 % тестов строка
S

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

Формат выход
ных данных
. Единственная строка выходного файла
должна содержать искомое число различных химических элементов.

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


OKOMnOO

3

ABABAB

2

AbABaB

4





1

Химические элементы и вещества, описанные
в примерах и тестах, могут не
существовать в природе.


31


Задача 4: День пряника

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

Ограничения по памят
и: 16 мебибайт


В школах страны Байтландии прижился интересный обычай. Один
раз в году, в т.н. «День пряника» девочки пекут (под руководством ста
р-
ших, конечно!) пряники, печенье и другие вкусные вещи, а потом уг
о-
щают ими своих одноклассников. Выпечка, приг
отовленная к Дню пр
я-
ника, обычно имеет форму треугольников или прямоугольников.

Маша приготовила на этот праздник
N

пряников различной формы
и размера и подготовила соответствующее число одинаковых круглых
коробок, чтобы упаковать угощение, по одному пряни
ку в коробку. Но
вот незадача! Оказывается, некоторые пряники не помещаются в подг
о-
товленные коробки…

Помогите Маше определить, что из приготовленного угощения
поместится в подготовленные упаковочные коробки, а что


нет.

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

В первой ст
роке входного файла записан
диаметр упаковочной коробки, а во второй


количество приготовленных
Машей угощений
N

(2

N

≤ 100).
Каждая из последующих
N

строк с
о-
держит описание одного пряника. Если пряник имеет треугольную фо
р-
му, то в начале строки записыв
ается 1, а затем


длины сторон этого тр
е-
угольника (треугольник невырожденный). Для прямоугольного пряника
в начале строки записывается 2, а затем


длины смежных сторон прям
о-
угольника. Числа в строках разделяются единственным пробелом. Все
размеры


целые

положительные числа, не превосходящие 10
17

(для 80 %
тестов эта величина не превосходит 10
3
).

Для 25 % тестов угощение имеет только форму прямоугольников.

Формат выходных данных
. Выведите в выходной файл строку из
N

символов. Каждый символ строки соответ
ствует одному прянику (в п
о-
рядке, заданном во входном файле). Символ

Y


означает, что пряник
можно поместить в коробку, а символ

N




что пряник поместить нел
ь-
зя.

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


20

2

2 15 17

2 19 5

NY




32


20

4

1 20 12 16

1 10 10 10

1 2
0 20 20

2 13 15

YYNY

2012/2013 учебный год

Авторы задач


С.И. Кашкевич и А.А. Толстиков.
Идея второй задачи
взята из соревнований
ВКОШП

(г. Санкт
-
Петербург).

Полное решение каждой задачи оценивалось в 100 баллов.

Им
ена

входн
ых

файл
ов для всех задач
:
inp
ut
.
txt

Имя в
ы
ходн
ых

файл
ов для всех задач
:
output
.
txt


Задача 1: Построить римское число

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

Ограничения по памяти: 6
4

мебибайта

One of the main causes of the fall of the Roman
Empire was that, lacking zero, they had no way t
o
indicate successful termination of their C programs.

Robert Firth


Напомним прежде всего правила записи натуральных чисел в ри
м-
ской системе счисления. В этой системе может быть представлено любое
натуральное число, не превосходящее 3999. Для записи отдел
ьных (т.н.
атомарных
) чисел используются следующие заглавные латинские буквы
и их комбинации:

1


I

4


IV

5


V

9


IX

10


X

40


X

50




90


XC

100


C

400


CD

500


D

900


CM

100
0



M




Число
P
, не входящее в приведенный список, записывается
сл
е-
дующим образом: находим наибольшее из атомарных чисел
K
, не пр
е-
восходящее
P
, и записываем его представление в римской системе счи
с-
ления. Затем повторяем эту же процедуру для числа
P
-
K

и т.д. до тех
пор, пока после вычитания не получим ноль. Представлени
я атомарных
чисел записываются слева направо без каких
-
либо промежутков. Так,
число 999 в римской системе счисления будет записано как CMXCIX (а
не IM, как может показаться!).


33


Задана непустая строка, состоящая из символов
'M'
,
'D'
,
'C'
,
''
,
'X'
,
'V'
,
'I'
. Переставьте символы в этой строке так, чтобы они
образовали правильное число в римской системе счисления.

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

В первой строке входного файла задаётся
число
N

количество подтестов (1

N

≤ 5).
Каждая из последующих
N

строк соответствуе
т одному подтесту и содержит исходную последов
а-
тельность символов. Длина последовательности не превосходит 15. В 50
% тестов длина последовательности не превосходит 5 для всех подтестов
этого теста.

Формат выходных данных
. Выходной файл содержит
N

строк, к
а-
ждая из которых соответствует одному подтесту. Она должна содержать
полученное число в десятичной системе счисления. Если построить чи
с-
ло невозможно, выведите ноль (отсутствие которого и стало причиной
краха Римской империи). Если задача допускает несколь
ко решений, в
ы-
ведите максимальное из возможных чисел.

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


5

IXIC

CMMMM

CMMMCM

II

D

112

3900

0

0

500


Задача
2
: Две матрицы

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

Ограничения по памяти: 6
4

мебибайта


Заданы две матрицы
A

и
B
, со
стоящие из
M

строк и
N

столбцов к
а-
ждая. Матрица
A

заполнена числами от 1 до
M

×
N

сначала по строкам, а
затем по столбцам, а матрица
B



вначале по столбцам, а потом по стр
о-
кам. Так, для
M

= 3 и
N

= 5 эти матрицы будут иметь вид

1

2

3

4

5


1

4

7

10

13

6

7

8

9

10


2

5

8

11

14

11

12

13

14

15


3

6

9

12

15

Найд
ите количество различных пар (
i
,
j
), 1

i


M
, 1

j


N

таких,
что
A
ij

=
B
ij
.


34


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

Единственная строка файла содержит
числа
M

и
N

(1

M
,
N

≤ 10
18
, для 20 % тестов
M
,
N

≤ 20,
а для
50 % те
с-
тов
M
,
N

≤ 1000)


размерности матриц.

Формат выходных данных
. Выведите одно число


искомое кол
и-
чество пар.

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


10 5

2

3 5

3


Задача 3: Резисторы

Ограничения по времени: 0
,
5 секунд
ы

Ограничения по памяти: 8 мебибай
т


В Вашем распоряжении имеется
N

резисторов, сопротивление к
о-
торых неизвестно. Единственное, что вы можете сделать


подключить
эти резисторы по одному к достаточно мощному
2

источнику постоянного
напряжения и замерить величину тока (в микроамперах), прохо
дящего
по полученной цепи. Для
i
-
го резистора (1

i


N
) эта величина равна
T
i
.

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

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

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

(5

N

≤ 10
6
, в 20 % тестов эта величина н
е превосходит 100,
а в 50 % тестов


10000). Вторая строка содержит значения
T
i



целые
положительные числа, не превосходящие 10000.

Формат выходных данных
.
Единственная строка выходного файла
должна содержать пять чисел
-

номера выбранных Вами резисторов


е-
зисторы нумеруются, начиная с единицы, в порядке появления информ
а-
ции о них во входном файле). Если задача допускает несколько решений,
выберите любое из них.

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

10

3 1 3 1 3 1 1 1 1 2

1 2 3 5 10




2

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


35


Задача 4: Юный чертёжник

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

Ограничения по памяти: 6
4

мебибайта


У Коли не так давно начались уроки черчения… Его любимое у
п-
ражнение


рисовать прямые линии с помощью линейки. Но просто пр
и-
кладывать линейку к ватману и проводить карандашом линию ему

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

Однажды он отметил 4 точки, и решил провести через них 2 пр
я-
мые (одну через первую и вторую точки, а вторую через третью и че
т-
вертую), но до этого момента он решил угадать, как будут соотносить
ся
эти прямые между собой, т.е. будут ли они пересекающимися, пара
л-
лельными или совпадающими. Коля уже записал свое предположение на
листке бумаги, помогите ему получить правильный ответ.

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

В первой строке входного файла запис
а-
но целое

число
T

(1

T

≤ 10)


количество подтестов. Далее в каждой из
T

строк записано по 8 целых чисел
x
1
, y
1
, x
2
, y
2
, x
3
, y
3
, x
4

и
y
4

(
-
1,000,000

x
1
, y
1
, x
2
, y
2
, x
3
, y
3
, x
4
, y
4

≤1,000,000,
в 50 % тестов эти величины не пр
е-
восходят 1000 для всех подтестов)


координаты четырёх отмеченных
Колей точек. Гарантируется, что первая и вторая, а также третья и че
т-
вёртая точки различны в каждом подтесте.

Формат выходных данных
. В выходной файл выведите
T

строк


по одной для каждого подтеста. Если прямые из
i
-
ого подте
ста совпад
а-
ют, то выведите

COINSIDE

; если они пересекаются в одной точке,
выведите

CROSS

; если параллельны



PARAE

.

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


7

1 2 4 8 16 32 64 128

1 2 3 4 5 6 7 8

0 0 1 1 1 0 2 1

1 2 2 1 0 4 4 0

1 1 2 2
-
1 1
-
2 2

1 2 3 4
4 3 2 1

1 9 8 3 4 5 2 7

COINSIDE

COINSIDE

PARAE

PARAE

CROSS

PARAE

CROSS





36


Разбор задач

А
вторы разбор
а



С.И. Кашкевич и В.В. Климович.

2005/2006 учебный год

Задача 1: Период времени


Наилучшим, по мнению автор
ов
, способом решения этой задачи,
было бы использование специальных типов, предназначенных для раб
о-
ты с датой и временем (наподобие типа
TDateTime

систем
Free

Pascal

и
Delphi
). В этом случае необходимо перевести входные строки в тип
TDateTime
, а затем с помощью функции
SecondsBetween

получ
ить р
е-
зультат.
3

Если участники не знают этих типов или не умеют с ними работать,
им придётся выполнять соответствующие преобразования вручную. В
этом случае оптимальным (опять
-
таки, по мнению автора) является сл
е-
дующий подход: подсчитать число секунд, прош
едших с полуночи 1 я
н-
варя 1801 года до момента времени, указанного во входном файле, а з
а-
тем выполнить вычитание полученных величин.

Приведём пример функции, считающей число секунд:

function Str2Secs(: string): extended;

var


Y, M, D, H, N, S: longint;


D
ays: extended;


i: word;

begin


Y := StrToInt(copy(, 7, 4));


M := StrToInt(copy(, 4, 2));


D := StrToInt(copy(, 1, 2));


H := StrToInt(copy(, 12, 2));


N := StrToInt(copy(, 15, 2));


S := StrToInt(copy(, 18, 2));


Days := 365*(Y
-
1801)+(Y
-
1801) div 4
;


if Y>1900 then


Days := Days
-
1;


for i := 1 to M
-
1 do


Days := Days+DayInMonth[i];


//
DayInMonth

-

массив дней в месяце




3

Последние версии системы программирования
Free

Pascal

некорректно о
брабатывают даты, относ
я-
щиеся к
XIX

столетию…



37



//
в

невисокосном

году


if (M>2) and (Y mod 4 = 0) and (Y <> 1900) and
(Y<>2100) then


Days := Days+1;


Days := Days+D
-
1
;


Str2Secs := 3600*H+60*N+S + 86400*Days;

end;

Наконец, участники, запутавшиеся в вычислении числа дней, или не
знающие, как это сделать, могут получить 50 % баллов, решая задачу для
тестов, относящихся к одной дате. В этом случае им достаточно опред
е-
лить

количество секунд, прошедших с начала дня, по формуле

3600*H+60*N+S


Задача 2: Правые части


Обозначим через
F
(
x
) сумму правых частей для чисел от 1 до
x


положим
F
(0) = 0). Тогда ответ задачи будет выражаться формулой
F
(
B
)


F
(
A

1).

Для нахождения
F
(
x
) разобьём числа из этого интервала на н
е-
сколько групп. В частности, группу
S
i

будут образовывать все числа, к
о-
торые не делятся нацело на
2
i
, но делятся на меньшие степени двойки. В
частности, все нечётные числа будут образовывать группу
S
0
. Правые
части
для каждого числа из группы
S
i

равны 2
i
, осталось оценить колич
е-
ство чисел в группе. Эта величина почти равна
x

div

2
i
+
1

(но если
i
-
й дв
о-
ичный разряд числа
x

содержит единицу, то к ней надо добавить ед
и
н
и-
цу).

Теперь расчёт суммы правых частей не представ
ляет сложностей.
Учитывая, что основные операции при вычислениях


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

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


Задача 3: Мат в один ход


Сейчас
авторы

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

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

38


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

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

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


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


2006/2007 учебный год

Задача 1: Игра


Это


типичная задача, относящая к классу антагонистических игр.
Ее решение закл
ючается в следующем. Введем на игровом поле систему
координат так, что левая нижняя клетка будет иметь координаты (1, 1), а
правая верхняя


(
M
,
N
).Все клетки игрового поля делятся на три вида:

Рисунок 3. Матующие позиции
(закрашены серым)

39




финальная

клетка с координатами (
M
,
N
);



выигрышные

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



проигрышные

клетки, переход из которых возможен только в
выигрышную либо финальную клетку.

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

Итак, для того, чтобы
решить поставленную з
а-
дачу, достаточно опред
е-
лить, является ли клетка (1,
1) выигрышной или прои
г-
рышной.

В

нашем случае спр
а-
ведливо следующее у
т-
верждение: клетка с координатами (
i
,
j
) является проигрышной, если
клетки (
i
,
j
+1), (
i
,
j
+2), (
i
+1,
j
), (
i
+2,
j
), (
i
+3,
j
) либо не существуют, либо
являются выигрышными. В противном случае клетка (
i
,
j
) является выи
г-
ры
шной.

Первый, нерациональный способ решения задачи заключается в
том, что формируется битовый массив размером
M

×

N
, который запо
л-
няется в следующем порядке: последняя строка, последний столбец,
предпоследняя строка и т.д. После того, как заполнена клетка
(1, 1), з
а-
дача решена. Из
-
за больших ограничений на
M

и
N

этот способ может
взять только 50 % тестов. Кроме того, при этом способе требуется бол
ь-
шой объем памяти для хранения массива, что требует дополнительных
усилий при решении задачи на
Borland

Pascal

(
например, можно хранить
в памяти не всю матрицу, а только 4 строки и 3 столбца).

Второй способ решает задачу за время, не зависящее от
M

и
N
. З
а-
полним вручную несколько последних строк и столбцов игрового поля
,
как

показано на рис.

4
, чтобы проследить закономерность (серым цветом

Рис
.

4
. Выигрышные и прои
грышные (закр
а-
шенные серым)


клетки для доски 10
× 10.


40


з
а
кр
а
ш
е
ны пр
о
и
г
ры
ш
ные клетки). Теперь очевидно, что при
M

mod

4 = 0
Вася вс
е
гда в
ы
игр
ы
вает, в других случаях нетрудно вывести формулу,
опред
е
ля
ю
щую вид клетки (1, 1) в зависимости от величин
M

mod

4 и
N

mod

3.


Задача 2: Постулат Бертрана


Казалось бы, о
пределение того, является ли натуральное число
A

простым, не представляет трудностей


достаточно находить остаток от
его деления на все предыдущие натуральные числа,
превосходящи
е

ед
и-
н
и
ц
у
. О
д
н
а
ко такое лобовое решение крайне неэффективно. Ускорить
р
а
боту мо
ж
но,

останавливая процесс деления, если делитель становится
бол
ь
шим, чем
sqrt
(
A
)


в этом случае
A

гарантированно является пр
о-
стым числом. Кр
о
ме того, нет смысла делить на составные числа


сл
е-
дует хранить в пам
я
ти массив простых чисел, не превосходящих
sqrt
(
A
),
и д
е
лить только на элементы этого массива. Оказывается, при
A
=2000000
н
е
обходимо хр
а
нить только 223 первых простых числа, что снимает пр
о-
блемы с в
ы
дел
е
нием памяти для программирующих в среде
Borland

Pa
s-
cal
.

Еще одно усовершенствование связано с тем, чт
о нет необходим
о-
сти просматривать все числа в промежутке [2, 2

×
N
); достаточно иссл
е-
довать два промежутка: [2,
int
(
sqrt
(2

×
N
))] и (
N
, 2

×
N
).


Задача 3: Пустые прямоугольники


Самый простой метод решения этой задачи заключается в том, что
перебираются в
се допустимые пары точек
i

и
j

(т. е. такие пары, что
x
i


x
j

и
y
i


y
j
) и для каждой такой пары просматриваются оставшиеся точки.
Если хотя бы одна из оставшихся точек лежит внутри или на границе
прямоугольника, образованного точками
i

и
j
, мы должны пере
йти к ан
а-
лизу следующей пары.

Это алгоритм имеет трудоемкость O(
N
3
). Ограничения по времени
не устанавливались, так что даже этот алгоритм при правильном переб
о-
ре (так, необходимо потребовать, чтобы выполнялось условие
i

<
j
, чт
о-
бы по крайней мере вдвое со
кратить число вычислений) должен брать
все тесты.

Оптимизация алгоритма заключается в том, что исходные точки
предварительно сортируются по возрастанию значений одной из коорд
и-
нат (например, координаты
X
). Тогда для выбранной пары точек
i

и
j

в
большинств
е случаев можно существенно уменьшить количество пр
о-

41


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


Задача 4: Поиск анаграмм


Заметим, что две строки
S
1

и
S
2

являются анаграммами друг друга,
если количество вхождений каждого символа в строку
S
1

и
S
2

одинак
о
во.
Поэтому для решения задачи достаточно определить два целочисле
н
ных
массива

из 52 элементов каждый, и, просматривая исходные строки, н
а-
капливать в этих массивах число соответствующих символов. После
окончания просмотра необходимо сравнить эти массивы поэлементно:
если массивы равны, то строки являются анаграммами друг друга, и н
а-
оборот. Трудоёмкость такого решения


O

(
N
), где
N



длина строки.

Другие подходы к решению этой задачи:



формировать один массив, и для строки
S
1

увеличивать соответс
т-
вующий элемент массива, а для строки
S
2



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



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


O
(
N

log

N
), что
может привести к нарушению лимита времени.



отсортировать обе строки, а затем сравнить их. Алгоритм также не
является оптимальным по времени.

2007/2008 учебный год

Задача 1: Экспрессные маршруты


Пусть
D
(
n
)


число всех маршрутов (обычных и экспрессных), с
о-
единяющих города
A

и
B

при условии
n

промежуточных остановок. Т
о-
гда ответ будет равен
D
(
n
)
-
1.

Составим рекуррентное соотношение для нахождения
D
(
n
):




42


D
(
n
) :=
D
(
n
-
1) //маршруты, делающие последню
ю


//
промежуточную остановку в пункте
n


+
D
(
n
-
2) // то же для последней остановки


//
в пункте
n
-
1


+
D
(
n
-
3) // то же для последней остановки в


//
пункте
n
-
2

Начальные значения для
D
(
n
):

D
(0) = 1;
D
(1) = 2;
D
(
2) := 4;

Остается написать программу для реализации этого рекуррентного
соотношения

.

Входные данные для не менее, чем 50 % тестов подобраны так,
чтобы результаты помещались в 4
-
байтовое целое число (тип longint в
Паскале или long в С++), для остальных т
естов результаты помещаются в
8
-
байтовое число.


Задача 2: Отрезки на прямой


Отсортируем все отрезки по неубыванию их начальных точек.

Просматривая отсортированную последовательность отрезков, мы
можем получить ответ по следующему алгоритму:

1.

первый из но
вых отрезков совпадает с первым отрезком из
условия;

2.

если начало очередного отрезка из условия выходит за гр
а-
ницы последнего нового отрезка
,

это


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

3.

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

Псевдокод приводится ниже.

с
[1] :=
a
[1];
d
[1] :=
b
[1];
k

:= [1];

for i := 2 to N do begin


if a[i]>d[k
]

then begin


// рассчитать длину максимального из просмотре
н-
ных отрезков


k := k+1;


c[k] := a[i]; d[k] := b[i]
;


end


else


d[k] := max (d[k], b[i]);


43


end
;

Для не менее

чем 50 % тестов размерность задачи позволяет выпо
л-
нить сортировку за время
O

(
n
2
), однако для полного решения задачи
требуется умение программировать более эффективные алгоритмы со
р-
тировки.


Задача 3: Проблема Гольдбаха


Заводим логический массив
P

из
N

элементов, и заполняем его зн
а-
чениями true или false в зависимости от того,

является ли число
i

(1

i


N
) простым. Метод заполнения


решето Эратосфена (те участники, к
о-
торые незнакомы с этим алгоритмом, могут, конечно, проверять прост
о-
ту числа другими методами, но это может привести к нарушению пред
е-
ла времени).

После этого вы
полняем поиск решения: просматриваем элементы
массива
P

в порядке уменьшения индексов. Пусть
P
[
i
]


простое число,
тогда проверяем на простоту число
N

P
[
i
]. Если и это число


простое,
задача решена. В противном случае продолжаем просмотр элементов
массива

P
.

Не менее 50 % тестов позволяют решить задачу с учетом огранич
е-
ний на объем статической памяти, накладываемых системой программ
и-
рования Borland Pascal, для прохождения остальных тестов требуется л
и-
бо работать в других средах, либо выделять память динами
чески.


Задача 4: Изменить Строку!


Определим условие, когда текущий символ строки стоит в начале
слова: текущий символ


не пробел и либо он стоит в начале строки, л
и-
бо перед ним находится пробел. Порядок проверки условий важен, п
о-
этому необходимо включи
ть режим неполного вычисления логических
выражений (по умолчанию он включен в системах программирования
для
Pascal
).

Режим неполного вычисления логических выражений, примен
и-
тельно к этой задаче, состоит в следующем. Если при вычислении выр
а-
жения

(
a
)
or

(
b
)

оказалось, что значение
a

-

истина, то
b

можно и не вычислять, а иногда
и нельзя вычислить... Если символ стоит в начале строки, то проверять,
не стоит ли перед ним пробел, нельзя.


44


Просматриваем строку и для каждого символа, стоящего в начале
слова и яв
ляющегося маленькой латинской буквой, выполняем соотве
т-
ствующую замену…

Не менее 50 % тестов позволяют решить задачу с учетом огранич
е-
ний на длину строки, накладываемых системой программирования
Borland Pascal, для прохождения остальных тестов требуется ли
бо раб
о-
тать в других средах, либо переходить к типу PChar.

2008/2009 учебный год

Задача 1: Тарабарская грамота


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


с исходным и
«перевернутым» порядком согласных букв, и заменять все
символы, которые были найдены в первом массиве, на соответствующие
элементы из второго массива.

Единственная сложность состоит в обработке длинных строк. Чт
е-
ние из входного файла по одному символу прив
едет к длительному в
ы-
полнению программы, поэтому для того, чтобы взять максимальное к
о-
личество баллов, необходимо уметь работать с типами AnsiString или
PChar

в системе программирования
Free

Pascal
. Сниженные ограничения
соответствуют типу s
tring

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

Затруднение у участников вызвала фраза из условия: «…в

проти
в-
ном случае последняя строка выходного файла должна заканчиваться
символами перевода строки
». Многие восприняли это, как

необход
и-
мость выводить в конце файла пустую строку. На самом деле это означ
а-
ет, что во входном файле последняя строка может оканчиваться симв
о-
лами перевода строки, а может и не оканчиваться ими (в тесте 03). В
ы-
ходной же файл ВСЕГДА должен завершаться этим
и символами (это н
е-
обходимо для правильной работы чекера).


Задача 2: Сглаживание матриц


Самая сложная, на мой взгляд, задача соревнования. В ней заложены
два подводных камня.

1) Необходимо правильно определить количество соседей каждого
элемента матри
цы (от 1 до 8) и просмотреть всех соседей. Одно из во
з-
можных решений этой задачи состоит в следующем. Пусть нам надо о
п-

45


ределить всех соседей элемента A[i, j]. Напишем следующий фрагмент
программы на Паскале:

for

di

:=
-
1
to

1
do


for

dj

:=
-
1
to

1
do




if ((di<>0) or (dj<>0)) and


(i+di>0) and (i+di<=M) and


(j+dj>0) and (j+dj<=N) then begin


{элемент
A
[
i
+
di
,
j
+
dj
] является соседом, обработать
его}


end;

2) Ограничения на размеры матрицы таковы, что невозможно выд
е-
лить память для ее хр
анения по максимуму. Поэтому надо либо выделять
память динамически, либо хранить в памяти только три очередных стр
о-
ки матрицы.

Сниженные ограничения дают возможность хранить матрицу в п
а-
мяти целиком без динамического выделения памяти.


Задача 3: Где
-
то нед
остаток, а где
-
то


избыток…


Самая простая задача, для решения которой необходимо лишь ум
е-
ние определять все делители натурального числа
N

путем полного пер
е-
бора всех чисел от 1 до
N

и проверки делимости.

Сниженные ограничения дают возможность использов
ать тип string
в системе программирования
Free

Pascal

для хранения результатов раб
о-
ты.


Задача 4: Черепаха


Задача является упрощенным двумерным вариантом задачи «Червяк
на яблоке», предложенной на четвертьфинале студенческого чемпионата
мира по програм
мированию, проходившем в БГУ в 2008 году.

Задача требует умения рассчитывать стороны прямоугольных тр
е-
угольников. Обозначим через
φ
A

и
φ
B

азимуты точек
A

и
B

соответстве
н-
но. Тогда угол
AOB
, равный
φ
, вычисляется по формуле

φ

:=
abs
(
φ
A

-

φ
B
);

if

φ

>180
the
n



φ

:= 360
-

φ
;

Расстояние
AB
, которое проползет черепаха, равно 2*
R
*
sin
(
φ

/2). Для
того, чтобы найти, какую часть этого пути составит луг, найдем
OH




46


высоту треугольника
AOB
. Она
равна
h

=
R

×
cos
(
φ
/2). Если
h



P
, весь путь черепахи прох
о-
дит по песку.

В противном сл
у-
чае расстояние, кот
о
рое черепаха
проползет по траве, вычисляется
по теореме Пифагора из тр
е-
угольника
OHT
.





2009/2010 учебный год

Задача 1: Литорея


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


по длине строки и по длине ключа, с учётом того,
что переход на новую строку не сбрасывает счётчик цикла по ключу!


Ограничения, накладываемые на 50 % тестов, дают возможность
работать

со стандартным типом string системы программирования Free
Pascal.


Задача 2: Две окружности


Задача, которая, по мнению авторов, должна была быть утеш
и-
тельной, но на самом деле такой не явилась…


Пусть
D



расстояние между центрами окружностей,
R
1

и
R
2



их
радиусы. Будем без ограничения общности полагать, что
R
1


R
2
. Тогда:



если центры окружностей и их радиусы равны, то ответ
-
1;



если (
R
1

+
R
2

=
D
) или (
R
1



R
2

=
D
), то ответ 1;

O


A


B


H


T


Рис
.

5
. Прямоугольные треугольни
ки
для расчёта


47




если (
R
1

+
R
2

>

D
) или (
R
1

+
R
2

<

D
), то ответ 0;



в противном случае ответ

2.

При этом не играет роли, как расположены окружности


находи
т-
ся ли центр одной из окружностей внутри другой, либо нет.

В 50 % тестов для вычислений достаточно использовать тип
double, в противном случае требуется работа с типом extended.


Задача 3: Ква
драты цифр числа


Задача взята из классической книги Гуго Штейнгауза "Сто задач"
(М.: «Наука», 1976). В этой книге доказывается, что искомая величина
после нескольких начальных вычислений (не более 12) либо становится
равной единице, либо циклически выбир
ается из последовательности
(145, 42, 20, 4, 16, 37, 58, 89).

Но даже если не знать этого факта, достаточно заметить, что иск
о-
мая величина не превосходит 81*9 = 729 для любого начального
N
, и в
ы-
полнять
K

вычислений совершенно необязательно


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

В 50 % тестов для вычислений достаточно использовать тип integer
системы программирования Free Pascal, в противн
ом случае требуется
работа с типом
longint
.


Задача 4: «Жизнь»


Задача требует умения работать с двумерными массивами и, в ч
а-
стности, правильно обрабатывать соседние элементы матрицы. Алгоритм
такой обработки приведен в разборе задач за 2008/2009 год.

Пус
ть нам надо определить всех соседей элемента A[i, j]. Как и в
задаче «Сглаживание матриц», напишем фрагмент программы на Паск
а-
ле, реализующий это:

for di :=
-
1 to 1 do


for dj :=
-
1 to 1 do


if ((di<>0) or (dj<>0)) and


(i+di>0) and (i+di<=M) a
nd


(j+dj>0) and (j+dj<=N) then begin

{элемент
A
[
i
+
di
,
j
+
dj
] является соседом, обработать
его }


end;


48


Для того
,

чтобы отличать только что родившиеся клетки от
влия
ю
щих на умирание своих соседей, рекомендуется давать им време
н-
ные пометки. Временн
ую пометку клетки [
i
,
j
] можно заменить на пост
о-
я
н
ную после определения судьбы клетки [
i
+1,
j
+1].

2010/2011 учебный год

Задача 1: Пвереернуть строку!


Самая простая задача в наборе, именно поэтому за её решение можно
получить 50 баллов, а не 100, как за р
ешение других. Всё, что нужно
уметь для решения этой задачи


организовывать совместную работу с
двумя индексами.

Определяем два целочисленных индекса
i

и
j
. Изначально
i

=

A
,
j

=

B
.
Основной цикл обработки исходной строки
S

выглядит следующим о
б-
разом:

while i


Tmp := S[i];


S[i] := S[j];


S[j] := Tmp;


i := i+1;


j

:=
j
-
1;

end
;

Те участники, которые умеют работать лишь с типом
string

Free

Pascal
,
могут взять 50 % тестов.


Задача 2: Гири и весы


Для решения этой задачи также требуется умение од
новременно
работать с несколькими индексами, хотя такая работа должна быть орг
а-
низована более хитро…

Обозначим через
P

массив весов гирь из одного комплекта, отсо
р-
тированный по возрастанию. Будем подбирать такие индексы
i
,
j
,
k
, что
P
[
i
] +
P
[
k
] = 2

×

P
[
j
]
, и
i

<
j

<
k
.

Средний индекс
j
, очевидно, пробегает значения от 2 до
N
-
1. И
н-
декс
k

для каждого нового значения
j

изначально устанавливаем в
j
+1.
Меньший индекс
i

будет изменяться от 1 до
j
-
1, а вот больший индекс
для каждого нового значения
i

должен, в за
висимости от знака выраж
е-
ния
P
[
i
] +
P
[
k
]
-

2

×

P
[
j
], либо уменьшаться, либо увеличиваться (остав
а-
ясь, тем не менее, в интервале [
j
+1,
N
]). Такой подход обеспечивает тр
у-

49


доёмкость
O

(
N
2
) для определения ситуации, когда уравновесить весы
нельзя. Очевидно, по
ложительный ответ на вопрос задачи будет дости
г-
нут быстрее.



Задача 3: Электронная мишень


Казалось бы, для решения этой задачи требуется умение рассчит
ы-
вать расстояние от точки до начала координат и выполнение поиска в
упорядоченном массиве. Однако…

Дл
я прохождения всех тестов этой задачи требуется умение выпо
л-
нять ещё две вещи:



вместо расчёта расстояния от каждой точки попадания до центра
мишени оперировать с квадратом этой величины (возводя исходные р
а-
диусы в квадрат);



использовать дихотомию для опред
еления нужного кольца и, с
о-
ответственно, количества очков, засчитанных за выстрел.

Игнорирование хотя бы одного из этих требований может привести
к нарушению предела времени для теста.

В 60 % тестов достаточно использовать тип
longint

для вычисления
квадра
тов расстояний; остальные тесты требуют типа
int
64.


Задача 4: Числа
-

близнецы


Для определения того, является ли заданное число простым, могут
быть использованы два алгоритма:



деление этого числа на предыдущие найденные простые числа
(или, что хуже, на
все числа, меньшие заданного);



построение т.н. «решета Эратосфена».

Второй способ является более быстрым (доказано, что его труд
о-
ёмкость равна
O

(
N

log

log

N
), где
N



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

Более того, даже построение решета Эратосфена для заданного
N

приводит к нарушению лимита времени из
-
за больших
N

(применение
метода деления позволяет взять 20% тестов, построение решета


80 %).

Для того, чтобы прошли все тесты, необходимо

заметить, что п
о-
иск следует производить только в интервале от
M

до
N
, который не столь
велик. С другой стороны, для вычёркивания в решете Эратосфена эл
е-
ментов, не превосходящих
N
, используются простые числа, не превосх
о-
дящие
sqrt
(
N
)

, в ограничениях задач
и


не более 32000.


50


Следовательно, можно организовать два массива


решета. Первый
содержит 32000 элементов и служит для поиска простых чисел, испол
ь-
зуемых для работы со вторым массивом. Второй массив содержит
N
-
M
+1 элемент, и именно в нём ищутся числа
-
бли
знецы.

2011/2012 учебный год

Задача 1: Метрическое время


Для решения этой задачи необходимо воспользоваться типовым
приёмом: перевести время в заданной системе исчисления времени, в к
о-
личество минимальных единиц в этой же системе (секунд или микро
д-
ней).

Затем это количество требуется перевести в другую систему (у
м-
ножением или делением на 86400/100000), а потом восстановить резул
ь-
тат в более крупных единицах.

Первый подтест примера:

1 06:04:17

даёт 21857 секунд (6*3600 + 4*60 + 17), что соответствует 25
297.45 ми
к-
родням (21857*100000/86400).

Большое количество подтестов позволяет отсечь возможные неэ
ф-
фективные вычисления.


Задача 2: Проверка на нечётность


Задача, которая допускает множество подходов к её решению. А
в-
торы, естественно, стремились оценить

каждый из таких подходов.

Простейшее решение «в лоб» предполагает, что для каждого числа
из интервала
[
A
,
B
]

мы будем подсчитывать количество единиц, не обр
а-
щая внимания на результаты предыдущих расчётов.

Если для определения количества единиц используютс
я операции
получения остатка от деления на 2 и последующего деления на 2, такое
решение берёт 35
-
40 % тестов.

Можно предположить, что побитовые операции
shr

и
and

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

(
X

mod

2)=1

эквивалентна

(
X

and

1)=1,

а вычисление


51


X

:=
X

div

2

можно заменить оператором

X

:=
X

shr

1.

Использование побитовых операций позволяет взять от 50 до 60 %
тестов.

Для полного решения задачи необходимо придумать формулу для
функции
F
(
X
)


количества чисел, не превосходящих
X
, содержащих н
е-
чётное количество единиц в своём двоичном представлении. Тогда отв
е-
том на задачу будет величина
F
(
B
)


F
(
A
-
1
).

Величина
F
(
X
) для нечётных
X

равна (
X
+1)
div

2, это доказывается
по индукции.

При
X
=1
F
(
X
) также равно единице. Пусть формула верна для
X

=

2
k

1 и
F
(2
k

1) =
k
. Далее следуют два числа: 2
k

(чётное) и 2
k
+1 (нечё
т-
ное). Их двоичные представления отличаются только младшим битом,
так что одно из них содержит в этом представлении нечётное количеств
о
единиц. Таким образом,
F
(2
k
+1) =
k
+1, что и требовалось доказать.

Для чётных
X

нам необходимо оценить, содержит ли
X

нечётное
количество единиц. Если да, то
F
(
X
) =
F
(
X

1)+1; в противном случае
F
(
X
) =
F
(
X
-
1).

Наконец, авторы сочли возможным оценить и подх
од «половина
чисел, входящих в интервал». Явно это не прописано в условии, однако
последний пример показывает, что и такое может быть…


Такое реш
е-
ние оценивается в 10 баллов.



Задача 3: Химия, химия…


Задача требует умения работать с одномерными и двум
ерными
массивами и использовать эти массивы для хранения результатов вычи
с-
лений.

Определяем два булевских массива: один


двумерный, размерн
о-
стью 26
× 26,
и второй


одномерный из 26 элементов. Первый из этих
массивов предназначен для хранения информации о

химических элеме
н-
тах с двухсимвольным обозначением, второй


с односимвольным.

На Паскале, где допускается использование типа
char

в качестве
индексного, описание массива выглядит особенно красиво:

var


A: array [’A’..’Z’, ’a’..’z’] of boolean;


B: ar
ray [’A’..’Z’] of boolean;


52


Изначально значения элементов этих массивов устанавливаются в
false
. Затем, сканируя входную строку
S
, определяем, является ли тек
у-
щий символ с индексом
i

признаком односимвольного элемента или пе
р-
вым символом двухсимвольного. В
первом случае записываем

B
[
S
[
i
]] :=
true
;

во втором


A
[
S
[
i
],
S
[
i
+1]] :=
true
;

После анализа строки достаточно подсчитать количество элеме
н-
тов, равных true, в обоих массивах. Такое решение имеет трудоёмкость
O

(
N
), где
N



длина строки.

Участники, которые

не умеют использовать массивы таким обр
а-
зом, могут находить количество различных элементов строки общим а
л-
горитмом, имеющим трудоёмкость
O

(
N
2
), однако это решение, очеви
д-
но, не наберёт полного балла. Наконец, те, кто не умеет выделять одн
о-
символьные и дв
ухсимвольные химические элементы, могут попроб
о-
вать написать решение для 25 % тестов.


Задача 4: День пряника


Ещё одна

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

Для прямоугольных пряников критерий того, что они поместятся в
коробку, прост


диагональ пряника не должна превосходить диаметр
коробки. Однако для того, чтобы не потерять точность, имеет смысл ра
с-
считывать квадраты расстояний (которые будут целыми

числами):

ܣ


ܦ


ܤ


(
1
)

где
A
,
B



стороны прямоугольника,
D



диаметр коробки.

В случае треугольного угощения необходимо рассмотреть два сл
у-
чая. Если треугольник


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

6
).

В противном случае требуется, чтобы диаметр окружности, оп
и-
санной около треугольника, не превосходил диаметра коробки.
Пусть
P



диаметр описанной окружности:


53


ܲ
=
஺஻஼



Здесь
A
,
B
,
C



длины сторон треугольника,
S



его площадь.

Поскольку
P


D
, эту формулу можно преобразовать:

4
ܵ

ܦ


ܣ

ܤ

ܥ


Возведение в квадрат, как и ранее, позволяет избежать по
тери то
ч-
ности.

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

В 80 % тестов для выполнения вычислений достаточно использ
о-
вать тип
int
64. Для
получения полного
балла требуется ум
е-
ние либо ре
а
лизов
ы-
вать длинную ари
ф-
метику с операцией
умножения на целое
число, либо, как ук
а-
зала А.

И. Лапо, раб
о-
тать с типом
extended

(её решение также б
е-
рёт все тесты). В кач
е-
стве иллюстрации
приведём пример ре
а-
лизации длинной
арифметики из авто
р-
ского решения:

Описание
типа «длинное число»:

type


BigInt

=
record


Dig
:
array
[1..1000]
of

int
64;


// каждый элемент массива


одна десятичная цифра


Size
:
integer
;



// количество значащих цифр


end
;

Процедура

умножения
:

procedure Mul(var A:BigInt; B: int64);

var

Описанная о
к-
ружность

Угощение

Коробка

Рис
.

6.

Возможный вариант расположения тупоугол
ь-
ного треу
гольника


54



i:

integer;


C: int64;

begin


for i := 1 to A.Size do


A.Dig[i] := A.Dig[i]*B;


C := 0;


for i := 1 to A.Size do begin


A.Dig[i] := (A.Dig[i]+C);


C := A.Dig[i] div 10;


A.Dig[i] := A.Dig[i] mod 10;


end;


while C>0 do begin


A.Size := A
.Size+1;


A.Dig[A.Size] := C mod 10;


C := C div 10;


end;

end;

Несложное преобразование формул для расчёта позволяет обо
й-
тись без реализации сложения и вычитания. Так, вместо формулы (1)
можно использовать формулу

ܣ


(
ܦ

ܤ
)
×
(
ܦ
+
ܤ
)

Для других
случаев выводятся аналогичные формулы.

201
2
/201
3

учебный год

Задача 1: Построить римское число


Возможны не менее двух подходов к решению этой задачи.

Первый подход.

Заводим двумерный массив
Q

размерности
3999

×

7. Элемент
Q
[
i
,
j
] будет содержать количес
тво символов, соотве
т-
ствующих
j
-
й допустимой латинской букве в римской записи числа
i
.
Напомним, что допустимыми буквами являются ’
M
’, ’
D
’, ’
C
’, ’

’, ’
X
’,

V
’, ’
I
’.

Заполняем этот массив ещё до чтения входного файла. Это позв
о-
лит не выполнять многократно о
дну и ту же работу.

Для каждого прочитанного подтеста аналогичным образом запо
л-
няем одномерный массив
P

из 7 элементов. Затем в цикле от 3999 до 1
пытаемся найти такую строку с номером
i

в массиве
Q
, что для всех
j

Q
[
i
,

j
] =
P
[
j
]. Если такая строка найдена
, выводим соответствующее
i
, в
противном случае, по завершении цикла выводим ноль.


55


Второй подход.

После чтения очередного подтеста и заполнения
массива
P

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

F
:
array

[1..7]
of

integer

= (4, 1, 4, 1, 4, 1, 3);

Если
F
[
j
] >
P
[
j
] хотя бы для одного
j
, число построить нельзя. В
противном случае строим вначале римское представление
числа: в цикле
от 1 до 7 переносим
P
[
i
] букв в результирующую строку. Однако перед
переносом четвёртой такой буквы мы должны убедиться, что
P
[
i
+1] = 0,
а
P
[
i
+2] = 1. Если приведенное условие неверно, число построить нельзя,
иначе вначале переносим (
i
+2)
-
ю
букву, а затем


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


Задача 2: Две матрицы


Решение «в лоб», которое предполагает заполнение обеих матриц в
соответствии

с условиями задачи и последующее попарное сравнение
каждого элемента этих матриц, из
-
за ограничений по памяти работает
только для
M
,
N

≤ 1000
и берёт только 50 % тестов.

Следовательно, надо искать решение, которое позволило бы обо
й-
тись без явного построен
ия матриц.

Значение элементов матриц
A
ij

и

B
ij

вычисляется по формулам

ܣ
௜௝
=
ܰ
×
(
݅

1
)
+
݆
,



ܤ
௜௝
=
ܯ
×
(
݆

1
)
+
݅

Приравняв эти величины и выполнив несложные преобразования,
получим (предполагая, что
N


M
)

݅
=
1
+
ܯ

1
ܰ

1
×
(
݆

1
)

Левая часть равенст
ва


целая, поэтому найти нужное
j

можно
только, если дробь


тоже целая. Это достигается, когда она равна
D

=

НОД(
M

1,
N

1). Тогда мы получаем
D
+1 серию из различных пар (
i
,
j
).

Случай
M
=1 или
N
=1 следует рассмотреть отдельно.

Тесты подобраны таким образо
м, что попытка вывести ответ 2 для
любых входных данных наберёт только 10 баллов.




56



Задача 3: Резисторы


Прежде всего, построим модель ситуации.

Как известно, закон Ома может быть записан в виде формулы

ܷ
=
ܶ

×
ܴ


где нам известна лишь величина
тока
T
i
. Но поскольку напряжение од
и-
наково для получения информации о каждом из резисторов, можно сд
е-
лать вывод, что чем больше величина тока, тем меньше сопротивление
соответствующего резистора.

С другой стороны, суммарное сопротивление схемы из пяти пара
л-
лельно соединённых резисторов, рассчитывается по формуле

1
ܴ
=


1
ܴ






,
1

ݏ


ܰ

Отсюда видно, что чем меньшие сопротивления мы выбираем в
правой части формулы, тем меньшей будет величина
R
, и, следовательно,
тем большей будет сила

тока, протекающего по неразветвлённой части
цепи.

Рассмотрим обоснование этого на примере из условия задачи.

Пусть, напряжение, вырабатываемое источником, равно 10 (можно
взять, конечно же, любое другое значение). Тогда сопротивления име
ю-
щихся транзисторо
в составляют 10/3 (три резистора), 10/2 (один рез
и-
стор), 10/1 (шесть резисторов).

При применении резисторов с наименьшим сопротивлением пол
у-
чаем

1
ܴ
=
3
×
3
10
+

1
×

2
10
+

1

×

1
10
;


ܴ
=

10
12

При применении резисторов с наибольшим сопротивлением пол
у-
чаем

1
ܴ
=
5

×

1
10
;


ܴ
=

2

В первом случае ток, протекающий по неразветвлённой части ц
е-
пи, равен 12, во втором


5.

Таким образом, задача свелась к нахождению индексов пяти эл
е-
ментов массива с наибольшими значениями
T
i
. Однако большие допу
с-
тимые значен
ия для
N

вместе с жёсткими ограничениями на время и п
а-
мять не дают возможности отсортировать этот массив. Так сортировка
«пузырьком» набирает в авторском решении 50 баллов, использование
алгоритма
sort

из библиотеки
ST



76 баллов, и даже использование г
о-

57


раздо более быстрого алгоритма
nth
_
element

из этой же библиотеки не
набирает полный балл.

Для полного решения задачи можно либо воспользоваться сл
е-
дующим подходом: создаём двумерный массив
P

размерностью 5
× 2,
первый столбец которого содержит значения
T
i
,

а второй


индексы с
о-
ответствующих резисторов в исходном массиве. Считываем из входного
файла первые пять значений, заполняем массив
P
, сортируем его по уб
ы-
ванию
T
i
. Для каждого из последующих значений определяем, можно ли
его занести его в массив
P

с соб
людением упорядоченности, и в случае
положительного ответа заносим его в этот массив, «вытесняя» после
д-
нюю строку. После завершения ввода достаточно вывести второй сто
л-
бец массива
P
.

Такой алгоритм имеет трудоёмкость
O

(
N
), что достаточно для
полного реше
ния задачи при заданных ограничениях на время и память.

Можно также применить алгоритм
partial
_
sort

из библиотеки
ST
,
хотя авторское решение, основанное на его использовании, требует 0.45


0.47 секунды на больших тестах. Значит, любая небрежность в напис
а-
нии программы может быть чревата потерей баллов…


Задача 4: Юный чертёжник


Известно, что коэффициенты прямой
Ax

+
By

+
C

= 0, проходящей
через две точки (
x
1
,
y
1
) и (
x
2
,
y
2
), можно рассчитать по формулам

ܣ
=

ݕ


ݕ

ܤ
=
ݔ


ݔ

ܥ
=
ݔ

ݕ


ݔ

ݕ


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

3
x

+ 9
y



12 = 0

и



x


3y + 4 = 0

на самом деле совпадают. Для того, чтобы исключить двусмысленность,
во
-
первых, делим полученные коэффициенты на НОД
(
A
,
B
), и во
-
вторых,
изменением знака всех коэффициентов добиваемся того, что
A

> 0 или
(
A

=

0 и
B

> 0
)
.

Пусть описанным выше образом получены коэффициенты
A
1
,
B
1
,
C
1
,
A
2
,
B
2
,
C
2

для каждой из двух прямых. Тогда



если
A
1

=
A
2
,
B
1

=
B
2
,
C
1

=
C
2
, то прямые с
овпадают;



если
A
1

=
A
2
,
B
1

=
B
2
,
C
1



C
2
, то прямые параллельны;



в противном случае прямые пересекаются.


58


Содержание

ПРЕДИСЛОВИЕ

................................
................................
................................
........................

3

УСЛОВИЯ ЗА
ДАЧ

................................
................................
................................
....................

5

2005/2006 учебный год

................................
................................
................................
............................

5

2006/2007 учебный год

................................
................................
................................
............................

8

2007/2008 учебный г
од

................................
................................
................................
..........................

12

2008/2009 учебный год

................................
................................
................................
..........................

15

2009/2010 учебный год

................................
................................
................................
..........................

19

2010/2011 учебный

год

................................
................................
................................
..........................

24

2011/2012 учебный год

................................
................................
................................
..........................

28

2012/2013 учебный год

................................
................................
................................
..........................

32

РАЗБОР ЗАДАЧ

................................
................................
................................
......................

36

2005/2006 учебный год

................................
................................
................................
..........................

36

2006/2007 учебный год

................................
................................
................................
..........................

38

2007/2008 учебный год

................................
................................
................................
..........................

41

2008/2009 учебный год

................................
................................
................................
..........................

44

2009/2010 учебный год

................................
................................
................................
..........................

46

2010/2011 учебный го
д

................................
................................
................................
..........................

48

2011/2012 учебный год

................................
................................
................................
.........................

50

2012/2013 учебный год

................................
................................
................................
.........................

54



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

  • pdf 24069828
    Размер файла: 1 MB Загрузок: 0

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