Олимпиадные задачи по информатике

[The Godfather]

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

Взято отсюда [Для просмотра данной ссылки нужно зарегистрироваться] - сейчас не работает
и отсюда [Для просмотра данной ссылки нужно зарегистрироваться]
Сборник всех областных олимпиад с 1989 по 2005 года - в аттаче

[The Godfather]

2005-2006 уч. год, Районная-городская олимпиада, г. Н.Новгород

Прочитать:

Задача 1. «Мишень» (10 баллов).

Мишень представляет собой 10 концентрических кругов. Радиус меньшего - 5, радиус каждого следующего на 5 больше предыдущего. Попадание пули задается в системе координат (см. рисунок) вещественными числами х и у, каждое из которых по модулю не превосходит 100. Количество выбитых очков зависит от того, в какую зону попала пуля и можег принимать значения 10, 9, ..., 2, 1,0.
Ваша программа должна
- запросить координаты попадания;
- найти и сообщить количество выбитых очков.



Пример: Исходные данные 8, 13, ответ = 7

Примечание. В случае попадания н границу круга может быть выведено любое из значений, соответствующих задетым кругам. Например, если исходные данные 3 и 4, то допустимы ответ и 10 и 9.


Задача 2. «Числа» (20 баллов).

Дано натуральное n-значное число (n <= 79), запись которого не содержит цифры 0. Из него отбрасывается несколько подряд идущих цифр с начала и несколько цифр (также подряд идущих) с конца (может быть ни одной). Программа должна сообщить количество разных чисел, которое может при этом может получиться.

Пример: n = 1323, ответ = 9

Примечание. Имеются ввиду числа 1323, 323, 132, 23, 32, 13, 3, 2, 1


Задача 3. «Многотомник» (30 баллов).

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

Пример:
Число томов 4
Начальная последовательность 4, 2, 3, 1
Число шагов 4
0 шаг: 4, 2, 3, 1
1 шаг: 4, 3, 1, 2
2 шаг. 4, 1, 2, 3
3 шаг: 1, 4, 2, 3
4 шаг: 1, 2, 3, 4


Задача 4. «Многоугольник» (40 баллов).

Часть поверхности прямоугольного стола покрыта одинаковыми листами бумаги. Стороны листов параллельны краю стола и одинаково ориентированы (см. рисунок).



Известно, что
- всего листов n (n < 6);
- размер каждого листа 30 см на 20 см
- целочисленные координаты (0 <= x <= 160, 30 <= y <= 90) левых верхних углов каждого листа в системе координат, связанной с левым нижним углом поверхности стола;
- ни один из листов не выходит за край стола;
- всеми листами покрыт многоугольник.
Написать программу, которая сообщает координаты вершин покрытого многоугольника в порядке обхода.
Исходные данные либо вводятся с клавиатуры, либо читаются из файла input.dat, которым к первой строке содержит натуральное число (n)- количество разложенных листов. Последующие n строк - пары координат (х, у) левого верхнего угла листа.

Пример:
Число листов 2
1 лист 30, 60
2 лист 40, 50
Ответ (30, 60) (50,60) (50, 50) (60,50) (60,20) (40,20) (40, 30) (30, 30)

2006-2007 уч. год, Районная-городская олимпиада, г. Н.Новгород

Прочитать:

Задача 1.«Числа». 10 баллов

Даны наименьшее общее кратное k и наибольший общий делитель n двух натуральных чисел a и b (n,k<=3200). Найти сами числа.
Запросить значения k и n
найти и сообщить числа a и b для которых введенные являются НОД и НОК соответственно (из всех возможных ответов вывести тот, для которого модуль разности a и b наименьший).

Пример: k = 240, n = 8, ответ = 48, 40


Задача 2. «Замок». 20 баллов

В подземелье графа Дракулы n^2 (n<10000) пещер, соединенных туннелями. Два вампира, Гриша и Миша, по очереди засыпают туннели землей (Гриша первый). За один ход можно засыпать от одного до шести туннелей, но так, чтобы из любой пещеры можно было добраться из- любой другой по оставшимся туннелям. Проигрывает тот кто не может сделать ход.

Запросить значение n.
Найти и сообщить, кто выигрывает при правильной игре, причем если выигрывает Гриша, то его первый выигрышный ход.

