ЗИМНИ МАТЕМАТИЧЕСКИ ПРАЗНИЦИ, БУРГАС

29 януари 2005

ТЕМА ЗА  ГРУПА B (10-11 КЛАС)

Задача B1. ПОХОД

Едно туристическо дружество организирало поход, в който участват N туристи (1 < N < 2000). Те се движат по тясна и дълга пътека в една и съща посока, като първоначално всеки турист се движи с постоянна скорост, различна от скоростта на всеки друг. Преди да тръгнат, туристите се нареждат един след друг на достатъчно големи разстояния по пътеката, като наредбата е произволна. При движението си по-бърз турист ще настигне по-бавно движещ се пред него (ако има такъв) и тогава по-бързо движещият се ще трябва да намали скоростта си до тази, на намиращия се отпред по-бавен. След достатъчно дълъг период от време ще се окаже, че туристите се групират в P групи (0 < P < N + 1), всяка една от които се движи със скоростта на най-бавния в групата. Въпросът е колко от всичките възможни начални разположения ще доведат до оформяне на P групи? Напишете програма MARCH.EXE, която решава тази задача.

Програмата трябва да прочете от стандартния вход стойностите на N и P, разделени с един интервал и да изведе на стандартния изход търсения брой по модул 1 020 847 (т.е. остатъка на търсения брой при деление на 1 020 847). В 50% от тестовете N < 20.

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

Вход Вход

4 3 11 1

Изход Изход

6 566259

ЗИМНИ МАТЕМАТИЧЕСКИ ПРАЗНИЦИ, БУРГАС

29 януари 2005

ТЕМА ЗА  ГРУПА B (10-11 КЛАС)

Задача B2. ГЕЙМЪРСКИ ПЪТИЩА

  Панчо е заклет геймър. Няма ниво на DOOM от 1, та чак до 3, което да не знае наизуст, заедно с всички тайни проходи и складове с оръжия. И си мислел, че не съществува местност, в която да се изгуби, докато не станал студент и не попаднал в Студентски град. Панчо не е някакъв прост геймър. Ходил е на състезания по информатика и е научил това-онова. Бързо съобразил, че може да представи Студентски град като множество от кръстовища (номерирани от 1 до N) и улици, които ги свързват, като всъщност го интересуват само улиците, които може да му се наложи да използва – от общежитието до залите в квартала (номерирани от 1 до K). Панчо си написал програа, която да намира един от най-кратките пътища от общежитието му до всяка зала в студентски град и запомнил само улиците, които участвали в тези пътища. Това решило проблемите с придвижването в студентски град до някъде. Често избраната зала се оказвала затворена или пълна и той трябвало да се върне до общежитието или пък решавал да влезе в зала, както си обикалял из Студенски град. Значи за всяко кръстовище трябвало да намери най-близката до него зала и да не се налага да се връща до общежитието. Освен това Панчо считал, че улиците, които вече познава в Студентски град са му напълно достатъчни и не искал да ползва други. Така пътищата, които търси, трябва да използват само познатите му вече улици. Напишете програма GPATHS.EXE, която чете описание на улиците в Студентски град, които Панчо познава и разположението на залите и за всяко кръстовище определя най-близката до него зала. 
 На първия ред на стандартния вход са зададени: броят на кръстовищата N (3£N£100 000) и броят на залите K (2£K£N). Всеки от следващите N–1 реда описва по една улица и съдържа 3 числа I, J, C, където I и J са номерата на кръстовищата, които са краища на поредната улица, а C е дължината на улицата (1£C£100 000). Следват още K реда, показващи на кои кръстовища има зала (залите получават номера от 1 до K в съответствие с реда по който са дадени кръстовищата на които се намират). 
 Програмата трябва да изведе на стандартния изход N реда – по един за всяко кръстовище. На всеки ред трябва да е посочен номерът на най-близката зала (която не се намира на същото кръстовище) и намереното разстояние до нея. Ако има няколко зали на едно и също разстояние да се изведе тази с най-малък номер. 
 
