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.|

ZOOTOUR - Tham quan vườn bách thú

Đọc đề đẹp hơn ở:
https://codeforces.com/group/FLVn1Sc504/contest/274863/problem/M
https://codeforces.com/group/FLVn1Sc504/contest/272622/problem/C

Hè đã về! Nhân dịp tết thiếu nhi, trường mầm non Sao Mai tổ chức cho N bé thiếu nhi đi thăm quan vườn bách thú. Trong vườn thú có M chuồng liên tiếp nhau, được đánh số liên tiếp từ 1 tới M. Ở mỗi chuồng có đúng một con thú được biểu diễn bởi một số tự nhiên trong khoảng từ 1 tới K. Sau khi đi thăm vườn thú về, N bé lần lượt kể cho cô giáo nghe về quan sát của mình. Mỗi bé kể lại: “Ở chuồng thứ i có con vật v1 và ở chuồng thứ i+1 có con vật v2”. Tuy nhiên, cô giáo biết chắc chắn có chính xác L bé nói dối trong N bé. Một bé nói thật sẽ nói đúng tên con vật ở cả 2 chuồng trong khi một bé nói dối sẽ nói sai tên con vật ở ít nhất một chuồng.

Cô giáo đưa ra Q phán đoán, mỗi phán đoán có dạng: “Ở chuồng thứ i là con vật v”. Hỏi trong trường hợp tốt nhất và xấu nhất, cô giáo có bao nhiêu câu đoán đúng?

Dữ liệu

  • Dòng đầu ghi các số N, M, K, L, Q. ( L <= N <= 200, M, K, Q <= 10000 )
  • N dòng sau, mỗi dòng ghi 3 số i, v1, v2.
  • Q dòng cuối, mỗi dòng ghi 2 số i, v.

Kết quả

  • Số câu đoán đúng tối thiểu và tối đa của cô giáo.

Ví dụ

Dữ liệu Kết quả
3 4 5 1 4

1 1 1

2 2 1

3 2 2

1 1

2 1

3 1

4 2

3 3
1 2 2 1 2

1 1 1

1 2

2 2

1 2
 

Giới hạn

  • 30% số test có N, M, K <= 10.
  • 70% số test có N, M, K <= 100.
  • Thời gian cho mỗi test là 2s.

Giải thích

Ở ví dụ 1, bé 1 và bé 2 không thể cùng nói thật (do nói khác nhau về chuồng 2). Tương tự bé 2 và bé 3 không thể cùng nói thật. Do có đúng 1 bé nói dối nên bé 2 là bé nói dối, bé 1 và bé 3 là 2 bé nói thật, con vật trong 4 chuồng lần lượt là: 1, 1, 2, 2. Vì thế, cô giáo luôn đoán đúng 3 câu.

Ở ví dụ 2, em bé duy nhất đã nói dối. Vì vậy ít nhất 1 trong 2 chuồng không có con vật 1. Vì chỉ có 2 loại con vật nên ít nhất 1 trong 2 chuồng có con vật 2. Cô giáo đoán đúng 1 câu trong trường hợp tệ nhất và 2 câu trong trường hợp tốt nhất.


Được gửi lên bởi:VOJ Team
Ngày:2010-06-19
Thời gian chạy:0.400s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: GOSU NODEJS OBJC PERL6 PYPY RUST SED SQLITE VB.NET
Nguồn bài:VM10 - Tác giả: Khúc Anh Tuấn

hide comments
2017-12-26 17:13:50
ai đc AC chưa
2011-10-09 14:37:17 hoc, hoc nua...hoc mai
đề gì mà kinh thế :-ss
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.