Сколькими способами Вася может добраться до последней ступеньки

@Like a Sir · Регистрация: 07.01.2019

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

Здравствуйте!Помогите решить данную задачу,спасибо!
Вася стоит на первой ступеньке свежепокрашенной лестницы и собирается подняться на самую верхнюю, одиннадцатую ступеньку. Некоторые ступеньки лестницы, а именно, ступеньки с номерами 4 и 8 еще не до конца высохли, и наступать на них Вася не намерен. Сколькими способами Вася может добраться до последней ступеньки, если он готов шагнуть на следующую ступеньку или перешагнуть через одну ступеньку. Вниз Вася ни в какой момент не спускается.

Комментарий. Если бы лестница состояла из четырех высохших ступенек, то Вася смог бы подняться с первой на четвертую тремя способами — шагая каждый раз на следующую ступеньку; сначала сделав шаг с первой на вторую, а потом сразу на четвертую; сначала с первой шагнув на третью, а потом с третьей на четвертую.

@Chvick · 30.03.2019, 18:00

Стандартная задача на дп.
Строите одномерный массив возможных шагов из данной клетки. Т е стоите в данной клетке и прибавляете к клеткам, куда можете походить, число вариантов добраться до данной(ans[1]=1), а клетки, которые не высохли игнорируете

Pascal

const size=1000;
var
  ans:array[1..size] of int64;
  suhaya:array[1..size] of byte;
  i, n:longint;
begin
  readln(n);
  for i:=1 to n do
    read(suhaya[i]); //тут вводите строку из 1 и 0, где 1-сухая, 0-не сухая
  if suhaya[n]=0 then 
    begin
    write(0);
    exit;
    end;
  ans[1]:=1;
  for i:=1 to n do
    if suhaya[i]=1 then
    begin
    inc(ans[i+1], ans[i]);
    inc(ans[i+2], ans[i]);
    inc(ans[i+3], ans[i]);
    end;
  write(ans[n]);
end.

@Like a Sir · 30.03.2019, 18:16 **[ТС]**

Спасибо!Понял.

@Cyborg Drone · 31.03.2019, 00:45

Chvick, решение неверное. Для лестницы, указанной в задании, то есть, если n = 11 и suhaya = (1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1), существует всего 8 способов её преодоления, поскольку в этом случае каждую мокрую ступеньку можно преодолеть только одним способом, а каждые подряд идущие три сухих ступеньки - двумя способами. Получается 2 * 1 * 2 * 1 * 2 = 8 способов. Вот они (числа - длина шага в ступенях):

1, 1, 2, 1, 1, 2, 1, 1
1, 1, 2, 1, 1, 2, 2
1, 1, 2, 2, 2, 1, 1
1, 1, 2, 2, 2, 2
2, 2, 1, 1, 2, 1, 1
2, 2, 1, 1, 2, 2
2, 2, 2, 2, 1, 1
2, 2, 2, 2, 2

Однако, Ваша программа утверждает, что таких способов 34.

Как исправить: нужно удалить строку 21.

Замечание: программа будет нормально работать только в Pascal ABC и в Pascal ABC.NET. Для совместимости с прочими диалектами паскаля проще всего добавить readln; перед строкой 10 и, возможно, перед строкой 24.

@Chvick · 31.03.2019, 17:40

Cyborg Drone, вы не правы. На FreePascal(3.0.4) всё прекрасно работает, а именно он является основным и, чаще всего, единственным возможным вариантов паскаля на олимпиадах.
А решение работает в этой задаче, если Ваня может переступать ещё и через две ступеньки. Что же поделать, если глаза видят то, чего нет

Давайте-ка тогда улучшим решение. В этой новой версии вы можете выбирать, через сколько ступенек Ванька может переступить.

Pascal

const size=1000;
var
  ans:array[1..size] of int64;
  suhaya:array[1..size] of byte;
  i, n, j, m:longint;
begin
  read(n, m);//n - кол-во ступенек, m-максимальное число ступенек, через которое 
             //может переступить Ваня(в вашем случае m=1)
  inc(m);
  for i:=1 to n do
    read(suhaya[i]); //тут вводите строку из 1 и 0, где 1-сухая, 0-не сухая
  if suhaya[n]=0 then 
    begin
    write(0);
    exit;
    end;
  ans[1]:=1;
  for i:=1 to n do
    if suhaya[i]=1 then
      for j:=1 to m do
       inc(ans[i+j], ans[i]);
  write(ans[n]);
