BOI 2018 - Ngày 2

Fredrik đang ở nhà chơi với mô hình đường sắt tự chế mà cậu rất tự hào. Đường sắt gồm \(N\) đoạn nối thành một vòng tròn, được đánh số \(1,2,\ldots,N\) theo chiều kim đồng hồ. Tàu được cấp điện qua \(M\) dây dẫn uốn cong chạy dọc theo vòng tròn. Mỗi đoạn đường sắt đều có ít nhất một dây dẫn chạy dọc theo nó.

Tuy nhiên, Fredrik bắt đầu thấy chán khi đoàn tàu cứ chạy vòng quanh, nên cậu quyết định lắp một bộ chuyển đường ray vào mỗi đoạn. Cậu có thể dùng chúng để gây ra những vụ trật bánh và các tình huống thú vị khác. Nhưng các bộ chuyển đường ray cũng cần điện, và phải là dòng điện xoay chiều. Điều này có lý vì đây là đường sắt Thụy Điển: ở Thụy Điển, tất cả các bộ chuyển đường ray (“växlar”) đều sử dụng dòng điện xoay chiều (“växelström”).

Fredrik nghĩ rằng muốn có dòng điện xoay chiều thì chỉ cần có dòng điện chạy theo cả hai chiều. Mỗi dây dẫn chỉ cho dòng điện chạy theo một chiều, hoặc cùng chiều kim đồng hồ, hoặc ngược chiều kim đồng hồ; Fredrik được tự chọn chiều đó. Cậu muốn chọn chiều dòng điện trên từng dây sao cho mỗi đoạn đường sắt đều được phủ bởi ít nhất một dây có dòng điện cùng chiều kim đồng hồ và ít nhất một dây có dòng điện ngược chiều kim đồng hồ.

Bạn có thể giúp Fredrik thực hiện việc này không?

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), lần lượt là số đoạn đường sắt và số dây dẫn.

Mỗi dòng trong \(M\) dòng tiếp theo chứa hai số \(a\) và \(b\), cho biết một dây dẫn phủ các đoạn \(a,a+1,\ldots,b\). Nếu \(b<a\), dãy này đi qua chỗ nối của vòng tròn, tức là dây phủ các đoạn \(a,\ldots,N,1,\ldots,b\). Nếu \(a=b\), dây chỉ phủ đúng một đoạn.

Dữ liệu ra

In ra một dòng gồm \(M\) ký tự, mỗi ký tự là 0 hoặc 1. Ký tự thứ \(i\) bằng 0 nếu dòng điện trên dây thứ \(i\) trong dữ liệu vào chạy cùng chiều kim đồng hồ, hoặc bằng 1 nếu chạy ngược chiều kim đồng hồ. Nếu có nhiều phương án, bạn có thể in ra bất kỳ phương án nào.

Nếu không có phương án hợp lệ, in ra impossible.

Ràng buộc

• \(2 \le N,M \le 100\,000\).
• \(1 \le a,b \le N\) với mỗi dây dẫn.
• Mỗi đoạn đường sắt có ít nhất một dây dẫn phủ lên nó.
• Một dây với \(a=b\) chỉ phủ một đoạn; một dây với \(b<a\) phủ các đoạn \(a,\ldots,N,1,\ldots,b\).

Phân nhóm

• Mỗi nhóm kiểm thử gồm một số bộ dữ liệu. Bạn chỉ nhận được điểm của một nhóm khi giải đúng tất cả các bộ dữ liệu trong nhóm đó.

• Điểm của một lần nộp là tổng điểm các nhóm đạt được. Điểm cuối cùng là điểm cao nhất của một lần nộp.

• Nhóm 1 (13 điểm): \(2 \le N,M \le 15\).

• Nhóm 2 (20 điểm): \(2 \le N,M \le 100\).
• Nhóm 3 (22 điểm): \(2 \le N,M \le 1\,000\).
• Nhóm 4 (19 điểm): \(2 \le N,M \le 100\,000\); không có dây nào có \(b<a\).
• Nhóm 5 (26 điểm): \(2 \le N,M \le 100\,000\); không có ràng buộc bổ sung.

Ví dụ

10 5
1 5
6 7
5 1
7 2
2 4

00101

10 5
1 4
2 5
4 7
6 10
8 1

impossible

5 2
1 5
3 3

impossible

5 3
3 3
2 1
4 2

101

Nguồn

Baltic Olympiad in Informatics 2018, ngày thi thứ hai.

Những kẻ phản diện có ý định thống trị thế giới thường tạo ra các bản sao của chính mình để tránh bị bắt. Bạn đã bắt được một nữ phản diện cùng \(N-1\) bản sao của cô ta và đang cố xác định ai mới là người thật.

Bạn có xâu DNA của từng người, gồm \(M\) ký tự, mỗi ký tự là A, C, G hoặc T. Bạn cũng biết các bản sao không được tạo ra một cách hoàn hảo: xâu DNA của mỗi bản sao khác xâu DNA của người thật ở đúng \(K\) vị trí.

Bạn có thể xác định nữ phản diện thật không?

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(N\), \(M\) và \(K\). Mỗi dòng trong \(N\) dòng tiếp theo là một xâu DNA gồm \(M\) ký tự, mỗi ký tự là A, C, G hoặc T.

