Сломанные ступеньки

@Капинус · Регистрация: 05.08.2017

Студворк — интернет-сервис помощи студентам

Всем привет. Помогите доработать задачу.

Заяц может ходить на следующую ступеньку, переступать через одну и через две, однако некоторые ступеньки сломаны. Сколькими способами можно попасть на N-ю ступеньку.

входные данные
В первой строке записано число N - номер ступеньки на которую нужно попасть и K - количество сломанных ступеней. (1 ≤ k ≤ n ≤ 60). В следующей строке записаны номера ступеней которые сломаны.

Исходные данные
Вывести одно число, количество способов которыми можно попасть на строчку с номером N, или -1, если попасть невозможно.

Задачу написал для варианта, когда ступеньки не сломаны.
Помоите дописать код, для сломаных ступенек.

Спасибо

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var n,i: byte;
a,b,c,q: uint64;
begin
readln(n);
a:=1 ;
b:=2 ;
c:=4 ;
case n of
1: q:=1;
2: q:=2;
3: q:=4;
end;
for i:=n downto 4 do
begin
q:=a+b+c;
a:=b; b:=c; c:=q
end;
writeln(q); 
end.

Суть моей идеи такова: если минимум 3 сломанные ступеньки идут рядом, тогда -1 иначе результат.
Вот код, но он не правильный, наверное:

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
var k,n,i: byte;
a,b,c,q,j: uint64;
a1:array[-99999..99999] of longint;
begin
read(n);
read(k);
for j:=1 to k do
begin
read (a1[j]);
end;
n:=n-k;
a:=1 ;
b:=2 ;
c:=4 ;
case n of
1: q:=1;
2: q:=2;
3: q:=4;
end;
for i:=n downto 4 do
begin
q:=a+b+c;
a:=b; b:=c; c:=q
end;
if ((j+(j+1)+(j+2)) div 3)=(j+1) then 
writeln ('-1') else
writeln(q);
end.

@кот Бегемот · 04.11.2017, 12:33

Ищи задачку "Зайчик", она здесь несколько раз мелькала. А вообще - это известная олимпиадная задача на динамическое программирование.

@Капинус · 04.11.2017, 18:08 **[ТС]**

Нашёл я зайца. В условии то что у меня. Мне нужно доработать программу при условии что ступеньки сломаны. Спасибо всем кто поможет

@Капинус · 06.11.2017, 14:36 **[ТС]**

Вот мой код вроде на Паскале работает, а на сайте проходит на 20%.
Суть идеии: если количество сломанных ступенек больше 2 и j+1 элемент находится между j и j+2 элементами (3 сломанные ступеньки идут подряд) то -1 иначе результат.
Помогите найти ошибку

Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
var k,kp,n,i: byte;
a,b,c,q,j: int64;
a1:array[-999..999] of longint;
p:boolean;
begin
read(n);
read(k);
for j:=1 to k do
begin
read (a1[j]);
end;
kp:=0;
for j:=1 to k do
begin
kp:=kp+1;
end;
for j:=1 to k do
begin
if (kp>2) and (a1[j+1]=a1[j]+1)and (a1[j+1]=a1[j+2]-1) then p:=true;
end;
begin
n:=n-k;
a:=1 ;
b:=2 ;
c:=4 ;
case n of
1: q:=1;
2: q:=2;
3: q:=4;
end;
for i:=n downto 4 do
begin
q:=a+b+c;
a:=b; b:=c; c:=q
end;
if p then writeln ('-1') else
writeln(q);
end;
end.

Новые блоги и статьи Все статьи Все блоги /
SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .	Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .
SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .	SDL3 для Android: Подключение Box2D v3, физика и отрисовка коллайдеров 8Observer8 29.01.2026 Содержание блога Box2D - это библиотека для 2D физики для анимаций и игр. С её помощью можно определять были ли коллизии между конкретными объектами. Версия v3 была полностью переписана на Си, в. . .	Инструменты COM: Сохранение данный из VARIANT в файл и загрузка из файла в VARIANT bedvit 28.01.2026 Сохранение базовых типов COM и массивов (одномерных или двухмерных) любой вложенности (деревья) в файл, с возможностью выбора алгоритмов сжатия и шифрования. Часть библиотеки BedvitCOM Использованы. . .	SDL3 для Android: Загрузка PNG с альфа-каналом с помощью SDL_LoadPNG (без SDL3_image) 8Observer8 28.01.2026 Содержание блога SDL3 имеет собственные средства для загрузки и отображения PNG-файлов с альфа-каналом и базовой работы с ними. В этой инструкции используется функция SDL_LoadPNG(), которая. . .

@кот Бегемот Платежеспособный зверь 8966 / 4389 / 1655 Регистрация: 28.10.2009 Сообщений: 11,647
	04.11.2017, 12:33
	Ищи задачку "Зайчик", она здесь несколько раз мелькала. А вообще - это известная олимпиадная задача на динамическое программирование. 0

@Капинус 2 / 2 / 1 Регистрация: 05.08.2017 Сообщений: 61
	04.11.2017, 18:08 [ТС]
	Нашёл я зайца. В условии то что у меня. Мне нужно доработать программу при условии что ступеньки сломаны. Спасибо всем кто поможет 0