Мой сайт
Пятница, 29.03.2024, 03:35
» Меню сайта
» Категории раздела
Лабораторные, практические и контрольные работы [13]
Олимпиадные работы [1]
тексты олимпиад разного уровня
Работы учащихся [8]
Материалы к урокам (презентации) [0]
Видеоуроки [1]
Поурочное планирование [3]
ФГОС ООО [0]
Промежуточная аттестация [0]
Билеты, тесты и письменные контрольные работы для промежуточной аттестации
» Наш опрос
Оцените мой сайт
Всего ответов: 959
» Статистика
» Форма входа
Главная » Файлы » Олимпиадные работы

Задания олимпиадной работы для 10 - 11 классов (2009)
[ Скачать с сервера (80.5 Kb) ] 16.11.2009, 12:26
 
ЗАДАНИЯ  
для II этапа Всероссийской олимпиады школьников 
по ИНФОРМАТИКЕ


Разработчики:
доцент ИПКРО
Зубков О.В.,
доцент ИПКРО
Петухин В.А.

2009 г.


Рекомендованные задачи расставлены в порядке возрастания их сложности. Для проведения олимпиады необходимо выбрать из предложенных шести задач три или четыре задачи. Для разных параллелей могут быть предложены как полностью одинаковые комплекты задач, так и чем-то отличающиеся.
Каждую задачу рекомендуется оценивать из 100 балов. По каждой задаче предлагается 10 тестов. Сумма баллов, которую участник получает за задачу, складывается из суммы баллов пройденных тестов. Сумма баллов всех тестов должна быть равна 100. Рекомендуется для всех тестов устанавливать одно и то же количество баллов (если тестов 10 - каждый "стоит" 10 баллов).
Тесты и ответы на них для каждой задачи лежат в папках "Задача 1", "Задача 2", и т.д. в соответствии с номером задачи. В этих папках файлы, содержащие тесты, имеют имена "test1.txt", "test2.txt", и т.д., а файлы, содержащие ответы - "otvet1.txt", "otvet2.txt", и т.д. в соответствии с номером теста.
При проверке решений участников рекомендуется установить ограничение по времени 1 секунда для прохождения одного теста для каждой задачи. Об установленном ограничении участники олимпиады должны быть оповещены перед началом олимпиады.
 
Задача 1. Большой дом. (100 баллов)

В доме m подъездов, n этажей и l квартир на каждом этаже (в одном подъезде). Вам требуется по номеру квартиры k определить, в каком подъезде и на каком этаже она находится.
Входные данные
В единственной строке входных данных через пробел записаны числа m, n, l, k (все они не превосходят 1000).
Выходные данные
 Программа должна вывести через пробел два числа – номер подъезда и номер этажа. В случае, если в доме нет указанной квартиры, следует вывести два нуля.

Пример входных данных: Выходные данные для примера:
4 5 3 22 2 3


Задача 2. Заборостроитель. (100 баллов)  

Г-н Чудаков купил дачный участок, по форме представляющий собой ничем не огороженный квадрат со стороной N. Посадив овощи, г-н Чудаков стал ждать урожая. Каково же было его негодование, когда ночью известный хулиган Вася совершил набег на грядки. Г-н Чудаков срочно завез на участок множество столбов одинакового диаметра D, и для начала вкопал четыре из них по углам участка. После этого несколько раз (а может и ни разу) повторялась следующая картина: ночью приходил хулиган Вася, и, если мог, проникал на участок г-на Чудакова, совершал там разбойное нападение на овощи, после чего уходил спать. Если на следующий день г-н Чудаков обнаруживал, что забор не спас, то он ровно посередине между каждыми двумя столбами по периметру участка вкапывал еще один, уменьшая, таким образом щели, в которые мог протиснуться хулиган. В зависимости от размера стороны участка N, диаметра столбов D и толщины хулигана T, у этой истории может быть одно из двух окончаний: 
либо однажды ночью хулиган обнаружит, что не может протиснуться ни в одну из щелей между столбами, и тогда г-н Чудаков может вздохнуть спокойно;
либо однажды днем г-н Чудаков обнаружит, что он не может вкопать между старыми столбами новые, но оставшиеся щели все еще велики…
Требуется по заданным X, D, и T определить, сколько столбов сможет вкопать г-н Чудаков и чем закончится эта история.

Входные данные
Во входном файле INPUT.TXT содержится три натуральных числа N, D, и T через пробел. 2N10000, 1DN, 1TN.

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

Пример INPUT.TXT: OUTPUT.TXT для примера:
6 2 1 8
 NO
Пример INPUT.TXT: OUTPUT.TXT для примера:
5 2 1 8
 YES

