Existem vagas de estacionamento P em um estacionamento, embora alguns sejam ocupados por carros representados por octothorpes, #enquanto os espaços livres são pontos .. Logo chegarão os caminhões T, cada um dos quais ocupará exatamente L espaços consecutivos. Os caminhões não precisam ser estacionados um ao lado do outro.

Sua tarefa é criar um programa que encontre o menor número de carros que precisam ser removidos para estacionar todos os caminhões. Sempre haverá espaços suficientes para caber em todos os caminhões, o que significaT*L<P

Entrada

Na primeira linha, haverá três números inteiros, P, T e L separados por espaços. Na segunda linha, haverá uma sequência de caracteres P representando o estacionamento em seu estado inicial.

Resultado

Na primeira e única linha, seu programa deve imprimir o menor número de carros que precisam ser removidos para estacionar todos os caminhões.

Casos de teste

Entrada:
6 1 3
#.#.##

Resultado: 1

Entrada:
9 2 3
.##..#..#

Resultado: 2

Entrada:
15 2 5
.#.....#.#####.

Resultado: 3

O menor código vence. (Observação: estou particularmente interessado em uma implementação de pyth, se for possível)

Python 2, 154 bytes

I,R=raw_input,range
P,T,L=map(int,I().split())
S=I()
D=R(P+1)
for r in R(P):D[1:r+2]=[min([D[c],D[c-1]+(S[r]<".")][c%L>0:])for c in R(1,r+2)]
print D[T*L]

Uma abordagem direta de DP. Uma boa parte do programa está apenas lendo a entrada.

Explicação

Calculamos uma tabela de programação dinâmica 2D em que cada linha corresponde aos primeiros nlugares de estacionamento e cada coluna corresponde ao número de caminhões (ou partes de um caminhão) colocados até agora. Em particular, coluna ksignifica que colocamos k//Lcaminhões cheios até agora e estamos k%Lno caminho de um caminhão novo. Cada célula é, então, o número mínimo de carros a serem liberados para atingir o estado (n,k), e nosso estado alvo é (P, L*T).

A ideia por trás da recorrência do DP é a seguinte:

• Se temos k%L > 0espaço para um caminhão novo, nossa única opção é ter vindo de k%L-1espaço para um caminhão novo
• Caso contrário, se k%L == 0acabamos de terminar um caminhão novo ou já terminamos o último caminhão e, desde então, pulamos alguns lugares de estacionamento. Tomamos o mínimo das duas opções.

Se k > n, ou seja, tivermos colocado mais quadrados de caminhões do que vagas de estacionamento, então colocaremos ∞para estado (n,k). Mas, para fins de golfe, colocamos, kjá que este é o pior caso de remover todos os carros e também serve como limite superior.

Isso foi um bocado, então vamos dar um exemplo, digamos:

5 1 3
..##.

As duas últimas linhas da tabela são

[0, 1, 2, 1, 2, ∞]
[0, 0, 1, 1, 1, 2]

A entrada no índice 2 da segunda última linha é 2, porque para atingir um estado de 2//3 = 0caminhões cheios colocados e 2%3 = 2espaços para um caminhão novo, esta é a única opção:

  TT
..XX

Mas a entrada no índice 3 da segunda última linha é 1, porque para atingir um estado de 3//3 = 1caminhões cheios colocados e 3%3 = 0espaços para um caminhão novo, o ideal é

TTT
..X#

A entrada no índice 3 da última linha considera as duas células acima como opções - pegamos o caso em que temos 2 espaços para um caminhão novo e o terminamos ou pegamos o caso em que temos um caminhão cheio já terminado?

  TTT            TTT
..XX.     vs     ..X#.

Claramente, o último é melhor, então colocamos um 1.

Pitão, 70 bytes

JmvdczdKw=GUhhJVhJ=HGFTUhN XHhThS>,@GhT+@GTq@KN\#>%hT@J2Z)=GH)@G*@J1eJ

Basicamente, uma porta do código acima. Ainda não muito bem jogado. Experimente online

Expandido

Jmvdczd              J = map(eval, input().split(" "))
Kw                   K = input()
=GUhhJ               G = range(J[0]+1)
VhJ                  for N in range(J[0]):
=HG                    H = G[:]
FTUhN                  for T in range(N+1):
 XHhT                    H[T+1] =
hS                                sorted(                                        )[0]
>                                                                 [            :]
,                                        (      ,                )
@GhT                                      G[T+1]
+@GTq@KN\#                                       G[T]+(K[N]=="#")
>%hT@J2Z                                                           (T+1)%J[2]>0
)=GH                   G = H[:]
)@G*@J1eJ            print(G[J[1]*J[-1]])

Agora, se ao menos Pyth tivesse várias atribuições para> 2 variáveis ​​...

Haskell, 196 caracteres

import Data.List
f=filter
m=map
q[_,t,l]=f((>=t).sum.m((`div`l).length).f(>"-").group).sequence.m(:".")
k[a,p]=minimum.m(sum.m fromEnum.zipWith(/=)p)$q(m read$words a)p
main=interact$show.k.lines

Executa todos os exemplos

& (echo 6 1 3 ; echo "#.#.##" )  | runhaskell 44946-Trucks.hs 
1

& (echo 9 2 3 ; echo ".##..#..#" )  | runhaskell 44946-Trucks.hs 
2

& (echo 15 2 5 ; echo ".#.....#.#####." )  | runhaskell 44946-Trucks.hs 
3

Um pouco lento: O (2 ^ P) onde P é o tamanho do lote.

Provavelmente ainda resta muito para jogar golfe.