ПРИМЕР
Вход:  Изход:
5 3  1 5 
1 2 5   2 12
1 3 5 2 2 
3 4 2   3 4
3 5 2   2 4
2 
4 
5 
 

ЗИМНИ МАТЕМАТИЧЕСКИ ПРАЗНИЦИ, БУРГАС

29 януари 2005

ТЕМА ЗА  ГРУПА B (10-11 КЛАС)

Задача B3. СИГНАЛИ

Иванчо и Марийка живеят в ж.к. “Славейков” в Бургас. Като всички млади, влюбени хора на тяхната възраст, те не искат разговорите им да бъдат подслушвани от други хора – родители, приятели и т.н. За съжаление нямат компютри в къщи, с които да си комуникират по Интернет, а пък и говоренето по телефона също не е добра идея. Блоковете, в които те живеят са доста близо, а прозорците на стаите им са един срещу друг. Затова решили да използват морзово-подобен код. С помощта на фенерче те си обменят серии от кратки и дълги светвания, които ще наричаме сигнали. Да означим кратко светване с 0, а дълго – с 1. Така всеки сигнал се представя като последователност от нули и единици.

Понеже морзовият код е добре известен, Иванчо и Марийка решили да дадат техни собствени значения на сигналите, които използват. Например, 101 да означава „здравей”, 010 – „чао”, а 01011 – „хайде да излезем тази вечер”. След време Иванчо забелязал, че ако използват едни и същи значения за сигналите, хората шпиониращи разговорите им могат да се досетят за значенията на някои от тях. Например, ако всички разговори завършват с 010, може да се предположи, че този сигнал е за довиждане. Ето защо решили, всеки месец да сменят значенията на сигналите, както и да подобрят сигурността на разговорите. Идеята за подобряване на сигурността е интересна – сигналите, които се използват, ще имат дължина N светвания, но при изпращането им може да се изпусне едно от светванията на съответния сигнал, за да се объркат хората, следящи разговора. Например, сигналът „здравей” от примера по-горе може да се изпрати както е или да се изпрати с едно светване по-малко, т.е. като 01, 10 или 11. Разбира се, Иванчо и Марийка искат да имат колкото може повече сигнали, които да използват, но и да могат да се разбират правилно. Ако N=3 и 101 означава „здравей”, а 010 – „чао”, то не е ясно дали сигналът 01 означава „здравей” или „чао”, защото той може да се получи и от двата.

Тест No	N
0	6
1	7
2	9
3	10
4	12
5	13
6	15
7	16
8	18
9	19

Вашата задача е за всеки тестов пример (виж Таблицата) да създадете файл, с колкото може повече сигнали с дължина N отговарящи на горното условие: няма два такива, че ако им махнем по едно светване, да се получава еднакъв сигнал с дължина N-1. Наример: за N=4 едно такова множество от сигнали е: 0000, 0011, 1100 и 1111. Към това множество не може да добавим пети сигнал.

Името на изходния файл за тестът с номер <test number> трябва да бъде signals.<test number>. Първият ред трябва да съдържа естествено число M – брой намерени сигнали, спразващи правилото. Останалата част от файла трябва да съдържа точно М реда, всеки с по един от намерените сигнали. Сигналът трябва да се състои от N двоични цифри (0 или 1), без интервали между тях. Наредбата на сигналите в изходния файл не е от значение.

За всеки тестов пример, ако не създадете изходен файл, създадете неправилно форматиран изходен файл или файл, съдържащ невалидно множество от сигнали, ще получите 0 точки за теста. При коректен изходен файл, ще получите 10*M/K точки, където K е максималният известен на Журито брой сигнали, а M е броят намерени от Вас сигнали.

ПРИМЕР

Възможен изходен файл signals.0

4

000000

001111

000011

001100