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


Сборник задач и решений

II этапа Всеукраинской ученической олимпиады по информатике

2014-2015 учебного года

Авторы-составители:

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

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

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

 

рецензенты:

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

 

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

 

Сборник содержит задачи и решения II этапа Всеукраинской ученической олимпиады по информатике, которая проводилась в Черниговской области в 2014-2015 учебном году.

Материалы рассчитаны на учителей информатики, слушателей курсов повышения квалификации. Могут быть использованы учениками 7-11 классов для подготовки к олимпиадам.

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

СОДЕРЖАНИЕ

Введение…………………………………………………………… 4
Задачи пробного тура второго этапа Всеукраинской ученической олимпиады по информатике …………………………………… …  

5

Задачи I (первого) варианта II этапа Всеукраинской ученической олимпиады по информатике …………………… …….  

13

Задачи ИИ (второго) варианта II этапа Всеукраинской ученической олимпиады по информатике …………………………  

26

Список рекомендованной литературы ……………… ……….. …. 34
Список рекомендованных ресурсов сети Интернет ……… … 35

 

Введение

Полезными материалами для подготовки к интеллектуальным соревнованиям является сборники олимпиадных задач прошлых лет с решениями. Данный сборник содержит задачи и решения II этапа Всеукраинской ученической олимпиады по информатике, которая проводилась в Черниговской области в 2014-2015 учебном году.

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

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

II этап олимпиады проводился с использованием центрального сервера автоматизированной проверки решений. Задачи для пробного тура и II этапа олимпиады (первый вариант) подобраны Петровым С.А., старшим преподавателем кафедры компьютерных наук Сумского государственного университета, кандидатом технических наук.

Алгоритмы решения задач, представленные в сборнике, предложенные Бондаренко Сергеем Михайловичем, учителем математики и информатики Прилуцкого общеобразовательной школы I-III ступеней № 7, учителем- методистом и Зубом Владимиром Владимировичем, директором Прилуцкого общеобразовательной школы I-III ступеней

№ 7 Прилуцкого городского совета, учителем математики, учителем- методистом.

Задачи пробного тура второго этапа Всеукраинской ученической олимпиады по информатике

Все программы-решения пользователя в среде FreePascal 2.6.4.

 

Задача A-Гипотенуза

Ограничение времени: 1 с
Ограничение памяти: 256 M

Даны два числа a и b. Выведите гипотенузу треугольника с заданными катетами с точностью 6 знаков.

Входные данные: два числа. Выходные данные: искомая величина.

примеры

входные данные результат работы
3

4

5.000000

решение

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

1. Теорема Пифагора. В прямоугольном треугольнике квадрат гипотенузы равен сумме квадратов катетов: c 2 = a 2 + b 2.

2. Действительные числа записываются в формате с плавающей запятой. Поэтому при обычном выводе результата, приведенного в примере на экране получим запись типа 5.0000000000000000Е + 0000 что соответствует стандартному виду 5.0 • 10 0.Для вывода чисел в обычном виде используют форматированный вывод: величина: n: m, где

n — общее количество позиций экрана, которые будут использоваться при выводе величины, а m — количество знаков после запятой.Форматированный вывод используется только для действительных величин.

var a, b: int64; c: real; begin

read (a, b) c = sqrt (a * a + b * b)

write (c: 0: 6) end.

 

Задача B-Кролики

Ограничение времени: 1 с
Ограничение памяти: 256 M

Когда земляне, наконец, нашли обитаемую планету, они назвали ее OLYMP и отправили на нее вместе с космическим кораблем одного кролика. Кролик понравился климат новой планеты и через месяц он привел на свет еще одного кролика.  Далее кролики продолжили размножаться с такой же скоростью, то есть каждый месяц каждый из кроликов, присутствующих на планете, приводил на свет еще одного кролика. Однако, размножения кроликов сдерживал монстр, откуда взялся на планете. Как только в начале какого-то месяца кроликов становилось строго больше, чем k, он приходил и съедал k кроликов. Определите, сколько кроликов будет на планете через n месяцев после прибытия туда космического корабля с первым кроликом. Число n от 0 до 100 включительно. Число k от 0 до 10000 включительно. Результат работы метода не превышает 2000000000.

