--->
7 задач
<---
На бумаге нарисовали клетчатое поле NxM клеток. В каждой клетке нарисовали стрелочку в одном из четырех направлений «вправо», «вверх», «влево» или «вниз».
| ← | → | → | ↓ | ↑ |
| → | ↑ | ↓ | ← | → |
| ↓ | ↑ | → | → | ↓ |
| → | ↑ | ← | ← | ← |
| ← | → | ↓ | ↓ | ↓ |
| ↑ | ↑ | ← | ↓ | ↑ |
Дальше в некоторую клетку этого поля ставят фишку. Затем эту фишку сдвигают в соседнюю клетку в направлении стрелочки, нарисованной в клетке, где стоит фишка. Затем ее снова сдвигают по стрелке, нарисованной в той клетке, где она оказалась. Так продолжается до тех пор, пока фишка не окажется за пределами поля. Однако возможно, что фишка будет бесконечно ходить по полю и никогда не выйдет за его пределы.
Напишите программу, которая по заданному полю определит количество клеток, начав с которых фишка никогда не покинет пределы поля.
Во входном файле заданы сначала размеры поля – число строк N и число столбцов M (1≤N≤1000, 1≤M≤1000). Далее идет N строк по M чисел в каждой, задающих направления стрелочек в клетках. Число 1 обозначает стрелочку вправо, 2 – вверх, 3 – влево, 4 – вниз. Числа в строке разделяются пробелами.
В выходной файл выведите одно число – количество клеток, начав с которых фишка никогда не покинет пределы поля.
Комментарии к примерам тестов.
Пример №1.Соответствует приведенному рисунку. Клетки, начавс которых, фишка никогда не покинет пределов поля на рисунке выделены серым цветом.
6 5 3 1 1 4 2 1 2 4 3 1 4 2 1 1 4 1 2 3 3 3 3 1 4 4 4 2 2 3 4 2
23
2 2 1 2 3 4
0
Скоро в Берляндии пройдет очередная Олимпиада. В рамках подготовки к этому важному мероприятию Берляндолимпстрой уже возвел N объектов и теперь хочет разобраться с тем, во сколько Берляндии это обошлось.
Стройка длилась \(K + 1\) день со дня номер \(0\) по день номер \(K\), причем стоимость j-го объекта в нулевой день была равна \(a_j\) бурлям. Однако каждый следующий день стоимость каждого объекта увеличивалась согласно следующему правилу: стоимость j-го объекта в i-й день становилась равна сумме стоимостей всех объектов с номерами, меньшими или равными j, в предыдущий день. Иначе говоря, \(S_{i,j}\) = \(\sum_{m=1}^{j} S_{i-1,m}\), где \(S_{i,j}\) — стоимость j-го объекта в i-й день. В итоге на j-й объект было потрачено \(S_{K,j}\) , то есть его стоимость в последний \(K\)-й день. \t{Назовем эту величину итоговой стоимостью j-го объекта.}
Такие увеличения стоимостей проектов для Берляндии не редкость, однако оказалось, что и этих денег не хватило! Выяснилось, что в некоторый день i > 0 стоимость некоторого объекта j дополнительно повысилась на пока не известную следователям сумму X (то есть \(S_{i,j}\) = \(\sum_{m=1}^{j} S_{i-1,m}\) + X), что повлияло на стоимости объектов в последующие дни. Следователи выяснили, что из-за этого сумма итоговых стоимостей всех объектов увеличилась на \(R\) бурлей.
Помогите следователям выяснить минимально возможное значение X.
В первой строке входного файла содержатся три целых числа \(N\), \(K\), \(R\): количество олимпийских объектов (\(1 \le N \le 10^5\) ), количество дней увеличения стоимости объектов (\(1 \le K \le 10^5\) ) и количество бурлей, на которое незаконно возросла итоговая сумма (\(1 \le R \le 10^{18}\)). В следующей строке входного файла содержатся N целых чисел \(a_i\) — стоимости объектов в нулевой день (\(1 \le a_i \le 10^9\)).
Единственная строка выходного файла должна содержать единственное целое число — минимально возможное значение \(X\)
Тесты к этой задаче состоят из четырех групп.
0. Тест 1. Тест из условия, оцениваемый в ноль баллов.
1. Тесты 2—25. В тестах этой группы \(N \le 10, K \le 10, a_i \le 10\), искомое значение \(X\) не превосходит \(10\). Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы.
2. Тесты 26—38. В тестах этой группы \(N \le 1 000, K \le 1 000\). Эта группа оценивается в 30 баллов, баллы начисляются только при прохождении всех тестов группы. Решение будет тестироваться на тестах этой группы только в случае прохождения всех тестов первой группы.
3. В тестах этой группы дополнительные ограничения отсутствуют. Эта группа оценивается в 40 баллов. Тесты в этой группе оцениваются \t{независимо}
3 3 12 1 3 3
2