JOI 2021 - Vòng loại 2

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 JOI 2021 - Round Sugoroku 100 (p) 2.0s 1G
2 JOI 2021 - Pancake 100 (p) 2.5s 1G
3 JOI 2021 - Event Hopping 100 (p) 1.5s 1G
4 JOI 2021 - Safety Inspection 100 (p) 2.0s 1G
5 JOI 2021 - Spy 2 100 (p) 2.0s 1G

1. JOI 2021 - Round Sugoroku

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Aoi, học sinh trường trung học JOI, vừa mua một bộ trò chơi sugoroku mới. Bàn chơi gồm \(N+2\) ô xếp thành một hàng ngang, được đánh số từ \(0\) đến \(N+1\) từ trái sang phải. Ban đầu, hai ô \(0\) và \(N+1\) ghi ký tự X; ô \(i\) (\(1 \le i \le N\)) ghi ký tự \(S_i\), là . hoặc #.

Aoi chơi bằng một quân cờ. Ban đầu, quân cờ được đặt ở ô \(A\) (\(1 \le A \le N\)), quay sang phải. Ký tự \(S_A\) là .. Cứ sau mỗi giây, Aoi di chuyển quân cờ một ô theo hướng quân cờ đang quay.

Trò chơi có các quy tắc sau:

  • Khi quân cờ đến ô ghi X, nó đổi sang hướng ngược lại.
  • Khi quân cờ đến ô ghi ., không có gì xảy ra.
  • Khi quân cờ đến ô ghi #, nó đổi sang hướng ngược lại, đồng thời ký tự trên ô đó được đổi thành .. Vì vậy, những lần sau khi quân cờ đến ô này, nó không đổi hướng nữa.

Thời gian đổi hướng và thay đổi ký tự được xem là không đáng kể.

Cho trạng thái ban đầu của bàn chơi và quân cờ, hãy viết chương trình tính thời gian cần thiết để không còn ô nào ghi #.

Dữ liệu vào

Dòng thứ nhất chứa hai số nguyên \(N, A\).

Dòng thứ hai chứa xâu \(S\) có độ dài \(N\), trong đó ký tự thứ \(i\) (\(1 \le i \le N\)) là \(S_i\).

Dữ liệu ra

In ra trên một dòng số giây cần thiết để không còn ô nào ghi #.

Ràng buộc

  • \(2 \le N \le 200\,000\).
  • \(1 \le A \le N\).
  • \(S_i\) là . hoặc # với mọi \(1 \le i \le N\).
  • \(S_A\) là ..
  • Có ít nhất một chỉ số \(i\) (\(1 \le i \le N\)) mà \(S_i\) là #.

Phân nhóm

Mọi phân nhóm đều thỏa mãn các ràng buộc chung ở trên.

  1. (40 điểm) \(N \le 3000\).
  2. (60 điểm) Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
7 3
.#.#..#
Output 
8
Giải thích

Trạng thái bàn chơi thay đổi theo thời gian như dưới đây. Ký hiệu > biểu diễn ô đang có quân cờ quay sang phải, còn < biểu diễn ô đang có quân cờ quay sang trái. Số đứng trước mỗi trạng thái là thời gian đã trôi qua, tính bằng giây.

0: X.#>#..#X
1: X.#.<..#X
2: X.#<...#X
3: X.>....#X
4: X..>...#X
5: X...>..#X
6: X....>.#X
7: X.....>#X
8: X......<X

Sau \(8\) giây, không còn ô nào ghi #, nên in ra \(8\).

Ví dụ 2

Input 
4 1
.#.#
Output 
7
Giải thích

Trạng thái bàn chơi thay đổi theo thời gian như dưới đây. Ký hiệu > và < lần lượt biểu diễn quân cờ quay sang phải và sang trái; số đứng trước mỗi trạng thái là thời gian đã trôi qua, tính bằng giây.

0: X>#.#X
1: X.<.#X
2: X<..#X
3: >...#X
4: X>..#X
5: X.>.#X
6: X..>#X
7: X...<X

Sau \(7\) giây, không còn ô nào ghi #, nên in ra \(7\).

Ví dụ 3

Input 
6 6
#####.
Output 
35

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

2. JOI 2021 - Pancake

