СБОРНИК ЗАДАЧ И РЕШЕНИЙ Всеукраинских ученических олимпиад С информатики 2013-2014


СБОРНИК ЗАДАЧ И РЕШЕНИЙ III этапа Всеукраинских ученических олимпиад

С информатики

2013-2014 УЧЕБНОГО ГОДА

Составители:

Баранова А.Е., методист отдела информатики, информационных технологий и дистанционного обучения Черниговского областного института последипломного педагогического образования имени К.Д. Ушинского

Литош Ю.Н., заведующий отделом информатики, информационных технологий и дистанционного обучения Черниговского областного института последипломного педагогического образования имени К.Д. Ушинского

Зуб В.В., директор Прилуцкого общеобразовательной школы I-III ступеней № 7 Прилуцкого городского совета, учитель-методист

Бондаренко С.Н., учитель математики и информатики Прилуцкого общеобразовательной школы I-III ступеней № 7 Прилуцкого городского совета, учитель-методист

Смирнова О.М., методист отдела информатики, информационных технологий и дистанционного обучения Черниговского областного института последипломного педагогического образования имени К.Д. Ушинского

рецензенты:

Горошко Ю.В., заведующий кафедрой информатики и вычислительной техники Черниговского национального педагогического университета имени Т.Г. Шевченко, доктор педагогических наук

Покрошенного Д.А., заведующий кафедрой информатики и информационно-коммуникационных технологий в образовании Черниговского областного института последипломного педагогического образования имени К.Д. Ушинского, кандидат педагогических наук, доцент

Рекомендовано к печати

ученым советом Черниговского областного института последипломного педагогического образования имени К.Д. Ушинского (протокол №6 от 17.09.2015р.)

 

СОДЕРЖАНИЕ

 

 

 

И тур

Задача A — Кондиционер Степана …………………………

 

4

Задача B — «Поле чудес» …………………………………… 8
Задача C. — Winter …………………………. ……………….. 18
Задача D — Хорошие числа ……… …….. ………………………. 27
Задача E — упражнения Степана …………………………… …… 36
II тур

Задача A — «Все, Степан! Ты меня достал!»……………… ..

 

46

Задача B — Степан — бизнесмен …………………………….. 48
Задача C — Transit …………………………………………… 51
Задача E — Видео-кафе Ужляндии …………………………… 54

8-11 класс

И тур

A — Кондиционер Степана

Input file name: cond.in
Output file name: cond.out
Time limit: 100 ms
Memory limit: 256 M

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

Кондиционер может работать в следующих четырех режимах:

— «Freeze» — охлаждение.В этом режиме кондиционер может только уменьшать температуру. Если температура в комнате и так не более желанной, то он выключается.

— «Heat» — нагрев.В этом режиме кондиционер может только увеличивать температуру. Если температура в комнате и так не менее желанной, то он выключается.

— «Auto» — автоматический режим.В этом режиме кондиционер может как увеличивать, так и уменьшать температуру в комнате до желаемой.

— «Fan» — вентиляция.В этом режиме кондиционер осуществляет только вентиляцию воздуха и не изменяет температуру в комнате.

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

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

Входные данные: Первая строка входного файла содержит два целых числа t room, и t cond, разделенных ровно одним пробелом (-50 ≤ t room 50, -50 ≤ t cond 50).Вторая строка содержит одно слово, записанное строчными буквами латинского алфавита — режим работы кондиционера.

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

Пояснения к примеров:

В первом примере кондиционер находится в режиме нагрева. Через час он нагреет комнату до желаемой температуры 20 градусов.

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

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

cond.in cond.out
20 октября

heat

20
20 октября

freeze

10

 

Идея решении задачи Таишева Фердинанда, ученика 11 класса Радянськослобидськои ООШ I-III ст. Черниговского района (Трейтяк А.В., учитель информатики высшей категории)

Программа на языке Pascal. Использовался компилятор FreePascal. Программа моделирует работу кондиционера.

Решение: var a, b: integer; var c: string;

var t1, t2: text; begin

assign (t1, «cond.in ‘);

assign (t2, ‘cond.out’); reset (t1) rewrite (t2); read (t1, a)

readln (t1, b)

read (t1, c)

if (c = ‘freeze’) and (b <a) then writeln (t2, b) if (c = ‘freeze’) and (b> a) then writeln (t2, a) if (c = ‘heat’) and (b> a) then writeln (t2, b) if (c = ‘heat’) and (b <a) then writeln (t2, a) if (c = ‘fan’) then writeln (t2, a)

if (c = ‘auto’) then writeln (t2, b) close (t1)

close (t2); end.

Программа неправильно выполняет 3 и 8 тесты. Результат — 80 баллов из 100.

 

 

 

 

 

 

 

 

решение:

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

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

В режиме «freeze» кондиционер реализует функцию min ( , ), В режим «heat» — функцию, в режиме «auto» — функцию (возвращает

второй аргумент), а в режиме «fan» — функцию

(возвращает первый аргумент).

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

идею:

var t1, t2: integer; s: string;

begin assign (input, «cond.in ‘); reset (input) readln (t1, t2) readln (s)

assign (output, «cond.out ‘); rewrite (output) ifs = ‘fan’thenwriteln (t1) ifs = ‘auto’thenwriteln (t2); ifs = ‘freeze’then

if t1> t2 thenwriteln (t2) elsewriteln (t1) ifs = ‘heat’then

if t1 <t2 thenwriteln (t2) elsewriteln (t1) end.

 

Идея решении задачи Зуба В.В., директора ООШ I-III ст. № 7 г.. Полян, учителя математики, учителя- методиста; Бондаренко С.М., учителя математики и информатики ООШ I-III ст. № 7 г.. Полян, учителя- методиста

Алгоритм на умение применять разветвления.

решение:

var troom, tcond, t: integer; reg: string; f: text; Begin

Assign (f, ‘cond.in’); Reset (f); Read (f, troom) ReadLN (f, tcond) Readln (f, reg)

Close (f)

If reg = ‘freeze «Then {режим охлаждения до желаемой температуры}

If troom <= tcond Then t = troom Else t = tcond;

If reg = ‘heat «Then {режим нагрева до желаемой температуры} If troom> = tcond Then t = troom Else t = tcond;

If reg = ‘auto’ Then t = tcond; {Автоматическая смена температуры до желаемой}

If reg = ‘fan’ Then t = troom; {Режим вентиляции, температуры не меняется} Assign (f, ‘cond.out’); Rewrite (f) WriteLN (f, t) Close (f)

End.

 

 

B — «Поле чудес»

Input file name: wonderland.in
Output file name: wonderland.out
Time limit: 100 ms
Memory limit: 256 M

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

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

Конечно, Степан желает выиграть игру и набрать как можно больше баллов. Если набранная сумма положительная, то Степан выиграл, иначе проиграл.

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

Входные данные: Первая строка входного файла содержит два целых числа N, M (1 ≤ N ≤ 100, 1 ≤ M ≤ 100) — размеры игрового поля.

Следующие N строк содержат по М целых чисел — значения ячеек игрового поля, по модулю не больше 1000.

Выходные данные: Первая строка выходного файла должна содержать одно слово — winner, если Степан выиграл игру, или loser — в другом случае.

