a227. 翻煎餅 (pancake) - 彰化精誠中學

內容

你即將舉辦一場派對，為了迎接客人，你決定拿出你的拿手好戲 --- 煎餅！

為了準備，你拿出一個很特殊的鐵盤，在這個鐵盤上做的所有煎餅都會是排成一直線的。

就在你煎得很快樂的時候，你的常用鍋鏟不見了，眼見還有許多煎餅需要翻面(不然會焦掉)，你迅速找到一把造型奇特的鍋鏟，它的長度是 k ，代表它只能一次為 k 個連續煎餅翻面。請注意，已經被翻面的煎餅若是再被翻面一次，視為未被翻面的狀態。

焦急地你面臨這樣的問題，假設我們把簡化煎餅的配置成一個字串 s ，代表哪些煎餅需要翻面，哪些是需要翻面的，請你找出能使得所有煎餅都翻面的最小次數。

輸入說明

輸入第一行為兩個整數 n, k，分別代表字串 s 的長度和鍋鏟的長度。( 1 ≤ k ≤ n )

第二行有一長度為 n 的字串 s ，代表煎餅配置，o 代表已翻面的煎餅，x 代表未被翻面的。

輸出說明

輸出一整數，代表使得所有煎餅都翻面的最小次數，如果無法在有限次內達成，輸出 -1。

範例輸入 #1

#test input 1:
5 3
oxoox

#test input 2:
6 1
oooooo

#test input 3:
7 3
oxooxxo

範例輸出 #1

#test output 1:
2

#test output 2:
0

#test output 3:
-1

測資資訊：

記憶體限制： 512 MB
公開測資點#0 (3%): 1.0s , <1K
公開測資點#1 (3%): 1.0s , <1K
公開測資點#2 (3%): 1.0s , <1M
公開測資點#3 (3%): 1.0s , <1M
公開測資點#4 (3%): 1.0s , <1M
公開測資點#5 (3%): 1.0s , <1M
公開測資點#6 (3%): 1.0s , <1M
公開測資點#7 (3%): 1.0s , <1M
公開測資點#8 (3%): 1.0s , <1M
公開測資點#9 (3%): 1.0s , <1M
公開測資點#10 (5%): 1.0s , <1M
公開測資點#11 (5%): 1.0s , <1M
公開測資點#12 (5%): 1.0s , <1M
公開測資點#13 (5%): 1.0s , <1M
公開測資點#14 (5%): 1.0s , <1M
公開測資點#15 (5%): 1.0s , <1M
公開測資點#16 (5%): 1.0s , <1M
公開測資點#17 (5%): 1.0s , <1M
公開測資點#18 (5%): 1.0s , <1M
公開測資點#19 (5%): 1.0s , <1M
公開測資點#20 (5%): 1.0s , <1M
公開測資點#21 (5%): 1.0s , <1M
公開測資點#22 (5%): 1.0s , <1M
公開測資點#23 (5%): 1.0s , <1M

提示：

implementation, greedy (CF 1600)

30% 的測資滿足 1 ≤ n ≤ 5000

70% 的測資滿足 1 ≤ n ≤ 1000000

標籤:

2020 Q6 少年圖靈計畫

出處:

Ypt [管理者：

iris@stu.cch... (iris)

]

編號	身分	題目	主題	人氣	發表日期
80	211096@stu.c... (唐狗針)	a227	不能做I/O優化	82	2024-04-07 16:58