НАЦИОНАЛНА ОЛИМПИАДА ПО ИНФОРМАТИКА’2005
Финален кръг, 23-24 април 2005 г.
 Група А (12 клас)

Задача A1. КОДОВЕ

Матрицата  A  с елементи 0 и 1 се нарича разделящ код, ако за всеки три различни стълба  p, q, r  съществува ред i, за който A[i][p]=1, A[i][q]=0, A[i][r]=0. Два кода са еквивалентни, ако единият може да се получи от другия с разместване на редове и стълбове.
Примери на разделящи кодове с 8 реда и 8 стълба:

A	B	C	
00000111
00011001
00101010
00110100
01001100
01010010
10000000
11100001	00000111
00011001
00101010
01001100
01110000
10010010
10100100
11000001	00000111
00111000
01001001
01010010
01100100
10001100
10010001
10100010	
 
Кодовете A и B не са еквивалентни, а кодовете B и C са еквивалентни.
Известно е, че с точност до еквивалентност, съществуват точно 4 различни разделящи кода с 8 реда и 8 стълба.  
Намерете, колкото се може повече два по два нееквивалентни разделящи кодове с 9 реда и 9 стълба.
Запишете намерените кодове в текстов файл с име CODE.TXT.  Кодовете трябва да бъдат последователно номерирани с числата 1, 2, 3, …, N. За всеки код се извежда на отделен ред неговият номер, а на следващите 9 реда се извеждат редовете на кода без никакви интервали между числата. Файлът не трябва да съдържа празни редове.
Ако сте намерили N на брой нееквивалентни кода, ще получите KN точки, където коефициентът K е избран така, че решение с максималния възможен брой кодове да получи 100 точки. Ако измежду кодовете във файла има еквивалентни, ще получите нула точки. Ако някоя от изведените матрици не е разделящ код, също ще получите нула точки.

НАЦИОНАЛНА ОЛИМПИАДА ПО ИНФОРМАТИКА’2005
Финален кръг, 23-24 април 2005 г.
 Група А (12 клас)

Задача A2. ОПЕРАЦИЯ

Нека K е естествено число (1 < K < 100). Разглеждаме множеството M = {1, 2, 3, ..., K}. Дадена е функция f(x, y), която е определена за всяко x и y от множеството M и която приема стойности в същото множество. Дефинираме операция * на два аргумента по формулата a*b = f(a, b). Нека a1, a2, .., an са дадени елементи от M (незадължително всичките различни, 0 < n < 30).  От тях образуваме изрази, като поставим знаци за операцията * и скоби за определяне реда на извършването й. Например при n = 4, възможни изрази са:  

a1* (a2* (a3*a4)),  a1* ((a2* a3)*a4),  (a1*a2)* (a3*a4),  (a1* (a2* a3) )*a4   и  (( a1* a2)* a3)*a4.

Напишете програма OPER, която при въведена таблица за стойностите на функцията f  и елементи a1, a2, .., an, пресмята броя на различните стойности, които се получават при образуването на всевъзможните изрази от описания вид.

Данните се четат от стандартния вход. На първия ред е записано числото K. Следват K реда, като x-тият от тях съдържа f(x, 1),  f(x, 2), ...,  f(x, K), разделени с интервали. Следва ред, съдържащ числото n. На последния ред са записани стойностите a1, a2, .., an, разделени с интервали. Програмата трябва да изведе резултата като едно цяло число на стандартния изход.

ПРИМЕР
Вход
6
1 2 5 4 5 3
2 1 2 5 5 3
3 6 2 3 3 2 
2 1 2 1 1 4
1 1 3 1 5 1
3 4 5 6 1 6
5
2 3 4 5 6

Изход
3

НАЦИОНАЛНА ОЛИМПИАДА ПО ИНФОРМАТИКА’2005
Финален кръг, 23-24 април 2005 г.
 Група А (12 клас)

Задача A3. ЗДРАВИНА

Преди да започне масово производство на едно изделие, трябва да се провери дали то отговаря на определени изисвания. Едно от тях е здравината. Тя се измерва с цяло число Z – максималната височина, от която може да се пусне изделието, без то да се счупи. Ще считаме, че изделията са напълно еднакви, т.е. за всяко от тях тази височина е една и съща. За установяване на здравината се използва кула с височина цяло число H (0 < H < 1010) и устройство,  което може да извършва следната последователност от действия, наричана опит – да вземе едно здраво изделие, да го издигне на височина между 1 и H (включително), да го пусне и да установи дали  изделието се е счупило. Ако е счупено, то не може да се използва повече за опити. Ако не е счупено, се счита, че е достатъчно здраво (не се е променило по никакъв начин) и може да се използва отново за опит. Тъй като устройството не може да издига изделие на височина по-голяма от H, в случай че изделието не се счупи при пускане от височина H се приема, че  Z = H.
За установяване на здравината на изделие разполагаме с N (0 < N < 106) напълно еднакви здрави екземпляра от изделието. Напишете програма RELIAB, която по зададени N и H определя минималния брой опити, които трябва да се извършат, за да може със сигурност да се определи Z.  
Програмата трябва да прочете от един ред на стандартния вход двете цели числа N и H, разделени с един интервал и да отпечата на стандартния изход едно число – намерения минимален брой опити.

ПРИМЕР 1
Вход
1 999999999
Изход
999999999

ПРИМЕР 2
Вход
2 100
Изход
14