Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], skipTags: ["script","noscript","style","textarea","code"], processEscapes: true }});

Problem A
  Secret of Chocolate Poles

  Wendy, the master of a chocolate shop, is thinking of displaying poles of chocolate disks in the showcase. She can use three kinds of chocolate disks: white thin disks, dark thin disks, and dark thick disks. The thin disks are $1$ cm thick, and the thick disks are $k$ cm thick. Disks will be piled in glass cylinders.

  Each pole should satisfy the following conditions for her secret mission, which we cannot tell.

 A pole should consist of at least one disk.

 The total thickness of disks in a pole should be less than or equal to $l$ cm.

 The top disk and the bottom disk of a pole should be dark.

 A disk directly upon a white disk should be dark and vice versa.

  As examples, six side views of poles are drawn in Figure A.1. These are the only possible side views she can make when $l = 5$ and $k = 3$.

  
  

    Figure A.1. Six chocolate poles corresponding to Sample Input 1
  

  Your task is to count the number of distinct side views she can make for given $l$ and $k$ to help her accomplish her secret mission.

Input

  The input consists of a single test case in the following format.

$l$ $k$

  Here, the maximum possible total thickness of disks in a pole is $l$ cm, and the thickness of the thick disks is $k$ cm. $l$ and $k$ are integers satisfying $1 \leq l \leq 100$ and $2 \leq k \leq 10$.

Output

  Output the number of possible distinct patterns.

Sample Input 1

5 3

Sample Output 1

6

Sample Input 2

9 10

Sample Output 2

5

Sample Input 3

10 10

Sample Output 3

6

Sample Input 4

20 5

Sample Output 4

86

Sample Input 5

100 2

Sample Output 5

3626169232670



Sample input:
5 3


Sample output:
6

Submission status: Wrong Answer

Solution code:
import math

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def main():
    l = list(map(int, input().split()))
    combinate_a = []
    combinate_b = []
    ans = 0
    for a in range(l[0]):
        for b in range(l[0]):
            if (l[1] + 1) * a + 2 * b <= l[0] + 1:
                combinate_a.append(a)
                combinate_b.append(b)

            if (l[1] + 1) * a + 2 * b > l[0] + 1:
                break

    for i in range(1, len(combinate_a)):
        if combinate_a[i] == 0:
            ans += 1

        else:
            ans += combinations_count(combinate_a[i]+combinate_b[i], combinate_a[i])
            
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
l, k = map(int, raw_input().split())

d = [[0, 0] for i in xrange(l + 1)]
d[0][1] = 1
s = 0
for i in xrange(1, l + 1):
    d[i][0] = d[i - 1][1]
    d[i][1] = d[i - 1][0]
    if i >= k:
        d[i][0] += d[i - k][1]
    s += d[i][0]
print s

Submission status: Accepted

Solution code:
l,k = map(int,input().split())
dp = [[0,0] for i in range(l+1)]
dp[1][0] = 1
if k <= l:
    dp[k][0] = 1
for h in range(1,l):
    dp[h+1][0] += dp[h][1]
    dp[h+1][1] += dp[h][0]
    if h+k <= l:
        dp[h+k][1] += dp[h][0]
ans = 0
for b,w in dp:
    ans += b
print(ans)

Submission status: Accepted

Solution code:
l, k = map(int, input().split())
memo = {(l, 0): 1, (l, 1): 0}
def dfs(cur, dark):
    if (cur, dark) in memo:
        return memo[cur, dark]
    res = dfs(cur + 1, dark^1) + (dark^1)
    if dark and cur + k <= l:
            res += dfs(cur + k, dark^1)
    memo[cur, dark] = res
    return res
print(dfs(0, 1))

Submission status: Accepted

Solution code:
import math
l, k = map(int, input().split())
c = 0
for i in range(1, int((l + 1) / 2) + 1):
    for j in range(i + 1):
        if 2 * i - 1 + j * (k - 1) <= l:
            c += math.factorial(i) / math.factorial(j) / math.factorial(i - j)
        else:
            break
print(int(c))

Submission status: Accepted

Solution code:
#!/usr/bin/env python

