cuburi
Джони
обича да си
играе на
кубчета. Той
има неограничено
много
кубчета от
два вида: бели
и черни.
Размерите на
всички
кубчета са еднакви
и всичките им
ръбове са с
дължина един
метър.
За
да построи
сграда, Джони
нарежда
кубчетата на N
нива, всяко
съдържащо 2*2
кубчета. Така
той
образувал
сграда с
височина N,
ширина 2 и дължина 2. След
това, Джони
видял, че
сградата ще
бъде красива,
ако тя има
свързана
компонента,
съставена
само от бели
кубчета и те
да са поне K
броя.
Казваме,
че две
кубчета X и Y принадлежат
на една и
съща
свързана
компонента,
ако
·
X и Y се
намират на
съседни
позиции (т.е.
имат обща
стена)
·
X е
съседен на
кубчето Z и Z се
намира в
същата
компонента
на свързаност,
в която е Y.
Задача
Определете
броя на
красивите
сгради, които
могат да бъдат
построени.
Резултатът
трябва да
бъде изведен
по модул 10000.
Вход
Входният
файл cuburi.in съдържа
на първия си
ред двете
положителни
цели числа N и K, разделени
с интервал.
Изход
Изходният
файл cuburi.out трябва да
съдържа
търсения
брой по модул 10000.
Ограничения
• 1 <= N <= 40
• 1 <= K <= 4*N
Примери
cuburi.in |
cuburi.out |
Обяснение |
3 12 |
1 |
Единствена
сграда,
съставена
само от бели кубчета. |
cuburi.in |
cuburi.out |
Обяснение |
4 15 |
17 |
Съществуват
17 сгради, всяка
съдържаща
общо по 16
кубчета.
Шестнадесет
от тези
сгради са
съставени
от по 15 бели кубчета
и едно черно,
а
седемнадесетата
е съставена
само от бели
кубчета. |
cuburi.in |
cuburi.out |
6 15 |
2244 |
Време
за работа на
програмата: 0.6 секунди
за тест
Daniel Pasaila
"Al. I Cuza" University,
IT Department
danielpasaila@yahoo.com
Превод на
български:
Емил
Келеведжиев