Входные данные: целое число n — количество месяцев, целое число k — количество кроликов, съедаемых монстром.

Выходные данные: целое число, равное количеству кроликов на планете OLYMP через n месяцев после поселения туда первого кролика.

примеры

входные данные результат работы
0 10 1
10 января 2
100 1024 2048
16 0 65536

решение

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

var i, n, k: longint; t: int64; begin

read (n, k) t = 1;

for i: = 1 to n do begin

if t> k then t = tk; t = t * 2;

end; write (t)

end.

 

Задача C-Old hocus-pocus

 

Ограничение времени: 1 с
Ограничение памяти: 256 M

Петя Пяточкин загадал число от 1 до 10 9, а Вам сообщил три остатка, образовавшиеся при делении задуманного числа на числа 971, 997, 1033.Сделайте фокус — быстро отгадайте число. Напишите программу, по данным остаток,

находит загаданное число.

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

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

примеры

входные данные результат работы
5 10 15 835049324

решение

Первый вариант программы вполне может быть таким:

var a, b, c, i: longint; begin

read (a, b, c)

for i: = 1 to 1000000000 do

if (i mod 971 = a) and (i mod 997 = b) and (i mod 1033 = c)

then begin write (i) break; end;

end.

Но при проверке работоспособности программы на входных данных увидим, что время работы программы далеко превышает отведенную 1с.

В курсе математики 6 класса в теме «Делимость натуральных чисел» рассматривается очень полезна для нас формула: a = b • n + r.С ее помощью можно представить любое число a-за неполной долю n и остаток r при его делении на b.Применение данной формулы позволит уменьшить максимальное количество итераций цикла с 10 сентябрь к менее, чем 10 июня. к вещи, если

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

Сначала найдем число, соответствующее одной из условий и проверим его на соответствие другим условиям. Лучше всего выбирать наибольший делитель 1033. Тогда таким числом будет число а = 1033 + 15 (см. Исходные данные).Оно не дает соответствующих

Остаток при делении на 997 и 971. Следующим будет число a + 1033, и т.д.Поэтому в цикле рассматриваем числа типа 1033 • n + r и проверяем, дают ли они соответствующие остатка при делении на 971 и 997.

var a, b, c, i, j, k, x: longint; begin

read (a, b, c)

if (a = b) and (b = c) then begin write (a) exit; end; x = 1033 + c;

while not ((x mod 971 = a) and (x mod 997 = b)) do x = x + 1033;

write (x) end.

 

Задача D-Количество чисел, не делятся на 2, 3 или 5

Ограничение времени: 1 с
Ограничение памяти: 256 M

Задано натуральное число N. Напишите программу, которая определяет количество натуральных чисел, не больше N и не делятся ни на одно из чисел 2, 3, 5.

Входные данные: число N (1 ≤ N ≤ 1000000000).Выходные данные: найденное число

примеры

входные данные результат работы
10 2

 

решение

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

Решим задачу с помощью кругов Эйлера и теориеи множеств по курсу математики 10 класса (уровень) или

8 класса (углубленный уровень) (Рис. 1).

Пусть прямоугольник представляет собой множество натуральных чисел N, данное в условии задачи.Круги B, C, D — множества чисел, делящихся на 2,

3 и 5 соответственно. Тогда неокрашенные часть прямоугольника (множество А) является множеством искомых чисел. B∩C — множество чисел, делящихся на 2 и на 3, то есть на 6; B∩D — делятся на 2 и на 5, то есть на 10, C∩D — делятся на 3 и на 5, то есть на 15; B∩C∩D — делятся на 2, на 3 и на 5, то есть на 30.

 

 

 

 

 

 

 

 

 

 

 

 