Вторую строчку должна содержать одно число — набранную сумму.

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

wonderland.in wonderland.out
3 февраля

1 февраля 1

-1 2 января

winner 6
3 февраля

1 -2 -1

-2 1 -2

loser 0

 

 

 

 

 

 

 

решение:

Идея решении задачи Хрол Н.П., учителя информатики общеобразовательной специализированной школы I-III ст. физико-математического профиля № 12 г..Чернигова, старшего учителя

Эта задача является классической задачей с использованием метода динамического программирования. Рассмотреть все возможные маршруты почти нереально.

Представим поле для игры в виде таблицы NxM (в программе — массив Х), в каждую клеточку которой запишем количество баллов в соответствующем квадратике игрового поля. По условию задачи Степан хочет набрать максимальное количество баллов. Очевидно, что для этого он должен выбирать клетку с максимальной

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

Будем искать лучшие пути с верхней левой клетки в другие. Для этого создадим таблицу «максимальных сумм» (в программе — массив Y).

Не следует забывать и о предельные значения. Поскольку для всех ячеек таблицы Y, кроме верхней строки и левого столбца, существует три пути, то нужно выполнить отдельные вычисления суммы для верхней и левой границы. Это легко сделать, поскольку для этих клеток существует только один маршрут. Например, для верхней строки таков:

Для первого примера: для второго примера:

Для других ячеек таблицы в ячейку (i, j) мы можем попасть только из соседних ячеек: слева (i, j-1), сверху (i-1, j) и по диагонали (i-1, j-1). Приоритет предоставим клетке с наибольшим количеством баллов. Итак, двигаясь по строкам (или столбцам), будем заполнять Y, используя формулу:

Y [i, j] = X [i, j] + max (max (Y [i, j-1], Y [i-1, j]), Y [i-1, j-1]), где max

— функция, определяющая большее из двух значений.

Для первого примера: Таблица X

2 1 1
-1 2 1

Таблица Y

2 3 4
1 5 6

 

Для второго примера: Таблица X

1 -2 -1
-2 1 -2

Таблица Y

1 -1 -2
-1 2

Проверяем, если значение Y [N, M] положительное, то выводим слово — winner, или loser — в противном случае, а также выводим именно значение ячейки Y [N, M].

решение:

const size = 100;

var X, Y: array [1..size, 1..size] of int64; i, j, n, m: integer;

procedure read_data; begin

assign (input, «wonderland.in ‘); reset (input)

readln (n, m) for i: = 1 to n do

for j = 1 to m do read (X [i, j]); close (input)

end;

function max (a, b: int64): int64; begin

if a> b then max = a

else max = b;

end;

procedure max_sum; begin

Y [1,1]: = X [1,1];

for i: = 2 to n do

 

Y [1, i]: = X [1, i] + Y [1, i-1];

for i: = 2 to m do Y [i, 1] = X [i, 1] + Y [i-1,1];

for i: = 2 to n do for j = 2 to m do

Y [i, j] = X [i, j] + max (max (Y [i, j-1], Y [i-1, j]), Y [i-1, j-1])

end;

procedure write_sol; begin

assign (output, «wonderland.out ‘); rewrite (output)

if Y [n, m]> 0 then writeln ( ‘winner «)

else writeln ( ‘loser’); writeln (Y [n, m])

close (output) end;

begin

read_data; max_sum; write_sol;

end.

Программа неправильно выполняет 3 и 12 тесты. Результат — 90 тестов из 100.

 

 

 

 

 

 

 

 

решение:

#include <cstdio>

Идея решении задачи Дасюк Антона, ученика 10 класса специализированной общеобразовательной школы № 2 I-III ст. с углубленным изучением иностранных языков г.. Чернигова (Коваленко А.И., учитель-методист, учитель информатики СЗНЗ

№ 2 г.. Чернигов)

#include <iostream>

#include <algorithm>

#include <vector> using namespace std; const int N = 101;

int main () {freopen ( «input.txt», «r», stdin);

freopen ( «output.txt», «w», stdout)

int a, b, i, j, k = 0, m, n, x [N] [N], y [N] [N] = {};

for (i = 1; i <N; ++ i) y [0] [i] = y [i] [0] = -1000000000;

scanf ( «% d% d», & n, & m) for (i = 1; i <= n; ++ i)

for (j = 1; j <= m; ++ j)

{

scanf ( «% d», & x [i] [j]);

y [i] [j] = x [i] [j] + max (y [i-1] [j-1], max (y [i-1] [j], y [i] [j-1 ]));

}

if (y [n] [m]> 0) printf ( «winner \ n»);

else

printf ( «loser \ n»); printf ( «% d \ n», y [n] [m]) return 0;

}

 

 

 

 

 

 

 

решение:

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

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

Будем в программе использовать две двумерные матрицы — одну для хранения данных из условия задачи, а другую для хранения результатов решения подзадач на каждом из шагов. Так как по условию задачи число не будут больше 1000, то можно было бы для первой матрицы использовать тип integer. При хранении результатов выполнения подзадач иметь в виду, что указанное направление движения дает возможность побывать в лучшем случае в 200 полях, а значит максимальное значение будет в пределах типа LongInt.

Понятно, что ячейка b [1,1] будет иметь то же значение, что и a [1,1]. Двигаясь по квадратам первой строки и первого столбца, легко заметить, что текущая сумма зависит празднования предыдущей ячейки и значение числа в данном квадрате. Во всех других случаях, находя сумму чисел пройденных квадратиков, следует найти три числа b [i-1, j-1] + a [i, j] (осуществляется движение по диагонали), b [i-1, j] + a [ i, j] (движение вниз) и b [i, j-1] + a [i, j] (движение справа), и выбрать максимальное с них.

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

идею:

var n, m, i, j: integer;

a: array [1..100,1..100] of integer; b: array [1..100,1..100] of longint; function max (x, y, z: longint): longint;

// функция нахождения максимального среди 3-х чисел begin

max = x;

if max <y then max = y; if max <z then max = z; end;

procedure readdata;

// процедура считывания информации из файла begin

assign (input, «wonderland.in ‘); reset (input)

readln (n, m) for i: = 1 to n do

for j = 1 to m do read (a [i, j]); close (input)

end; procedure run;

// процедура решения подзадач методом динамического программирования

begin b [1,1]: = a [1,1];

for i: = 2 to m do b [1, i] = b [1, i-1] + a [1, i];

for j = 2 to n do b [j, 1] = b [j-1,1] + a [j, 1]; for i: = 2 to n do

for j = 2 to m do b [i, j] = max (b [i-1, j-1] + a [i, j], b [i-1, j] + a [i, j ], b [i, j- 1] + a [i, j]);

end;

procedure writedata;

// процедура записи ответа в файл begin

assign (output, «wonderland.out ‘); rewrite (output)

if b [n, m]> 0 then writeln ( ‘winner’) else writeln ( ‘loser’); writeln (b [n, m])

close (output) end;

begin

// обнуление значений элементов массива, в котором будут храниться

// результаты решения подзадач fillchar (b, sizeof (b), 0);

readdata; run; writedata; end.

 