Điểm: 100 (p) Thời gian: 2.5s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Bitaro làm việc tại một cửa hàng bánh pancake. Món được yêu thích nhất là tháp gồm \(N\) chiếc bánh pancake xếp chồng lên nhau. Cửa hàng có ba hương vị bánh, được ký hiệu là A, B, C.

Một tháp bánh được gọi là tháp bánh tốt nếu cách xếp bánh thỏa mãn tất cả các điều kiện sau:

  • Với mọi cặp bánh vị A và bánh vị B, bánh vị A nằm phía trên bánh vị B.
  • Với mọi cặp bánh vị A và bánh vị C, bánh vị A nằm phía trên bánh vị C.
  • Với mọi cặp bánh vị B và bánh vị C, bánh vị B nằm phía trên bánh vị C.

Ví dụ, các tháp có hương vị từ trên xuống lần lượt là AABBBC, ACC, BBBB đều là tháp bánh tốt; các tháp AABABCC, CA thì không.

Bitaro phụ trách bày bánh và có thể thực hiện thao tác sau:

Thao tác \(k\) (\(2 \le k \le N\)): luồn xẻng lật bánh xuống dưới chiếc bánh thứ \(k\) tính từ trên xuống rồi lật ngược phần bánh phía trên xẻng. Nói cách khác, đảo ngược thứ tự của \(k\) chiếc bánh trên cùng.

Chẳng hạn, với tháp có hương vị từ trên xuống là ABCB, nếu thực hiện riêng từng thao tác \(2\), \(3\), \(4\) trên tháp ban đầu thì lần lượt thu được BACB, CBAB, BCBA.

Hiện có \(Q\) đĩa tháp bánh. Đĩa thứ \(i\) (\(1 \le i \le Q\)) có các hương vị từ trên xuống là \(S_{i,1}S_{i,2}\ldots S_{i,N}\). Bitaro muốn biến từng tháp thành tháp bánh tốt với số thao tác ít nhất có thể.

Cho thông tin về \(Q\) tháp bánh, hãy viết chương trình tìm số thao tác ít nhất cần thực hiện cho mỗi tháp.

Dữ liệu vào

Dòng thứ nhất chứa hai số nguyên \(N, Q\).

Trong \(Q\) dòng tiếp theo, dòng thứ \(i\) chứa xâu \(S_i\) có độ dài \(N\), trong đó ký tự thứ \(j\) là \(S_{i,j}\), mô tả hương vị từ trên xuống của tháp bánh thứ \(i\).

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(i\) (\(1 \le i \le Q\)) chứa số thao tác ít nhất cần thực hiện để biến tháp bánh thứ \(i\) thành tháp bánh tốt.

Ràng buộc

  • \(2 \le N \le 13\).
  • \(1 \le Q \le 100\,000\).
  • \(S_{i,j}\) là A, B hoặc C với mọi \(1 \le i \le Q\), \(1 \le j \le N\).

Phân nhóm

Mọi phân nhóm đều thỏa mãn các ràng buộc chung ở trên.

  1. (4 điểm) \(N \le 5\), \(Q=1\).
  2. (10 điểm) \(N \le 5\).
  3. (60 điểm) \(Q=1\).
  4. (26 điểm) Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
5 3
ABCBA
CCBAB
AAAAA
Output 
3
2
0
Giải thích

Với tháp bánh thứ nhất, có thể tạo thành tháp bánh tốt bằng ba thao tác sau:

  1. Thực hiện thao tác \(4\), thu được BCBAA.
  2. Thực hiện thao tác \(2\), thu được CBBAA.
  3. Thực hiện thao tác \(5\), thu được AABBC.

Không thể tạo thành tháp bánh tốt bằng từ \(2\) thao tác trở xuống, nên dòng thứ nhất in ra \(3\).

Với tháp bánh thứ hai, có thể tạo thành tháp bánh tốt bằng hai thao tác sau:

  1. Thực hiện thao tác \(5\), thu được BABCC.
  2. Thực hiện thao tác \(2\), thu được ABBCC.

Không thể tạo thành tháp bánh tốt bằng từ \(1\) thao tác trở xuống, nên dòng thứ hai in ra \(2\).

