BOI 2018 - Ngày 1

Như chúng ta đều biết, những bộ phim truyền hình dài tập có nhiều nhân vật có thể dẫn đến những chuyện tình vô cùng rắc rối. Trong một bộ phim có \(N\) nhân vật. Mỗi nhân vật yêu đúng một nhân vật, có thể là chính mình. Hai nhân vật khác nhau được gọi là một cặp đôi khi và chỉ khi họ yêu nhau.

Một kiểu rắc rối đặc biệt được gọi là “đa giác tình yêu”. Từ ba nhân vật trở lên tạo thành một đa giác tình yêu nếu người thứ nhất yêu người thứ hai, người thứ hai yêu người thứ ba, cứ như vậy, và người cuối cùng yêu người thứ nhất.

Một cuộc khảo sát gần đây cho thấy khán giả đã chán những chuyện tình rắc rối này và muốn xem điều gì đó lãng mạn hơn. Vì vậy, người ta quyết định bắn những mũi tên tình yêu vào một số nhân vật để tất cả mọi người đều có đôi. Khi bắn một mũi tên tình yêu vào một nhân vật, bạn có thể thay đổi người mà nhân vật đó yêu thành bất kỳ nhân vật nào bạn chọn.

Cần ít nhất bao nhiêu mũi tên tình yêu để tất cả mọi người đều có đôi?

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\), là số nhân vật. Mỗi dòng trong \(N\) dòng tiếp theo chứa hai tên \(s\) và \(t\) cách nhau bởi một dấu cách, cho biết nhân vật tên \(s\) ban đầu yêu nhân vật tên \(t\).

Dữ liệu ra

In ra một số nguyên: số mũi tên tình yêu ít nhất cần dùng để tất cả mọi người đều có đôi. Nếu không thể làm được, in ra -1.

Ràng buộc

• \(2 \le N \le 100\,000\).
• Tên của mỗi nhân vật dài không quá \(10\) chữ cái và chỉ gồm các chữ cái tiếng Anh viết thường.
• Mỗi nhân vật yêu đúng một nhân vật; người đó có thể là chính mình.

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 (21 điểm): \(2 \le N \le 20\).

• Nhóm 2 (25 điểm): \(2 \le N \le 100\,000\); mỗi nhân vật đều được một người nào đó yêu, có thể là chính mình.
• Nhóm 3 (29 điểm): \(2 \le N \le 100\,000\); ban đầu không có cặp đôi nào và không có đa giác tình yêu nào.
• Nhóm 4 (25 điểm): \(2 \le N \le 100\,000\); không có ràng buộc bổ sung.

Ví dụ

8
leonard emmy
ada emmy
isaac leonard
emmy pierre
pierre bernhard
bernhard emmy
sofia karl
karl sofia

3

4
a c
b c
c d
d d

3

3
rocky scarlet
scarlet patrick
patrick rocky

-1

Nguồn

Baltic Olympiad in Informatics 2018, ngày thi thứ nhất.

Như bạn có thể đã biết, DNA của con người có thể được biểu diễn bằng một xâu dài trên bảng chữ cái gồm bốn ký hiệu A, C, G, T. Mỗi ký hiệu biểu thị một loại bazơ nitơ khác nhau, lần lượt là adenine, cytosine, guanine và thymine.

Tuy nhiên, với người sao Hỏa thì mọi thứ hơi khác. Nghiên cứu trên người sao Hỏa mới nhất mà NASA bắt được cho thấy DNA của họ có tới \(K\) loại bazơ nitơ khác nhau! Vì vậy, DNA của người sao Hỏa có thể được biểu diễn bằng một xâu trên bảng chữ cái gồm \(K\) ký hiệu.

Một nhóm nghiên cứu muốn khai thác DNA của người sao Hỏa trong các ứng dụng trí tuệ nhân tạo đã yêu cầu lấy một đoạn liên tiếp duy nhất của một xâu DNA. Với \(R\) loại bazơ nitơ, họ chỉ định số lượng tối thiểu của từng loại cần có trong mẫu.

Bạn cần tìm đoạn con ngắn nhất của xâu DNA thỏa mãn các yêu cầu đó.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(N\), \(K\) và \(R\), lần lượt là tổng độ dài của xâu DNA, số loại bazơ nitơ và số loại mà các nhà nghiên cứu yêu cầu một số lượng tối thiểu.

Dòng thứ hai chứa \(N\) số nguyên cách nhau bởi dấu cách, biểu diễn toàn bộ xâu DNA. Số nguyên thứ \(i\), ký hiệu là \(D_i\), cho biết loại bazơ nitơ ở vị trí thứ \(i\). Các loại bazơ được đánh số từ \(0\) đến \(K-1\). Mỗi loại xuất hiện ít nhất một lần trong xâu DNA.

Mỗi dòng trong \(R\) dòng tiếp theo chứa hai số nguyên \(B\) và \(Q\), lần lượt là một loại bazơ và số lượng tối thiểu cần có của loại đó. Không có loại bazơ nào được liệt kê nhiều hơn một lần trong \(R\) dòng này.

Dữ liệu ra

In ra một số nguyên là độ dài của đoạn con liên tiếp ngắn nhất thỏa mãn yêu cầu của các nhà nghiên cứu. Nếu không tồn tại đoạn con như vậy, in ra impossible.

Ràng buộc