Идея решении задачи Зуба В.В., директора ООШ I-III ст. № 7 г.. Полян, учителя математики, учителя- методиста; Бондаренко С.М., учителя математики и информатики, ООШ I-III ст. № 7 г.. Полян, учителя- методиста

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

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

В ячейку (2, 2) можно попасть с трех ячеек (1, 1), (1, 2) и (2, 1).выбирать нужно

ячейку с наибольшим количеством баллов. Очевидно, что это ячейка (1, 2).

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

 

var i, j, m, n, x, y: integer; s: int64; a: array [1..100,1..100] of int64; f: text;

Begin Assign (f, ‘wonderland.in’); Reset (f); Read (f, n) Read (f, m)

For i: = 1 to n do For j = 1 to m do Read (f, a [i, j]) {зачитывания данных}

Close (f) s: = 0;

For j = 1 to m do Begin s = s + a [1, j]; a [1, j]: = s; End; {Формирования сумм для первой строки таблицы}

s: = 0;

For i: = 1 to n do Begin s = s + a [i, 1]; a [i, 1] = s; End; {Формирования сумм для первого столбца}

If (i> 1) and (j> 1) then

For i = 2 to n do {рассмотрение остальных ячеек таблицы} Begin

For j = 2 to m do Begin

x = i-1; y = j-1;

If a [x, y] <a [i, j-1] Then x = i {определения оптимального пути …}

If a [x, y] <a [i-1, j] Then Begin y = j; x = i-1; End {… для данной ячейки}

a [i, j] = a [i, j] + a [x, y]; {Запись наибольшей суммы для данной ячейки}

End;

End;

Assign (f, ‘wonderland.out’); Rewrite (f);

If a [n, m]> 0 Then WriteLn (f, ‘winner «, a [n, m]) Else WriteLn (f,’ loser», a [n, m])

Close (f) End.

 

C. — Winter

Input file name: winter.in
Output file name: winter.out
Time limit: 500 ms
Memory limit: 256 M

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

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

Входные данные: В первой строке записано два числа N и M (1 ≤ N ≤ 100000,0 ≤ M ≤ 200000) — количество городов в Ужляндии и количество не заблокированных дорог соответственно.В следующих M строках записано по два числа i и j (1 ≤ i, j ≤ N), что значит дорога между городами с номерами i и j не заблокирован.Города Ужляндии нумеруются в 1 до N.

Выходные данные: В единственной строке выведите минимальное количество приземлений вертолета.

Пояснения к примеру:

Города 1, 2 и 3 соединены между собой, а потому чтобы обеспечить их обогревателями, необходимо осуществить одно приземления в одном из этих городов, дальше обогреватели доставят грузовиками. Города 4 и 5 связаны между собой, поэтому надо еще одно приземление. И наконец город 6, которое изолировано от других, чтобы доставить обогреватели в этот город, надо отдельное приземления вертолета. Всего получается 3 приземления.

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

winter.in winter.out
4 июня

1 марта

1 февраля

4 мая

3 февраля

3

 

 

 

 

 

 

 

 

решение:

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

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

Сформулируем математическую модель данной задачи. Дано неориентированный граф с N вершинами и М ребрами, которые заданы списком. Подсчитать количество компонент связности.

Подсчитать количество компонент связности в неориентированном графе, состоящий из N вершин и M ребер, можно с помощью алгоритма поиска в глубину. Поскольку количество вершин N≤ 100000, то использовать рекурсивный алгоритм нельзя. Заметим, что применить матрицу смежности также не удастся из установлено ограничение на используемую память и большое количество вершин. Поэтому придется пользоваться списком смежности. Он является структурой данных, для каждой вершины графа сохраняет список смежных с ней вершин. Список является массивом указателей, i-й элемент которого содержит указатель на список вершин, смежных с i-й вершиной.

При создании таких списков считается, что граф является ориентированным, поэтому задействуем процедуру добавления ребер Add дважды: для и .Массив used приобретает значение true, если в вершине уже были, и false — если в ней еще не были.

Сложность такого алгоритма O (N + M). Полученный результат удовлетворяет условию оптимальности, а потому будет ответом на задачу.

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

идею:

 

Var n, m, u, v, kil, i: LongInt;

used: array [1..100000] of boolean; head: array [1..100000] of LongInt;

// индексы начал списков

next: array [1..400002] of LongInt;

// индексы следующих элементов списков value: array [1..400002] of LongInt;

// значения элементов списков free_pos: LongInt;

// следующая свободная позиция, сначала установить 1.

 

Procedure Add (v, u: LongInt)

// процедура добавления ребра (v-> u) в список смежности begin

next [free_pos] = head [v];

// в свободную ячейку следующим элементом делаем начало списка вершины V

value [free_pos] = u;

// в эту ячейку записываем информацию о ребро (конец ребра) head [v] = free_pos;

// устанавливаем новое начало списка вершин V Inc (free_pos)

// увеличиваем значение свободной позиции. end;

procedure Dfs (v: LongInt)

// поиск вглубь начиная с вершины v-> Var u, i: LongInt;

// вспомогательные переменные, где i — индекс в списках, u — конец ребра begin

used [v]: = true; i = head [v];

// устанавливаем на начало списка while i <> 0 do

// пока не покажет на конец списка begin

 

 

 

 

 

end;

 

 

end;

u = value [i];

if (not used [u]) then Dfs (u)

i = next [i];

procedure initial;

// инициализация массивов begin

fillchar (used, sizeof (used), false); fillchar (head, sizeof (head), 0);

fillchar (next, sizeof (next), 0); fillchar (value, sizeof (value), 0); end;

procedure run;

// процедура нахождения компонент связности поиском вглубь Begin

// считывания предельных значений вершин и ребер assign (input, «winter.in ‘);

reset (input) readln (n, m)

// установка указателя на первый элемент списка смежности free_pos: = 1;

// обнуление количества компонент связности kil: = 0;

for i: = 1 to m do begin

// считывание нового ребра readln (u, v)

// добавление ребер в списки смежности Add (u, v)

Add (v, u) end;

for i: = 1 to n do begin

// если вершина не пройдена — задействовать поиск вглубь if (not used [i]) then

begin

// добавить количеству компонент 1 Inc (kil)

Dfs (i) end end;

close (input) end;

procedure writedata;

// запись результата в файл begin

assign (output, «winter.out ‘); rewrite (output) writeln (kil)

close (output) end;

begin initial; run; writedata; end.

 

 

 

 

 

 

 

 

решение:

#include <iostream>

#include <vector>

using namespace std; int n, count = 0;

Идея решении задачи Дасюк Антона, ученика 10 класса специализированной общеобразовательной школы № 2 I-III ст. с углубленным изучением иностранных языков г.. Чернигова (Коваленко А.И., учитель-методист, учитель информатики СЗНЗ

№ 2 г.. Чернигов)

vector <vector <int >> Graph; vector <bool> a;

void dfs (int v)

{

a [v] = 1;

for (int i = 0; i <Graph [v] .size (); i ++)

{

int to = Graph [v] [i];

if (!a [to]) dfs (to)

}

}

int main ()