Рис. 1

Множество B содержит N / 2 чисел, множество C- N / 3, множество D

— N / 5. Для определения количества цифр, входящих в множество А достаточно воспользоваться формулой K = N / 2 + N / 3 + N / 5-N / 6-N / 10- N / 15 + N / 30.

var a, n, i: int64; begin

read (n)

a = (n div 2) + (n div 3) + (n div 5) + (n div 30) — (n div 6) — (n div 10) — (n div 15);

write (na) end.

Задача E-Следующее и предварительное

Ограничение времени: 1 с
Ограничение памяти: 256 M

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

примеры

входные данные результат работы
25 The next number for the number 25 is 26. The previous number for the number 25 is 24.

решение

var n: int64; begin

read (n)

writeln ( ‘The next number for the number’, n, ‘is’, n + 1, «.’);

write ( ‘The previous number for the number’, n, ‘is’, n-1, «.’);

end.

 

Задача F-Сумма цифр числа

Ограничение времени: 1 с
Ограничение памяти: 256 M

Задано четырехзначный число N. Напишите программу, которая определяет сумму цифр данного числа.

Входные данные: число N. Выходные данные: найдена сумма.

примеры

входные данные результат работы
1012 4

решение

Классическая задача на деление числа на цифры.Условия предоставления дано Четырехцифровое число. Итак, можно просто написать четыре команды выделение цифр с помощью операций div и mod, а затем их добавить.

Пусть n = 1000a + 100b + 10c + d.Тогда a = n div 1000, b = n mod 100 div 100, c = n mod 100 div 10 d = n mod 10.

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

var n, s: integer; begin

read (n) while n> 0 do

begin

s = s + n mod 10;

n = n div 10; end;

write (s) end.

Задачи I (первого) варианта II этапа Всеукраинской ученической олимпиады по

информатики

Все решения-программы написаны в среде FreePascal 2.6.4.

Задача A — Сдача

Ограничение времени: 100 мс
Ограничение памяти: 128 M

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

Входные данные: в единственной строке содержится четыре натуральных числа A, B, C, D (0 ≤ A, B, C, D ≤ 100).

Выходные данные: выведите два числа — сдачу Степана.

примеры

входные данные результат работы
1 30 февраля 50 20 января

решение

Самый простой способ — перевести суммы в копейки, отнять и перевести обратно (в гривне и копейки).

var a, b, c, d, e: longint; begin

read (a, b, c, d)

e = (ca) * 100 + (db)

write (e div 100, », e mod 100); end.

Задача B — Игровые дни

Ограничение времени: 100 мс
Ограничение памяти: 128 M

Родители позволяют Степану играть за компьютером, если он получил в этот день пятерку (в школе, в которой учится Степан, пятибалльная система оценивания), но не получил троек (Степан двоек и единиц не получает). Напишите программу, которая определяет, сможет сегодня Степан поиграть за компьютером?

Входные данные В первой строке содержится одно натуральное число N (1 ≤ N ≤ 100) — количество оценок, которые получил Степан.Во второй строке записаны N чисел — оценки, которые получил Степан, каждая из которых 3, 4 или 5.

Выходные данные: Выведите «YES» — если Степан сможет поиграть за компьютером, или «NO» в противном случае.

примеры

входные данные результат работы
3

4 мая 4

YES
4

5 3 5 4

NO

решение

Решение задачи может быть реализован различными способами. Например, S — таблица количества оценок 3, 4, 5 Степана.Ячейка s [5] содержит количество пятерок, а ячейка s [3] — количество троек (остальные оценки не важны). Согласно условию Степан играть на компьютере только в случае, когда s [5]> 0, а s [3] = 0.

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

procedure FillChar (var Buffer; Count: Integer; const Fill) Описание: Buffer X — буфер, который нужно заполнить, Count —

количество символов, Value — заполнитель (типа Byte или Char).

var n, a, i: integer; s: array [3..5] of integer; begin

read (n)

