НАЦИОНАЛНА ОЛИМПИАДА ПО ИНФОРМАТИКА’2005
Областен
кръг, 13 март 2005 г.
Група B (10–11 клас)
Задача B1. КАРТОНЧЕТА
Ваньо имал
няколко картончета, на които били написани естествени числа. Докато скучаел в
градския транспорт, той си играел с тях и забелязал, че като отдели едно или
няколко от тях, може да получи като сума всяко естествено число от 1 до сбора
на всичките и то по единствен начин (с точност до реда на
събираемите: 2+4 и 4+2 не са различни). “Ама разбира се!”, тупнал се по главата
Ваньо. “Числата ми са 1, 2, 4 и 8 – какво да се получи друго?! Двоична бройна
система!”
Да, но червеят
на любопитството го заглождил – ами ако не бяха първите последователни степени
на двойката? Дали 15 (каквато е сумата в сегашния му случай) има и друго такова
“разбиване по картончета” (бързо измислил и термин Ваньо): набор от естествени
числа със сума 15, така че всяко число от 1 до 15 да може да се представя по
единствен начин чрез едно или сума от няколко събираеми от набора? Ами ако не е
15, а някакво естествено N, колко такива набори има за него?
Ваньо много
бързо се отказал от привлекателната идея на картончетата да има непременно
различни числа, тъй като тогава: 1 трябва да го има, 2 – също, 3 не трябва, че
вече го има като 1+2, но четири – задължително... И така – стига се пак до
“тривиалното” решение – двоична бройна система (при това – има решение само за
N=2k-1). Той решил да допусне за всяко картонче най-много още едно
картонче със същото число, като, ако има повтарящи се – просто да не ги
различава при образуване на сумите. Така N=5, например, което в първата
формулировка няма решение, сега може да се представи като {a=1, b=2, c=2}, например.
Вярно, че 3=1+2 формално се представя по два начина (a+b и a+c), но то си е
все 1+2.
Ето примери, да
уточним идеите на Ваньо: {1, 2, 3} не е добър набор от картончета (за N=6),
защото 3 се представя от една страна със самото себе си, от друга – чрез
поднабора {1, 2} и се губи единствеността; {1, 1} е единствената възможност за
N=2; {1, 1, 1} не е добър набор за N=3 – има трето картонче с един и същи
надпис; {1, 2, 5} не е добър набор за N=8 (4 не може да се представи чрез
поднабор от тях), но {1, 1, 3, 3} е добър.
Помогнете на
Ваньо да намира броя на добрите “разбивания по картончета” за зададено N, като
напишете програма CART.EXE, която определя този брой.
ВХОД: От стандартния вход се
въвежда един ред с естественото число N, не по-голямо от 2000000000.
ИЗХОД: На стандартния изход се
извежда един ред с получения брой или числото 0, ако такова “разбиване” няма.
ПРИМЕР
Вход
15
Изход
1
ОБЯСНЕНИЕ: От
всичките осем разбивания, които удовлетворяват условието за единственост, само
в последното (“тривиалното”) е изпълнено и условието за не повече от две
срещания на всяко от събираемите (там просто няма повторения):
{1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1, 1, 1, 1, 1}, {1, 1, 1, 1, 1, 1, 1,
8}, {1, 1, 1, 4, 4, 4}, {1, 1, 1, 4, 8},
{1, 2, 2, 2, 2, 2, 2, 2}, {1, 2,
2, 2, 8}, {1, 2, 4, 4, 4}, {1, 2, 4, 8}
Задача B2. РАЗХОДКИ
Слончето Нели живее в обширното Равно поле, през което тече известната
Права река. Пак там се намира и не по-малко известното Кръгло езеро. Докато си
почиваше на сянка под една палма, слончето си мислеше само за едно: “Каквато е
жега, да взема да ида до реката... Или до езерото... Най-добре – и до двете!
Колко ли път трябва да измина най-малко за тази разходка? Всъщност – за всяка
от двете разходки: от тук до реката и после до езерото и от тук до езерото и
после до реката... Я да видим...“ И, като се замисли дълбоко, Нели заспа. Не,
не я будете, преди да сте написали програма WALK.EXE, която отговаря на нейните
въпроси.
ВХОД: От стандартния вход се въвеждат следните редове:
-
ред 1: три цели числа A, B
и C, разделени с интервал: коефициентите на правата p,
която описва Права река: p: Ax + By +
C = 0. A и B не са едновременно нули,
а абсолютната стойност на числата не надвишава 100. Широчината на Права река е
пренебрежимо малка;
-
ред 2: две цели числа (P
и Q) и едно естествено R, разделени с интервал:
съответно координатите на центъра и радиуса на окръжността, очертана от
Кръглото езеро. Абсолютната стойност на тези числа не надвишава 200;
-
ред 3: две цели числа X и
Y разделени с интервал – координатите на Нели. Абсолютната
стойност на тези числа не надвишава 500.
ИЗХОД:
Запишете на стандартния изход два реда с
по едно реално число, закръглено с точност до втория знак след десетичната
точка:
-
ред 1: дължината на най-краткия път,
който води от мястото на Нели до реката, а след това до езерото;
-
ред 2: дължината на най-краткия път,
който води от мястото на Нели до езерото и след това до реката.
УТОЧНЕНИЯ: Езерото няма общaточка с реката. Нито реката,
нито езерото са дълбоки и Нели може спокойно да ги “прецопва”. Не е проблем (направо
си е удоволствие!), ако на път за реката при първата разходка Нели поцопа из
езерото, но после пак трябва да се върне до него, както и ако на път за езерото
пресече реката (после пак трябва да стигне до нея). На картата са показани две
напълно допустими разходкиXAB и XCD.
ПРИМЕР
Вход
3 4 -12
5 4 2
1 5
Изход
5.10
4.78
Задача B3. ПЕЧАТНИ ПЛАТКИ
Изработването
на печатни платки в електрониката е високотехнологичен и скъпо струващ процес:
известен брой точки на специално изработена (евентуално многослойна) изолационна пластина (“платка”)
се свързват чрез непресичащи се тънки електропроводими покрития (“пътечки”). На
платките, с които разполагате, две мислени линии от точки A и B са съединени с
пътечки, като някои точки от A са свързани с някои точки от B. Това много Ви
устройва: електронната платка, която разработвате, трябва да има точно такава
конструкция. Само че, във Вашия случай, всяка точка от A трябва да е свързана
точно с две точки от B, а всяка точка от B – най-много с една точка от A. Дали
можете да пригодите наличните платки за нуждите си и да реализирате сериозни
икономии? Единственото оръжие, с което разполагате, е възможност да прекъснете
някои от дадените пътечки – които искате и колкото искате: това е много
по-евтино от създаването на нова платка. Напишете програмата PLATE.EXE,
която да определя има ли задачата решение и кои от пътечките трябва да се прекъснат.
ВХОД: От стандартния вход се
въвеждат:
-
ред 1: трите естествени числа M (брой
на точките на линия A), N (брой на точките на линия B) и K, разделени с
интервал. M и N не надвишават 100, а K не е повече от 5000;
-
на всеки от следващите K реда се описва
една от пътечките чрез две естествени числа, разделени с интервал. Първото е
номер на точка от линия A, а второто – от линия B.
ИЗХОД: Запишете на стандартния
изход:
-
един ред със съобщението NО, ако, уви,
платката не може да бъде пригодена за нуждите Ви;
иначе:
-
ред 1: едно цяло неотрицателно число S
– брой на пътечките, които ще бъдат прекъснати. Ако S е нула други редове няма;
-
на всеки от следващите S реда опишете
по една от пътечките, която ще бъде прекъсната в същия формат, в какъвто е
дадена при въвеждането.
ЗАБЕЛЕЖКА: На схемата по-горе
пътечките, свързващи точките, не се пресичат – те минават на различни слоеве.
ПРИМЕР
Вход Изход
3 6 10
4
1 1 1 4
1 3 1 5
1 4 2 5
1 5 3 1
2 2
2 4
2 5
3 1
3 5
3 6