Пример: n = 4, ответ "Гриша", первый ход 2.


Задача 3. «Строка». 35 баллов.

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

Запросить строку (не более 120 символов).
Запросить значение k (k<100).
Найти и сообщить наименьшее возможное число перестановок для сбора k символов 1 в любом месте строки.

Пример: строка = 100110101, k = 3, ответ = 100110101, 100111001


Задача 4. "Разложение". 35 баллов.

Натуральное число n (n<100) можно представить различными способами в виде суммы натуральных чисел:
n=b1+b2+...+bk ; b1>=b2>=...>=bk

Запросить значение n.
Найти и сообщить количество разных способов разложения n на сумму натуральных чисел.

Пример: n = 3, ответ = 3 (3=3, 3=2+1, 3=1+1+1)

[The Godfather]

Олимпиада по информатике НГТУ 2007 год

Прочитать:

1 Два отрезка на плоскости заданы целочисленными координатами своих концов в декартовой системе координат.
Требуется определить, существует ли у них общая точка. Ограничения: координаты целые и по модулю не превосходят 10 000.
Требования к программе:
Ввод из файла segments.in. В первой строке содержатся координаты первого конца первого отрезка, во второй— второго конца первого отрезка, в третьей и четвертой — координаты концов второго отрезка. Вывод в файл segments.out. Выводится слово «Yes», если общая точка есть, слово «No» — в противном случае.
ПРИМЕР :
Ввод 1 Ввод 2
00 00
10 10
10 20
11 30
Вывод 1 Вывод 2
Yes No


2. Заданы вес Е пустой копилки и вес F копилки с монетами. В копилке могут находиться монеты N видов; известны ценность Рi каждого вида монет и вес Wi одной монеты. Найти минимальную и максимальную суммы денег, которые могут находиться в копилке.
Ограничения: 1 < Е< F< 10 000,1 < N < 500,1 < Рi < 50 000,
1 < Wi < 10 000, все числа целые, время 2 с.
Требования к программе:
Ввод из файла piggy.in. В первой строке числа Е и F, во второй -число N, в следующих N строках — по два числа, Р, и Wi. Вывод в файл piggy.out. Выводятся два числа через пробел- минимальная и максимальная суммы. Если копилка не может иметь точно заданный вес при условии, что она наполнена монетами заданных видов, — вывести "This is impossible".
ПРИМЕР:

Ввод 1 Ввод 2 Ввод 3
1000 1100 1000 1010 1000 2000
2 2 1
1 1 6 3 10 3
5 2 2 2
Вывод 1 Вывод 2 Вывод 3
100 250 10 16 This is impossible


3 Два круга заданы координатами центров в прямоугольной декартовой системе координат и радиусами. Найти площадь их пересечения. Ограничения: во входных данных числа вещественные и по модулю не превосходят 1000.
Требования к программе:
Ввод из файла circarea.in. В первой строке находятся шесть вещественных чисел через пробел— координаты центров и радиусы двух кругов: х1, у1, г1, х2, у2, г2.
Вывод в файл circarea.out. Вывести вещественное число
с двумя знаками после запятой— площадь пересечения.
ПРИМЕР:
Ввод
20.0 30.0 15.0 40.0 30.0 30.0
Вывод
608.37


4. Определим правильные скобочные выражения так:
1. Пустое выражение - правильное.
2. Если выражение S правильнее , то (S) и [s] также правильные.
3. Если выражения А и В правильные, то АВ также правильное.
Дана последовательность скобок (, ), [ и ]. Требуется найти самое короткое правильное выражение, в котором данная последовательность является подпоследовательностью, т.е. такое, из которого можно вычеркнуть некоторые символы (возможно, ноль) и получить исходную последовательность не меняя порядок оставшихся.Ограничения: исходная последовательность содержит не более 100 скобок.
Требования к программе;
Ввод из файла bracket3.in. В первой строке символы (,), [ и ] без пробелов.
Вывод в файл bracket3.oui: Выводится искомая последовательность скобок без пробелов.

Пример 1

[The Godfather]

2004-2005 г., Школьная олимпиада, г. Н.Новгород

Задача 1. "Репьюниты". 15 баллов

