Четыре задачи из личного первенства нашего института.

[frankenstein]

Добрый день.

Недавно организовали личное первенство юниоров по спортивному программированию в институте.
Олимпиада проходила на онлайн судье по правилам ACM ICPC. Решил выложить задачи сюда,
чтобы был для них общий доступ. Задачи, наверное, легки для общества dxdy, но все таки,
надеюсь что вы найдете в них что-то интересное. Если нужен набор тестов, можете написать,
я выложу их сюда.

Привожу 4 задачи из олимпиады. Хотелось бы услышать критику в сторону задач, а так же
помочь оценить сложность задач в стиле: стандартная задача для 1/2../11-го класса или
1/2../4-го курса.

Итак первая задачи звучат так:

НУЛИ ФАКТОРИАЛОВ
Ограничение на время работы 1 секунда
Ограничение на память 64 мегабайт
Для всех неотрицательных целых чисел $n$ функция факториала, $n!$, определяется следующим образом:

$$ n! = \begin{cases} 1,&\text{если $n=0$;}\\ n \times (n-1)!,&\text{если $n>0$.}\\ \end{cases} $$

Посчитайте количество нулей в конце факториала целого неотрицательного числа $x$.

Формат ввода
В первой строке записано целое число $x$ ($0 \le x \le 10^7$).

Формат вывода
В единственной строке выведите ответ - количество нулей в конце факториала $x$

Примеры
Ввод
5
Вывод
1

Ввод
10
Вывод
2

ДЕЛИТЕЛИ ФАКТОРИАЛОВ
Ограничение на время работы 1 секунда
Ограничение на память 64 мегабайт

Мы говорим что $a$ делит $b$, если существует такое целое $k$, что

$$ k \times a = b $$

Формат ввода
В первой строке записано целое число $N$ ($1 \le N \le 100$). Далее идут $N$ строк.
В каждой строке через пробел записаны два целых числа
$n$ и $m$ ($0 \le n \le 2^{31}-1$, $1 \le m \le 2^{31}-1$).

Формат вывода
В первой строке выходных данных выведите число $N$.
Далее, с новой строки, для каждой строки входных данных, начиная со второй, выведите в формате показанном
в примерах, строку, говорящую, делит ли $m$ $n!$ или нет.

Пример
Ввод
5
6 9
6 27
20 10000
20 100000
1000 1009
Вывод
5
9 divides 6!
27 does not divide 6!
10000 divides 20!
100000 does not divide 20!
1009 does not divide 1000!

ПОКУПКА САРАЯ
Ограничение на время работы 1 секунда
Ограничение на память 64 мегабайт

Фермеру Джону отлично известно что если не оградить двух быков друг от друга, то
скорее всего они подерутся, а это убытки для фермы и лишние хлопоты. Сейчас Джон
ищет хороший сарай где он мог бы спокойно оставлять своих животных. У Джона
$n$ быков и соответственно он хочет приобрести сарай с как минимум $n$ изолированными
друг от друга загонами. Помогите ему в этом.

Формат ввода
В первой строке записано целое число $n$ ($1 \le n \le 2401$) - количество быков.
Во второй строке даны через пробел два целых положительных числа размеры сарая $a$ и $b$, такие что
$3 \le a, b \le 100$. Далее с новой строки идет $a$ строк каждая длиной $b$ - план сарая.
На пересечении $i$-й строки и $j$-го столбца содержится символ $\#$, если на том месте
сарая стоит ограда, или символ точка если эта клетка свободна. В первой и последней строке,
а так же в первом и последнем столбце все символы решетки.
Два загона считаются изолированными, если, двигаясь по свободным клеткам с общими сторонами, нельзя
попасть из первого загона во второй.

Формат вывода
В единственной строке выведите "GOODBARN" (без кавычек), если сарай подходит для Джона.
В противном случае выведите "FEWROOMS".

Пример
Ввод
2
3 6
######
#.##.#
######

Вывод
GOODBARN

Ввод
2
4 5
#####
#...#
#...#
#####

Вывод
FEWROOMS


ТЕЛЕФОН ФИБОНАЧЧИ
Ограничение на время работы 1 секунда
Ограничение на память 64 мегабайт

