НАЦИОНАЛНА ОЛИМПИАДА ПО ИНФОРМАТИКА 
ОБЛАСТЕН  КРЪГ
16 март 2003 г.

Тема за 9 – 10 клас (група B)

ЗАДАЧА   B1.  НОМЕРАЦИЯ

Пълно k-ично дърво (k2) с височина d0 се нарича дърво, всеки връх на което е на разстояние не по-голямо от d от  корена, като всеки връх на разстояние по-малко от d има  точно k (подредени) наследника, а тези на разстояние d нямат наследници.
Да се направи програма NUM.EXE, която по зададен пореден номер на връх n0 при обхождане “по редове” на пълно k-ично дърво с височина d намира поредния номер на същия връх при обхождане на дървото в ред  “корен, първо поддърво, второ поддърво,...,k-то поддърво”, (където за всяко поддърво рекурсивно се прилага същата схема).
Двете части на фигурата показват едно и също двоично дърво с номера на върховете, отговарящи на изброяване “по редове” и в ред “корен, първо поддърво, второ поддърво”.

                        0                0
                      /   \            /   \
                     1     2          1     4
                    / \   / \        / \   / \
                   3   4 5   6      2   3 5   6

Програмата въвежда k, d и n от един ред на стандартния вход и извежда на стандартния изход съответния на n номер при втория вид обхождане. 
Изпълнено е k5 и d12. 
Примерът  се отнася за дървото от фигурата.

ПРИМЕР
Вход
2 2 2
Изход
4

ЗАДАЧА  B2.  НЕРАВЕНСТВО

Да се направи  програма  INEQ.EXE,   която  за  дадено цяло положително число n, n < 1012, намира броя на неотрицателните целочислени решения  (x, y)  на неравенството  x2 + y2 < n.
Входните данни се въвеждат от стандартния вход като едно цяло положително число n. Резултатът трябва да бъде изведен на стандартния изход като едно цяло число.

ПРИМЕР
Вход 
5
Изход 
6

ЗАДАЧА   B3.  СУМА

Да се направи програма SUM.EXE, която по зададени цяло число  s   (1≤  s ≤ 1000)  и  цяло  число  a   (0≤  a ≤ 10100),  намира най-малкото цяло число b, което е по-голямо или равно на  a  и има сума на цифрите  s.
Програмата въвежда  s  и  a  от стандартния  вход,  като числото s  е на първия ред, а числото a – на втория. Намереното число b да се изведе  на стандартния изход. 

ПРИМЕР
Вход
13
567
Изход
571