fillchar (s, sizeof (s), 0) {заполнения таблицы S нулями}

for i: = 1 to n do begin

read (a) {Чтение очередной оценки Степана} inc (s [a]) {Увеличение значений ячеек s [3],

s [4], s [5] таблицы на 1 в зависимости от a} end;

if (s [5]> 0) and (s [3] = 0) then write ( ‘YES’) else write ( ‘NO’);

end.

 

Задача C — налог

Ограничение времени: 100 мс
Ограничение памяти: 128 M

В некоторой стране инфляция достигла таких размеров, что доходы стали выражаться числами, количество знаков десятичной записи которых доходит до 200. Это сильно усложнило задачу сбора налогов. Один из налогов на доходы составляет 1%. Напишите программу, которая по введенным числом D (величине дохода гражданина) вычислит этот налог.При этом применяются следующие правила округления:

1. Если налог выражается целым числом, то он не округляется.

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

Входные данные В первой строке содержится одно натуральное число D (10 мая ≤ D ≤ 10200) — величина дохода гражданина.

Выходные данные: Выведите одно натуральное число — величину налога.

Система оценивания: Развязки, которые верно работают при D (10 Мая ≤ D ≤ 10 9), будут оцениваться в 40 баллов.Решения, которые верно работают при D (10 мая ≤ D ≤ 15 октября), будут оцениваться в 60 баллов.

примеры

входные данные результат работы
1000001 10001
12345600 123456

решение

Алгоритм действий прописан в условии — если остаток от деления числа D на 100 ≠ 0, то целую часть нужно увеличить на 1, иначе оставить от изменений. Для получения 40 баллов достаточно было использовать тип longint и написать код примерно так:

p = d div 100;

if d mod 100 <> 0 then p = p + 1;

При использовании int64 можно получить 60 баллов.Использование других числовых типов принципиального выигрыша не дает, поскольку ни один из них не имеет точности в необходимые 200 знаков. Итак, используем символьные величины.

Разделить число, записанное в символьном виде, на 100 просто — достаточно отрезать последние два символа. Если это были два нуля, то полученное число и является искомым. В противном случае нужно увеличить полученное число на 1. Рассмотрим два случая:

1) последняя цифра полученного числа не 9, то ее достаточно увеличить на 1,

2) последняя цифра 9.Тогда все немного сложнее, ведь 9 + 1 = 10. То есть, при добавлении единицы рассматривают предварительную цифру и осуществляют переход через десяток. А это опять два случая. Итак, организуется цикл, в котором мы проверяем цифры с конца числа. Пока они равны 9, их нужно заменять нулями. Первую же цифру, которая не является девяткой нужно просто увеличить на 1.

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

— девятки. Тогда мы получим одни нули — не забыть добавить

первой единицу !!!

function Ord (Arg: Char): Integer;

Описание: функция Ord, превращает символ Arg в его числовой код.Коды всех символов можно увидеть в кодовой таблицы ASCII. ASCII (American Standard Code for Information Interchange) — международный стандарт, принятый для кодирования текстовой информации. Всего в ней 256 символов.

function Chr (IntValue: Integer): AnsiChar;

Описание: функция Chr противоположная функции Ord. Эта функция превращает числовой код IntValue символа в сам символ.

var a, b: string; n, i, j: integer; begin

read (a)

n = length (a) -2, {Количество цифр числа налога} b = copy (a, 1, n) {величина налога}

if copy (a, n + 1,2) <> ’00’ then if b [n] <> ‘9’

then b [n] = chr (ord (b [n]) + 1) {добавления 1 к настоящему разряда числа}

else begin

b [n] = ‘0’; j = 1;

while (nj> 0) and (b [nj] = ‘9’) do begin

b [nj] = ‘0’; inc (j) end;

if j <> n then b [nj] = chr (ord (b [nj]) + 1) else b = ‘1’ + b;

end;

write (b) end.

Задача D — Строительство школы

