На стоянке есть P парковочных мест, хотя некоторые места заняты автомобилями, представленными восьмиугольниками, #а свободные места - точечными .. Вскоре прибывают Т грузовики, каждый из которых займет ровно L мест подряд. Грузовики не должны быть припаркованы рядом друг с другом.

Ваша задача - создать программу, которая найдет наименьшее количество автомобилей, которые необходимо удалить, чтобы оставить все грузовики. Там всегда будет достаточно места для всех грузовиков, то естьT*L<P

вход

В первом ряду будут три целых числа, P, T и L, разделенные пробелами. Во втором ряду будет строка из P символов, представляющих парковку в исходном состоянии.

Вывод

В первой и единственной строке ваша программа должна распечатать наименьшее количество автомобилей, которые необходимо удалить, чтобы оставить все грузовики.

Контрольные примеры

Входные данные:
6 1 3
#.#.##

Вывод: 1

Входные данные:
9 2 3
.##..#..#

Вывод: 2

Входные данные:
15 2 5
.#.....#.#####.

Вывод: 3

Самый короткий код выигрывает. (Примечание: я особенно заинтересован в реализации Pyth, если это возможно)

Python 2, 154 байта

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]

Простой подход DP. Большая часть программы просто читает входные данные.

объяснение

Мы рассчитываем таблицу динамического двухмерного программирования, где каждая строка соответствует первому месту nпарковки, а каждый столбец соответствует количеству грузовиков (или частей грузовика), размещенных до настоящего времени. В частности, столбец kозначает, что мы уже установили k//Lполные грузовики и готовимся k%Lк новому грузовику. Тогда каждая ячейка - это минимальное количество машин, которое нужно очистить, чтобы достичь штата (n,k), и наша целевая задача - (P, L*T).

Идея повторения DP заключается в следующем:

• Если у нас есть k%L > 0места для нового грузовика, то наш единственный вариант - это быть k%L-1рядом с новым грузовиком
• В противном случае, если k%L == 0мы только что закончили новый грузовик или уже закончили последний грузовик и с тех пор пропустили несколько парковочных мест. Мы берем минимум из двух вариантов.

Если k > n, т. Е. Мы разместили больше площадей для грузовиков, чем парковочных мест, то мы ставим ∞для штата (n,k). Но для целей игры в гольф мы ставим, kтак как это наихудший случай удаления каждой машины, а также служит верхней границей.

Это было довольно много, так что давайте рассмотрим пример:

5 1 3
..##.

Последние две строки таблицы

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

Запись по индексу 2 во втором последнем ряду - 2, потому что для достижения состояния 2//3 = 0полностью заполненных грузовиков и 2%3 = 2мест для нового грузовика это единственный вариант:

  TT
..XX

Но запись по индексу 3 второго последнего ряда равна 1, потому что для достижения состояния 3//3 = 1заполненных грузовиков и свободного 3%3 = 0пространства для нового грузовика оптимальным является

TTT
..X#

Запись в индексе 3 последнего ряда рассматривает две вышеупомянутые ячейки как варианты - возьмем ли мы случай, когда мы находимся на 2 пробела для нового грузовика, и закончим его, или мы возьмем случай, когда у нас есть полный грузовик уже закончен?

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

Очевидно, что последний лучше, поэтому мы ставим 1.

Pyth, 70 байт

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

В основном порт вышеуказанного кода. Пока не очень хорошо играли в гольф. Попробуйте онлайн

расширенный

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

Теперь, если бы только Pyth имел множественное назначение> 2 переменным ...

Haskell, 196 символов

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

Запускает все примеры

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

Несколько медленно: O (2 ^ P), где P - размер лота.

Вероятно, много осталось до гольфа здесь.