end.

@кот Бегемот · 31.03.2019, 22:33

Chvick, Ваше решение нельзя назвать удовлетворительным. Представьте себе, что лестница состоит из 3000 ступенек, её тоже прикажете вводить?
Самая простая программа такая:

Pascal

var
a:array[0..11]of integer;
i:integer;
begin
a[1]:=1;
for i:=2 to 11 do
begin
  if (i=4)or(i=8)then a[i]:=0 else
   begin
     a[i]:=a[i]+a[i-1];
     a[i]:=a[i]+a[i-2];
   end;
end;
writeln(a[11]);
end.

@Cyborg Drone · 31.03.2019, 22:45

Chvick, Free Pascal в чистом виде я никогда не использовал, всегда в комплекте с Lazarus. Консольное окно закрывается, как только программа заканчивает работу. Что там за результат, увидеть не успеешь. Кроме того, read, readln, write и writeln работают правильно, а не как в PABC. Например, если с помощью read попытаться ввести что-нибудь, реально введено ничего не будет до тех пор, пока не будет нажат <Enter>, и, если затем попытаться вести строку, догадайтесь, что будет введено? Правильно, пустая строка (<Enter> из буфера ввода клавиатуры). Никогда нельзя путать read и readln, write и writeln, иногда это порождает трудно обнаруживаемые ошибки. Конечно, обычно на проверочных сайтах стандартный ввод-вывод перенаправлен на файлы, поэтому можно использовать только read и write, а о readln и writeln смело забыть. Это одна из причин, почему я (сильно) не люблю проверочные (олимпийские) сайты, и стараюсь на них вообще не заходить. Всё сделано как-то несуразно, за исключением, может быть, (эталонных) реализаций некоторых алгоритмов (и то, сдаётся мне, полученных от абонентов сайта). С целой горой каких-то условностей и допущений. Знаете, как ковбой на корове: вроде и седло под ним, вроде и едет, но что-то не так...

@кот Бегемот · 01.04.2019, 11:41

Cyborg Drone, нет никакой беды в том, что консольное окно во FreePascal (как и в Турбо) закрывается после выполнения программы - два щелчка по менюшке Debug, Output или Debug, User Screen и наслаждайтесь результатом пока не надоест без всяких лишних добавлений в программу команды readln. Если, конечно, Вы не настолько ленивы, чтобы два раза щёлкнуть мышью.

PS окно вывода можно и зафиксировать в нижней части экрана и вообще не заморачиваться.

@Cyborg Drone · 01.04.2019, 12:55

кот Бегемот, лень здесь ни при чём, readln набирать дольше, чем два раза щёлкнуть мышкой

. Это у меня такая забота о программе (и о том, чтобы моё настроение не портилось). Сами знаете, что есть люди, которые не в силах понять смысл Вашего первого предложения, но считают себя шибко умными. Я был поражён и обескуражен, когда это узнал, и поначалу думал, что надо мною цинично издеваются. Очень неприятно бывает иногда слышать, что "твоя программа не работает", особенно, когда выясняется, что "работает" говнокод с файлопомойки со священными uses crt и repeat until keypressed. Проще написать readln, и программа с большой степенью вероятности сможет выдержать прямое попадание в руки самого махрового неуча и лентяя. И программа "работает", и глупый вопрос "а нельзя ли без repeat until keypressed?" не задаётся. Другой вопрос: стоит ли помогать? Но - я добрый, а к конструированию саморассыпающихся ракет неучей и лентяев не допускают (вроде бы). Хотя, по большому счёту, сейчас этот readln нужен разве что если только есть хотелка, чтобы экзешник не закрывался даже при выставленной опции "закрывать окно после завершения работы". Да и в этом случае, по большому счёту, не нужен.