Tháp bánh thứ ba đã là tháp bánh tốt, không cần thực hiện thao tác nào, nên dòng thứ ba in ra \(0\).

Ví dụ 2

Input 
2 5
AC
AC
AC
AC
AC
Output 
0
0
0
0
0
Giải thích

Có thể có nhiều tháp bánh được xếp giống hệt nhau.

Ví dụ 3

Input 
13 1
ABCCABCBACBAA
Output 
9

Ví dụ 4

Input 
13 4
CCAAACBAAAABB
BBBCCBCCCBCBC
CCCAAAABBBBBB
AABCBCACBACBA
Output 
4
6
2
10

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

3. JOI 2021 - Event Hopping

Điểm: 100 (p) Thời gian: 1.5s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Nước IOI có hai thị trấn, được đánh số \(1\) và \(2\). Tổng cộng có \(N\) sự kiện được tổ chức tại hai thị trấn, đánh số từ \(1\) đến \(N\). Sự kiện \(i\) (\(1 \le i \le N\)) diễn ra tại thị trấn \(P_i\), từ thời điểm \(S_i+0.1\) đến thời điểm \(S_i+0.9\), trong đó \(S_i\) là số nguyên. Để tham gia sự kiện \(i\), JOI phải ở thị trấn \(P_i\) trong toàn bộ khoảng thời gian từ \(S_i+0.1\) đến \(S_i+0.9\).

JOI quyết định đi tham gia các sự kiện. JOI có thể tham gia một số sự kiện và di chuyển giữa hai thị trấn khi cần. Hành trình bắt đầu tại thời điểm \(0\), ở một trong hai thị trấn do JOI tùy ý chọn.

JOI có thể di chuyển giữa hai thị trấn theo cả hai chiều. Gọi \(j\) là số sự kiện JOI đã tham gia trước thời điểm bắt đầu một lần di chuyển. Thời gian cần cho lần di chuyển đó là \(D+K \times j\).

Cho thông tin về các sự kiện và việc di chuyển, hãy viết chương trình tìm số sự kiện nhiều nhất mà JOI có thể tham gia.

Dữ liệu vào

Dòng thứ nhất chứa ba số nguyên \(N, D, K\).

Trong \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(P_i, S_i\), cách nhau bởi dấu cách.

Dữ liệu ra

In ra trên một dòng số sự kiện nhiều nhất mà JOI có thể tham gia.

Ràng buộc

  • \(1 \le N \le 200\,000\).
  • \(1 \le D \le 10^{12}\).
  • \(0 \le K \le 10^{12}\).
  • \(1 \le P_i \le 2\) với mọi \(1 \le i \le N\).
  • \(1 \le S_i \le 10^{12}\) với mọi \(1 \le i \le N\).
  • \(S_i \ne S_j\) với mọi \(1 \le i < j \le N\).
  • Tất cả các giá trị đầu vào đều là số nguyên.

Phân nhóm

Mọi phân nhóm đều thỏa mãn các ràng buộc chung ở trên.

  1. (8 điểm) \(K=0\), \(N \le 20\).
  2. (11 điểm) \(K=0\), \(N \le 4000\).
  3. (24 điểm) \(K=0\).
  4. (12 điểm) \(N \le 160\).
  5. (23 điểm) \(N \le 4000\).
  6. (22 điểm) Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
5 3 0
1 1
1 2
1 10
2 5
2 6
Output 
4
Giải thích

Chẳng hạn, JOI có thể tham gia \(4\) sự kiện theo hành trình sau:

  • Tại thời điểm \(0\), JOI ở thị trấn \(1\).
  • Từ thời điểm \(1.1\) đến \(1.9\), tham gia sự kiện \(1\) ở thị trấn \(1\).
  • Từ thời điểm \(2.1\) đến \(2.9\), tham gia sự kiện \(2\) ở thị trấn \(1\).
  • Từ thời điểm \(3\) đến \(6\), di chuyển từ thị trấn \(1\) đến thị trấn \(2\), mất \(3 = D+K \times 2\) đơn vị thời gian.
  • Từ thời điểm \(6.1\) đến \(6.9\), tham gia sự kiện \(5\) ở thị trấn \(2\).
  • Từ thời điểm \(7\) đến \(10\), di chuyển từ thị trấn \(2\) đến thị trấn \(1\), mất \(3 = D+K \times 3\) đơn vị thời gian.
  • Từ thời điểm \(10.1\) đến \(10.9\), tham gia sự kiện \(3\) ở thị trấn \(1\).

