CEOI 2022 - Ngày 2

Đề bài

Paint & Wine là xưởng vẽ đầu tiên tại Zagreb cung cấp những buổi học vẽ thư giãn cùng một ly rượu vang. Trong mỗi buổi học, học viên nhận một chủ đề nhất định và, với sự hỗ trợ của các họa sĩ bậc thầy, thường tạo ra một tác phẩm ấn tượng.

Ante là họa sĩ hướng dẫn, Luka là học viên của anh, và câu chuyện trong bài toán này diễn ra vào một buổi học có phần nhiều rượu hơn bình thường.

Ante nói: "Hãy vẽ cho tôi một cái cây!"

Luka hỏi: "Được thôi. Anh muốn cây gì? Cọ, sồi hay thông?"

Ante đáp: "Tôi muốn một đồ thị vô hướng liên thông không có chu trình!"

Luka nói: "Tôi làm được... Anh còn yêu cầu gì không?"

Ante nói: "Tôi thích mỗi đỉnh kề với không quá ba đỉnh khác!"

Luka đáp: "Ừm, được... Nhưng có rất nhiều cây như vậy."

Ante nói: "Đây là danh sách các cạnh. Tôi muốn đúng cây này!"

Luka đáp: "Được rồi. Nhưng vẫn có nhiều cách vẽ nó."

Ante nói: "Đây là danh sách các điểm trên mặt phẳng mà tôi muốn đặt các đỉnh. Tôi cũng không muốn thấy bất kỳ cặp cạnh nào cắt nhau."

Luka đáp: "Tôi làm ngay!"

Hãy giúp Luka vẽ cây theo đúng yêu cầu của Ante. Cụ thể, bạn được cho một cây mà mỗi đỉnh kề với không quá ba đỉnh khác, cùng một danh sách điểm trên mặt phẳng. Hãy tìm một ánh xạ một-một từ các đỉnh đến các điểm sao cho khi vẽ mỗi cạnh của cây thành đoạn thẳng nối hai điểm tương ứng, không có hai cạnh nào giao nhau, ngoại trừ tại đầu mút chung.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên \(N\), đồng thời là số đỉnh của cây và số điểm trên mặt phẳng.

\(N-1\) dòng tiếp theo mô tả các cạnh của cây. Mỗi dòng chứa hai số nguyên \(a\) và \(b\), là nhãn của hai đỉnh được nối bởi cạnh đó. Các đỉnh được đánh số từ \(1\) đến \(N\).

Dữ liệu bảo đảm mỗi đỉnh kề với không quá ba đỉnh khác.

\(N\) dòng tiếp theo mô tả các điểm dùng để vẽ cây. Mỗi dòng chứa hai tọa độ nguyên của một điểm. Không có hai điểm nào có cùng cặp tọa độ và không có ba điểm nào thẳng hàng.

Dữ liệu ra

In một hoán vị của các số nguyên từ \(1\) đến \(N\) trên một dòng. Số thứ \(i\) là nhãn của đỉnh được ánh xạ tới điểm thứ \(i\) trong dữ liệu vào.

Nếu có nhiều lời giải hợp lệ, có thể in bất kỳ lời giải nào. Dữ liệu bảo đảm luôn tồn tại lời giải.

Ràng buộc

Trong tất cả các subtask, tọa độ các điểm là số nguyên từ \(0\) đến \(10^9\).

Phân nhóm

• Subtask 1 (10 điểm): \(3\le N\le 200\,000\) và tồn tại một đa giác lồi nhận tất cả các điểm đã cho làm đỉnh.
• Subtask 2 (15 điểm): \(1\le N\le 4\,000\).
• Subtask 3 (15 điểm): \(1\le N\le 10\,000\).
• Subtask 4 (35 điểm): \(1\le N\le 80\,000\).
• Subtask 5 (25 điểm): \(1\le N\le 200\,000\).

Ví dụ

3
1 2
2 3
10 10
10 20
20 10

1 2 3

5
1 2
1 3
1 4
4 5
10 10
10 30
30 10
30 30
20 25

5 4 2 3 1

6
1 2
2 3
1 4
4 5
4 6
10 60
10 40
40 50
40 30
70 30
70 10

6 5 4 1 2 3

Đề bài

Đại dịch COVID-19 khiến thế giới bất ngờ theo nhiều cách. Gần như chỉ sau một đêm, mọi người trên khắp thế giới phải thích nghi với lối sống mới, chủ yếu được định hình bởi các biện pháp phòng ngừa do chính quyền địa phương ban hành nhằm ngăn chặn và kiểm soát sự lây lan của dịch bệnh.