Блоги программистов
Обновление сайта www.historian.by Reglage 05.01.2025 Обещал подвести итоги 2024 года для сайта. Однако начну с того, что изменилось за неделю. Добавил краткий урок по последовательности действий при анализе вредоносных файлов и значительно улучшил урок. . .	Как использовать GraphQL в C# с HotChocolate Programming 05.01.2025 GraphQL — это современный подход к разработке API, который позволяет клиентам запрашивать только те данные, которые им необходимы. Это делает взаимодействие с API более гибким и эффективным по. . .	Модель полного двоичного суматора с помощью логических операций (python) AlexSky-coder 04.01.2025 def binSum(x:list, y:list): s=^y] p=x and y for i in range(1,len(x)): s. append((x^y)^p) p=(x and y)or(p and (x or y)) return s x=list() y=list()	Это мы не проходили, это нам не задавали...(асихронный счётчик с управляющим сигналом задержки). Hrethgir 04.01.2025 Асинхронный счётчик на сумматорах (шестиразрядный по числу диодов на плате, но наверное разрядов будет больше - восемь или шестнадцать, а диоды на старшие), так как триггеры прошли тестирование и. . .	Руководство по созданию бота для Телеграм на Python IT_Exp 04.01.2025 Боты для Телеграм представляют собой автоматизированные программы, которые выполняют различные задачи, взаимодействуя с пользователями через интерфейс мессенджера. В данной статье мы рассмотрим,. . .	Применение компонентов PrimeVue в Vue.js 3 на TypeScript BasicMan 04.01.2025 Введение в PrimeVue и настройка окружения PrimeVue представляет собой мощную библиотеку компонентов пользовательского интерфейса для Vue. js 3, которая предоставляет разработчикам богатый набор. . .
Как стать Senior developer cpp_developer 04.01.2025 В современной индустрии разработки программного обеспечения позиция Senior Developer представляет собой не просто следующую ступень карьерной лестницы, а качественно новый уровень профессионального. . .	Что известно о дате выхода Windows 12 и чего от нее ждать IT_Exp 04.01.2025 В мире технологий постоянно происходят изменения, и операционные системы не являются исключением. Windows 11, выпущенная в октябре 2021 года, принесла множество инноваций и улучшений, но. . .	Что новенького в .NET Core 9 Programming 04.01.2025 Обзор ключевых изменений в . NET Core 9 Платформа . NET Core продолжает активно развиваться, и версия 9 представляет собой значительный шаг вперед в эволюции этой технологии. Новый релиз. . .	Инструкция по установке python3.13.1 в Debian 12 AlexSky-coder 03.01.2025 sudo apt update sudo apt install build-essential zlib1g-dev libncurses5-dev libgdbm-dev libnss3-dev libssl-dev libreadline-dev libffi-dev wget. . .	Затестил триггеры. архив проекта прилагаю с GOA файлами в настройках архиватора проектов. Hrethgir 03.01.2025 В этот раз нет закольцованности, потому что от неё только глюки, как я понял, логика не вырезанная. Триггеры очень быстрые если верить измерениям с помощью анализатора от Gowin. Есть ещё регистры,. . .	Python в помощь DevOps IT_Exp 03.01.2025 Причины использования Python в работе DevOps Python стал неотъемлемой частью мира DevOps, и это не случайно. Этот язык программирования обладает множеством преимуществ, которые делают его. . .

@Like a Sir 0 / 0 / 0 Регистрация: 07.01.2019 Сообщений: 85
		1
	Сколькими способами Вася может добраться до последней ступеньки 30.03.2019, 16:20. Показов 5153. Ответов 8 Метки pascal abc (Все метки) Здравствуйте!Помогите решить данную задачу,спасибо! Вася стоит на первой ступеньке свежепокрашенной лестницы и собирается подняться на самую верхнюю, одиннадцатую ступеньку. Некоторые ступеньки лестницы, а именно, ступеньки с номерами 4 и 8 еще не до конца высохли, и наступать на них Вася не намерен. Сколькими способами Вася может добраться до последней ступеньки, если он готов шагнуть на следующую ступеньку или перешагнуть через одну ступеньку. Вниз Вася ни в какой момент не спускается. Комментарий. Если бы лестница состояла из четырех высохших ступенек, то Вася смог бы подняться с первой на четвертую тремя способами — шагая каждый раз на следующую ступеньку; сначала сделав шаг с первой на вторую, а потом сразу на четвертую; сначала с первой шагнув на третью, а потом с третьей на четвертую. 0

@Like a Sir 0 / 0 / 0 Регистрация: 07.01.2019 Сообщений: 85
	30.03.2019, 18:16 [ТС]	3
	Спасибо!Понял. 0