Ограничение времени: 100 мс
Ограничение памяти: 128 M

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

Входные данные: Сначала вводится число N (1 ≤ N ≤

105) — количество учеников.Далее идут в строго возрастающем порядке координаты домам — целые числа, не превышающие 2 * 10 9 по модулю.

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

Система оценивания: Развязки, которые верно работают при N (1 ≤ N ≤ 10 марта) для координат, которые не превышают по модулю 1000, будут оцениваться в 30 баллов.Решения, которые верно работают при N (1 ≤ N ≤ 10 5) для координат, которые не превышают по модулю 100000, будут оцениваться в 70 баллов.

примеры

входные данные результат работы
4

1 2 3 4

2
3

-1 0 1

решение

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

Рис. 2

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

var n, i, j: longint; l, xmin, min: int64; a: array [1..10000] of int64;

begin

read (n)

for i: = 1 to n do read (a [i]); min = 2000000000; xmin = a [1];

for i = a [1] to a [n] do begin

l = 0;

for j = 1 to n do l = l + abs (a [j] -i)

if l <min then begin min = l; xmin = i; end; end;

write (xmin) end.

В чем проблемы такому решению? Во-первых, нужно выполнить (10 5) 2 = 10 10 итераций, а это довольно много — программа не уложится в отведенное время.Во-вторых, не исключено, что текущая сумма может выйти за пределы int64.И что же делать? Используем уже написанную программу полного перебора для анализа размещения школы для различных вариантов проживания

учеников.

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

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

[N div 2; N div 2 + 1].

Рассмотрим пример с нечетным количеством точек.

Рис. 3

Манипуляции с координатами при нечетном количестве учеников (Рис.3) подтверждают предположение — школу нужно строить в точке, соответствующей средней ячейке таблицы, данной в условии.

Поэтому имеем следующую программу.

var n, i, j: longint; l, xmin, min, s: int64; a: array [1..10000] of longint;

begin

read (n)

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

if n div 2 = 0 then write (a [n div 2]) else write (a [n div 2 + 1])

end.

Задача E-Праздник

Ограничение времени: 1000 мс
Ограничение памяти: 128 M

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

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

Помогите Софии определить, какие коврижки поместятся в коробки, а какие нет.

Входные данные В первой строке записано диаметр упаковочной коробки, а во втором — количество приготовленных Софией пряников N (1 ≤ N ≤ 100).Каждый из последующих N строк содержит описание одного пряника.Если пряник имеет форму треугольника, то в начале строки записывается число 1, а затем — длины сторон этого треугольника (треугольник невырожденный). Для прямоугольного пряника в начале строки записано число 2, а затем длины смежных сторон прямоугольника. Числа разделены одним пробелом.  Все размеры — целые положительные числа, не

превышают 10 17 (в 80% тестов эта величина не более 10 3).В 25% тестов пряники имеют форму прямоугольника.

Выходные данные: Выведите строку с N символов.Каждый символ строки соответствует одному прянику (в порядке ввода данных). Символ «Y» означает, что пряник можно поместить в коробку, а символ «N» — что пряник поместить нельзя.

примеры

входные данные результат работы
20

2

15 февраля 17

19 февраля 5

NY
20

4

20 января 16 декабря

1 10 10 10

20 января 20 20

13 февраля 15

YYNY

 

решение

Случай первый — прямоугольник (рис.4).пряник можно

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

Хорошая формула и простая, но при значениях аргументов больше 10 9 Она есть не предоставляет требуемой точности вычисления.лучше вычислить

Рис. 4

диагональ по формуле

.с обратных

тригонометрических функций язык Паскаль имеет только arctg, поэтому

.

Случай второй — треугольник (рис.5).

    1. если треугольник тупоугольный или прямоугольный, то есть

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

    1. Если треугольник остроугольный (рис.6), то ищем диаметр описанной окружности. Это лучше сделать по теореме синусов, а угол — с помощью теоремы косинусов:

, , .

Последнюю формулу лучше записывать в виде