Để chuẩn bị tốt hơn cho khả năng xa xôi rằng một đợt dịch nghiêm trọng hơn sẽ xảy ra trong tương lai, Viện Y tế Công cộng Quốc gia Croatia quyết định thành lập nhiều bộ phận nghiên cứu. Mục tiêu chính của các bộ phận này là xây dựng những quy trình hiệu quả giúp người dân nhanh chóng tuân thủ một biện pháp phòng ngừa mới.

Alenka làm việc tại một bộ phận như vậy. Cô đang nghiên cứu tình huống một nhóm người đứng trên một đường thẳng, chẳng hạn trước một bưu điện, rồi một quy định an toàn mới đột ngột có hiệu lực: khoảng cách giữa hai người bất kỳ phải ít nhất là \(D\).

Alenka đã xây dựng một ứng dụng cho phép người dùng nhập khoảng cách \(D\) và vị trí của \(N\) người dưới dạng các tọa độ trên một đường thẳng. Ứng dụng vẽ lại tình huống và tính thời gian nhỏ nhất tính bằng giây, ký hiệu là \(t_{opt}\), để cả nhóm đạt được một cách sắp xếp thỏa mãn quy định. Ứng dụng giả sử mọi người lập tức bắt đầu sắp xếp lại vị trí một cách tối ưu và tất cả đều di chuyển với cùng vận tốc không đổi là một đơn vị mỗi giây.

Alenka muốn bổ sung tính năng cho phép người dùng thêm \(M\) người vào nhóm bằng cách chạm lên đường thẳng để chỉ định vị trí của họ. Sau mỗi lần chạm, tức là sau mỗi người mới được thêm vào, ứng dụng phải tính lại \(t_{opt}\).

Hãy giúp Alenka cài đặt tính năng này.

Dữ liệu vào

Dòng đầu tiên chứa ba số nguyên \(N\), \(M\) và \(D\).

Dòng thứ hai chứa \(N\) số nguyên \(a_1,a_2,\ldots,a_N\), là vị trí của \(N\) người ban đầu. Nếu \(N=0\), dòng này rỗng.

Dòng thứ ba chứa \(M\) số nguyên \(b_1,b_2,\ldots,b_M\), là vị trí của \(M\) người được thêm vào.

Dữ liệu ra

In \(M\) số trên một dòng. Số thứ \(i\) là giá trị \(t_{opt}\) khi nhóm gồm \(N+i\) người tại các vị trí

Mỗi số phải được in ở dạng thập phân không có chữ số 0 thừa ở cuối. Ví dụ, hãy in 1.23 thay vì 1.2300, và in 123 thay vì 123. hoặc 123.0. Có thể chứng minh rằng mọi đáp án đều có biểu diễn thập phân hữu hạn.

Ràng buộc

Trong tất cả các subtask:

• \(1\le D\le 10^9\).
• \(1\le a_i\le 10^9\).
• \(1\le b_i\le 10^9\).

Phân nhóm

• Subtask 1 (10 điểm): \(0\le N\le 2\,000\), \(1\le M\le 10\).
• Subtask 2 (14 điểm): \(0\le N\le 200\,000\), \(1\le M\le 10\).
• Subtask 3 (35 điểm): \(N=0\), \(1\le M\le 200\,000\) và \(b_1\le b_2\le\cdots\le b_M\).
• Subtask 4 (41 điểm): \(N=0\), \(1\le M\le 200\,000\).

Ví dụ

2 1 2
1 3
2

1

0 5 3

1 2 3 4 5

0 1 2 3 4

3 3 3
3 3 3
3 3 3

4.5 6 7.5

Đề bài

Valerija làm nhân viên giữ xe tại một nhà hàng sang trọng. Công việc của cô là đón những vị khách quý, nhận chìa khóa và đưa xe của họ vào bãi đỗ gần đó. Khi sự kiện kết thúc, cô bảo đảm mỗi vị khách nhận lại đúng xe và vui vẻ rời đi.

Một buổi tối, ngay sau khi đỗ xong tất cả các xe, Valerija nhận thấy một tính chất thú vị về màu sắc của chúng. Có đúng \(2N\) chiếc xe với \(N\) màu khác nhau, và mỗi màu xuất hiện trên đúng hai chiếc xe. Ta biểu diễn các màu bằng những số nguyên từ \(1\) đến \(N\).