Không có cách nào tham gia từ \(5\) sự kiện trở lên, nên in ra \(4\).

Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(1, 2, 3, 4, 5, 6\).

Ví dụ 2

Input 
7 2 3
2 2
1 8
1 10
1 11
2 23
2 24
2 25
Output 
6
Giải thích

Chẳng hạn, JOI có thể tham gia \(6\) sự kiện theo hành trình sau:

  • Tại thời điểm \(0\), JOI ở thị trấn \(2\).
  • Từ thời điểm \(2.1\) đến \(2.9\), tham gia sự kiện \(1\) ở thị trấn \(2\).
  • Từ thời điểm \(3\) đến \(8\), di chuyển từ thị trấn \(2\) đến thị trấn \(1\), mất \(5 = D+K \times 1\) đơn vị thời gian.
  • Từ thời điểm \(8.1\) đến \(8.9\), tham gia sự kiện \(2\) ở thị trấn \(1\).
  • Từ thời điểm \(11.1\) đến \(11.9\), tham gia sự kiện \(4\) ở thị trấn \(1\).
  • Từ thời điểm \(12\) đến \(23\), di chuyển từ thị trấn \(1\) đến thị trấn \(2\), mất \(11 = D+K \times 3\) đơn vị thời gian.
  • Từ thời điểm \(23.1\) đến \(23.9\), tham gia sự kiện \(5\) ở thị trấn \(2\).
  • Từ thời điểm \(24.1\) đến \(24.9\), tham gia sự kiện \(6\) ở thị trấn \(2\).
  • Từ thời điểm \(25.1\) đến \(25.9\), tham gia sự kiện \(7\) ở thị trấn \(2\).

Không có cách nào tham gia từ \(7\) sự kiện trở lên, nên in ra \(6\).

Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(4, 5, 6\).

Ví dụ 3

Input 
12 153 0
1 155
2 861
1 646
1 218
2 450
2 56
1 932
2 295
2 863
1 612
2 38
2 768
Output 
8
Giải thích

Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(1, 2, 3, 4, 5, 6\).

Ví dụ 4

Input 
15 89 104
1 4379
1 738
1 4862
1 4236
2 1416
1 9905
1 4775
2 4574
2 439
1 3956
1 955
2 8862
2 801
2 2299
2 575
Output 
11
Giải thích

Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(4, 5, 6\).

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

4. JOI 2021 - Safety Inspection

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Thành phố JOI có một con đường đủ dài, có thể xem như một trục số; mỗi vị trí trên đường được biểu diễn bằng một tọa độ thực. Có \(N\) cơ sở nằm dọc theo con đường, được đánh số từ \(1\) đến \(N\) theo thứ tự tọa độ tăng dần. Cơ sở \(i\) (\(1 \le i \le N\)) nằm tại tọa độ \(A_i\).

Thành phố sắp tiến hành kiểm tra an toàn các cơ sở. Cơ sở \(i\) có \(B_i\) hạng mục cần kiểm tra. Có \(K\) người thợ mộc được tập hợp để thực hiện việc kiểm tra. Khi bắt đầu, tất cả họ đều ở tọa độ \(0\). Trong mỗi phút, mỗi người thợ có thể thực hiện một trong hai hành động sau:

  • Di chuyển một khoảng cách bằng \(1\) dọc theo trục số.
  • Chọn một hạng mục của cơ sở tại tọa độ hiện tại và kiểm tra hạng mục đó.

Khi kết thúc, mọi hạng mục của mọi cơ sở phải được ít nhất một người thợ kiểm tra.

Cho số người thợ và thông tin về các cơ sở, hãy viết chương trình tìm số phút ít nhất cần thiết để hoàn tất việc kiểm tra an toàn.

Dữ liệu vào

Dòng thứ nhất chứa hai số nguyên \(N, K\).

Dòng thứ hai chứa \(N\) số nguyên \(A_1, A_2, \ldots, A_N\).