.

 

Рис. 5 Рис.6

 

var n, i, t: integer; d1, d, cosc, x, y, z: extended; a, b, c: int64;

begin

read (d, n)

for i: = 1 to n do begin

read (t, a, b) {читаем тип фигуры и первые две стороны}

if t = 1 then {случай треугольника} begin

read (c) {читаем третью сторону и находим наибольшее}

if (a> = b) and (a> = c) then begin x = a; y = b; z = c; end;

if (b> = a) and (b> = c) then begin x = b; y = a; z = c; end;

if (c> = b) and (c> = a) then begin x = c; y = b; z = a; end;

if x * x> = y * y + z * z then begin {проверяем тип треугольника}

 

write ( ‘N’); end

if x <= d then write ( ‘Y’) else

 

else begin

cosc = a / 2 / bc / 2 / a * c / b + b / 2 / a; d1 = c / sqrt (1-cosc * cosc)

if d1 <= d then write ( ‘Y’)

else write ( ‘N’);

end; end

else begin {случай четырехугольника} d1 = a / sin (arctan (a / b));

if d1 <= d then write ( ‘Y’) else write ( ‘N’); end;

end; end.

Задачи ИИ (второго) варианта II этапа Всеукраинской ученической олимпиады по

информатики

Все программы-решения пользователя в среде FreePascal 2.6.4.

Задача A — Золотой аквариум

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

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

Входные данные: Единственное целое число V — объем выбранного аквариума.

Выходные данные: Единственное целое число N — допустимое количество золотых рыбок.

Ограничения: 20 <V <500.

Пример ввода: 22

Пример вывода: 7

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

решение

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

аквариума на 3.

var n, v: integer; begin

read (v) n = v div 3; write (n)

end.

 

Задача B — Веселая азбука

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

Петрик учится в начальной школе. Он еще не очень хорошо знает английский алфавит и поэтому очень расстроился, когда Ольга Павловна (учительница английского языка) попросила его переставить буквы слова S в алфавитном порядке (от «А» до «Z»). Помогите Пете справиться с задачей.

Входные данные В строке содержится слово S.

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

Ограничения: слово S содержит от 1 до 10 символов, только маленькие латинские буквы.

Пример ввода: champion

Пример вывода: Achimnop

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

решение

Поскольку S — строка, то это величина типа string, то есть таблица символов. для ее упорядочение по алфавиту можно

воспользоваться произвольным методом сортировки. Но есть оптимальный способ, который гарантированно сделает «за один проход». Для этого используем таблицу на 26 символов английского алфавита и в ее ячейки будем записывать количество соответствующих букв входного слова. Например, для данного в условии слова: a [ ‘a’] = 1, a [ ‘b’] = 0, a [ ‘c’] = 1 … Таким образом, нам не придется организовывать таблицу, существенно сэкономит время (хотя для данных ограничений это не принципиально).

Элементы таблицы индексируются произвольным перечисленным типом данных. Чаще всего для этого используют целочисленные величины. В данной задаче мы используем буквы английского алфавита. Это упорядоченный перечислен тип, поэтому индексы таблицы вполне могут ему принадлежать. Поэтому объявим таблицу a: array [ ‘a’ .. ‘z’] of integer.

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

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

procedure FillChar (var Buffer; Count: Integer; const Fill) Описание: Buffer X — буфер, который нужно заполнить, Count —

количество символов, Value — заполнитель (типа Byte или Char).

var s: string; a: array [ ‘a’ .. ‘z’] of integer; i: integer; j: char;

begin

read (s) {читаем слово} fillchar (a, sizeof (a), 0) {очищаем таблицу} for i: = 1 to length (s) do

inc (a [s [i]]) {увеличиваем на 1 значение ячейки, соответствующей i-й букве данного слова}

for j: = ‘a’ to’z’do

if a [j]> 0 then {это необязательный строку, поскольку тело цикла с параметром не выполняется,

если конечное значение параметра меньше начальное, то есть при a [j] <1}