Репьюниты, десятичные натуральные числа, состоящие только из единиц, обозначаются Rn, где n - число единиц в записи числа.
Для заданных целых чисел n и k (n + k < 3000) подсчитать, какие цифры и сколько раз встречаются в записи произведения Rn * Rk.
Пример: если n = 2, k = 5, то цифра 1 встречается 2 раза, цифра 2 - 4 раза.

Задача 2. "Робот". 20 баллов

Робот перемещается по неограниченному клетчатому полю, ориентированному по сторонам света. Программа робота состоит из символов n - шаг на север, s - шаг на юг, w - шаг на запад, e - шаг на восток.
Для перехода робота, заданного программой (не больше 128 символов), определить количество посещенных им клеток.
Например: программа nnwsse, ответ - 6.

Задача 3. "Кучки". 20 баллов

Имеется кучка из n (n < 32000) орехов. Разрешается разделить ее на две. Каждую из полученных кучек можно также разделить на две. За каждое деление кучки на две неравные полагается штраф - 1 мрот. Деление продолжается до тех пор, пока кучки не будут содержать по одному ореху.
Для введенного с клавиатуры числа орехов определить наименьший возможный штраф за деление.
Например, если n = 100, то наименьший штраф s = 2 мрот.

[The Godfather]

2005-2006г., Школьная олимпиада, г.Н.Новгород

Задача 1. "Прямоугольник". 15 баллов

Прямоугольник, стороны которого выражены целыми числами m и n (m,n < 100), разделен на квадраты размером 1х1. Составить программу, которая находит число квадратов, пересекаемых диагональю прямоугольника (перескает, только тогда, когда делит его на две части).
Пример 1: m = 5 n = 3, ответ = 7.
Пример 2: m = 10 n = 6, ответ = 14.

Задача 2. "Делимость". 20 баллов

Два числа вводятся двоичным представлением своих цифр, причем первое содержит не более 72 двоичных знаков, а второе, меньшее, - не более 14. Проверить, делится ли первое число на второе.
Пример 1: 11100111000111000111111111:111 - делится
Пример 2: 1110010100011100011111111:1110 - не делится

Задача 3. "Кенгуру". 25 баллов

Перед кенгуру дорожка длиной k у.е., по которой она может двигаться прыжками только вперед. Длина прыжка кенгуру 1, 2, 3, 4, 5 или 6 у.е. Найти число различных вариантов преодоления дорожки, если k < 32.
Пример 1: k = 5, ответ = 8
Пример 2: k = 8, ответ = 125

[The Godfather]

2006-2007 уч. год, Школьная олимпиада, г. Н.Новгород

Задача 1.«Многоугольник». 15 баллов

Вектор ОА( 100, 0) поворачивается относительно начала координат на заданный угол а градусов (а - целое, 0 < а < 180) по часовой стрелке. Новый вектор также поворачивается и т.д. Концы вектора рассматриваются как вершины многоугольника. Сколько у полученного многоугольника вершин?

Пример 1: a = 30, ответ = 12
Пример 2: a = 27, ответ = 40

Решение на Паскале:

{Задача 1.«Многоугольник». 15 баллов. 2006-2007 уч. год, Школьная олимпиада, г. Н.Новгород
Вектор ОА( 100, 0) поворачивается относительно начала координат на заданный угол а градусов (а - целое, 0 < а < 180) по часовой стрелке. Новый вектор также поворачивается и т.д. Концы вектора рассматриваются как вершины многоугольника. Сколько у полученного многоугольника вершин?}
program abc;
uses crt;
label kon;
var a,s,x:integer;
begin
clrscr;
writeln ('Input a');
readln(a);
x:=0;
s:=a;
if (a=0)OR(a>180) then begin
writeln ('No solutions');
goto kon;
end;
while NOT (s mod 360 =0) do begin
x:=x+1;
s:=s+a;
end;
writeln ('Kolvo uglov ',x+1);
kon:readln;
end.

Задача 2. «Остаток». 20 баллов

На доске подряд выписаны натуральные числа от 1 до n (n < 1000000000). Сначала с доски стерли все нечетные числа. Из оставшихся чисел стирают все числа, оказавшиеся на четных местах. Затем снова стирают все числа, оказавшиеся на нечетных местах, и так далее, пока не останется одно число. Какое?

Пример 1: n = 6, ответ = 6
Пример 2: n = 100, ответ = 86

Решение на Паскале. Вариант 1:

