ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА
Шумен, 24 ноември 2001г.
ТЕМА ЗА 7-8 КЛАС
Задача 1. НАЙ-ДОБРИТЕ К
Дадени са N (5<=N<=20000) цели положителни числа, не по-големи от 20000 и цяло положително число K (3<=K<=100 и K<N) . Напишете програма MAXK.EXE която намира най-големите K от зададените N числа.
Първият ред на входния файл MAXK.INP ще съдържа числата N и K. Всеки от останалите N реда ще съдържа по едно от зададените N числа. Изходният файл MAXK.OUT трябва да се състои от K реда – във всеки от които е записано по едно от намерените най-големи числа, подредени в нарастващ ред.
ПРИМЕР:
MAXK.INP MAXK.OUT
8 4 38
133 56
74 74
12 133
38
29
56
19
31
Задача 2. ОБЩ ПОДНИЗ
Дадени са два низа А и В, всеки от които съставен от поне 3 и не повече от 250 десетични цифри. Максимален общ подниз на А и В е най-дългият подниз, който се среща и в двата низа. Например, най дългият общ подниз на 112135349 и 66353 е 353, а 112135349 и 67887 нямат общ подниз.
Напишете програма SUBS.EXE, която да определя един максимален общ подниз на двата зададени низа.. Входният файл SUBS.INP сe състои от два реда. Първият от тях съдържа низа А, а вторият - низа В. Изходният файл SUBS.OUT се състои само от един ред, в който трябва да се изведе един максимален общ подниз, ако двата низа имат общ подниз. Ако двата низа нямат общ подниз, тогава единственият ред на изходния файл да съдържа низа NO.
ПРИМЕР 1:
SUBS.INP SUBS.OUT
112135349 353
66353
ПРИМЕР 2:
SUBS.INP SUBS.OUT
67887 NO
112135349
Задача 3. ЛЕДЕН КЪС
Плътно парче лед има форма, която може да се изобрази в таблица с N реда и N стълба (8<=N<=200) както е показано на фиг. 1 с потъмнените клетки. Клетките от първия и последния ред, както и клетките от първия и последния стълб на таблицата са винаги празни. От температурата на въздуха парчето лед започва да се топи, като по-външните му, т.е. по-изложени на действието на въздуха участъци се топят по-бързо от по-вътрешните. За 1 час се стопява изцяло ледът във всяка клетка, поне 2 от съседните 4 (отгоре, отдолу, отляво и отдясно) клетки на която са празни. Ледът от останалите клетки не се топи изобщо На фиг. 2 е показано какво ще остане от парчето от фиг. 1, един час след като е стояло на въздуха.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Фигура 1 Фигура 2
Напишете програма ICE.EXE, която определя за колко време ще се стопи целият леден къс. Първият ред на входния файл ICE.INP ще съдържа числото N. Всеки от останалите N реда ще съдържа описанието на един от редовете на таблицата – низ с дължина N, съставен от нули и знака *. Нула означава, че клетката от таблицата е празна, а знакът * – че в клетката има част от ледения къс. Изходният файл ICE.OUT трябва да се състои от един ред в който да се изведе броя часове, за които леденият къс ще се стопи изцяло.
ПРИМЕР:
ICE.INP ICE.OUT
8 4
00000000
00**0000
00**0**0
0******0
0*****00
0**0**00
00000000
00000000
Желаем ви приятна работа и успех!