НАЦИОНАЛЕН ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА И ИНФОРМАЦИОННИ ТЕХНОЛОГИИ “Джон Атанасов”

Шумен, 27 ноември 2004г

 

ТЕМА ПО ИНФОРМАТИКА ЗА  12 КЛАС (ГРУПА A)

 

Задача A1. СЕЛА

 

В една страна имало N села. Кралят решил да защити поданиците си като построи стена, която да обгражда всички села и да има формата на затворена крива. Възможно е някои села да са точно върху стената. Ако стената преминава през едно село, то за това село се казва, че е на стената. Но възникнал проблем. Тъй като кралят искал да спести възможно най-много пари било решено стената да има минимален периметър. Но както е добре известно всяко добро дело извършено от един управляващ трябва да бъде добре рекламирано сред хората. За целта кралят решил да направи празничен марш от едно село в страната си до друго за да привлече вниманието. Но възникнали две условия. Първото е, че не било хубаво маршът да е между села, поне едното от които е на стената – отзвукът нямало да достигне до всички поданици. Второто нещо, за което се замислил кралят е, че разстоянието, което щяло да се измине трябвало да бъде минимално по дължина, за да се спестят още пари. Така в крайна сметка целта е да се намерят две села, нито едното от които да е на стената и разстоянието между тях да е минимално измежду всички такива разстояния в страната.

                Напишете програма VILL, която намира разстоянието между две села, които отговарят на условията на краля.

ВХОД: Програмата въвежда данните от стандартния вход. На първия ред е зададено числото (N £ 20000). На следващите N реда са зададени по две цели числа в интервала           [­–10 000 000, 10 000 000] – координатите на поредното село съответно по абсцисата и по ординатата. Във всички тестови примери поне две от селата не са на стената, която кралят построява и поради това може да се направи поход според условията.

ИЗХОД: Програмата извежда данните на стандартния изход. Едно единствено число – разстоянието между две села, които отговарят на условията на краля. Числото трябва да бъде изведено с точност до 10-5.

 

ПРИМЕР:

ВХОД:

5

0 –3

3 0

0 0

-2 2

1 –1

 

ИЗХОД:

1.41421

 

ВХОД:

11

1 -1

-1 -4

-2 0

-3 -5

2 -4

0 1

5 -2

3 3

1 5

-4 4

-5 –5

 

ИЗХОД:

2.23607

 

НАЦИОНАЛЕН ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА И ИНФОРМАЦИОННИ ТЕХНОЛОГИИ “Джон Атанасов”

Шумен, 27 ноември 2004г

 

ТЕМА ПО ИНФОРМАТИКА ЗА  12 КЛАС (ГРУПА A)

 

 

Задача A2. ПРОЧИТ НА ГЕН

 

От биологическата наука е известно, че всеки ген се състои от наредени кодони, а всеки кодон се състои от три наредени азотни бази. Азотните бази биват четири вида, които се бележат с главните латински букви A, C, G и T. Всеки кодон кодира аминокиселина. Еднаквите кодони кодират еднакви аминокиселини, а за целите на тази задача ще приемем, че различните кодони кодират различни аминокиселини. Аминокиселините, наредени в редица, образуват белтък. Когато клетъчният апарат прочита даден ген, той прочита някои от кодоните и конструира съответните им аминокиселини. След това нарежда аминокиселините в същия ред в който са съответните им кодони върху гена и така конструира белтък. Броя на прочетените кодони може да бъде от 1 до броя на кодоните в гена.

 

Напишете програма GENE, която по зададен ген намира броя на различните белтъци, които могат да бъдат конструирани от него.

 

Входните данни се четат от стандартния вход и се състоят от единствен ред, съдържащ последователност от главни латински букви измежду A, C, G и T – азотните бази на гена. Броят на азотните бази се дели на три и е не по-голям от 12 000 000 (т.е. в гена има не повече от 4 000 000 кодона). В 50% от тестовете броят на азотните бази ще е не по-голям от 1 500 000 (т.е. не повече от 500 000 кодона).

 

Резултатът трябва да бъде изведен на стандартния изход. За ваше улеснение, не трябва да извеждате целия резултат, а само остатъка му по модул 1 048 576 (това е 2 на степен 20). Изведеното на стандартния изход трябва да съдържа единствен ред с единствено число на него – броя на различните белтъци, които могат да се конструират от гена, по модул 1 048 576.

 

 

 

ПРИМЕР 1                                                                                                            ПРИМЕР 2

 

Вход                                                                                                                      Вход

ACGTTTACG                                                                                                        AGGCTACTACTA

 

Изход                                                                                                                    Изход

6                                                                                                                              7

Възможни прочетени кодони                                                                     Възможни прочетени кодони

ACG                                                                                                                        AGG

ACGACG                                                                                                               AGGCTA

ACGTTT                                                                                                                 AGGCTACTA

ACGTTTACG                                                                                                        AGGCTACTACTA

TTT                                                                                                                         CTA

TTTACG                                                                                                                 CTACTA

                                                                                                                                CTACTACTA

 

НАЦИОНАЛЕН ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА И ИНФОРМАЦИОННИ ТЕХНОЛОГИИ “Джон Атанасов”

Шумен, 27 ноември 2004г

 

ТЕМА ПО ИНФОРМАТИКА ЗА  12 КЛАС (ГРУПА A)

 

 

Задача A3. ТРАЕКТОРИЯ

 

Една точка започва движението си от началото на координатната система, като се насочва надясно и едновременно нагоре или надолу под ъгъл 45 градуса спрямо оста Ox. Смяната на посоката (нагоре или надолу) се извършва в някои от целочислените моменти на времето, а скоростта на движението е постоянна. През цялото време движещата се точка се намира над или върху оста Ox и задължително попада в точката с координати (n, 0), където движението спира. Разглеждаме всички възможни траектории за така описаното движение и ги подреждаме, като приемаме, че една траектория P предхожда друга траектория Q, ако от началото до някакъв момент движението по двете траектории се извършва еднакво, а след това в следващия малък интервал от време точката, движейки се по траекторията P се намира по-ниско, отколкото, ако би се движила по траекторията Q.

 

Напишете програма LINE, която въвежда от стандартния вход цялото четно положително число n, n < 65, а след това от следващия ред – описание на една възможна траектория като последователност от общо n нули и единици, разделени с по един интервал (нулата съответства на участък на движение надолу, а единицата – на движение нагоре. На първия ред на стандартния изход вашата програмата трябва да изведе непосредствено следващата траектория, съгласно описаното подреждане, като последователност от нули и единици, разделени с по един интервал. Входните данни са такива, че въведената траектория не е последна според описаното подреждане. На втория ред на стандартния изход програмата трябва да изведе броя на всички траектории, които са разположени не по-ниско от въведената (т.е такива, които лежат изцяло над въведената или имат общи части с нея, но нямат нито една част, която се намира под въведената траектория).

 

Пример

 

Вход

 

6

1 0 1 1 0 0

 

Изход

 

1 1 0 0 1 0

3