Задача 3.Лыжные гонки. (100 баллов)  
В лыжных гонках участвуют n лыжников. На старте им раздали номера от 1 до n. Гонки проводятся по кольцевой трассе – в два круга. Вася Сидоров, наблюдая за гонками, записал, в каком порядке лыжники завершили первый круг, и в каком порядке закончили гонку. Помогите Васе подсчитать минимальное количество обгонов, которые были произведены на протяжении гонки. (Обгон заключается в том, что два рядом бегущих лыжника меняются местами. Если один лыжник обгоняет сразу нескольких, это считается не за один обгон, а по количеству обогнанных лыжников.)
Входные данные
В первой строке входных данных содержится количество лыжников n (n < 1 000). Во второй строке задаётся порядок прохождения лыжниками первого круга – через пробел записаны номера лыжников в том порядке, в котором они завершили первый круг. В третьей строке через пробел записаны номера лыжников в том порядке, в котором они завершили гонку.
Выходные данные
 Программа должна вывести минимально возможное количество обгонов, совершенное всеми лыжниками на протяжении гонки.

Пример входных данных: Выходные данные для примера:
4 6
1 2 3 4
4 3 2 1
 

Задача 4. Треугольники в квадрате. (100 баллов)  
.
Большой квадрат разбит линиями, параллельными его сторонам на N2 одинаковых маленьких квадратов, в каждом из которых проведена диагональ. Все диагонали имеют одинаковое направление. Требуется по N определить, сколько треугольников содержится на таком рисунке. Учитывать следует все треугольники, как самые маленькие, так и большие, состоящие из меньших.

Входные данные
Во входном файле INPUT.TXT содержится число N – количество маленьких квадратов, расположенных на стороне большого. 1N1400.

Выходные данные
 В выходной файла OUTPUT.TXT нужно выдать искомое число треугольников, которые можно встретить на рисунке.

 
Пример INPUT.TXT: OUTPUT.TXT для примера:
3 28

Задача 5. Правильная скобочная последовательность. (100 баллов)  

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

Входные данные
В первой строке входных данных содержатся число n (n < 1 000 000). Во второй строке – n символов, задающих скобочную последовательность.
Выходные данные
Программа должна в первой строке вывести длину найденной максимальной скобочной последовательности, а во второй – саму найденную скобочную последовательность (только символы скобок без пробелов).
 