Dữ liệu bảo đảm có đúng một xâu khác từng xâu còn lại ở đúng \(K\) vị trí.

Lượng dữ liệu vào của bài này khá lớn; chương trình Java cần sử dụng phương thức đọc dữ liệu nhanh.

Dữ liệu ra

In ra một số nguyên là chỉ số của xâu DNA thuộc về nữ phản diện thật. Các xâu được đánh số từ \(1\) theo thứ tự trong dữ liệu vào.

Ràng buộc

• \(3 \le N,M \le 4\,100\).
• \(1 \le K \le M\).
• Mỗi xâu có đúng \(M\) ký tự thuộc tập A, C, G, T.
• Có đúng một xâu khác mỗi xâu còn lại ở đúng \(K\) vị trí.

Phân nhóm

• Mỗi nhóm kiểm thử gồm một số bộ dữ liệu. Bạn chỉ nhận được điểm của một nhóm khi giải đúng tất cả các bộ dữ liệu trong nhóm đó.

• Điểm của một lần nộp là tổng điểm các nhóm đạt được. Điểm cuối cùng là điểm cao nhất của một lần nộp.

• Nhóm 1 (27 điểm): \(3 \le N,M \le 100\).

• Nhóm 2 (19 điểm): \(3 \le N,M \le 1\,800\); mọi ký tự đều là A hoặc C.
• Nhóm 3 (28 điểm): \(3 \le N,M \le 4\,100\); mọi ký tự đều là A hoặc C.
• Nhóm 4 (26 điểm): \(3 \le N,M \le 4\,100\); không có ràng buộc bổ sung.

Ví dụ

4 3 1
ACC
CCA
ACA
AAA

3

4 4 3
CATT
CAAA
ATGA
TCTA

4

Nguồn

Baltic Olympiad in Informatics 2018, ngày thi thứ hai.

Đồ thị là một cấu trúc toán học gồm một tập các đỉnh và một tập các cạnh, mỗi cạnh nối hai đỉnh. Một đồ thị có \(4\) đỉnh và \(3\) cạnh được minh họa trong phần giải thích ví dụ bên dưới.

Một đường đi trong đồ thị là một danh sách có thứ tự gồm ít nhất hai đỉnh, sao cho giữa hai đỉnh liên tiếp trong danh sách luôn có một cạnh. Trong bài này, ta chỉ xét các đường đi đơn, nghĩa là không có đỉnh nào xuất hiện nhiều hơn một lần. Danh sách có thứ tự, nên chẳng hạn 5-6-7, 5-7-6 và 7-6-5 được coi là những đường đi khác nhau.

Mỗi đỉnh của đồ thị có một trong \(K\) màu. Hãy tìm số đường đi đơn mà không có hai đỉnh nào cùng màu.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(N\), \(M\) và \(K\), lần lượt là số đỉnh, số cạnh và số màu.

Dòng thứ hai chứa \(N\) số nguyên từ \(1\) đến \(K\), là màu của các đỉnh theo thứ tự từ đỉnh \(1\) đến đỉnh \(N\).

Mỗi dòng trong \(M\) dòng tiếp theo mô tả một cạnh bằng hai số nguyên \(a\) và \(b\), là hai đỉnh mà cạnh đó nối. Giữa hai đỉnh bất kỳ có nhiều nhất một cạnh.

Dữ liệu ra

In ra một số nguyên là số đường đi có các đỉnh mang màu đôi một khác nhau. Kết quả luôn nhỏ hơn \(10^{18}\).

Ràng buộc

• \(1 \le N,M \le 300\,000\) và \(1 \le K \le 5\), với giới hạn cụ thể theo từng nhóm bên dưới.
• Màu của mỗi đỉnh là một số nguyên từ \(1\) đến \(K\).
• Với mỗi cạnh, \(1 \le a,b \le N\) và \(a \ne b\).
• Giữa hai đỉnh bất kỳ có nhiều nhất một cạnh; các cạnh là vô hướng.
• Mỗi đường đi được tính phải có ít nhất hai đỉnh và các đỉnh mang màu đôi một khác nhau.
• Kết quả nhỏ hơn \(10^{18}\).

Phân nhóm

• Mỗi nhóm kiểm thử gồm một số bộ dữ liệu. Bạn chỉ nhận được điểm của một nhóm khi giải đúng tất cả các bộ dữ liệu trong nhóm đó.

• Điểm của một lần nộp là tổng điểm các nhóm đạt được. Điểm cuối cùng là điểm cao nhất của một lần nộp.

• Nhóm 1 (23 điểm): \(1 \le N,M \le 100\), \(1 \le K \le 4\).

• Nhóm 2 (20 điểm): \(1 \le N,M \le 300\,000\), \(1 \le K \le 3\).
• Nhóm 3 (27 điểm): \(1 \le N,M \le 300\,000\), \(1 \le K \le 4\).
• Nhóm 4 (30 điểm): \(1 \le N,M \le 100\,000\), \(1 \le K \le 5\).

Ví dụ

4 3 3
1 2 1 3
1 2
2 3
4 2

10

9 11 4
1 2 3 4 1 2 1 2 2
1 2
1 3
2 3
2 4
3 6
6 2
6 5
4 3
4 5
7 8
9 8

70

Nguồn

Baltic Olympiad in Informatics 2018, ngày thi thứ hai.