{

int m;

cin >> n >> m;

Graph.assign (n + 1, vector <int> ()); a.assign (n + 1, 0);

for (int i = 0; i <n; i ++) a [i] = 0;

for (int i = 0; i <m; i ++)

{

int x, y;

cin >> x >> y;

Graph [x-1] .push_back (y-1);

Graph [y-1] .push_back (x-1);

}

for (int i = 0; i <n; i ++) if (!a [i])

{

count ++; dfs (i)

}

cout << count << endl; return 0;

}

Идея решении задачи Зуба В.В., директора ООШ I-III ст. № 7 г.. Полян, учителя математики, учителя- методиста; Бондаренко С.М., учителя математики и информатики ООШ I-III ст. № 7 г.. Полян, учителя- методиста

 

4 июня

5

Для решения задачи использован поиск количества островов несвязного графа. Островами будем называть группы городов, которые не связаны дорогами с другим городами. Для данных задачи можно создать следующие три острова: {1,2,3}, {4, 5}, {6}.

решение:

var i, j, m, n, x, y, z, k, l: longint; s: int64; a: array [1..100000] of longint; f: text;

Begin Assign (f, ‘winter.in’); Reset (f);

s: = 1; z = 0; FillChar (a, SizeOf (a), 0);

Read (f, n) Read (f, m) For i: = 1 to m do Begin

Read (f, x) Read (f, y)

If (a [x] = 0) and (a [y] = 0) {если города не принадлежат ни одному острову}

Then Begin a [x] = s; a [y] = s; s = s + 1, End {то создаем номер нового острова}

Else {если хотя бы один город принадлежит каком-нибудь острову}

Begin

If (a [x]> 0) and (a [y]> 0) Then {если оба города относятся к каким-то островов}

Begin {если города принадлежат к разным островов, то города с большим номером острова «переносятся» на остров с меньшим номером}

If a [x]> a [y]

Then Begin k = a [y]; l = a [x]; z = z + 1; End; If a [x] <a [y]

Then Begin k = a [x]; l = a [y]; z = z + 1; End; If a [x] <> a [y]

Then For j = 1 to n do If a [j] = l Then a [j] = k; End;

If (a [x]> 0) and (a [y] = 0) Then a [y] = a [x]; {Если один из городов не принадлежит острову}

If (a [y]> 0) and (a [x] = 0) Then a [x] = a [y]; End;

End;

Close (f)

s = s-1-z; {Формула определения количества найденных островов с несколькими городами}

For i: = 1 to n do If a [i] = 0 Then s = s + 1, {Если есть города-острова, то их также учитываем} Assign (f, ‘winter.out’); Rewrite (f) WriteLN (f, s); Close (f)

End.

На сервере программа правильно выполняет 20 тестов, 21-25 — ограничение по времени.Результат проверки на локальном компьютере 80 из 100.

D — Хорошие числа

Input file name: beautiful.in
Output file name: beautiful.out
Time limit: 1000 ms
Memory limit: 256 M

Школа № 1331 в Ужляндии известна очень высоким уровнем знаний своих учеников по математике, так как большинство учеников посещают факультативные занятия известного учителя Антона

Андреевича.

Сегодня Антон Андреевич рассказал своим ученикам о числах, которые, по его мнению, могут обладать рядом интересных свойств. Он назвал такие числа красивыми. Число называется хорошим, если не существует такого целого числа, большего единицы, на квадрат которого оно бы делилось без остатка.  Например, число 12 не является

хорошим, потому что оно делится на 4, то есть на квадрат числа 2. Числа 13 и 14 являются хорошими числами.

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

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

Входные данные: Первая строка входного файла содержит число N (1 ≤ N ≤ 100) — количество чисел, учитель написал на доске для Марыси.вторую строчку

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

Выходные данные: Если число является хорошим, выведите единственную строку, состоящую из слова Beautiful.Иначе, выведите какое-нибудь число, отличное от единицы, на квадрат которого делится произведение N чисел.

Пояснения к примеров:

Первый пример: 5 * 6 * 7 = 210. Не существует числа, большего единицы, на квадрат которого 210 делилось бы без остатка, поэтому 210 — хорошее число.

Второй пример: 35 * 12 = 420. 420 делится на 4, то есть на квадрат числа 2.

оценивание:

A 1 * A 2 * …* A N ≤ 10 Июнь — не менее 20 баллов A 1 * A 2 * …* A N ≤ 10 декабря — не менее 40 баллов Для всех и: A i ≤ 10 декабря — не менее 60 баллов Примеры входных и выходных данных:

beautiful.in beautiful.out
3

5 6 7

Beautiful
2

35 12

2

 

Идея решении задачи Хрол Н.П., учителя информатики общеобразовательной специализированной школы I-III ст. физико-математического профиля № 12 м.Чернигова, старшего учителя

Идея решения:

Если произведение чисел делится на квадрат целого числа (например k), то возможны два случая:

1. Число k является делителем не менее двух чисел из этого произведения.

2. Квадрат числа k является делителем одного из цифр произведения.

В первом случае будем искать НОД всех попарно чисел массива А.

Во втором случае будем искать квадрат числа, является делителем одного из чисел.

решение:

var A: array [1..100] of comp; n, i, j: integer;

k: int64;

function nsd (x, y: comp): comp; begin

repeat

if x> y then begin

x = trunc (x-trunc (x / y) * y) end

else begin

y = trunc (y-trunc (y / x) * x) end;

until (x = 0) or (y = 0); nsd = x + y;

end; begin

assign (input, «beautiful.in ‘); assign (output, «beautiful.out ‘); reset (input)

rewrite (output) readln (n);

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

for i: = 1 to n-1 do for j = i + 1 to n do

if trunc (nsd (A [i], A [j])) <> 1 then begin

write (trunc (nsd (A [i], A [j]))) close (input)

close (output)

 

 

for i: = 1 to n do begin

k = trunc (sqrt (A [i]));

exit end;

 

if A [i]> 1000000000000 then

while k> trunc (sqrt (A [i])) — 1000 do begin

if (trunc (A [i] -trunc (A [i] / sqr (k)) * sqr (k)) = 0) then begin

write (k) close (input) close (output) exit

end;

k = k-1;

end

 

while k> 1 do begin

 

else

if (trunc (A [i] -trunc (A [i] / sqr (k)) * sqr (k)) = 0) then begin

write (k) close (input) close (output) exit

end;

k = k-1;

end end;

writeln ( ‘Beautiful’); close (input) close (output)

end.

Идея решении задачи Дасюк Антона, ученика 10 класса специализированной общеобразовательной школы № 2 I-III ст. с углубленным изучением иностранных языков г.. Чернигова (Коваленко А.И., учитель-методист, учитель информатики СЗНЗ

№ 2 г.. Чернигов)

Рассмотрим случаи, когда произведение N заданных чисел ( ) Делиться без остатка на квадрат целого числа, больше единицы:

1) если   ( , НОД — наибольший общий делитель двух чисел (Алгоритм Евклида нахождения НОД)).То есть и делятся без остатка, тогда делиться на без остатка. Итак, является ответом на задачу.

2) если — точный квадрат, тогда — ответ.

3) если , тогда    — ответ на задачу. Чтобы найти такое , Достаточно перебрать все делители числа к кубического корня из этого числа

() И проверить следующие условия:

a) если , то — ответ; б) если — точный квадрат, то — ответ.

Если ни одно из условий не выполняется, нужно вывести «Beautiful».

решение:

#include <cstdio>

#include <iostream>

#include <algorithm>

#include <cmath>

 

using namespace std;

int main ()

{

freopen ( «input.txt», «r», stdin);

freopen ( «output.txt», «w», stdout) long long a, b, r = 1, z [100];

int i, j, n; cin >> n;

for (i = 0; i <n; ++ i) cin >> z [i];

for (i = 0; i <n — 1; ++ i) // Если НОД (z [i], z [j])> 1 for (j = i + 1; j <n; ++ j)

{

a = z [i], b = z [j]; while (b> 0)

{

a% = b; swap (a, b)

}

if (a> 1)

{

cout << a << endl; return 0;

}

}

for (i = 0; i <n; ++ i)

{

b = (long long) sqrt ((long double) z [i]); // Если z [i] — повнийквадрат

if (b * b == z [i] && b> 1)

{

cout << b << endl; return 0;

}

for (a = 2; a * a * a <= z [i]; ++ a)

if (z [i]% a == 0) // Если z [i] делится на а * а if (z [i]% (a * a) == 0)

{

 

 

else

cout << a << endl; return 0;

}

{// Если z [i] / а — полный квадрат

b = (long long) sqrt ((long double) (z [i] / a)); if (a * b * b == z [i] && b> 1)

{

cout << b << endl; return 0;

}

}

}

cout << «Beautiful \ n»; return 0;

}

 

Идея решении задачи Зуба В.В., директора ООШ I-III ст. № 7 г.. Полян, учителя математики, учителя- методиста; Бондаренко С.М., учителя математики и информатики, учителя- методиста ООШ I-III ст. № 7 г.. полян

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

Разобьем алгоритм на три части.

1. Рассматриваем все возможные пары данных чисел. Если НОД какой пары не равен 1, то произведение точно

делится на квадрат найденного числа. Надо вывести найденное число.

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

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

4. В случае несрабатывания пункта 3 остается констатировать «гарнисть» числа.

var i, y: longint; j, n, x, z: int64; a: array [1..100] of int64; f: text; ok: boolean;

Function GCD (a, b: int64): int64; {рекурсивная функция нахождения НОД двух чисел}

Begin

If b = 0 Then GCD = a Else GCD = GCD (b, a mod b) end;

Begin Assign (f, ‘beautiful.in’); Reset (f); Read (f, n)

For i: = 1 to n do Read (f, a [i]); Close (f)

{1}

x = 1;

For i: = 1 to n-1 do Begin

y = i + 1;

While (y <= n) and (x = 1) do Begin

If GCD (a [i], a [y])> x Then x = GCD (a [i], a [y]) y = y + 1;

End;

If x> 1 Then Break; End;

{2}

If x = 1 Then Begin

For i: = 1 to n do Begin j = Trunc (sqrt (a [i]));

If Sqr (j) = a [i] Then x = j; If x> 1 Then Break;

End;

End;

{3}

If x = 1 Then Begin

y: = 1;

While (y <= n) and (x = 1) do Begin

z = 1;

While (sqr (Trunc (sqrt (a [y]))) <> a [y]) and (y <= n) do Begin

If z <= 2 Then z = z + 1

Else Begin z = z + 2; If z mod 3 = 0 Then z = z + 2; End; If a [y] mod z = 0 Then a [y] = a [y] div z;

End;

If sqr (Trunc (sqrt (a [y]))) = a [y] Then x = Trunc (sqrt (a [y])); If x> 1 Then Break;

y = y + 1;

End;

End;

{4}

Assign (f, ‘beautiful.out’); Rewrite (f);

If x> 1 then WriteLN (f, x) else WriteLN (f, ‘Beautiful’); Close (f)

End.

E — упражнения Степана

Input file name: exercises.in
Output file name: exercises.out
Time limit: 1000 ms
Memory limit: 128 M

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

Придумать упражнения для тренировок оказалось непросто. Поэтому Степан решил поискать идеи в Интернете. Он нашел сайт, на котором предлагалось несколько серий тренировочных упражнений. Каждая серия тренировок по плану занимает N дней.В каждый из этих N дней предлагается делать одну «упражнение дня», а также к нему прилагаются рекомендации по выполнению в виде «A i — B i».Это означает, что для повышения уровня силы нужно выполнять упражнение от A i в B i раз.Если выполнять упражнение менее A i, или более чем B i раз, то это принесет скорее вред, чем пользу.Степан не хочет причинять себе вреда, поэтому будет делать от A i в B i раз, или вовсе не делать это упражнение.

Почитав все описания упражнений, Степан понял, что этот курс не рассчитан на новичков, но решил не сдаваться и адаптировать курс упражнений под себя. Он знает, что при изучении i -й упражнения ему придется потерять K i уровней силы, зато за выполнение упражнения X раз его уровень силы возрастет на F i * X. Степан не может изучить и выполнить упражнение, если его текущий уровень силы меньше K i.В дни, когда Степану не хватает сил или времени тренироваться, он может пропускать тренировки, и уровень его силы остается без изменения. Зная свои возможности, Степан понимает, если в какой-то день он выполнит упражнение более T раз, то следующие D дней он будет слишком усталым, чтобы заниматься.

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

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

Входные данные: Первая строка входного файла содержит целое число N (1 ≤ N ≤ 10 5) — количество дней тренировок.

Вторая строка содержит два целых числа T, D (1 ≤ T ≤ 10 Июня, 1

≤ D ≤ 10 5), если в какой-то день Степан выполнит упражнение

более T раз, то ему придется отдыхать D следующих дней.Следующие N строк описывают упражнения, i + 2 -й строка содержит описание упражнения в день i.Каждое упражнение описывается числами A i, B i, K i, F i, (0 ≤ K i 9 октября, 1 ≤ A i B i 10 июня, 1 ≤ F i 10 6), разделенными одиночными пробелами, — где A i, B i соответственно рекомендован минимум и максимум количества раз выполнения упражнения, K i — количество теряются уровней силы при изучении упражнения, F i — количество уровней силы, получаемых по каждый раз выполнения

упражнения.

Выходные данные: Первая строка выходного файла должна содержать одно целое число S — максимальный уровень силы, который Степан может достичь к концу тренировок.Следующая строка должен содержать N целых чисел X i — количество раз выполнения упражнения в день и, если в и-ый день он отдыхал, то выведите 0.

Пояснения к примеров:

Чтобы достичь максимального уровня силы, надо в первый день выполнять упражнение 4 раза, чтобы не пришлось пропускать следующий день. Во второй день Афанасий сможет увеличить свой уровень еще на 790 (теряет 10 уровней при изучении и выполняет упражнение 8 раз), но тогда он не сможет заниматься 1 день (третий день).

В четвертый день он увеличивает свой уровень на 48, так как Степан выполнил упражнение более 4 раз, он вынужден пропустить пятый.

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

exercises.in exercises.out
5

1 апреля

5 марта 0 10

8 июня 10100

2 августа 15 октября

5 июня 0 8

2 февраля 7 Января

878

4 8 0 6 0

 

