Il y a P places de parking dans un parking, bien que certains espaces soient occupés par des voitures représentées par des octothorpes #tandis que les espaces libres sont des points .. Bientôt arrivent des camions T, dont chacun occupera exactement L espaces consécutifs. Les camions n'ont pas besoin d'être garés côte à côte.

Votre tâche consiste à créer un programme qui trouvera le plus petit nombre de voitures à retirer pour garer tous les camions. Il y aura toujours suffisamment d'espace pour accueillir tous les camions, ce qui signifieT*L<P

Contribution

Dans la première ligne, il y aura trois entiers, P, T et L séparés par des espaces. Dans la deuxième rangée, il y aura une chaîne de caractères P représentant le parking dans son état initial.

Production

Dans la première et la seule ligne, votre programme devrait imprimer le plus petit nombre de voitures à retirer pour garer tous les camions.

Cas de test

Contribution:
6 1 3
#.#.##

Production: 1

Contribution:
9 2 3
.##..#..#

Production: 2

Contribution:
15 2 5
.#.....#.#####.

Production: 3

Le code le plus court gagne. (Remarque: je suis particulièrement intéressé par une implémentation pyth, si possible)

Python 2, 154 octets

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]

Une approche DP simple. Une bonne partie du programme ne fait que lire les entrées.

Explication

Nous calculons une table de programmation dynamique 2D où chaque ligne correspond aux premières nplaces de stationnement, et chaque colonne correspond au nombre de camions (ou parties de camion) placés jusqu'à présent. En particulier, la colonne ksignifie que nous avons k//Ljusqu'à présent placé des camions pleins et que nous sommes k%Len route pour un nouveau camion. Chaque cellule est alors le nombre minimal de voitures à nettoyer pour atteindre l'état (n,k), et notre état cible est (P, L*T).

L'idée derrière la récurrence du DP est la suivante:

• Si nous sommes des k%L > 0espaces pour un nouveau camion, alors notre seule option est d'avoir été des k%L-1espaces pour un nouveau camion
• Sinon, si k%L == 0nous venons de terminer un nouveau camion, ou si nous avions déjà terminé le dernier camion et avons depuis sauté quelques places de stationnement. Nous prenons le minimum des deux options.

Si k > n, c'est-à-dire que nous avons placé plus de places de camion qu'il n'y a de places de stationnement, alors nous mettons ∞pour l'état (n,k). Mais pour les besoins du golf, nous avons mis kcar il s'agit du pire cas de suppression de chaque voiture, et sert également de limite supérieure.

Ce fut une bouchée, alors prenons un exemple, disons:

5 1 3
..##.

Les deux dernières lignes du tableau sont

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

L'entrée à l'index 2 de l'avant-dernière ligne est 2, car pour atteindre un état de 2//3 = 0camions pleins placés et étant des 2%3 = 2espaces le long d'un nouveau camion, c'est la seule option:

  TT
..XX

Mais l'entrée à l'index 3 de l'avant-dernière ligne est 1, car pour atteindre un état de 3//3 = 1camions pleins placés et étant des 3%3 = 0espaces le long d'un nouveau camion, l'optimal est

TTT
..X#

L'entrée à l'index 3 de la dernière ligne considère les deux cellules ci-dessus comme des options - prenons-nous le cas où nous sommes deux espaces pour un nouveau camion et terminons-le, ou prenons-nous le cas où nous avons un camion plein déjà fini?

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

Clairement, ce dernier est meilleur, nous avons donc mis un 1.

Pyth, 70 octets

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

Fondamentalement, un port du code ci-dessus. Pas encore très bien joué au golf. Essayez-le en ligne

Étendu

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]])

Maintenant, si seulement Pyth avait une affectation multiple à> 2 variables ...

Haskell, 196 caractères

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

Exécute tous les exemples

& (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

Un peu lent: O (2 ^ P) où P est la taille du lot.

Il reste probablement beaucoup de golf ici.