• \(1 \le N \le 200\,000\).
• \(1 \le R \le K \le N\).
• \(0 \le D_i < K\) với mọi \(1 \le i \le N\).
• Mỗi loại bazơ từ \(0\) đến \(K-1\) xuất hiện ít nhất một lần trong xâu DNA.
• Với mỗi yêu cầu, \(0 \le B < K\) và \(1 \le Q \le N\).
• Các giá trị \(B\) trong \(R\) yêu cầu đôi một khác nhau.

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 (16 điểm): \(1 \le N \le 100\), \(R \le 10\).

• Nhóm 2 (24 điểm): \(1 \le N \le 4\,000\), \(R \le 10\).
• Nhóm 3 (28 điểm): \(1 \le N \le 200\,000\), \(R \le 10\).
• Nhóm 4 (32 điểm): \(1 \le N \le 200\,000\); không có ràng buộc bổ sung.

Ví dụ

5 2 2
0 1 1 0 1
0 1
1 1

2

13 4 3
1 1 3 2 0 1 2 0 0 0 0 3 1
0 2
2 1
1 2

7

5 3 1
1 2 0 1 2
0 2

impossible

Nguồn

Baltic Olympiad in Informatics 2018, ngày thi thứ nhất.

Bạn đang tìm một vị trí trong đất để đặt chú giun cưng Maximus. Bạn giới hạn việc tìm kiếm trong một vùng hình hộp có kích thước \(N \times M \times K\) xentimét, được chia thành một lưới ba chiều gồm các ô lập phương có thể tích một xentimét khối. Mỗi ô có tọa độ \((x,y,z)\) với \(1 \le x \le N\), \(1 \le y \le M\), \(1 \le z \le K\). Độ ẩm \(H[x,y,z]\) là một số nguyên từ \(1\) đến \(10^9\).

Maximus thích những nơi ẩm ướt. Hãy tìm một ô có độ ẩm không nhỏ hơn độ ẩm của cả sáu ô kề nó theo các trục, để chú không bò đi. Chính xác hơn, cần tìm một ô \((x,y,z)\) sao cho

Độ ẩm ngoài hình hộp được xem là \(0\). Độ ẩm trong hộp cố định từ trước và không phụ thuộc vào các phép đo. Bạn chỉ được đo độ ẩm nhiều nhất \(Q\) lần.

Giao diện lập trình

Phiên bản này sử dụng giao diện hàm C++17. Tải tệp đính kèm worm.h, khai báo #include "worm.h" và cài đặt hàm sau; không viết main:

struct WormPosition { int x, y, z; };  // Đã được định nghĩa trong worm.h.
WormPosition find_worm(int N, int M, int K, int Q);

Trình chấm gọi hàm một lần cho mỗi bộ dữ liệu. Ba tham số đầu là kích thước hình hộp, còn \(Q\) là số phép đo tối đa. Hàm trả về tọa độ đánh số từ 1 của một ô thỏa mãn điều kiện trên. Trả về kết quả không tốn truy vấn; ô kết quả không bắt buộc phải được đo trước đó.

Trình chấm cung cấp hàm sau trong worm.h:

int measure(int x, int y, int z);

Hàm trả về \(H[x,y,z]\). Mỗi lời gọi đều tính một truy vấn, kể cả khi hỏi lại cùng một ô. Tọa độ phải nằm trong hộp. Một lời gọi không hợp lệ hoặc vượt quá \(Q\) truy vấn làm bộ dữ liệu bị chấm sai ngay lập tức. Chương trình không cần xử lý giá trị -1 hay flush như giao thức tương tác cũ.

Chỉ dùng một luồng, phép tính và bộ nhớ C++ thông thường. Không đọc/ghi đầu vào/đầu ra, mở tệp, tạo tiến trình hoặc kiểm tra hệ thống. Chỉ gọi measure trong quá trình thực hiện find_worm, không gọi từ hàm khởi tạo biến toàn cục. Chi tiết và chương trình minh họa có trong tệp đính kèm API.md.

Ràng buộc

• \(N\), \(M\), \(K\), \(Q\) là số nguyên dương, với giá trị cụ thể theo từng nhóm bên dưới.
• \(1 \le H[x,y,z] \le 10^9\) trong hình hộp; ngoài hộp có độ ẩm bằng \(0\).
• Mọi tọa độ truyền cho measure và tọa độ trả về đều phải nằm trong hình hộp.
• Được gọi measure nhiều nhất \(Q\) lần.

Phân nhóm

Mỗi nhóm chỉ có điểm khi tất cả các bộ dữ liệu trong nhóm đều đúng. Đ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 (10 điểm): \(M=K=1\), \(N=1\,000\,000\), \(Q=10\,000\).
• Nhóm 2 (22 điểm): \(M=K=1\), \(N=1\,000\,000\), \(Q=35\).
• Nhóm 3 (12 điểm): \(K=1\), \(N=M=200\), \(Q=4\,000\).
• Nhóm 4 (19 điểm): \(K=1\), \(N=M=1\,000\), \(Q=3\,500\).
• Nhóm 5 (14 điểm): \(N=M=K=100\), \(Q=100\,000\).
• Nhóm 6 (23 điểm): \(N=M=K=500\), \(Q=150\,000\).

Ví dụ

measure(3, 1, 1) trả về 13
measure(2, 1, 1) trả về 14
measure(1, 1, 1) trả về 10
find_worm trả về {2, 1, 1}

Nguồn

Baltic Olympiad in Informatics 2018, ngày thi thứ nhất.