школьная олимпиада по информатике 2011-2012 уч год

Олимпиада тапсырмаларын орындау -  2 сағат

8-9 -сынып

«Паскаль үшбұрышы»

   Паскаль үшбұрышы мынадай түрде құрылады. Бірінші жолы тең бірлікте бір саннан тұрады.  Келесілер бұрынғыдан бір саннан көп.  Бұл сандардан бірінші мен соңғысы тең,  бұрынғы  жолда тұрған және сандар, одан бұрынғы жолдың сол жағында тұрған, ал қалған барлығы санның суммасы ретінде саналады.

Кіріс мәліметтер.  Файлда INPUT.  N (0≤N≤30) бір санмен IN жазылған.

Шығу мәліметтері.  Файлда OUTPUT. N (0≤N≤30) бір санмен IN жазылған.

Ескерту. Паскаль үшбұрышындағы барлық сандар  Longint –ке кіреді.

Кіріс және шығыс файлындағы мысалдар:

INPUT. IN	OUTPUT. OUT
8	1 1  1 1  2  1 1  3  3  1 1  4  6  4  1 1  5  10  10  5  1 1  6  15  20  15  6  1 1  7  21  35  35  21  7  1

 

"Шегелер"

Тегіс тақтайға шегелер енгізілген. Кез келген екі шегені жіппен жалғауға болады. Жіппен екі шегені жалғау  талап етіледі, яғни әр шегеге бір жіптен байлану керек, ал барлық жіптің  жиынтыңының ұзындығы кем болады.

Кіріс мәліметтері. Бірінші жолда кіріс INPUT файлы. (2 ≤ N ≤ 100) N – шегелер саны IN берілген. Келесі жолда N саны – барлық шегелер координаты (теріс емес сандар, 1000-нан басым емес)

Шығыс мәліметтері. Шығыс файлында OUTPUT. OUT жеке санды шығару үшін керек – барлық жіптің ұзындығының кіші жиынтығы.

Кіріс және шығыс файлдары:

INPUT. IN	OUTPUT. OUT
5 4   10    0    12    2	6

 

 

 

«Үлгі және сөз»

Берілген үлгі бойынша берілген сөзді анықтау талап етіледі. Үлгі үлкен латын әріптерімен беріледі, "?"- кез келген белгі, "*" – кез келген реттілік белгілер (бос болса да).

Кіру мәліметтері: INPUT файлында. IN бірінші екі жолында үлгі мен сөз жазылған: бір жолда үлгі жазылған -  үлкен латын әріптері ретімен, "?" және  "*", басқасында – үлкен латын әріптерінен тұратын сөз (100 белгідентұратын жолдар)    

Шығу мәліметтері: OUTPUT файлында. OUT –тан YES шығару керек, егер де сөз дұрыс келсе және NO, немесе жоқ.

Кіріс және шығыс файлдары:

INPUT. IN	OUTPUT. OUT
ABBCDA A*CDA	YES

 

10-11 - сынып

"Үлгілер"

(a,...,z, A,...,Z) ағылшын әріптері  және "?" и "*" белгілерінен тұратын жол үлгі деп аталады. Әр "?" белгісін еркін әріпке, ал әр "*" белгісін – еркін (мүмкіндігінше бос орынға) реттік әріптерге өзгертуге болады.Кез келген жолға әріптерден, үлгілерден алуға болады. Екі үлгі бар. Жолдың кіші ұзындығын табу, немесе хабар беру, яғни ондай жол жоқ.

Кіру мәліметтері. Үлгінің тапсырмалары кіру файлы INPUT  бірінші екі жолында жазылған. Әр үлгінің ұзындығы 80 белгіден асып тұспеу керек.

Шығу мәліметтері. Шығуда  OUTPUT файлы. OUT кіші ұзындық жолын, екі үлгі бойынша немесе <-1> хабарын шығарады

Кіру және шығу файлдары:

INPUT. IN	OUTPUT. OUT
A* *B	AB

 

«Қалалар мен жолдар»

Патшалықта N қаласы болыпты, кейбіреуі жолдармен байланысқан. Патша өз мемлекетінде жолдарды инвентеризациялауды шешті. Бірақ, ол математиканы білмегендіктен, сіздерден жолдар санын санауды өтінді.

Кіру мәліметтері. INPUT файлында. IN жазылған N (0≤N≤100) санына. Келесі N  жолында  N саны бойынша жазылған, әрқайсысы 1 немесе 0 болып табылады. Неліктен, егер де  орныққан жері (i,j) квадратты матрицалар 1 тұрады, яғни i-ый немесе j-ый қала жолдармен байланысқан, егер де 0 байланыспаған.

Шығу мәліметтері. OUTPUT файлында. Патшалықтағы жол санын – OUT бір санын шығару.

Ескерту. Барлық жолдар екіжақты, i қаласынан j қаласына жол бар ма, бар болса j қаласынан i қаласына жол бар, яғни бұл да сол жол.