Пример входных данных: Выходные данные для примера:
9 8
((()()()) (()()())


Задача 6. Город перекрестков. (100 баллов)  

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

Входные данные
Во входном файле INPUT.TXT содержится карта перекрёстков города. В первой строке содержатся два числа N — число кварталов с севера на юг и M — число кварталов с запада на восток (1 N, M 50). Точка A находится на северо-западе, точка B на юго-востоке. Далее в 2*N+1 строках содержится описание разрешённых направлений движения. Улицы города запад-восток нумеруются с севера на юг от 1 до N+1. В нечётных строках с номером 2s-1 содержится по M символов без пробела, указывающих возможное движение по отрезкам улицы запад-восток с номером s, в чётных строках с номером 2s по M+1 символов, указывающих возможное движение по отрезкам улиц север-юг между улицами запад-восток с номерами s и s+1. Движение на север, юг, запад, восток обозначается буквами n, s, w, e соответственно.

Выходные данные
 В первую строку выходного файла OUTPUT.TXT нужно выдать число отрезков в самом коротком маршруте из точки A в точку B. Во вторую строку нужно выдать описание этого маршрута в виде последовательности символов n, s, w, e без пробелов. Если кратчайших маршрутов несколько, выдать любой. Если маршрута нет, вывести 0.

Пример INPUT.TXT(см. рис.): OUTPUT.TXT для примера:
4 5 13
eweee sseeennessess
ssnnss 
wwwwe
sssnsn
eeewe
snsnss
eweww
nnssns
wweew
 
Комментарии 
Задача №1 (Большой дом)
Сначала надо проверить, что квартира есть в доме. То есть k>0 и k  p × n × l.
Для нахождения подъезда надо определить, сколько подъездов p расположено до искомой квартиры. Для этого k-1 (количество квартир до искомой) надо нацело разделить на количество квартир в подъезде - n × l. Теперь можно найти номер квартиры в подъезде: kp = k-(p × n × l). Этаж находится по такой же схеме: kp-1 делим нацело на l – получается количество этажей q до квартиры. Ответ: подъезд = p+1, этаж = q+1.

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

Задача №3 (Лыжные гонки)
Для решения задачи достаточно провести сортировку номеров лыжников после первого круга в порядке окончательно занятых ими мест. Если мы выполняем сортировку методом пузырька, то количество обменов соседних элементов массива и будет равно количеству обгонов.
Для того, чтобы быстро определять место, на котором оказался лыжник в результате гонки, достаточно перед сортировкой создать соответствующий массив. Пусть k1 – последовательность номеров лыжников после первого круга, а k2 – окончательная последовательность. Тогда такой массив (res) можно заполнить с помощью следующего цикла:
  for i:=1 to n do res[k2[i]]:=i;
Теперь достаточно отсортировать методом пузырька элементы массива k1, сравнивая значения res[k1[i]] и подсчитывая количество перестановок.
  obgon:=0;
  for i:=1 to n-1 do
  for j:=1 to n-i do
 if res[k1[j]] > res[k1[j+1]] then begin
  inc(obgon);
  tmp:=k1[j]; k1[j]:=k1[j+1]; k1[j+1]:=tmp;
 end;


Задача №4 (Треугольники в квадрате)
Данную задачу можно решать очень разными способами, как опираясь на результаты предыдущих меньших задач (динамически), так и напрямую формулой. Наиболее удачной является формула K(n)=2*(12+22+32+…+N2). Эту формулу можно свернуть до вида K(n)=2*(N*(N+1/2)*(N+1))/3. Полезно помнить, что для больших N результат будет больше 109.

Задача №5 (Правильная скобочная последовательность)
Задача имеет достаточно очевидное решение с квадратичной сложностью. Оно заключается с переборе всевозможных (от 1 до n) позиций начала правильной скобочной последовательности. Для каждой такой позиции достаточно находить наибольшую скобочную последовательность, начинающуюся с этой позиции. Это можно осуществить с помощью подсчёта баланса скобок по мере увеличения отрезка, проверяемого на правильность скобочной последовательности. Под балансом скобок мы понимаем разность количества открывающихся и закрывающихся скобок. Если в какой-то момент баланс меньше нуля, значит последовательность уже неправильная и продолжать не надо. Иначе скобочную последовательность надо наращивать. Если баланс в какой-то момент равен нулю (при условии, что до этого он не был меньше нуля, а это условие алгоритм обеспечивает), то текущая скобочная последовательность – правильная и её надо проверить на максимальность длины.
Данный алгоритм можно записать таким образом (скобки содержатся в массиве s)
  max:=0; max1:=1; max2:=0;
  for i:=1 to n-1 do begin
 balans := 0;
 for j:=i to n do begin
  if s[j]=’(’ then inc(balans) else dec(balans);
  if balans=0 then if j-i+1>max then begin
  max:=j-i+1; max1:=i; max2:=j
  end;
  if balans<0 then break
 end;
  end;

Однако для больших n (около 1 000 000) время работы алгоритма будет слишком велико. Видно, что оптимизировать данный алгоритм можно за счёт сокращения объёма перебора начала скобочной последовательности. Так, если с позиции i до позиции j найдена правильная скобочная последовательность, то перебирать позиции от i+1 до j в качестве стартовых для скобочной последовательности нет смысла и можно продолжить с позиции j+1. Такая оптимизация значительно уменьшает скорость работы программы в большинстве случаев, однако, если во входной последовательности есть очень длинный отрезок так и не приводящий к отрицательному балансу, то количество операций всё равно будет пропорционально квадрату длины строки. Для того, чтобы избегать таких случаев можно осуществлять два варианта поиска – слева направо и, наоборот, справа налево. Для каждого направления в случае, если строка заканчивается раньше, чем будет найдена правильная скобочная последовательность, поиск можно прекращать. В результате получится линейный по сложности алгоритм.
Вот текст фрагмента программы, осуществляющего такой поиск слева направо. Для полного решения необходимо также провести подобный поиск справа налево.
max:=0; max1:=1; max2:=0;
i:=1;
cont:
 balans := 0;
 for j:=i to n do begin
  if s[j]=’(’ then inc(balans) else dec(balans);
  if balans=0 then if j-i+1>max then begin
  max:=j-i+1; max1:=i; max2:=j
  end;
  if balans<0 then begin
  i:=j+1;
  if i<n then goto cont;
  end;
 end;

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

Задача №6 (Город перекрестков )

Задача решается несколькими способами. 
1). Рекурсивным перебором в глубину. Перебираются все возможные маршруты. При больших N и M может не пройти по времени.
2) Динамическим программированием. Для каждого промежуточного перекрёстка находится кратчайший маршрут в него, для последнего перекрёстка ответ вывести в файл.
3) Алгоритмом Дейкстры поиска пути на графе

Категория: Олимпиадные работы | Добавил: shamshurina
Просмотров: 1017 | Загрузок: 245 | Комментарии: 1 | Рейтинг: 5.0/3
Всего комментариев: 1
1 shamshurina  
0
tongue surprised cry

Имя *:
Email *:
Код *:
» Поиск
» Друзья сайта
  • Официальный блог
  • Сообщество uCoz
  • FAQ по системе
  • Инструкции для uCoz
  • Copyright MyCorp © 2024Бесплатный конструктор сайтов - uCoz