Идея решении задачи Дасюк Антона, ученика 10 класса специализированной общеобразовательной школы № 2 I-III ст. с углубленным изучением иностранных языков г.. Чернигова (Коваленко А.И., учитель-методист, учитель информатики СЗНЗ

№ 2 г.. Чернигов)

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

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

Для решения данной задачи воспользуемся методом

динамического программирования.Нужно заметить, что для оптимального накопления силы, упражнение нужно выполнять или или или раз, остальное количество не улучшит результат.Сохранять динамику — максимальный уровень

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

1) , То есть i-го дня упражнение не выполняется;

2) (, ), Если i-го дня Степан выполнит упражнение раз, при почему;

3) (,), Если i-го дня Степан

выполнит упражнение раз, при почему;

4) (,), Если i-го дня Степан выполнит упражнение раз, при почему;

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

решение:

#include <cstdio>

#include <iostream>

#include <algorithm> using namespace std; const int N = 100001; int main () {

freopen ( «input.txt», «r», stdin);

freopen ( «output.txt», «w», stdout)

int a, b, d, f, i, k, m, n, t, z [N] = {}; long long v [N] = {}, s = 0, u = 1; pair <int, int> P [N];

scanf ( «% d», & n);

scanf ( «% d% d», & t, & d)

for (i = 0; i <n; ++ i)

{

scanf ( «% d% d% d% d», & a, & b, & k, & f) if (v [i + 1] <= v [i])

{

v [i + 1] = v [i];

P [i + 1] .first = i; P [i + 1] .second = 0;

}

if (v [i]> = k)

{

if (b <= t)

{

if (v [i] — k + u * f * b> v [i + 1])

{

 

 

 

}

}

else

{

v [i + 1] = v [i] — k + u * f * b; P [i + 1] .first = i;

P [i + 1] .second = b;

if (t> = a && v [i] — k + u * f * t> v [i + 1])

{

v [i + 1] = v [i] — k + u * f * t; P [i + 1] .first = i;

P [i + 1] .second = t;

}

m = min (n, i + d + 1);

if (v [i] — k + u * f * b> v [m])

{

v [m] = v [i] — k + u * f * b; P [m] .first = i; P [m] .second = b;

}

}

}

if (v [i]> s)

s = v [i];

}

if (v [n]> s)

s = v [n];

cout << s << endl; i = n;

while (i)

{

a = P [i] .first;

z [a] = P [i] .second; i = a;

}

printf ( «% d», z [0]); for (i = 1; i <n; ++ i)

printf ( «% d», z [i]); cout << endl;

return 0;

}

 

 

 

 

 

 

 

 

 

решение:

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

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

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

Для решения данной задачи воспользуемся методом динамического программирования.Легко заметить, что для оптимального накопления силы, упражнение нужно выполнять или или или раз, остальное количество не улучшит результат.Сохранять динамику — максимальный уровень

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

1. , То есть i-го дня упражнение не выполняется;

2. (,), Если i-го дня Степан выполнит упражнение раз, при почему;

3. ( ,), Если i-го дня

Степан выполнит упражнение раз, при почему;

4. (,) если i-го дня Степан выполнит упражнение раз, при почему;

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

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

идею: usessysutils;

var n, t, d: longint;

i, day, cur, prev: longint;

a, b, k, f, days: array [0..100000] of int64;

// массивы, в которых будут храниться считывании из файла данные

// days — массив для хранения количества упражнений, выполненных Степаном

mx: array [0..100000 + 1] of int64;

// массив для хранения накопленной Степаном силы lst, done: array [0..100000 + 1] of int64;

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

have, tomorrow: int64;

// имеющиеся на данный и вчерашний день силы functionmin (x, y: int64): int64;

// функция нахождения минимального значения среди 2-х чисел

begin min = x;

if y <minthenmin = y; end;

procedure initial;

// процедура инициализации массивов begin

fillchar (lst, sizeof (lst) — 1); fillchar (a, sizeof (a), 0); fillchar (b, sizeof (b), 0); fillchar (k, sizeof (k), 0); fillchar (days, sizeof (days), 0); fillchar (done, sizeof (done), 0); end;

procedure readdata;

// процедура считывания информации из файла begin

assign (input, «exercises.in ‘); reset (input)

read (n)

read (t, d)

for i: = 0 to n — 1 doread (a [i], b [i], k [i], f [i]); end;

procedure writedata;

// процедура записи ответа в файл begin

assign (output, «exercises.out ‘); rewrite (output)

writeln (mx [n])

for i: = 0 to n — 1 do begin

if (i> 0) thenwrite ( »);

write (days [i]); end;

writeln; end;

procedure run; begin

forday = 0 to n — 1 dobegin

// если после выполнения упражнений количество силы уменьшается, то упражнения

// Степан не выполняет

if (mx [day + 1] <mx [day]) then begin

mx [day + 1] = mx [day]; lst [day + 1] = lst [day]; done [day + 1] = done [day]; end;

have = mx [day];

// если сил достаточно для выполнения упражнений if (have> = k [day]) then

begin

// случай, когда a [i] <= t <= b [i]

if (a [day] <= t) and (t <= b [day]) then begin tomorrow = have — k [day] + t * f [day];

if (mx [day + 1] <tomorrow) then begin mx [day + 1] = tomorrow; lst [day + 1] = day;

done [day + 1] = t;

end; end;

// случай, когда b [i] <= t

if (b [day] <= t) then begin

tomorrow = have — k [day] + b [day] * f [day]; if (mx [day + 1] <tomorrow) then begin

mx [day + 1] = tomorrow; lst [day + 1] = day; done [day + 1] = b [day];

end; endelsebegin

// альтернативный случай с контролем индекса массива tomorrow = have — k [day] + b [day] * f [day];

if (mx [min (n, day + 1 + d)] <tomorrow) then begin mx [min (n, day + 1 + d)] = tomorrow;

lst [min (n, day + 1 + d)] = day; done [min (n, day + 1 + d)] = b [day]; end;

end; end;

// возврат списка дней до начала и формирования значений массива

// выполнение упражнений cur = n;

while (true) do begin

 

 

 

end; end; begin initial;

prev = lst [cur];

if (prev <0) then break; days [prev] = done [cur]; cur = prev;

readdata; run; writedata; end.

8-11 классы

II тур

A — «Все, Степан! Ты меня достал!»

Input file name: bubble.in
Output file name: bubble.out
Time limit: 100 ms
Memory limit: 256 M

Степан недавно отдыхал в Японии и привез оттуда новую жевательную резинку. На первой паре в университете он поделился резинкой со своим товарищем. Дождавшись момента, когда лектор вернулся к доске, на счет «три — четыре» ребята дружно начали надувать пузыри. Известно, что Степан надувает пузырь до максимально возможного размера за время t 1, после чего пузырь мгновенно лопается, и Степан начинает надувать пузырь заново с той же скоростью.Товарищ Степана делает то же самое за время t 2.

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

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

Например, если t 1 = 2, t 2 = 3, то будет происходить следующее:

Степан надувает пузырь с момента времени t = 0 до момента времени t = 2, потом пузырь лопается, и он надувает пузырь снова — с момента времени t = 2 до момента времени t = 4, а затем еще раз — с момента времени t = 4 к t = 6.