Dòng thứ ba chứa \(N\) số nguyên \(B_1, B_2, \ldots, B_N\). Các số trên cùng một dòng được cách nhau bởi dấu cách.

Dữ liệu ra

In ra trên một dòng số phút ít nhất cần thiết để hoàn tất việc kiểm tra an toàn.

Ràng buộc

  • \(1 \le N \le 100\,000\).
  • \(1 \le K \le 10^9\).
  • \(1 \le A_i \le 10^9\) với mọi \(1 \le i \le N\).
  • \(A_i < A_{i+1}\) với mọi \(1 \le i \le N-1\).
  • \(1 \le B_i \le 10^9\) với mọi \(1 \le i \le N\).
  • Tất cả các giá trị đầu vào đều là số nguyên.

Phân nhóm

Mọi phân nhóm đều thỏa mãn các ràng buộc chung ở trên.

  1. (3 điểm) \(K=1\).
  2. (15 điểm) \(K=2\).
  3. (82 điểm) Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
3 3
1 3 4
4 2 4
Output 
7
Giải thích

Chẳng hạn, có thể hoàn tất việc kiểm tra trong \(7\) phút theo cách sau. Đánh số ba người thợ là \(1,2,3\); mỗi bước dưới đây tương ứng với một phút.

  1. Cả ba người thợ di chuyển đến tọa độ \(1\).
  2. Mỗi người thợ kiểm tra một hạng mục khác nhau của cơ sở \(1\).
  3. Thợ \(1,2\) di chuyển đến tọa độ \(2\); thợ \(3\) kiểm tra một hạng mục của cơ sở \(1\).
  4. Thợ \(1,2\) di chuyển đến tọa độ \(3\); thợ \(3\) di chuyển đến tọa độ \(2\).
  5. Thợ \(1,2\) di chuyển đến tọa độ \(4\); thợ \(3\) di chuyển đến tọa độ \(3\).
  6. Thợ \(1,2\) mỗi người kiểm tra một hạng mục của cơ sở \(3\); thợ \(3\) kiểm tra một hạng mục của cơ sở \(2\).
  7. Thợ \(1,2\) mỗi người kiểm tra thêm một hạng mục của cơ sở \(3\); thợ \(3\) kiểm tra thêm một hạng mục của cơ sở \(2\).

Không thể hoàn tất việc kiểm tra trong ít hơn \(7\) phút, nên in ra \(7\).

Ví dụ 2

Input 
6 1
1 4 5 6 11 15
12 5 9 8 10 4
Output 
63
Giải thích

Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(1, 3\).

Ví dụ 3

Input 
6 2
1 4 5 6 11 15
12 5 9 8 10 4
Output 
35
Giải thích

Ví dụ này thỏa mãn các ràng buộc của các phân nhóm \(2, 3\).

Ví dụ 4

Input 
6 5
1 4 5 6 11 15
12 5 9 8 10 4
Output 
19

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.

5. JOI 2021 - Spy 2

Điểm: 100 (p) Thời gian: 2.0s Bộ nhớ: 1G Input: bàn phím Output: màn hình

Nước JOI có \(N\) nghị sĩ, được đánh số từ \(1\) đến \(N\). Là một bộ trưởng, bạn đang cố tìm ra những gián điệp trong số các nghị sĩ. Với mỗi nghị sĩ \(i\) (\(1 \le i \le N\)), bạn có thông tin sau:

  • Nếu \(T_i=1\), nghị sĩ \(i\) là gián điệp.
  • Nếu \(T_i=2\), nghị sĩ \(i\) không phải gián điệp.
  • Nếu \(T_i=3\), chưa biết nghị sĩ \(i\) có phải gián điệp hay không.

Qua phỏng vấn, bạn thu được thêm \(M\) thông tin. Thông tin thứ \(j\) (\(1 \le j \le M\)) cho biết nghị sĩ \(A_j\) đã phát biểu: “Nghị sĩ \(B_j\) là gián điệp, đồng thời nghị sĩ \(C_j\) không phải gián điệp.”