{2006-2007 уч. год, Школьная олимпиада, г. Н.Новгород
Задача 2. «Остаток». 20 баллов
На доске подряд выписаны натуральные числа от 1 до n (n < 1000000000). Сначала с доски стерли все нечетные числа. Из оставшихся чисел стирают все числа, оказавшиеся на четных местах. Затем снова стирают все числа, оказавшиеся на нечетных местах, и так далее, пока не останется одно число. Какое?
Пример 1: n = 6, ответ = 6
Пример 2: n = 100, ответ = 86}
program abc;
uses crt;
label kon;
var i,n,n2,a,d:longint;
begin
clrscr;
writeln ('Input a');
readln (a);
n:=1;
d:=0;
n2:=2;
i:=1;
kon:d:=d+1;
if (d mod 2)=1 then begin
n:=n+i;
n2:=n2+4*i;
end;
i:=i*2;
if ((a>n)AND(a<n2))OR(a=n) then writeln ('Останется число ', n)
else if a=n2 then writeln ('Останется число ',n2)
else if a=1 then writeln ('Останется число 1')
else goto kon;
readln;
end.

Решение на Паскале. Вариант 2:

{2006-2007 уч. год, Школьная олимпиада, г. Н.Новгород
Задача 2. «Остаток». 20 баллов
На доске подряд выписаны натуральные числа от 1 до n (n < 1000000000). Сначала с доски стерли все нечетные числа. Из оставшихся чисел стирают все числа, оказавшиеся на четных местах. Затем снова стирают все числа, оказавшиеся на нечетных местах, и так далее, пока не останется одно число. Какое?
Пример 1: n = 6, ответ = 6
Пример 2: n = 100, ответ = 86}
program abc;
uses crt;
label kon,konec;
var i,i2,n,n2,a,b,d:longint;
begin
clrscr;
writeln ('Input a');
readln (a);
if a=1 then begin
writeln ('Bla 1');
goto konec;
end;
n:=1;
d:=0;
n2:=2;
i:=1;
kon:d:=d+1;
if (d mod 2)=1 then begin
n:=n+i;
n2:=n2+4*i;
end;
i:=i*2;
if ((a>n)AND(a<n2))OR(a=n) then writeln ('Bla ', n)
else if a=n2 then writeln ('Bla ',n2)
else goto kon;
konec:readln;
end.

Задача 3. «Дроби». 25 баллов

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

Пример 1: Числитель = 2, Знаменатель = 3, ответ 2/3 = 1/2 + 1/6
Пример 2: Числитель = 500 Знаменатель = 1001, ответ 500/1001 = 1/3 + 1/7 + 1/43 + 1/18447

[The Godfather]

1996-1997 уч. год, Школьная олимпиада, г. Н.Новгород

Прочитать:

Задача 1.«Площадь». 10 баллов

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

Формат входных данных
Четыре строчки. В каждой по два целых числа - координаты очередной точки.

Пример
Входной файл	20 20
	40 40
	60 60
	80 80
Выходной файл	1600

Задача 2. «Детали». 10 баллов

Имеется N одинаковых деталей каждую из которых нужно обработать на одном из трех станков, выполняющих одну и туже операцию. Производительность первого станка - 1 деталь за 2 минуты, второго - деталь за 5 минут, третьего - деталь за 7 минут. Требуется распределить детали по станкам так, чтобы время обработки всей партии было бы наименьшим.

Формат выходных данных
В первой строке вывести время обработки. Далее в 3-х строчках вывеси количество деталей обработанных каждым станком и через пробел время работы станка.

Пример
Входной файл	200
Выходной файл	238
	119 238
	47 235
	34 238

Задача 3. «Шахматная доска». 10 баллов

По координатам двух клеток шахматной доски определить окрашены ли они одинаково.

Пример	1	2
Входной файл	с5 а2	g5 b4
Выходной файл	NO	YES

[The Godfather]

2000-2001 уч. год, Школьная олимпиада, г. Н.Новгород

Прочитать:

Задача 1.«Сумма». 10 баллов.

Дано натуральное число N. Найти число K, которое является перевернутым N. Вывести N+K.

Пример: N = 1879, ответ = 11660

Решение на Паскале:

