Форум программистов, компьютерный форум, киберфорум
alhaos
Войти
Регистрация
Восстановить пароль
Оценить эту запись

Задача №11 Зайчик

Запись от alhaos размещена 25.10.2020 в 17:33

Красноярский краевой Дворец пионеров, (c)2006 - 2020

В нашем зоопарке появился заяц. Его поместили в клетку, и чтобы ему не было скучно, директор зоопарка распорядился поставить в его клетке лесенку. Теперь наш зайчик может прыгать по лесенке вверх, перепрыгивая через ступеньки. Лестница имеет определенное количество ступенек N. Заяц может одним прыжком преодолеть не более К ступенек. Для разнообразия зайчик пытается каждый раз найти новый путь к вершине лестницы. Директору любопытно, сколько различных способов есть у зайца добраться до вершины лестницы при заданных значениях K и N. Помогите директору написать программу, которая поможет вычислить это количество. Например, если K=3 и N=4, то существуют следующие маршруты: 1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2, 1+3, 3+1. Т.е. при данных значениях у зайца всего 7 различных маршрутов добраться до вершины лестницы.


Входные данные
В единственной строке входного файла INPUT.TXT записаны два натуральных числа K и N (1 ≤ K ≤ N ≤ 300). К - максимальное количество ступенек, которое может преодолеть заяц одним прыжком, N – общее число ступенек лестницы.

Выходные данные
В единственную строку выходного файла OUTPUT.TXT нужно вывести количество возможных вариантов различных маршрутов зайца на верхнюю ступеньку лестницы без ведущих нулей.

PowerShell
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
class problem_011 {
    static solve ([String]$inputFileName, [string]$outputFileName){
    [int]$MaxGroupCount, [int]$StarsCount = [int[]]((GC C:\PROBLEMS\011\INPUT.TXT) -split "[^\d-]+")
        &{
            param(
                [Int]$StarsCount,
                [Int]$MaxGroupCount,
                [Int]$CaseCount
            )
 
            $Places = $StarsCount - 1
            For ($i = 0; $i -le ([math]::Pow(2, $Places)-1); $i++){
                $case = [Convert]::ToString($i,2)
                $stringCase = $($case.PadLeft($Places,'0'))
                $rep = "*$($case.PadLeft($Places,'0') -replace 0, ' *' -replace 1, '|*')"
                $StarsArray = ($rep -replace " " -split "\|").ForEach({$_.Length}) 
                if (($StarsArray | Measure-Object -Maximum).Maximum -le $MaxGroupCount)
                {
                    #"$rep ($($StarsArray -join ","))"        
                    $CaseCount++
                }
            }
            $CaseCount
        } -StarsCount $StarsCount -MaxGroupCount $MaxGroupCount| Out-File $outputFileName
    }
}
 
[problem_011]::solve('C:\PROBLEMS\011\INPUT.TXT', 'C:\PROBLEMS\011\OUTPUT.TXT')
Размещено в Без категории
Просмотров 621 Комментарии 1
Всего комментариев 1
Комментарии
  1. Старый комментарий
    Ох уж мне этот заяц
    Запись от alhaos размещена 25.10.2020 в 17:34 alhaos на форуме
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.