@Cyborg Drone Модератор 10063 / 5405 / 3353 Регистрация: 17.08.2012 Сообщений: 16,543
	31.03.2019, 00:45	4
	Сообщение было отмечено Like a Sir как решение Решение Chvick, решение неверное. Для лестницы, указанной в задании, то есть, если n = 11 и suhaya = (1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1), существует всего 8 способов её преодоления, поскольку в этом случае каждую мокрую ступеньку можно преодолеть только одним способом, а каждые подряд идущие три сухих ступеньки - двумя способами. Получается 2 * 1 * 2 * 1 * 2 = 8 способов. Вот они (числа - длина шага в ступенях): 1, 1, 2, 1, 1, 2, 1, 1 1, 1, 2, 1, 1, 2, 2 1, 1, 2, 2, 2, 1, 1 1, 1, 2, 2, 2, 2 2, 2, 1, 1, 2, 1, 1 2, 2, 1, 1, 2, 2 2, 2, 2, 2, 1, 1 2, 2, 2, 2, 2 Однако, Ваша программа утверждает, что таких способов 34. Как исправить: нужно удалить строку 21. Замечание: программа будет нормально работать только в Pascal ABC и в Pascal ABC.NET. Для совместимости с прочими диалектами паскаля проще всего добавить `readln;` перед строкой 10 и, возможно, перед строкой 24. 1

@Cyborg Drone Модератор 10063 / 5405 / 3353 Регистрация: 17.08.2012 Сообщений: 16,543
	31.03.2019, 22:45	7
	Chvick, Free Pascal в чистом виде я никогда не использовал, всегда в комплекте с Lazarus. Консольное окно закрывается, как только программа заканчивает работу. Что там за результат, увидеть не успеешь. Кроме того, read, readln, write и writeln работают правильно, а не как в PABC. Например, если с помощью read попытаться ввести что-нибудь, реально введено ничего не будет до тех пор, пока не будет нажат <Enter>, и, если затем попытаться вести строку, догадайтесь, что будет введено? Правильно, пустая строка (<Enter> из буфера ввода клавиатуры). Никогда нельзя путать read и readln, write и writeln, иногда это порождает трудно обнаруживаемые ошибки. Конечно, обычно на проверочных сайтах стандартный ввод-вывод перенаправлен на файлы, поэтому можно использовать только read и write, а о readln и writeln смело забыть. Это одна из причин, почему я (сильно) не люблю проверочные (олимпийские) сайты, и стараюсь на них вообще не заходить. Всё сделано как-то несуразно, за исключением, может быть, (эталонных) реализаций некоторых алгоритмов (и то, сдаётся мне, полученных от абонентов сайта). С целой горой каких-то условностей и допущений. Знаете, как ковбой на корове: вроде и седло под ним, вроде и едет, но что-то не так... 0

@кот Бегемот Платежеспособный зверь 8956 / 4382 / 1649 Регистрация: 28.10.2009 Сообщений: 11,624
	01.04.2019, 11:41	8
	Cyborg Drone, нет никакой беды в том, что консольное окно во FreePascal (как и в Турбо) закрывается после выполнения программы - два щелчка по менюшке Debug, Output или Debug, User Screen и наслаждайтесь результатом пока не надоест без всяких лишних добавлений в программу команды readln. Если, конечно, Вы не настолько ленивы, чтобы два раза щёлкнуть мышью. PS окно вывода можно и зафиксировать в нижней части экрана и вообще не заморачиваться. 0

@Cyborg Drone Модератор 10063 / 5405 / 3353 Регистрация: 17.08.2012 Сообщений: 16,543
	01.04.2019, 12:55	9
	кот Бегемот, лень здесь ни при чём, readln набирать дольше, чем два раза щёлкнуть мышкой . Это у меня такая забота о программе (и о том, чтобы моё настроение не портилось). Сами знаете, что есть люди, которые не в силах понять смысл Вашего первого предложения, но считают себя шибко умными. Я был поражён и обескуражен, когда это узнал, и поначалу думал, что надо мною цинично издеваются. Очень неприятно бывает иногда слышать, что "твоя программа не работает", особенно, когда выясняется, что "работает" говнокод с файлопомойки со священными uses crt и repeat until keypressed. Проще написать readln, и программа с большой степенью вероятности сможет выдержать прямое попадание в руки самого махрового неуча и лентяя. И программа "работает", и глупый вопрос "а нельзя ли без repeat until keypressed?" не задаётся. Другой вопрос: стоит ли помогать? Но - я добрый, а к конструированию саморассыпающихся ракет неучей и лентяев не допускают (вроде бы). Хотя, по большому счёту, сейчас этот readln нужен разве что если только есть хотелка, чтобы экзешник не закрывался даже при выставленной опции "закрывать окно после завершения работы". Да и в этом случае, по большому счёту, не нужен. 0

Сколькими способами Вася может добраться до последней ступеньки

Решение