{2000-2001 уч. год, Школьная олимпиада, г. Н.Новгород
Задача 1.«Сумма». 10 баллов.
Дано натуральное число N. Найти число K, которое является перевернутым N. Вывести N+K.
Пример: N = 1879, ответ = 11660}
{Программа вычисляет сумму числа и числа, обратного ему}
program abc;
uses crt;
var a,a1,b,i:integer;
begin
clrscr;
writeln ('Input number ');
read(a);
a1:=a;
i:=0;
while not(a=0) do begin
i:=i*10+ a mod 10;
a:=a div 10;
end;
b:=a1+i;
writeln ('Summa 4isel ravna ',b);
readln; readln
end.

Задача 2. «Телефонизация». 15 баллов.

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

Формат входных данных
В единственной строке входного файла записано N (N<=100) чисел. Каждое i-ое число - это расстояние между i-м и (i+1)-м домом.

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

Пример
Входной файл	100 50 150 40 80
Выходной файл	810 3

Задача 3. «Стая». 20 баллов.

Летела стая одноголовых сороконожек и трехголовых драконов. Охотник сосчитал их общее количество голов G и ног N. По этим данным требуется определить число ног у одного дракона, сколько летело сороконожек и сколько драконов. Если задача имеет несколько решений, то вывести каждое из них, если охотник ошибся - вывести 0.

Формат входных данных
Во входном файле записаны числа G и N соответственно. Числа не превосходят 1000.


Формат выходных данных
В первой строке вывести число решений K. Далее в K строках вывести каждое решение в любом порядке. Формат решения. Три числа: первое - число ног у дракона, второе - число сороконожек и последнее - число драконов.

Пример
Входной файл	30 600
Выходной файл	2
	20 12 6
	45 6 8

2001-2002 уч. год, Школьная олимпиада, г. Н.Новгород

Прочитать:

Задача 1.«Параллелограмм». 10 баллов.

Найти координаты вершин параллелограма ABCD, если извесны координаты точек M - середина AB, N - середина BC, K - середина AD. Если такого параллелограма не существует, то сообщить об этом.

Формат входных данных
В первой строке входного файла записаны координаты точки M, во второй - точки N, в треьей - точки K. Координаты записаны через пробел в стандартном виде (x y). Все числа во входном файле целые и не превосходят по модулю 1000.

Формат выходных данных
В первой строке вывести координаты точки A, во второй - B, в третьей - C и в последней - D. Координаты разделять пробелом. Если решения нет, то вывести без кавычек "No Solution"

Пример
Входной файл	Выходной файл
1 2	0 0
5 4	2 4
3 0	8 4
	6 0

Задача 2. «Разность». 15 баллов.

Даны два натуральных числа n и m (уменьшаемое и вычитаемое). Каждое из них содержит 100 или меньше цифр. Найти их разность.

Пример 1: n = 6543211234567890, m = 333333333333, ответ = 6542877901234557
Пример 1: n = 333333333333, m = 6543211234567890, ответ = -6542877901234557

Задача 3. «Таблица». 20 баллов.

Квадратная таблица 3*3 заполнена числами 1 и 0. За один ход разрешается выбрать одну из строк (или один из столбцов) и земенить в выбранной строке (в столбце) каждый из элементов на противоположный (0 на 1, а 1 на 0). Играющий стремится сделать несколько ходов так, чтобы в итоге в таблице осталось как можно меньше чисел 1.
Найдите минимальное число элементов 1, которое может получиться в результате таких преобразований.

Формат входных данных
Дана матрица 3*3. Числа идут без пробелов по три в одной строке. Всего во входном файле 3 строки.

Пример 1:
111
010 - ответ 1
101

Пример 2:
011
101 - ответ 2
110

2002-2003 уч. год, Школьная олимпиада, г. Н.Новгород

Прочитать:

Задача 1.«Шашки». 10 баллов.

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

Формат входных данных
В первой строке входного файла записано число N - количество цветов. Далее в N следующих строках записано по числу - количество шашек i-го цвета.


Формат выходных данных
Если требуемое размещение не существует, вывести "NO" (без кавычек). Иначе вывести в первой строке "YES" (без кавычек), а во второй - пример размещения по следущему формату: вывести через пробел K чисел; на i-ом месте должно стоять число - номер цвета.

Пример
	Входной файл	Выходной файл
Пример 1	3 7 15 4	NO
Пример 2	4 7 15 4 5	YES 2 1 2 1 2 1 2 1 2 1 2 1 2 4 2 4 2 4 2 4 2 4 2 3 2 3 2 3 2 3 1