Bãi đỗ gồm một dãy \(M\) chỗ, được đánh số từ \(1\) đến \(M\). Mỗi chỗ chứa nhiều nhất hai xe và chỉ có một lối ra vào. Một xe chỉ có thể vào hoặc ra nếu không bị xe khác chắn lối. Xe gần lối vào hơn được gọi là xe trên, còn xe xa lối vào hơn được gọi là xe dưới. Valerija đã đỗ xe sao cho mỗi chỗ hoặc trống, hoặc đầy hai xe, hoặc chỉ có một xe dưới.

Valerija muốn sắp xếp lại sao cho hai xe cùng màu nằm trong cùng một chỗ đỗ. Cô không quan tâm chỗ nào chứa màu nào, cũng không quan tâm xe cụ thể nào nằm trên hay dưới. Việc sắp xếp lại gồm một chuỗi lượt di chuyển.

Trong mỗi lượt, Valerija ngồi vào một chiếc xe đang có thể rời khỏi chỗ hiện tại và lái nó đến một chỗ khác thuộc một trong hai loại sau:

• Chỗ đó đang trống; khi ấy cô đỗ xe làm xe dưới.
• Chỗ đó chỉ chứa một xe cùng màu với chiếc cô đang lái; khi ấy cô đỗ xe làm xe trên.

Valerija muốn dùng ít lượt di chuyển nhất để đạt cách sắp xếp mong muốn. Hãy tìm một chuỗi di chuyển ngắn nhất, hoặc xác định rằng không tồn tại chuỗi nào như vậy.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(M\), cách nhau bởi dấu cách.

Dòng thứ \(i\) trong \(M\) dòng tiếp theo chứa hai số nguyên \(b_i\) và \(t_i\) \((0\le b_i,t_i\le N)\), mô tả chỗ đỗ thứ \(i\). Giá trị \(b_i\) là màu của xe dưới và \(t_i\) là màu của xe trên. Nếu một vị trí trong chỗ đỗ đang trống, số tương ứng bằng \(0\).

Dữ liệu bảo đảm không có chỗ nào chỉ chứa xe trên: nếu \(b_i=0\) thì \(t_i=0\).

Dữ liệu ra

Nếu không tồn tại chuỗi di chuyển nào có thể sắp xếp các xe theo yêu cầu, in -1 trên dòng duy nhất.

Ngược lại, dòng đầu tiên chứa số nguyên \(K\), là số lượt di chuyển nhỏ nhất cần thiết.

Dòng thứ \(i\) trong \(K\) dòng tiếp theo mô tả lượt di chuyển thứ \(i\) và chứa hai số nguyên \(x_i\) và \(y_i\) \((1\le x_i,y_i\le M, x_i\ne y_i)\). Trong lượt đó, Valerija chuyển một xe từ chỗ \(x_i\) sang chỗ \(y_i\).

Tại thời điểm thực hiện lượt di chuyển, chỗ \(x_i\) phải chứa ít nhất một xe. Chiếc xe gần lối vào nhất tại chỗ \(x_i\) phải có thể chuyển đến chỗ \(y_i\): chỗ \(y_i\) phải đang trống hoặc chỉ chứa một xe cùng màu.

Ràng buộc

Trong tất cả các subtask, \(1\le N\le M\le 200\,000\).

Phân nhóm

Nếu lời giải xác định đúng số lượt di chuyển nhỏ nhất cho mọi bộ kiểm thử của một subtask, nhưng mô tả sai một số lượt di chuyển hoặc không in mô tả, lời giải nhận \(20\%\) số điểm của subtask đó.

• Subtask 1 (10 điểm): \(M\le 4\).
• Subtask 2 (10 điểm): \(2N\le M\).
• Subtask 3 (25 điểm): Ban đầu mọi chỗ đỗ đều trống hoặc đầy, và \(N\le 1\,000\).
• Subtask 4 (15 điểm): Ban đầu mọi chỗ đỗ đều trống hoặc đầy.
• Subtask 5 (25 điểm): \(N\le 1\,000\).
• Subtask 6 (15 điểm): Không có ràng buộc bổ sung.

Ví dụ

4 5
1 0
2 0
1 3
4 4
3 2

3
5 2
3 5
3 1

4 5
0 0
2 1
3 1
3 4
2 4

-1

5 7
1 0
2 1
2 3
4 3
5 4
5 0
0 0

6
2 1
3 7
4 7
2 3
5 4
5 6