Товарищ Степана надувает пузырь с t = 0 до t = 3 и еще раз с t = 3 до t = 6.

В момент времени t = 6 пузырьки лопаются одновременно в обоих студентов, преподаватель возвращается и говорит: «Все, Степан!Ты меня достал!».

Входные данные: Первая строка входного файла содержит два целых числа t 1, t 2 (1 ≤ t 1, t 2 ≤ 10 9).

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

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

bubble.in bubble.out
3 февраля 6
16 января 16

 

Идея решении задачи Зуба В.В., директора ООШ I-III ст. № 7 г.. Полян, учителя математики, учителя- методиста; Бондаренко С.М., учителя математики и информатики ООШ I-III ст. № 7 г.. Полян, учителя- методиста

Нужно найти НОК двух данных чисел.

решение:

Var m, n, mn: int64; f: text; Begin

Assign (f, ‘bubble.in’); Reset (f); Read (f, n) Read (f, m) Close (f) mn = m * n;

While m <> n do If m> n then m = mn else n = nm; {Поиск НОД двух чисел по алгоритму Евклида} Assign (f, ‘bubble.out’); Rewrite (f);

Writeln (f, mn div m) {Формула НСК (m, n) = m * n / НОД (m, n)} Close (f)

End.

B — Степан — бизнесмен

Input file name: businessman.in
Output file name: businessman.out
Time limit: 300 ms
Memory limit: 256 M

Ужляндия, как известно, страна с развитыми торговыми отношениями.

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

Степан узнал, что каждый продавец продает один компьютер, и каждый покупатель готов купить ровно один компьютер. Всего на рынке торгуют N продавцов, стоимость компьютера в i-го из них равна A i Ужляндських монет, причем цены могут отличаться у разных продавцов.Кроме того, он нашел для себя M потенциальных покупателей, каждый из которых хочет купить компьютер B i монет.При этом сам Степан может купить и продать любое количество компьютеров.

Степану необходимо получить наибольшую прибыль (выгодно купить и выгодно продать). Поэтому он обратился за помощью к Вам — лучшему программисту Ужляндии.

Входные данные: Первая строка входного файла содержит разделенные одиночным пробелом два целых числа N, M (1 ≤ N, M ≤ 10 5) — количество продавцов на рынке Байтландии и количество потенциальных покупателей соответственно.Вторая строка содержит N целых чисел A i (0 ≤ A i 10 9) — стоимости, по которым продавцы готовы продавать компьютеры.Третья строка содержит M целых чисел B i (0 ≤ B i 10 9) — суммы, потенциальные покупатели готовы отдать при покупке компьютера.

Выходные данные: Первая строка выходного файла должна содержать одно целое число S — размер максимальной выгоды в монетах, которую может получить Степан.

Пояснения к примеров:

В первом примере Степан покупает компьютеры в 1-го и 2-го продавцов и продает их любым двум покупателям. Во втором примере Степану наиболее выгодно купить компьютеры в 1-м, 4-го и 6-го продавцов и продать 3-м, 4-м и 5-м покупателям.

оценивание:

N + M ≤ 20 для всех и: A i, B j ≤ 1000 — не менее 40 баллов N + M ≤ 2000, для всех и: A i, B j ≤ 1000 — не менее 50 баллов N + M ≤ 2000 — не менее 75 баллов

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

businessman.in businessman.out
3 февраля

1 января

3 3 3

4
6 мая

5 10 8 4 7 2

3 1 11 18 9

27

 

Идея решении задачи Зуба В.В., директора ООШ I-III ст. № 7 г.. Полян, учителя математики, учителя- методиста; Бондаренко С.М., учителя математики и информатики ООШ I-III ст. № 7 г.. Полян, учителя-методиста

Для получения максимальной прибыли нужно купить как можно дешевле, а продать — дороже. Поэтому имеем отсортировать данные массивы по росту закупочной цены и по убыванию цены продажи. Затем ищем прибыль от реализации каждой партии компьютеров. Если прибыли нет (неположительные), то такая операция не осуществляется.

решение:

type massiv = array [1..100000] of longint;

Var i, j: longint; n, m, r, x: int64; a, b: massiv; f: text; l: boolean;

{Сортировка быстрое}

Procedure QuickSort (var a: massiv; l, r: longint) var m, x, y: longint;

Begin

m = ((l + r) div 2)

i = l; j = r; x = a [m]; while i <= j do

begin

While a [i] <x do inc (i); While a [j]> x do dec (j) If i <= j Then

Begin y = a [i]; a [i] = a [j]; a [j]: = y; inc (i);

dec (j) End; End;

If l <j Then QuickSort (a, l, j) If r> i Then QuickSort (a, i, r) End;

Begin Assign (f, ‘businessman.in’); Reset (f); Read (f, n, m) If m> n Then x = n Else x = m;

For i: = 1 to n do Read (f, a [i]);

QuickSort (a, 1, n) {Сортировка за ростом} For i: = 1 to m do Read (f, b [i]);

QuickSort (b, 1, m) {Сортировка за ростом}

For i: = 1 to m div 2 do {пересортицы на убыванию} Begin r = b [i]; b [i] = b [m-i + 1]; b [m-i + 1] = r; End;

Close (f)

i = 1, r = 0;

 

While (i <= x) and (b [i] -a [i]> = 0) do {если разница> 0, то считаем прибыль}

Begin r = r + b [i] -a [i]; i = i + 1; End; Assign (f, ‘businessman.out’); Rewrite (f) WriteLN (f, r) Close (f) End.

 

C — Transit

Input file name: transit.in
Output file name: transit.out
Time limit: 1000 ms
Memory limit: 256 M

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

На границе Ужляндии и братского государства, где начинается этот путь, расположен специальный пропускной пункт, через который ежедневно проезжает поезд с огромным количеством обогревателей. Совсем недавно между правительствами двух братских стран был согласован новые правила транзита обогревателей через территорию Ужляндии на ближайшие N дней.Согласно новому договору имеет избраться определенное число m — максимальное количество обогревателей в одном поезде.Тогда с каждого поезда, транспортирующего A i обогревателей, будет отгружено ровно A i -m единиц иностранной продукции (конечно, если A i> m, иначе же поезд будет двигаться без остановок и ничего отгружено не будет).Собственно это и будет плата за прохождение поезда по территории Ужляндии, она эквивалентна денежным расходам на содержание железнодорожных путей. Суммарное количество отгруженных в Ужляндии за N дней обогревателей должна быть не менее K, иначе страна испытывает убытков.

Стала известна количество обогревателей в поезде в каждый из N дней (эта информация предоставляется по условиям контракта).

 

Найдите максимальное число m, при котором Ужляндия не претерпит экономический ущерб.

Входные данные В первой строке записано два числа N, K (1 ≤ N ≤ 10 Июнь, 1 ≤ K ≤ 2 * 10 9).В следующей строке заданы N чисел — количество обогревателей в поезде в каждый из N дней, не превышает 10 сентября.

Выходные данные: В единственной строке выведите одно число — ответ на задачу, гарантируется, что ответ всегда существует.

Пояснения к примеру:

Всего по территории Ужляндии пройдет 4 поезда с 11, 6, 1 и