-- Саша, нужна твоя помощь! -- сказал Петя, вглядываясь в напряженное лицо Саши,
который сидел за компом и решал задачу.

-- Что случилось? -- спросил Саша, радостно глядя на вердикт "Accepted" на мониторе.

-- Вчера я познакомился с одной девушкой, и попросил ее номер телефона.
Она отправила мне pdf документ, -- Петя достал листок из кармана, развернул и протянул Саше.
Саша взял лист. На листе были написаны $M$ номеров и одна фраза "Только мой номер является
некой непрерывной подпоследовательностью цифр в $N$м числе Фибоначчи"

Напомним что $N$-е число Фибоначчи это $N$-й элемент числовой последовательности,
заданной таким образом:

$$ F_n=\begin{cases} 0,&\text{ если $n = 0$;}\\ 1,&\text{ если $n = 1$;}\\ F_{n-1}+F_{n-2}&\text{ если $n \ge 2$} \end{cases} $$

Формат ввода
В первой строке входных данных через пробел даны два целых числа $N$ и $M$ ($64 \le N \le 8192$, $1 \le M \le 10000$).
Далее идут $M$ строк в каждой строке записана последовательность цифр, состоящая ровно из $8$ми цифр.

Формат вывода
В единственной строке выведите номер телефона той девушки (гарантируется что
ответ всегда существует).

Пример
Ввод
64 3
98136313
12345678
09857723

Вывод
09857723

$64$е число Фибоначчи равно $10610209857723$, отсюда видно,
что из данных строк только строка $09857723$ содержится в этом числе, следовательно
это номер телефона той девушки.

[kp9r4d]

Все задачи очень простые. Неясно что и обсуждать.

[frankenstein]

Ну, об этом я уже сказал. Но все равно спасибо.
"Задачи очень простые" не очень точная оценка, может расцените по предложенной шкале?

[Corund]

2
4 5
#####
#.#.#
#####
#####

такой вариант не подходит?

[frankenstein]

Corund в сообщении #871869 писал(а):

2
4 5
#####
#.#.#
#####
#####

такой вариант не подходит?

А какой для него правильный ответ?

[venco]

Corund в сообщении #871869 писал(а):

2
4 5
#####
#.#.#
#####
#####

такой вариант не подходит?

Должен подходить. Две области на двух быков.

[frankenstein]

frankenstein в сообщении #871879 писал(а):

Corund в сообщении #871869 писал(а):

2
4 5
#####
#.#.#
#####
#####

такой вариант не подходит?

А какой для него правильный ответ?

Попробуйте написать программу, которая отвечает на такой вопрос.

[Corund]

Ну перед написанием программы неплохо бы просто понять условие задачи - а в примере для двух быков сарайчик размером 4 на 5 признан негодным, хотя вроде бы все наоборот.

[venco]

А при чём тут размер сарайчика? Требуется то не размер.
Примеры правильные.

[rockclimber]

frankenstein в сообщении #871803 писал(а):

"Задачи очень простые" не очень точная оценка, может расцените по предложенной шкале?

Возможно, я слишком требователен, но мне кажется, что задачу №1, например, должен уметь решать каждый семклассник... Ну хорошо, каждый семиклассник, претендующий на "5"

[frankenstein]

rockclimber в сообщении #872066 писал(а):

frankenstein в сообщении #871803 писал(а):

"Задачи очень простые" не очень точная оценка, может расцените по предложенной шкале?

Возможно, я слишком требователен, но мне кажется, что задачу №1, например, должен уметь решать каждый семклассник... Ну хорошо, каждый семиклассник, претендующий на "5"

Да, вы точно угадали, она как раз взята из книги олимпиадных задач средней школы.
Она планировалась как легкая задача, которую должны решить все. Но, когда я смотрел
на код участников, думал "Перепрограммировали", "Слишком увлеклись программированием и забыли простые вещи".
Многие решали так. Вычисляли факториал числа, а затем делили его на 10 пока возможно, и попутно считали сколько было делений. Естественно, их код слетал, как только они пробовали вычислить допустим 100! или более.