Na parkingu znajdują się miejsca parkingowe P, ale niektóre miejsca są zajęte przez samochody reprezentowane przez oktororpy, #podczas gdy wolne miejsca są kropkami .. Wkrótce przybędą ciężarówki T, z których każda zajmie dokładnie L kolejnych miejsc. Ciężarówki nie muszą być zaparkowane obok siebie.

Twoim zadaniem jest stworzenie programu, który znajdzie najmniejszą liczbę samochodów, które należy usunąć, aby zaparkować wszystkie ciężarówki. Oznacza to, że zawsze będzie wystarczająco dużo miejsca, aby zmieścić wszystkie ciężarówkiT*L<P

Wejście

W pierwszym rzędzie będą trzy liczby całkowite, P, T i L oddzielone spacjami. W drugim rzędzie będzie ciąg P znaków reprezentujących parking w jego początkowym stanie.

Wynik

W pierwszym i jedynym wierszu program powinien wydrukować najmniejszą liczbę samochodów, które należy usunąć, aby zaparkować wszystkie ciężarówki.

Przypadki testowe

Wejście:
6 1 3
#.#.##

Wynik: 1

Wejście:
9 2 3
.##..#..#

Wynik: 2

Wejście:
15 2 5
.#.....#.#####.

Wynik: 3

Najkrótszy kod wygrywa. (Uwaga: szczególnie interesuje mnie implementacja pyth, jeśli taka jest możliwa)

Python 2, 154 bajty

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]

Proste podejście do DP. Spora część programu to tylko czytanie danych wejściowych.

Wyjaśnienie

Obliczamy dynamiczną tabelę programowania 2D, w której każdy rząd odpowiada pierwszym nmiejscom parkingowym, a każda kolumna odpowiada liczbie ustawionych do tej pory ciężarówek (lub części ciężarówki). W szczególności kolumna koznacza, że ​​do k//Ltej pory umieściliśmy pełne ciężarówki i jesteśmy k%Lna drodze do nowej ciężarówki. Każda komórka jest wówczas minimalną liczbą samochodów, które należy wyczyścić, aby osiągnąć stan (n,k), a naszym stanem docelowym jest (P, L*T).

Idea ponownego wystąpienia DP jest następująca:

• Jeśli mamy wolne k%L > 0miejsca na nową ciężarówkę, naszą jedyną opcją jest bycie k%L-1obok nowego ciężarówki
• W przeciwnym razie, jeśli k%L == 0to właśnie skończyliśmy nową ciężarówkę, lub już skończyliśmy ostatnią ciężarówkę i od tego czasu pominęliśmy kilka miejsc parkingowych. Przyjmujemy minimum dwie opcje.

Jeśli k > nnp. Umieściliśmy więcej kwadratów dla ciężarówek niż miejsc parkingowych, to stawiamy ∞na stan (n,k). Ale na potrzeby gry w golfa stawiamy, kponieważ jest to najgorszy przypadek usunięcia każdego samochodu, a także służy jako górna granica.

To było całkiem kęs, więc dajmy przykład, powiedz:

5 1 3
..##.

Ostatnie dwa rzędy tabeli to

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

Wpis w indeksie 2 drugiego ostatniego rzędu to 2, ponieważ aby osiągnąć stan 2//3 = 0pełnych ciężarówek ustawionych i stanowiących miejsce 2%3 = 2dla nowej ciężarówki, jest to jedyna opcja:

  TT
..XX

Ale pozycja pod indeksem 3 drugiego ostatniego rzędu to 1, ponieważ aby osiągnąć stan 3//3 = 1pełnych ciężarówek ustawionych i stanowiących miejsce 3%3 = 0dla nowej ciężarówki, optymalne jest

TTT
..X#

Wpis pod indeksem 3 ostatniego rzędu patrzy na powyższe dwie komórki jako opcje - czy bierzemy przypadek, w którym mamy 2 miejsca na nową ciężarówkę i kończymy, czy też przyjmujemy przypadek, w którym mamy pełną ciężarówkę już skończone?

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

Oczywiście to drugie jest lepsze, więc odłożyliśmy 1.

Pyth, 70 bajtów

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

Zasadniczo port powyższego kodu. Jeszcze nie bardzo dobrze gra w golfa. Wypróbuj online

Rozszerzony

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

Teraz, jeśli tylko Pyth miał wiele przypisań do> 2 zmiennych ...

Haskell, 196 znaków

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

Uruchamia wszystkie przykłady

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

Nieco wolno: O (2 ^ P) , gdy P jest wielkością partii.

Prawdopodobnie zostało tu wiele do gry w golfa.