Задача 2. «Волшебная яблоня». 15 баллов.

На волшебной яблоне росли апельсины (A штук), бананы (B штук) и сливы (C штук), а яблоки еще не выросли - не сезон.
Известно, что если сорвать и съесть подряд апельсин и банан (именно в таком порядке), то на ней вырастет одна слива. Если сорвать и съесть подряд в любом порядке банан и сливу, то вырастет апельсин. А есть сорвать и съесть подряд три банана, то на волшебной яблоне вырастают два банана. При этом, если будет съедено подряд четыре банана, то вырастет четыре банана, пять бананов - шесть и так далее.
Вам дана последовательность поедания фруктов. Необходимо сообщить число апельсинов, бананов и слив, оставшихся на волшебной яблоне после поедания.

Формат входных данных
В первой строке входного файла записаны через пробел числа A, B, C. Все числа не превышают 100. Во второй строке без пробелов записана последовательность поедания фруктов. a-апельсин, b-банан, c-слива. Длина последовательности не превышает 100 символов.

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

Пример: a = 10, b = 8, c = 12, последовательность = bbbabacbccbacacc, ответ = 9, 4, 7

Задача 3. «Переход». 25 баллов.

Прямоугольная таблица 16*25, приведенная ниже, представляет собой карту участка моря с группой отсровов. Клетка "." соответствует морю, а клетка "#" - острову. Судно необходимо перевести из точки с координатами (x1,y1) в точку (x2,y2), где x - номер строки, y - номкр столбца таблицы (целые числа от 1 до 16 и от 1 до 25 соответственно). За один шаг разрешается переместиться в любую соседнюю клетку, не являющуюся частью острова. Соседними клетками считать такие, у которых есть хотя бы одна общая точка.
Найти число минимального количества шагов для достижения цели, считая, что происходит это на приведенном ниже участке моря.



Формат входных данных
Во входном файле через пробел записано четыре числа - x1, y1, x2, y2. Гарантируется, что данные точки находятся в море.

Пример 1: x1 = 3, y1 = 23, x2 = 12, y2 = 5, ответ = 24

[FlaXX]

Что-то ты разошёлся прям, это вообще зачем? оО

[The Godfather]

FlaXX, ну во первых тексты этих задач собраны в кучу буквально на 2-3 сайтах. И фиг найдешь....
Во вторых сами задачи то хорошие, можт кому пригодятся
Ну и в третьих - можно обмениваться решениями

[veNto]

какой кошмар..это не для моих мозгов

[The Godfather]

2003-2004 уч. год, Школьная олимпиада, г. Н.Новгород

Задача 1.«Третий». 10 баллов.

Даны числа A1,A2,...,AN. Найти порядковый номер третьего по величине числа.

Формат входных данных
В первой строчке записано число N (0<N<=100). Во второй строчке записаны подряд через пробел числа A1,A2,...,AN. Любое |Ai|<=1000.

Пример: N = 10, последовательность = 1 6 7 -51 -10 -16 71 53 11 -13, ответ = 9

Задача 2. «Сумма». 15 баллов.

Для числа N (Не более 50 цифр) подсчитывается сумма его цифр. Если результат превышает 9, то для результата сново подсчитывается сумма цифр и так далее, пока результат не станет меньше 10. Выполнить расчет для N.

Пример: N = 3247598, ответ = 2

Задача 3. «Маршруты». 20 баллов.

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

Пример: N = 3, M = 4, ответ = 10

Добавлено вскоре

veNto, ну это ж школьные задачки

[veNto]

The Godfather, нее, у меня не математический склад ума! к сожалению или к счастью - не знаю!
я наверно даже вдумывацца не хочу

[The Godfather]

2006-2007 уч. год, Городская олимпиада, г. Н.Новгород

Прочитать:

Задача 1.«Бассейны и трубы». 100 баллов.

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

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

Формат входных данных
В первой строке указано количество бассейнов N (1 <= N <= 100). Далее следуют N строк, содержащих информацию о бассейнах. Для каждого бассейна, начиная с 1-го и кончая N-ым, указана разница между дополнительным втекающим и вытекающим потоком - целое число, не превышающее по модулю 30 000 (положительное число соответствует втеканию, отрицательное - вытеканию).