for i: = 1 to a [j] do write (j) {выводим результат}

end.

 

Задача C — Сумы

(Задача с II этапа Всеукраинской ученической олимпиады 2010-2011 учебного года во Львовской области)

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

Пусть имеется массив чисел а = {2, 1, 4. 3}. Запишем, как согласно условию задачи, будет формироваться таблица для данного массива.

2 1 4 3
2 2 * 2 = 4 2 * 1 = 2 2 * 4 = 8 2 * 3 = 6
1 1 * 2 = 2 1 * 1 = 1 1 * 4 = 4 1 * 3 = 3
4 4 * 2 = 8 4 * 1 = 4 4 * 4 = 16 4 * 3 = 12
3 3 * 2 = 6 3 * 1 = 3 3 * 4 = 12 3 * 3 = 9

Сумма элементов нижней треугольной части (элементы которой выделены серым цветом) 4 + 2 + 1 + 8 + 4 + 16 + 6 + 3 + 12 + 9 =

65.

Входные данные В первой строке задано число N — количество элементов массива.В следующей строке заданы N чисел, разделенных пробелом, — элементы массива A j.

Выходные данные: Единственное целое число.ограничения:

1 ≤ N≤ 100000,

0 ≤A j ≤100.

Пример ввода:

4

14 февраля 3

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

65

решение

Рассмотрим таблицу из условия задачи в компактном виде и проанализируем.

 

4 2 8 6
2 1 4 3
8 4 16 12
6 3 12 9

Ячейки, для которых i = j, образуют так называемую главную диагональ.Поскольку от перестановки множителей произведение не меняется, то b [i, j] = b [j, i].То есть, таблица симметрична относительно главной диагонали. Вычислять элементы самой таблицу не нуждается. Для вычисления искомой суммы используем двойной цикл с условием 1 ≤ i ≤ j ≤ n.

var n, i, j: longint; s: int64; a: array [1..100] of longint;

begin

read (n)

for i: = 1 to n do read (a [i]); s: = 0;

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

s = s + a [i] * a [j]; write (s)

end.

Задача D — Продажа слоников

(Задача с II этапа Всеукраинской ученической олимпиады 2010-2011 учебного года во Львовской области)

Темнеет. Солнце еще пускает последние лучи света. На дворе уже ни души. А Петя Пяточкин дальше считает слоников!

Решив, что стоит отдохнуть, он пошел домой смотреть перед сном ТВ. И тут на экране прошел рекламный строка, он сразу же записал. Неужели распродажа слоников ?! Так как он почти спал, он мог перепутать некоторые буквы, поэтому его интересует такой вопрос: сколькими способами можно выбрать К последовательных символов строки, из букв которых можно составить слово «slonyk» (символы в подстроке можно менять местами).

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

Выходные данные: Единственное число — количество возможных подстрок по требованиям Петрика.

Ограничения: 1 K 10

1 длина строки S 44.

Пример ввода: solkynssaleuptotendollars 9

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

2

решение

Работа с символьными данными требует знаний некоторых функций:

Function Pos (Substr: String; S: String): Byte;

Описание: Ищет позицию подстроки Substr в строке S. Параметры Substr и S — строчные выражения.Pos ищет первое вхождение строки Substr в строке S и возвращает целочисленное значение, которое является индексом

первого символа Substr в середине S. Если строка Substr не найден, то Pos возвращает ноль.

Function Copy (S: String; Index: Integer; Count: Integer): String;

Описание: Возвращает подстроку строки. Параметр S — выражение строчной типа.Index и Count — выражения целочисленного типа. Функция Copy возвращает подстроку строки S, содержит Count символов, начиная с символа с номером Index. Если значение Index больше, чем длина строки S, то Copy возвращает пустую строку. Если значение Count больше, чем количество оставшихся символов в строке с позиции Index до конца строки, то возвращается Length (S) -Index символов.