8 обогревателями соответственно. Чтобы страна не знала убытков, нужно отгрузить не менее 7 обогревателей. Очевидно, что максимальное возможное m, которое удовлетворит это условие, будет равно 6, тогда из поездов будет отгружено соответственно 5, 0, 0, 2 обогревателей, в сумме равен 7 и удовлетворяет условию.

оценивание:

N ≤ 300 — не менее 20 баллов

N ≤ 10000 — не менее 40 баллов

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

transit.in transit.out
7 Апреля

6 ноября 1 августа

6

 

 

 

 

 

 

 

решение:

Идея решении задачи Зуба В.В., директора ООШ I-III ст. № 7 г.. Полян, учителя математики, учителя- методиста; Бондаренко С.М., учителя математики и информатики ООШ I-III ст. № 7 г.. Полян, учителя- методиста

Представим количество обогревателей в поездах в виде отсортированного столбчатой ​​диаграммы и на ее примере покажем алгоритм работы программы.  Зачеркнутые клетки изображают

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

0 шт. 3 шт. 7 шт.

type massiv = array [0..1000000] of

longint;

Var i, j: longint; x, y, z, n, k, kk, m: int64; a: massiv; f: text;

{Процедура быстрой сортировки}

Procedure QuickSort (var a: massiv; l, r: longint) var m, x, y: longint;

Begin

m = ((l + r) div 2)

i = l; j = r; x = a [m]; While i <= j do

Begin

While a [i] <x do inc (i); While a [j]> x do dec (j) If i <= j Then

Begin y = a [i]; a [i] = a [j]; a [j]: = y; inc (i);

dec (j)

End;

End;

If l <j Then QuickSort (a, l, j) If r> i Then QuickSort (a, i, r) End;

Begin Assign (f, ‘transit.in’); Reset (f); Read (f, n, k) For i: = 1 to n do Read (f, a [i]); Close (f) QuickSort (a, 1, n) {Сортировки массива} m = a [n]; kk = 0; y = n; j = 1;

While kk <k do {идея работы данного цикла описана выше}

Begin m = a [y-1];

x = a [y] -a [y-1]; kk = kk + x * j; z = kk;

While (zj> = k) and (x> 0) Do Begin z = zj; inc (m) End; dec (y) inc (j)

End; Assign (f, ‘transit.out’); Rewrite (f) WriteLN (f, m) Close (f) End.

 

E — Видео-кафе Ужляндии

Input file name: video_cafe.in
Output file name: video_cafe.out
Time limit: 1500 ms
Memory limit: 128 M

Как известно, чемпионат мира по хоккею в 2014 году пройдет в Ужляндии. Для успешного проведения мероприятия принимающей стороне предстоит выполнить ряд требований, предъявляемых Международной хоккейной федерацией. Хоккейные матчи планируется провести в. Ужкачево и м. Ужковель (в Ужляндиии все города начинаются на Уж). Данные города связаны между собой прямой автомагистрали Ужкачево — Ужковель.

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

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

2. Если по дороге из г.. Ужкачево в г.. Ужковель остановиться в некотором видео-кафе, то расстояние между данными видео кафе и следующим на автомагистрали видео-кафе (если таковое имеется) должно быть не менее А км и не более В км.

3. Расстояние от г.. Ужкачево и м. Ужковель в ближайшее видео-кафе не должно быть меньше А км и не более В км.

Рисунок к примеру №1: N = 5, K = 3, A = 20, B = 70.

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

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

более одного видео-кафе. Верно и обратное — видео-кафе может располагаться только на территории кемпинга.

Входные данные: Первая строка входного файла содержит два целых числа — N, K (1 ≤ K ≤ N ≤ 1000) соответственно.

Второй строка входного файла содержит два целых числа A, B (1 ≤ A <B ≤ 10 9).Третий строка входного файла содержит одно целое число S (1 ≤ S ≤ 10 9) — расстояние между м.Ужкачево и м.Ужковель. Четвертый строка входного файла содержит N целых чисел C i (0 <C i <S, C i <C j если i <j) — расстояние i-го кемпинга от м.Ужкачево.

Выходные данные: Выходной файл должен содержать одно целое число — максимальную сумму коэффициентов Z i построения K видео-кафе.Решение всегда существует.

Пояснения к примеров:

В первом примере кемпинги {1, 2, 4}

Во втором примере кемпинги {2, 5, 8, 10}.

оценивание:

K ≤ 2 — не менее 15 баллов N K 6 октября — не менее 30 баллов N ≤ 50 — не менее 45 баллов N ≤ 300 — не менее 60 баллов

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

video_cafe.in video_cafe.out
5 марта

20 70

195

30 70 90 135 170

420
10 апреля

28 октября

100

10 19 23 32 47 51 62 74 82 89

474

 

 

 

 

 

 

 

графе.

Идея решении задачи Зуба В.В., директора ООШ I-III ст. № 7 г.. Полян, учителя математики, учителя- методиста; Бондаренко С.М., учителя математики и информатики ООШ I-III ст. № 7 г.. Полян, учителя- методиста

Задача на реализацию алгоритма поиска в глубину в

 

решение:

type massiv = array [1..1002] of longint; Var i, j, n, k, a, b, s, x, y, z, cnt: longint; zi: int64;

c: massiv; f: text; vc: array [0..1001,0..1001] of boolean; vv: array [1..1000] of boolean; vq: array [1..1000] of longint;

Procedure DFS (v, x: longint; var cnt: longint) {Алгоритм поиска в глубину}

var i, j, d, f, m, max: longint;

Begin m = 0; j = 0;

For d = 1 to n do

If vv [d] = true Then Begin j = j + 1; vq [j]: = d; inc (m) End; If (v = x) or (m> k) or (k = 1) Then

Begin

If m = k Then Begin max: = 0;

For d = 1 to j-1 do

For f = d + 1 to j do max = max + abs (c [vq [d]] — c [vq [f]]) max = max * 2; If max> = cnt Then cnt = max;

End; Exit; End;

vv [v]: = true;

For i: = 1 to n + 1 do

If vc [v, i] and not vv [i] Then Begin DFS (i, x, cnt) End; vv [v]: = false;

End;

Begin Assign (f, ‘videocafe.in’); Reset (f); Read (f, n, k) Read (f, a, b) Read (f, s); For i: = 1 to n do Read (f, c [i]); Close (f)

c [n + 1] = s; c [n + 2] = 1000000001; cnt = 0;

{Построение матрицы смежности} z = 0;

For i: = 1 to n do Begin

x = z + a; y = z + b; j = i;

while (c [j] <= y) and (j <= n + 1) do Begin

If c [j]> = x Then vc [i-1, j]: = true; j = j + 1;

End; z = c [i]; End;

vc [i, n + 1] = true;

For i: = 1 to n do If vc [0, i] Then DFS (i, n + 1, cnt) Assign (f, ‘videocafe.out’); Rewrite (f) WriteLN (f, cnt) Close (f) End.

 

Программа неправильно выполняет 6-12, 14-20 тесты (ограничение по времени).Результат — 30 из 100.

 

[Всего голосов: 4    Средний: 5/5]

Читать  Сборник задач и решений олимпиады по информатике