На следующей строке входного файла находится число труб M, (0 <= M <= 4950). В последующих M строках находится описание труб: для каждой трубы указаны два числа - номера бассейнов, которые труба соединяет. Между каждой парой бассейнов есть не более одной трубы, трубы не могут соединять бассейн с самим собой.

Формат выходных данных
Если решение существует, выведите в выходной файл M строчек, по числу на строку. Для каждой трубы в том же порядке, как во входном файле, должно быть указано целое число - поток воды через неё. Положительным числом обозначается поток от бассейна, указанного первым во входном файле, ко второму; отрицательным - обратный поток. Потоки в выходном файле не должны превышать 2 000 000 000.

Если возможно несколько решений, можно выводить любое из них.

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

Пример:


Задача 2. «Батон». 100 баллов.

Несколько школьников решили отпраздновать Новый Год вместе. Для празднования они закупили гору продуктов, и в том числе батон колбасы. Количество еды было настолько велико, что об этом батоне вспомнили только через два с лишним часа после боя курантов. И, конечно, в честь столь знаменательного момента времени школьники решили как можно быстрее съесть этот батон. Но на этом пути их поджидала одна трудность: батон надо разрезать на N (по числу школьников) равных частей, причём как можно быстрее, чтобы не упустить момент. Для этой цели нашёлся очень длинный и острый нож, который смог бы при необходимости разрезать даже N батонов колбасы за один раз. Кроме того, нашлась линейка, с помощью которой можно отмерять любую наперёд заданную часть батона, выбирая место будущего разреза с достаточной точностью. Батон колбасы оказался настолько тонким и длинным, что резать его имело смысл только перпендикулярно его оси.
Конечно, школьники быстро сообразили, что для ускорения процесса можно резать несколько кусков батона одновременно. Батон колбасы оказался прямым и негнущимся, поэтому сэкономить число действий за счёт складывания батона перед разрезанием нельзя. Им осталось определить минимальное количество движений ножом, с помощью которых можно осуществить их намерения. Помогите им в этом.
В процессе разрезания школьник может приложить некоторые имеющиеся у него куски батона колбасы друг к другу как он хочет (напомним, что батон очень длинный и тонкий, поэтому имеет смысл прикладывать куски только параллельно друг другу), и одним движением ножа разрезать все куски. Изначально у школьника есть один кусок — сам батон; в конце у него должно быть N одинаковых по длине кусков (каждый длиной в 1/N начального батона).

Например, разрезать батон на 6 частей (N = 6) школьник может всего за 3 действия ножом:
1. Отмерить 1/3 длины всего батона и в этом месте разрезать батон.
2. Больший из получившихся кусков разрезать пополам (в итоге получаются три куска равной длины).
3. Приложив их вплотную друг к другу, выровнять концы и разрезать все три куска посередине, в результате чего получится шесть одинаковых кусков.

Чтобы разрезать батон на 5 равных частей (N = 5), также необходимо 3 действия ножом, например:
1. Отмеряем 2/5 длины батона и разрезаем батон в этом месте.
2. Получившиеся куски складываем вместе так, чтобы середина меньшего куска находилась против трети большего, и разрезаем их так, чтобы меньший разрезать пополам, а больший — в отношении 1 : 2. Получаем три куска длиной в 1/5 всего батона и один—длиной 2/5.
3. Больший из имеющихся кусков разрезаем пополам и получаем пять одинаковых кусков.

Формат входных данных
Во входном файле находится одно число N (1 <= N <= 2 000 000 000).

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

Пример: N = 6, ответ = 3

Задача 3. «А ты купи коня!». 100 баллов.

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

Среди множества моделей, предложенных экономистами для описания различных видов рынков, вашему другу больше всего понравилась знаменитая «модель конного рынка» Е. фон Бём-Баверка. Эта модель состоит в следующем: в базарный день на рыночной площади собрались N продавцов и М покупателей. У каждого продавца есть одна единица товара (принято говорить о конях); каждый покупатель хочет купить одного коня. С точки зрения покупателей, все продавцы и все кони абсолютно одинаковы, т.е. покупателям всё равно, у кого покупать (значение имеет только цена). Аналогично, с точки зрения продавцов все покупатели одинаковы: продавцам всё равно, кому продавать (опять-таки, значение имеет только цена). Но субъективные оценки товара различаются:
Каждый продавец заранее определил для себя цену, дешевле которой он продавать ни в коем случае не будет: i-ый продавец готов продавать коня по цене Si и выше.
Аналогично, каждый покупатель заранее определил для себя цену, дороже которой он покупать ни в коем случае не будет: i-ый покупатель готов покупать коня по цене Bi и ниже.

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

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

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