Function Length (S: String: Integer; Описание: Возвращает длину строки.

Итак, имеем последовательно проверять слова, образованные копированием последовательных n символов входной строки, начиная с первого и до length (s) -n, и в полученном таким образом слове проверять возможность образования слова slonyk перестановка букв.

Алгоритм решения задачи разобьем на два шага.

1. Получение слова длиной n с строки S.

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

var i, k, n: integer; s, s1: string; begin

readln (s) read (n) k = 0;

for i: = 1 to length (s) -n do begin

s1 = copy (s, i, n) if

pos ( ‘s’, s1) * pos ( ‘l’, s1) * pos ( ‘o’, s1) * pos ( ‘n’, s1) *

* Pos ( ‘y’, s1) * pos ( ‘k’, s1)> 0

then inc (k); end;

write (k) end.

литература

 

1. Герасимчук Н.А. Решение олимпиадных задач по программированию: учебное пособие для слушателей отделения компьютерных наук МАН. — Луцк ВО МАН, 2010. — 76 с.

2. Караванова Т.П. Методика решения алгоритмических задач. Основы алгоритмизации и программирования: учебно-методическое пособие для учителей / Т.П. Караванова. — Каменец-Подольский: Аксиома, 2013. — 460 с.

3. Караванова Т.П. Методика решения алгоритмических задач. Построение алгоритмов: учебно-методическое пособие для учителя / Т.П. Караванова. — Каменец-Подольский: Аксиома, 2014. — 344 с.

4. Олимпиадные задачи по информатике: решение задач второго этапа Всеукраинской олимпиады по информатике 2007, 2008гг./ В.Е. Величко, М.М. Рубан, В.П. Батунин, С.Е. Устинов. — Славянск, 2009. — 34 с.

5. Пасихов Ю.Я. Олимпиадные задачи по информатике / Юрий Пасихов, Григорий Непомнящий. — М.: шк. Мир, 2011. — 128 с. — (Библиотека

«Школьного мира»).

6. Рекомендации к решению задач Международных и Всеукраинских олимпиад по информатике среди учащихся: навч.- метод. пособие. — М .: ООО Редакция «Компьютер», 2008. — 128 с.: ил ..

Список рекомендованных ресурсов сети Интернет

 

1. АСМ-Контестер: Украинский портал АСМ-сообщества [Электронный ресурс]. — Режим доступа: http://acm.lviv.ua/ — Название с экрана.

2. Дистанционная подготовка по информатике [Электронный ресурс]. — Режим доступа: http://informatics.mccme.ru/moodle/ — Название с экрана.

3. Днепропетровские олимпиады по информатике [Электронный ресурс]. — Режим доступа: http://oi.dp.ua/ — Название с экрана.

4. Интернгет-портал организационно методического обеспечение дистанционных олимпиад по программированию для одаренной молодежи учебных заведений Украины [Электронный ресурс]. — Режим доступа: http://e-olymp.com/ — Название с экрана.

5. Киевские ученические олимпиады по информатике. Проведение е результаты [Электронный ресурс]. — Режим доступа: http://kievoi.ippo.kubg.edu.ua/ — Название с экрана.

6. Материалы Всеукраинских ученических олимпиад по информатике [Электронный ресурс]. — Режим доступа: http://matholymp.org.ua/contests/types/olympiads/informatics/ — Название с экрана.

7. Центр поддержки и проведения олимпиад школьников с использованием возможностей Internet [Электронный ресурс]. — Режим доступа: http://www.olymp.vinnica.ua/ — Название с экрана.

8. Школа программиста [Электронный ресурс]. — Режим доступа: http://acmp.ru/ — Название с экрана.

9. Timus Online Judge: архив задач с проверяющими системой [Электронный ресурс]. — Режим доступа: http://acm.timus.ru/ — Название с экрана.

 

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

Читать  Основы программирования и алгоритмические языки – ЦЕЛИ И ЗАДАЧИ КУРСОВОЙ РАБОТЫ