Задачи муниципального этапа олимпиады школьников по информатике 2011

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

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

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

Вывести одно целое число — максимальную суммарную площадь комнат в квадратных метрах.

5 2 3 4

26

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

Для целочисленного деления в языке Pascal используется операция `N` div `K`, в языке Basic – `N` \ `K`, в языке C – `N` / `K`. Для получения остатка от деления в языках Pascal и Basic используется операция `N` mod `K`, в языке C – `N` % `K`.

В первой строке ввода содержится одно целое число `N` (`2\ ≤\ N\ ≤\ 10^9`).

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

12

2
2
3

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

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

В первой строке содержатся одно целое число `N` (`1\ ≤\ N\ ≤\ 100`) – количество стопок коробок. Во второй строке содержатся `N` целых чисел в диапазоне от 1 до 100 — высоты стопок.

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

5
3 1 4 2 4

10

Пятиклассник Вася, выполняя домашнее задание по природоведению, в течение `N` дней каждое утро записывал показания уличного термометра в рабочую тетрадь. В учебнике Вася прочитал, что Уральские горы преграждают путь массам воздуха, поступающим с запада, зато холодный арктический воздух и теплые воздушные массы Прикаспия и южных пустынь сюда могут беспрепятственно проникать. Поэтому для Урала характерны резкие колебания температур: зимой — от суровых морозов до оттепелей и дождей, летом — от жары выше +35`°`C до заморозков. Вася захотел найти среди своих записей наблюдений температуры такие резкие изменения.

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

В первой строке содержатся одно целое число `N` (`2\ ≤\ N\ ≤\ 100`) – количество наблюдений температуры. Во второй строке содержатся `N` целых чисел в диапазоне от `-40` до `40` — показания термометра.

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

6
10 6 3 9 7 7

4

Третьеклассник Вася прочитал про теорему Ферма и придумал свою теорему: «Для любых натуральных чисел `a>1` и `b>1` найдется бесконечно много натуральных чисел `n` таких, что `a^n\ +\ b^n` делится на `n` без остатка».

Напишите программу, которая найдет для заданных `a` и `b` все числа `n`, не превосходящие `M`, для которых выполняется свойство из теоремы Васи. При проверке делимости некоторого выражения на `n` можно все вычисления в этом выражении выполнять с остатками от деления на `n`:

`(x+y)\ mod\ n\ =\ ((x\ mod\ n)\ +\ (y\ mod\ n))\ mod\ n`

`(x*y)\ mod\ n\ =\ ((x\ mod\ n)\ *\ (y\ mod\ n))\ mod\ n`

В первой строке содержатся три целых числа `a`, `b` и `M` (`2\ ≤\ a,\ b\ ≤\ 100`, `2\ ≤\ M\ ≤\ 100000`).

Вывести варианты `n` в диапазоне от 1 до `M` включительно в порядке возрастания, для которых выполняется свойство, указанное в теореме Васи. Каждое значение вывести на отдельной строке.

2 3 100

1
5
25
55

В математике для целой части некоторого числа `x` используют обозначение `[x]`. А запись `[N/i]` обозначает частное, получающееся при делении нацело `N` на `i`. Для целочисленного деления в языке Pascal используется операция `N` div `i`, в языке Basic – `N` \ `i`, в языке C – `N` / `i`. Напишите программу, вычисляющую сумму `[N/i]` для `i` от 1 до `N`, т.е.

`[N/1]\ +\ [N/2]\ +\ [N/3]\ +\ …\ +\ [N/(N-1)]\ +\ [N/N]`.

В первой строке содержатся одно целое число `N` (`2\ ≤\ N\ ≤\ 10^9`).

Вывести одно целое число — значение суммы.

5

10

Третьеклассник Вася прочитал в одной книге, что в компьютере используются для вычислений двоичные числа. Так как никаких пояснений в книге не было, Вася предположил, что двоичные числа — это числа, в записи которых используется только цифра 2, т.е. «двоичными» числами будут числа 2, 22, 222, 2222 и т. д. По предположениям Васи все числа в компьютере представляются в виде произведения «двоичных» чисел. Если какое-либо число представить в таком виде нельзя, то используется ближайшее к нему большее число, представимое в виде произведения «двоичных» чисел. Поэтому в килобайте 1024 байта, а не 1000 байт, так как вместо числа 1000 используется число 1024, которое является произведением десяти чисел 2.

Напишите программу, которая для заданного числа `X` находит наименьшее число `Y\ ≥\ X`, представимое в виде произведения «двоичных» чисел. Например, для числа `X=70` таким числом является `Y=2*2*22=88`.

В первой строке содержатся одно целое число `X` (`2\ ≤\ X\ ≤\ 10^18`).

Вывести одно целое число `Y`.

70

88