Формат входных данных
В первой строке входного файла находятся два целых числа N и М (1 <= N,M <= 1000) — количество продавцов и покупателей соответственно. На второй строке находятся N целых чисел s1, s2, ..., sN, а на третьей строке — М целых чисел Bi, b2, ..., bM; эти числа положительны и не превосходят 2 000 000 000.

Формат выходных данных
Если в соответствии с пп. 1—4 может произойти хотя бы одна сделка, выведите в выходной файл два числа: сначала нижнюю границу диапазона, потом — верхнюю. Если не произойдёт ни одной сделки, выведите в выходной файл одну строку "No solution" (без кавычек).

Пример:


Задача 4.«Строительство в городе». 100 баллов.

Ограничение по времени - 4 с.

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

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

Формат входных данных
На первой строке входного файла находятся два числа: целое N (1 <= N <= 800) и вещественное R (0 < R <= 10^6) — количество уже существующих зданий и радиус торгово-развлекательного комплекса.
Далее следуют N строк, на i-й из которых находятся три числа хi, уi и ri — координаты центра и радиус i-го здания. Координаты не превосходят 10^6 по модулю, радиусы положительны и не превосходят 106.
Система координат введена таким образом, что центр города имеет координаты (0,0).

Формат выходных данных
В выходной файл выведите два числа: координаты центра торгово-развлекательного комплекса. Выданная точка должна удовлетворять следующим требованиям:
для каждого i расстояние от выданной точки до центра i-го здания должно быть больше, чем ri + R — 10^-3;
расстояние от выданной точки до начала координат должно отличаться от оптимального не более чем на 10^-3.

Пример:
2 1.0
-1 0 1.0 - ответ 0 1.7320508075688772
1 0 1

Задача 5 «Кофе». 100 баллов.

В Научно-образовательном центре ИПФ РАН недавно заново покрасили стены. Всё было бы ничего, если бы на этаж ниже не стоял кофейный аппарат: особую опасность для недавно покрашенных стен представляют школьники, пьющие кофе, поскольку иногда они разливают кофе и он забрызгивает стены, находящиеся от школьника на расстоянии, меньшем некоторого заданного R (если расстояние до стены равно R, она не пачкается). Для борьбы с этой напастью в одной из секретных лабораторий ИПФ РАН разрабатывается система, которая в момент разливания школьником кофе регистрирует его координаты (x, у) и радиус разлёта кофе R. Предполагается, что она будет устанавливаться во всех свежепокрашенных комнатах, а данные наблюдений будут записываться в единый журнал. Каждая комната считается прямоугольником ненулевой площади со сторонами, параллельными осям координат.

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

Формат входных данных
Во входном файле приведено содержание журнала разливания кофе. В первой строке указано число записей в журнале N (1 <= N <= 20). Во второй и последующих строках приведены сами записи, по одной записи на строку. Каждая запись представляет собой 7 чисел х1, y2, x2, y2, R, x, y, разделённых пробелами. Здесь (x1, y1), (x2, y2) — координаты двух противоположных углов комнаты, в которой зафиксировано данное разливание кофе, R — радиус разлёта кофе, (х, у) — координаты точки внутри комнаты, в которой кофе был разлит. Все координаты во входном файле целые и не превосходят по модулю 10 000, радиус R тоже целый, 0 <= R <= 10 000.

Формат выходных данных
В выходом файле должно быть N строк. На i-й строке должно быть выведено "yes", если при i-м разливании кофе испачкало стену, иначе должно быть выведено "no".

Пример
Входные данные	Выходные данные
3
-2 1 10 9 1 0 2	no
3 5 16 -3 2 10 0	no
3 -6 5 20 2 4 13	yes

[DJRust]

лучше б задача+решение!

[The Godfather]

DJRust, напиши решение - добавим к задаче

А пока все решения, которые я буду писать - это мои решения, не копипаст с инета

[Axel2150]

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