НАЦИОНАЛНА ОЛИМПИАДА ПО ИНФОРМАТИКА’2005

Областен кръг, 13 март 2005 г.

  Група А (12 клас)

 

 

Задача A1.  ПОДРЕДИЦИ

 

Напишете програмаSUBSEQ.EXE, която намира броя на различните начини за представянето на цялото положително число N като сума на числа, образуващи подредица на  редицата 1, 2, 3, ..., N– 1.

 

Стойността на N се четe от стандартния вход (2 < N < 500).

Резултатът се извежда на стандартния изход като едно цяло положително число. 

 

ПРИМЕР

 

Вход

6

 

Изход

3

 

 

Задача A2.  МАТРИЦИ

 

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

 

Пример на разделящ код с 8 реда и 7 стълба:

 

 

0 0 0 0 1 1 1

 

0 0 1 1 0 0 1

 

0 1 0 1 0 1 0

A   =

0 1 1 0 1 0 0

 

1 0 0 1 1 0 0

 

1 0 1 0 0 1 0

 

1 1 0 0 0 0 1

 

1 1 0 0 0 1 0

 

Намерете разделящ код с 9 реда и колкото се може повече стълбове.

Запишете намереното решение в текстов файл с имеMAT.TXT. Файлът трябва да има 9 реда, като числата във всеки ред да са разделени с по един интервал.

Ако матрицата във файла е разделящ код с Nстълба, решението ще получи  K(N–2) точки, където коефициентът Kе избран така, че решение с максималния възможен брой стълбове да получи 100 точки.


Задача А3. ПЪТЕКА

 


            Дворът на училище е правоъгълник с размери Nна Mметра, върху който са построени K здания с правоъгълни основи. Ще използваме правоъгълна координатна система, началото на която е разположено в долния ляв край на двора (вж. на фигурата двор с N=24 и M=10), т.е. долният десен ъгъл е с координати (N,0), горният ляв – с координати (0,M), а горният десен – с координати (N,M). В тази координатна система разположението на всяка сграда се представя с координатите на долния си ляв и горния си десен ъгъл. Напишете програма PATH.EXE, която да определя възможно ли е да се прокара пътека (вж. пунктираната линия на фигурата), която започва в долния ляв и завършва в горния десен ъгъл на двора, като не пресича основите на сградите и не се допира до тях.

Данните се въвеждат от стандартния вход. На първия  ред са зададени целите числа N, M и K(0<N, M£ 2 000 000 000, 0£ K<500). На всеки от следващите K реда са зададени, разделени с по един интервал, целите числа X1, Y1, X2и Y2 – координати на долния ляв и горния десен ъгъл на  една от сградите, разположена в двора.

Ако може да се прекара пътека, програмата трябва да изведе трасето на тази пътека (като последователност от отсечки ) на стандартния изход. На първия ред програмата трябва да изведе броя L на точките в пътеката, без началната (0,0) и крайната (N, M), а на всеки от следващите L реда – координатите X,Yна поредната точка.  Координатите да се печатат с 2 знака след десетичната точка. Всяка пътека с посочените свойства е приемлива, ако Lне надвишава 4K. Ако няма възможност да се прокара пътека, програмата трябва да изведе на стандартния изход единствен ред, съдържащ числото –1.

 

ПРИМЕР

 

Вход                                                                            Изход

24 10 4                                                                         6

1 1 8 7                                                                          0.50 8.50

19 4 24 9                                                                       8.50 8.50

8 0 20 3                                                                        8.50 3.50

9 4 17 10                                                                       17.50 3.50

                                                                                    17.50 9.50

                                                                                    19.50 9.50