trang chủ / đề bài / icpcwf09_h

Mớ hỗn độn lớn của các bộ trưởng

Đề bài

Mô tả

Các bộ trưởng của đất nước xa xôi Stanistan đang gặp rắc rối nghiêm trọng trong việc ra quyết định. Mọi chuyện bắt đầu từ vài tuần trước, khi một quy trình mới để quyết định thông qua những dự luật nào được đưa vào sử dụng. Quy trình hoạt động như sau. Trong mỗi phiên biểu quyết có một số dự luật cần được biểu quyết. Mỗi bộ trưởng bày tỏ ý kiến bằng cách bỏ phiếu "đồng ý" (yes) hoặc "không đồng ý" (no) cho một số dự luật trong đó. Do hạn chế trong thiết kế của giải pháp kỹ thuật dùng để xử lý việc biểu quyết, mỗi bộ trưởng chỉ được bỏ phiếu cho nhiều nhất bốn dự luật khác nhau (điều này thường không thành vấn đề, vì đa số bộ trưởng chỉ quan tâm tới một vài vấn đề). Sau đó, dựa trên các lá phiếu, tập các dự luật được thông qua được chọn sao cho mỗi bộ trưởng có hơn một nửa số ý kiến của mình được thỏa mãn.

Như độc giả tinh ý hẳn đã nhận ra, quy trình này có thể dẫn tới nhiều vấn đề. Chẳng hạn, nếu có nhiều cách chọn cùng làm hài lòng mọi bộ trưởng thì sao, hoặc tệ hơn, nếu không thể làm hài lòng tất cả các bộ trưởng thì sao? Và ngay cả khi ý kiến của các bộ trưởng dẫn tới một lựa chọn duy nhất, làm sao tìm ra lựa chọn đó?

Nhiệm vụ của bạn là viết chương trình giúp các bộ trưởng giải quyết một số vấn đề này. Cho các lá phiếu của các bộ trưởng, chương trình phải xác định xem có thể làm hài lòng tất cả các bộ trưởng hay không, và nếu có thì xác định quyết định đối với những dự luật mà, với các ràng buộc đã cho, chỉ có đúng một lựa chọn khả thi.

Nói cách khác: mỗi dự luật được gán "thông qua" (y) hoặc "không thông qua" (n). Ý kiến "yes" về một dự luật được thỏa mãn khi dự luật đó được thông qua, ý kiến "no" được thỏa mãn khi dự luật đó không được thông qua. Một cách gán là hợp lệ nếu với mọi bộ trưởng, số ý kiến được thỏa mãn của bộ trưởng đó lớn hơn một nửa số dự luật mà bộ trưởng đó đã bỏ phiếu.

Dữ liệu vào

Dữ liệu vào gồm nhiều bộ test. Mỗi bộ test bắt đầu bằng hai số nguyên B là số dự luật cần biểu quyết và M là số bộ trưởng. M dòng tiếp theo cho lá phiếu của các bộ trưởng. Mỗi dòng bắt đầu bằng số nguyên k là số dự luật mà bộ trưởng đó bỏ phiếu, tiếp theo là k lá phiếu. Mỗi lá phiếu có dạng <bill> <vote>, trong đó <bill> là số nguyên từ 1 tới B cho biết dự luật được bỏ phiếu, còn <vote> là y hoặc n, cho biết ý kiến của bộ trưởng là "yes" hay "no". Không bộ trưởng nào bỏ phiếu cho cùng một dự luật quá một lần.

Sau bộ test cuối cùng là một dòng chứa hai số 0.

Dữ liệu ra

Với mỗi bộ test, in số thứ tự của bộ test (bắt đầu từ 1) và kết quả của quy trình, theo đúng định dạng trong ví dụ (Case i: rồi tới kết quả). Nếu không thể làm hài lòng tất cả các bộ trưởng, kết quả là impossible. Ngược lại, kết quả là một xâu độ dài B, trong đó ký tự thứ i là y, n hoặc ?, tùy theo dự luật thứ i bắt buộc phải được thông qua (y), bắt buộc không được thông qua (n), hay các lá phiếu đã cho không quyết định được dự luật này (?, tức là tồn tại cách gán hợp lệ thông qua nó và cũng tồn tại cách gán hợp lệ không thông qua nó).

Ràng buộc

  • 1≤B≤100, 1≤M≤500.
  • 1≤k≤4, các dự luật trong một lá phiếu của một bộ trưởng đôi một khác nhau.
  • Mỗi file có không quá 1000 bộ test và tổng các giá trị M trong một file không quá 20000.

Ví dụ

Input Output Giải thích
5 2
4 2 y 5 n 3 n 4 n
4 4 y 3 y 5 n 2 y
4 2
4 1 y 2 y 3 y 4 y
3 1 n 2 n 3 n
0 0
Case 1: ?y??n
Case 2: impossible
Bộ test 1: mỗi bộ trưởng bỏ phiếu cho 4 dự luật nên cần ít nhất 3 ý kiến được thỏa mãn. Nếu dự luật 2 không được thông qua thì cả hai bộ trưởng đều đã có một ý kiến không thỏa mãn, nên các dự luật 3, 4, 5 phải thỏa mãn cả hai, mâu thuẫn ở dự luật 3. Tương tự dự luật 5 phải là n. Bộ test 2: bộ trưởng thứ hai cần ít nhất 2 trong 3 dự luật đầu bị bác, khi đó bộ trưởng thứ nhất có ít nhất 2 ý kiến không thỏa mãn trong 4.
4 3
3 1 y 2 y 3 n
3 1 y 2 n 3 y
1 4 n
3 2
2 1 y 2 n
3 1 n 2 y 3 y
4 1
4 1 y 2 y 3 n 4 n
0 0
Case 1: y??n
Case 2: impossible
Case 3: ????
Bộ test 1: hai bộ trưởng đầu mỗi người chịu nhiều nhất một ý kiến không thỏa mãn; nếu dự luật 1 bị bác thì một trong hai người có hai ý kiến không thỏa mãn, nên dự luật 1 phải là y, còn dự luật 2 và 3 chỉ cần giống nhau. Bộ test 2: bộ trưởng có 2 lá phiếu cần cả 2 được thỏa mãn (1 trên 2 không phải hơn một nửa), khi đó bộ trưởng thứ hai có 2 ý kiến không thỏa mãn. Bộ test 3: mọi dự luật đều có thể đổi giá trị.

Bình luận

Không có bình luận tại thời điểm này.

gnatmake 12.2.0 a68g 3.1.2 nasm 2.16.1 as_x64 2.47 awk 1.3.4 gcc 16.2.0 dotnet 10.0.402 g++ 16.2.0 g++-themis 16.2.0 g++17 16.2.0 g++20 16.2.0 g++23 16.2.0 clang++ 22.1.8 dmd 2.113.0 dart 3.13.6 gforth 0.7.3 gfortran 15.3.0 go 1.27.3 groovyc 5.1.3 javac 26.0.2.1 node 26.12.1 julia 1.13.2 kotlinc 2.4.21 lean 4.35.0 sbcl 2.2.9 lua 5.5.1 nim 2.2.12 fpc 3.2.2 fpc-themis 3.2.2 perl 5.42.3 php 8.5.12 pike 8.0 swipl 9.0.4 pypy3 7.3.23 python3 3.15.1 racket 8.7 ruby 4.0.8 rustc 1.99.1 csc 5.3.0 ctoj-scratch 0.0.1 sed 4.9 swiftc 6.4.1 tclsh 8.6 bun 1.4.4 deno 2.9.8 v 0.5.2 zig 0.17.0