Nếu nghị sĩ \(A_j\) là gián điệp thì phát biểu này không đúng sự thật. Cụ thể, ít nhất một trong hai mệnh đề “nghị sĩ \(B_j\) là gián điệp” và “nghị sĩ \(C_j\) không phải gián điệp” phải sai. Ngược lại, nếu nghị sĩ \(A_j\) không phải gián điệp thì phát biểu của người đó có thể đúng hoặc sai.

Cho thông tin về từng nghị sĩ và kết quả phỏng vấn, hãy viết chương trình xác định \(N+M\) thông tin có mâu thuẫn với nhau hay không. Nếu không mâu thuẫn, hãy xác định một cách gán trạng thái gián điệp hoặc không phải gián điệp cho từng nghị sĩ sao cho phù hợp với tất cả thông tin. Nếu có nhiều đáp án phù hợp, có thể in ra bất kỳ đáp án nào.

Dữ liệu vào

Dòng thứ nhất chứa hai số nguyên \(N, M\).

Dòng thứ hai chứa \(N\) số nguyên \(T_1, T_2, \ldots, T_N\).

Trong \(M\) dòng tiếp theo, dòng thứ \(j\) chứa ba số nguyên \(A_j, B_j, C_j\). Các số trên cùng một dòng được cách nhau bởi dấu cách.

Dữ liệu ra

Nếu các thông tin đã cho mâu thuẫn với nhau, in ra -1 trên một dòng.

Ngược lại, in ra \(N\) dòng. Dòng thứ \(i\) (\(1 \le i \le N\)) chứa \(1\) nếu nghị sĩ \(i\) là gián điệp, hoặc \(2\) nếu nghị sĩ \(i\) không phải gián điệp. Nếu có nhiều đáp án phù hợp với toàn bộ \(N+M\) thông tin, có thể in ra bất kỳ đáp án nào.

Ràng buộc

  • \(1 \le N \le 300\,000\).
  • \(1 \le M \le 300\,000\).
  • \(1 \le T_i \le 3\) với mọi \(1 \le i \le N\).
  • \(1 \le A_j \le N\) với mọi \(1 \le j \le M\).
  • \(1 \le B_j \le N\) với mọi \(1 \le j \le M\).
  • \(1 \le C_j \le N\) với mọi \(1 \le j \le M\).
  • \(A_j \ne B_j\) với mọi \(1 \le j \le M\).
  • \(A_j \ne C_j\) với mọi \(1 \le j \le M\).
  • \(B_j \ne C_j\) với mọi \(1 \le j \le M\).

Phân nhóm

Mọi phân nhóm đều thỏa mãn các ràng buộc chung ở trên.

  1. (7 điểm) \(N \le 16\), \(M \le 100\).
  2. (38 điểm) \(N \le 3000\), \(M \le 3000\).
  3. (55 điểm) Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
4 1
1 3 2 3
1 2 3
Output 
1
2
2
1
Giải thích

Trong đầu ra mẫu, nghị sĩ \(1\) là gián điệp. Phát biểu “nghị sĩ \(2\) là gián điệp, đồng thời nghị sĩ \(3\) không phải gián điệp” là sai vì nghị sĩ \(2\) không phải gián điệp. Do đó, đầu ra mẫu phù hợp với các thông tin và là một đáp án đúng.

Một đáp án đúng khác là chỉ nghị sĩ \(1\) là gián điệp, còn tất cả những người khác đều không phải gián điệp.

Ví dụ 2

Input 
4 2
2 1 3 1
4 3 1
2 4 3
Output 
-1
Giải thích

Nếu nghị sĩ \(3\) là gián điệp thì không phù hợp với thông tin phỏng vấn thứ nhất. Nếu nghị sĩ \(3\) không phải gián điệp thì không phù hợp với thông tin phỏng vấn thứ hai. Các thông tin mâu thuẫn với nhau, nên in ra -1.

Ví dụ 3

Input 
3 2
1 2 2
2 1 3
2 3 1
Output 
1
2
2
Giải thích

Trong ví dụ này, trạng thái của tất cả nghị sĩ đều đã được cho biết. Các trạng thái đó cũng phù hợp với thông tin phỏng vấn, nên đầu ra mẫu là đáp án đúng duy nhất. Lưu ý rằng phát biểu của một nghị sĩ không phải gián điệp có thể đúng hoặc sai.

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.