Кіру және шығу файлдары:

Время выполнения олимпиады  2 часа.

8 – 9 класс

"Треугольник Паскаля"

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

Входные данные. В файле INPUT. IN записано одно число N (0≤N≤30).

Выходные данные. В файл OUTPUT. OUT вывести N строк треугольника Паскаля.

Примечание. Все числа в треугольнике Паскаля при указанных ограничениях входят в Longint.

Пример входного и выходного файлов:

INPUT. IN	OUTPUT. OUT
8	1 1  1 1  2  1 1  3  3  1 1  4  6  4  1 1  5  10  10  5  1 1  6  15  20  15  6  1 1  7  21  35  35  21  7  1

 

"Гвоздики"

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

Входные данные. В первой строке входного файла INPUT. IN записано число N – количество гвоздиков (2 ≤ N ≤ 100). В следующей строке записано N чисел -координаты всех гвоздиков (неотрицательные целые числа,не превосходящие 10000).

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

Пример входного и выходного файлов:

INPUT. IN	OUTPUT. OUT
5 4   10    0    12    2	6

 

"Шаблон и слово"

Требуется определить подходит ли заданное слово под заданный шаблон. Шаблон задается большими латинскими буквами, знаками "?" - любой символ, "*" - любая последовательность символов (даже пустая).

Входные данные: В файле INPUT. IN в первых двух строках записаны шаблон и слово: в одной строки записан шаблон - последовательность больших латинских букв, "?" и "*", в другой  - слово, состоящее только из больших латинских букв (строки короче 100 символов).

Выходные данные:  В файл OUTPUT. OUT вывести YES, если слово подходит или NO, если нет.

Пример входного и выходного файлов:

INPUT. IN	OUTPUT. OUT
ABBCDA A*CDA	YES

  

10-11 - класс

"Шаблоны"

Шаблоном называется строка, состоящая из английских букв (a,...,z, A,...,Z) и символов "?" и "*". Каждый из символов "?" разрешается заменить на одну произвольную букву, а каждый из символов "*" - на произвольную (возможно пустую) последовательность букв. Про любую строку из букв, которую можно получить из шаблона такими заменами, будем говорить, что она удовлетворяет этому шаблону. Имеются два шаблона. Требуется найти строку минимальной длины, которая удовлетворяет обоим шаблона, либо выдать сообщение, что такойстроки не существует.

Входные данные. Заданные шаблоны записаны в первых двух строках входного файла INPUT. IN. Длина каждого шаблона не превосходит 80 символов.

Выходные данные. В выходной файл OUTPUT. OUT  следует вывести строку минимальной длины, удовлетворяющую обоим шаблонам, либо сообщение <-1>

Пример входного и выходного файлов:

INPUT. IN	OUTPUT. OUT
A* *B	AB

 

"Города и дороги"

В одном царстве есть N городов, некоторые из которых соединены дорогами. Царь решил провести инвентаризацию дорог в своем государстве. Но, как оказалось, он не силен в математике, поэтому он просит вас сосчитать количество дорог.

Входные данные. В файле INPUT. IN записано число N (0≤N≤100). В следующих N строках записано по N чисел, каждое из которых является единичкой или ноликом. Причем, если в позиции (i,j) квадратной матрицы стоит единичка, то i-ый и j-ый города соединены дорогами, а если нолик, то не соединены.

Выходные данные. В файл OUTPUT. OUT вывести одно число - количество дорог в царстве.

Примечание. Все дороги двусторонние, то есть если есть дорога из города i в город j, то есть и дорога из города j в город i, и это та же самая дорога.

Пример входного и выходного файлов:

INPUT. IN	OUTPUT. OUT
5 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0	3

"Лабиринт знаний"

В одном городе построили аттракцион "Лабиринт знаний". Лабиринт представляет собой N комнат, занумерованных от 1 до N, между некоторыми из которых есть двери. Когда ученик проходит через дверь, показатель его знаний изменяется на определенную величину, фиксированную для данной двери. Вход в лабиринт находится в комнате 1, выход - в комнате N. Каждый школьник этого города проходит лабиринт ровно один раз и попадает в определенную группу в зависимости от набранных знаний (при входе в лабиринт этот показатель равен нулю). Ваша задача показать наилучший результат.

Входные данные. Первая строка входного файла INPUT. IN содержит целые числа N (1 ≤ N ≤ 2000) - количество комнат и M (1 ≤ M ≤ 10000) -количество дверей. В каждой из следующих M строк содержится описание двери - номера комнат, из которой она ведет и в которую она ведет, а также целое число, которое прибавляется к количеству знаний при прохождении через дверь (это число по модулю не превышает 10000). Двери могут вести из комнаты в нее саму, между двумя комнатами может быть более одной двери.

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

Пример входного и выходного файлов:

INPUT. IN	OUTPUT. OUT
2 2 1 2 5 1 2 -5	5