НАЦИОНАЛЕН ПРОЛЕТЕН ТУРНИР ПО ИНФОРМАТИКА

ПЛОВДИВ, 27–28 МАЙ 2006

Задача D1. Пръчки

Разполагаме с неограничено количество от два вида дървени пръчки. Пръчките от единия вид са с дължина 1 метър, а от другия – с дължина 2 метра. Пръчките от всеки вид са неразличими помежду си. Вземаме няколко от тези пръчки и ги нареждаме плътно една след друга по права линия, така че да образуват редица с обща дължина от n метра. По колко различни начини може да се направи това нареждане?

Напишете програма STICKS, която въвежда цялото положително число n от стандартния вход (0 < n < 30) и извежда резултата на стандартния изход.

Пример: Вход:

4

Изход:

5

НАЦИОНАЛЕН ПРОЛЕТЕН ТУРНИР ПО ИНФОРМАТИКА

ПЛОВДИВ, 27–28 МАЙ 2006

Задача D2. Нули

Напишете програма ZERO, която при зададено цяло положително число N (N < 50000) намира най-дясната ненулева цифра и броя на нулите след нея на числото N! = 1 . 2 . 3. ... . N.

Вход: Програмата прочита от стандартния вход числото N.

Изход: Програмата извежда на стандартния изход един ред, съдържащ две числа, разделени с един интервал: най-дясната ненулева цифра на N! и броя на нулите след нея.

Пример: Вход Изход

12 6 2

Пояснение: 12! = 479001600.

НАЦИОНАЛЕН ПРОЛЕТЕН ТУРНИР ПО ИНФОРМАТИКА

ПЛОВДИВ, 27–28 МАЙ 2006

Задача D3. Породени редици

Пред учените от Магаданския университет на Откривателите, Мислителите и Гадателите (ОМГ) възникнал следният проблем: Даденo е множество от M (2 ≤ М ≤ 2752006) цели числа по-големи от 0 и по-малки от 52006. От него могат да се “пораждат” различни редици. Учените разглеждали само редици, които съдържат точно N (2 ≤ N ≤ 52006) елемента, подредени в нарастващ ред и такива, че разликата между всеки два съседни елемента в редицата е винаги K (0 < K < N). Учените се интересуват какъв е броят на различните редици, които могат да се “породят” от даденото множество.

Помогнете им като съставите програма SEQ, която по зададено множество и числа N и K, намира броя на различните “породени” от него редици, такива че да удовлетворяват горното условие.

От първия ред на стандартния вход програмата трябва да прочете целите числа M, N и K. От втория ред се въвеждат елементите на множеството (възможно е някои от елементите да се повтарят във входните данни). Числата във входа са разделени с интервали. Програмата отпечатва на единствения ред на стандартния изход търсения брой на редиците.

Примерен вход:

9 2 2

5 2 7 1 3 3 4 5 1

Примерен изход:

4

Обяснение: различните редици с дължина 2 и разлика 2, “породени” от зададеното множество са:

1 3

2 4

3 5

5 7