from collections import deque, defaultdict
import itertools as ite
import sys
import math
import decimal

sys.setrecursionlimit(1000000)

INF = 10 ** 18
MOD = 10 ** 9 + 7

l, k = map(int, raw_input().split())
DP1 = [0] * 200
DP2 = [1] + [0] * 200

for i in range(1, l + 1):
    DP1[i] = DP2[i - 1]
    DP2[i] = DP1[i - 1]
    if i >= k:
        DP1[i] += DP2[i - k]
print sum(DP1)

Submission status: Accepted

Solution code:
#!/usr/bin/python3

import os
import sys


def main():
    L, K = read_ints()
    print(solve(L, K))


def solve(L, K):
    D = [[0, 0] for _ in range(L + 1)]
    D[1][0] = 1
    if K <= L:
        D[K][0] = 1

    for i in range(1, L):
        D[i + 1][1] += D[i][0]
        D[i + 1][0] += D[i][1]
        if i + K <= L:
            D[i + K][0] += D[i][1]

    return sum([D[i][0] for i in range(1, L + 1)])


###############################################################################

DEBUG = 'DEBUG' in os.environ


def inp():
    return sys.stdin.readline().rstrip()


def read_int():
    return int(inp())


def read_ints():
    return [int(e) for e in inp().split()]


def dprint(*value, sep=' ', end='\n'):
    if DEBUG:
        print(*value, sep=sep, end=end)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def main():
    l, k = map(int, input().split())

    dp = [[0] * 2 for i in range(101)]
    dp[0][1] = 1
    ans = 0
    for i in range(1, l+1):
        dp[i][0] = dp[i-1][1]
        if i-k >= 0:
            dp[i][0] += dp[i-k][1]
        dp[i][1] = dp[i-1][0]
        ans += dp[i][0]
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from functools import lru_cache  # おまじない

l,k=map(int,input().split())

@lru_cache()     # python 素晴らしい
def rec(i,isBlack):
    if i < 0: return 0
    if i == 0: return 1 if not isBlack else 0  # black at bottom
    if isBlack: # top is black
        return rec(i-1, False) + rec(i-k, False)
    else:  # top is white
        return rec(i-1, True)

ans = sum ( rec(i,True) for i in range(1, l+1))
    
print(ans)

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LS()
    return l
sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n,k = LI()
    ans = 0
    for l in range(1,n+1):
        for i in range(1000):
            if i*k > l:break
            j = l-i*k+i
            if j%2:
                j //= 2
                j += 1
                s = 1
                for a in range(i):
                    s *= j-a
                    s //= a+1
                ans += s
    print(ans)
    return

#B
def B():
    return

#C
def C():
    return

#D
def D():
    return

#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#I
def I_():
    return

#J
def J():
    return

#Solve
if __name__ == "__main__":
    A()

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    def f(l,k):
        r = [0] * (l+1)
        r[1] = 1
        if l >= k:
            r[k] += 1
        for i in range(1,l):
            if i + 2 <= l:
                r[i+2] += r[i]
            if i + 1 + k <= l:
                r[i+1+k] += r[i]

        return sum(r)


    while 1:
        n,m = LI()
        if n == 0:
            break
        rr.append(f(n,m))
        break

    return '\n'.join(map(str, rr))


print(main())

Submission status: Accepted

Solution code:
l, k = map(int, input().split())

dpW = [0] * 101
dpB = [0] * 101

dpW[0] = 1

ans = 0
for i in range(1, l + 1):
    if i >= k:
        dpB[i] += dpW[i - k]
        ans += dpW[i - k]
        
    dpB[i] += dpW[i - 1]
    dpW[i] += dpB[i - 1]
    ans += dpW[i - 1]

print(ans)

Submission status: Accepted

Solution code:
l , k = [int(i) for i in input().split()]

INIT = 0
tableB = [INIT] * 110
tableW = [INIT] * 110
tableW[0] = 1

for i in range(1,l+1):
  tableB[i] += tableW[i-1]
  if i - k >= 0:
    tableB[i] += tableW[i-k]
  tableW[i+1] = tableB[i]

print(sum(tableB))
#print(tableB)