Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VOCARD - Trò chơi chọn bài

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/vocard


RRpirate là hai cao thủ chơi bài. Bài gì họ cũng đã từng chơi qua và lần nào cũng ngang tài ngang sức với nhau. Bây giờ thì họ đã chơi tất cả các thể loại bài rồi mà vẫn chưa phân được thắng bại. Vì vậy họ tìm gặp pháp sư flashmt để nhờ anh ta sáng chế ra một kiểu chơi bài mới để họ tranh tài tranh sức với nhau.

flashmt vốn cũng thích chơi bài từ nhỏ nên anh ấy đã nhanh chóng nghĩ ra được một trò chơi như sau: Vị pháp sư lấy từ túi quần ra 1 bộ bài N lá, và đặt xuống bàn. Các lá bài được đánh số từ 1 đến N từ dưới lên. Mỗi lượt chơi, người chơi phải chọn lấy ít nhất là 1 lá bài và nhiều nhất là K lá bài từ trên xuống, tức là đầu tiên lá bài N sẽ được lấy, rồi đến N-1, N-2,..., tất nhiên số lượng bài được chọn không vượt quá số lượng lá bài còn lại. Trong các lá bài đó có một số lá bài màu đen, còn một số khác thì màu đỏ. RRpirate được biết trước vị trí của những lá bài màu đen và đỏ trên bộ bài, người nào bốc được 1 lá bài màu đen tương ứng với 1 điểm. Hai người sẽ lần lượt lấy các lá bài cho tới khi nào tất cả N lá bài đều được lấy hết. Cuối cùng ai được nhiều điểm hơn sẽ thắng.

RRpirate chơi bài rất giỏi nên cho dù với trò chơi mới này họ cũng luôn biết cách chơi tối ưu, nghĩa là họ sẽ luôn cố gắng để được nhiều điểm nhất có thể. Nhưng họ đang thắc mắc liệu trò chơi mới này có giúp họ phân thắng bại hay không? Hay kết quả lại hòa như những lần trước? Điều này thì ngay cả pháp sư flashmt cũng không biết được. Bạn là một lập trình viên giỏi, hãy giúp RR, pirateflashmt trả lời câu hỏi này nhé.

Yêu cầu

Cho số N, K, trạng thái màu của từng lá bài từ 1 đến N. Hãy trả lời xem liệu khi kết thúc trò chơi thì hai người chơi có thể phân được thắng bại hay không? Nếu câu trả lời là có thì người thua sẽ được bao nhiêu điểm? Chú ý: Chúng ta không quan tâm đến người nào đi trước người nào đi sau mà chỉ quan tâm đến điểm của người thắng và người thua sau khi trò chơi kết thúc.

Input

  • Dòng đầu tiên chứa 2 số N, K
  • Dòng thứ 2 chứa N kí tự '0' hoặc '1' (không có dấu ngoặc dơn) mô tả trạng thái màu của các lá bài từ dưới lên. Kí tự thứ i là '0' nếu lá bài được đánh số i màu đỏ. Kí tự thứ i là '1' nếu lá bài được đánh số i màu đen.

Output

  • Dòng đầu tiên là "YES" (không có dấu hoặc kép) nếu sau khi kết thúc trò chơi thì hai người chơi có thể phân biệt được thắng bại. Hoặc là "NO" nếu trò chơi kết thúc với kết quả hòa.
  • Nếu dòng đầu tiên là "YES" thì dòng này sẽ là số điểm cao nhất mà người thua đạt được.

Giới hạn:

  • 40% số test có 1 ≤ K ≤ N ≤ 5000.
  • Trong tất cả các test có 1 ≤ K ≤ N ≤ 2.106 (2 triệu)

Example

Input 1:
5 3
10110

Output 1:
YES
1


Input 2:
4 2
1111

Output 2:

NO

Giải thích:

- Ví dụ 1: Nếu người đi đầu bốc 3 lá bài trên cùng (lá 5, 4 và 3) thì sẽ được 2 điểm (ở lá 3 và lá 4), người đi sau bốc 2 lá bài còn lại (lá 2 và 1) thì được 1 điểm (ở lá 1). Như vậy người đi trước đã thắng người đi sau. Người đi sau là người thua có thể có nhiều nhất là 1 điểm.

- Ví dụ 2: Sau khi kết thúc trò chơi cả 2 người đều ghi được nhiều nhất là 2 điểm. Vì vậy hai người không phân được thắng bại.


Được gửi lên bởi:VOJ Team
Ngày:2012-12-12
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:C C++ 4.3.2 CPP JAVA PAS-GPC PAS-FPC
Nguồn bài:VNOI Online 2013 - Ngày 1 - Lê Yên Thanh

hide comments
2016-07-08 16:51:33
BFS =))
2013-07-05 16:15:02 Ho Hoang Hiep-A2k41pbc
DÙng de que ue ue :))))

posted by : hồ Hoàng Hiệp _ hú hú - A2K41 -PBC
2013-07-03 08:48:51 PasCal
ừ khó

Last edit: 2013-07-03 08:49:28
2013-06-23 17:23:46 ♫œ‰ Hùng ♫
khó thiệt
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.