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

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

 

 

ТЕМА ПО ИНФОРМАТИКА ЗА  10–11 КЛАС (ГРУПА B)

 

 

Задача В1.  Делимост

 

Напишете програмата DIV, която получава от стандартния вход  две  цели числа  N  и  P,  0 < N < 1 000 000 001,  0 < Р < 50001,  и извежда  на  стандартния изход  най-голямото  цяло  число  М,  такова  че  N!  се  дели на Р М (напомняме, че N!=1·2·3... N).

 

Пример:

 

Вход

4 2

 

Изход

 

3

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

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

 

ТЕМА ПО ИНФОРМАТИКА ЗА  10–11 КЛАС (ГРУПА B)

 

 

Задача B2. СРЕДНА СТОЙНОСТ И ВАРИАЦИЯ

 

Третокурсникът Велин пише проект за своя курс по машинно зрение в Масачусетския Технологичен Институт. За да работи проектът достатъчно бързо, той има нужда от бърза подпрограма, която да определя дали даден линеен сегмент от черно-бяла снимка (със степени на сивото) е едноцветен и ако да – какъв е цветът му. Снимката може да бъде разглеждана като поредица от N точки, всяка от които има интензитет на светлината цяло число между 0 и 255 включително. Линейните сегменти, които интересуват Велин, са просто интервали в тази поредица. За всеки такъв сегмент, означавайки интензитетите на точките му с x1, x2, x3, … , xn, Велин се нуждае от следните статистики:

-          Средната стойност на интензитетите E = (x1 + x2 + x3 + … + xn) / n

(просто средното аритметично от интензитетите на точките)

-          Вариацията на интензитетите S = ((x1 – E)2 + (x2 – E)2 + (x3 – E)2 + … + (xn – E)2) / n

(средното аритметично на квадратите на отклоненията на отделните точки от средната стойност E)

Помогнете на Велин, като напишете програма AVERAGE, която по зададена снимка и зададени линейни сегменти (интервали) намира средната стойност и вариацията на светлината за всеки от дадените интервали.

Входните данни се четат от стандартния вход. Първият ред съдържа две цели числа, разделени с интервал – броя на точките N (8 ≤ N ≤ 500 000) и броя на интервалите K (1 ≤ K ≤ 500 000). Следва ред с N цели числа, разделени с по един интервал – интензитетите на светлината в точките на снимката. Първото число на реда съответства на точка с номер 1, второто на точка с номер 2 и т.н. Следват K реда, всеки описващ един интервал и съдържащ по две числа между 1 и N – индексите на двете крайни точки в интервала (които също са включени в интервала). Първото число винаги е по-малко или равно на второто.

Резултатът трябва да бъде изведен на стандартния изход и трябва да се състои от K реда – по един за всеки интервал във входа. Подредбата на изведените редове трябва да съвпада с тази във входния файл (т.е. X-тият ред в изхода трябва да съответства на X-тия поред интервал описан във входа). Всеки ред трябва да съдържа две дробни числа, изведени и закръглени до четвъртия знак след десетичната запетая – статистиките E и S за съответния интервал. Ще се толерира само грешка с една единица на последния знак (четвъртия след десетичната запетая). В 50% от тестовете N ≤ 2 000. Във всички тестове сумата от квадратите на интензитетите ще е по-малка от 2 000 000 000.

Упътване: Опитайте се да изведете по- удобна формула за S, в която (квадратите на) интензитетите и средният интензитет участват поотделно (т.е. без произведение помежду си).

 

Пример

 

Вход                                                                                                                     Изход

8 3                                                                                                                          30.2500 2.1875

30 32 28 31 255 255 255 255                                                                          142.2500 12713.6875

1 4                                                                                                                          255.0000 0.0000

3 6

5 8

 

(както се вижда от примера, чрез изхода можем да заключим, че интервалите с малка стойност на S се състоят предимно от един цвят, а тези с голяма стойност на S – не)

 

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

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

 

ТЕМА ПО ИНФОРМАТИКА ЗА  10–11 КЛАС (ГРУПА B)

 

 

Задача B3. СУМА

 

Винаги когато пазарувал, един гражданин запазвал всичките касови бележки. Веднъж по време на сън, той срещнал милионер, който му обещавал, че ще му даде такава парична сума от цяло число левове L, но не по-голяма от дадено число M, и такава, че L да е възможно най-малко различаващо се от някаква сума S, по-малка или равна на L, така, че S да може да се образува като се сумират стойностите от няколко от касовите бележки (или евентуално от всичките). Гражданинът се събудил и не могъл да заспи в размисъл – колко най-много лева може да получи от милионера.

 

Напишете програма SUM, която въвежда от първия ред на стандартния вход броя N на касовите бележки (N < 101) и максималното число левове М, които може да даде милионерът (M < 101) и след това, от втория ред на стандартния вход въвежда N числа с десетична точка (с най-много две цифри в цялата част и с точно две цифри след десетичната точка), съответстващи на стойностите на касовите бележки. Програмата трябва да изведе на стандартния изход най-голямото цяло число левове, които може да даде милионерът.

 

Пример

 

Вход:

 

5 8

0.70 1.30 0.80 0.40 0.50

 

Изход:

 

3