APIO 2007

Bạn được nhờ mua một món quà cho em trai Ike. Tuy nhiên, Ike có sở thích rất riêng: em chỉ thích những món quà được sắp xếp theo đúng kiểu mình muốn.

Bạn tìm thấy một cửa hàng bán đồ chơi treo. Mỗi bộ đồ chơi treo là một vật trang trí nhiều tầng, thường được treo trên trần nhà, gồm các thanh ngang nối với nhau bằng dây thẳng đứng. Ở mỗi đầu của mỗi thanh có một sợi dây treo một thanh ngang khác hoặc một món đồ chơi.

Để Ike thích món quà, bạn cần tìm một bộ đồ chơi treo có thể được sắp xếp lại sao cho:

1. Hai món đồ chơi bất kỳ nằm ở cùng một tầng (nghĩa là được nối với trần nhà qua cùng số thanh ngang), hoặc chỉ chênh nhau một tầng.
2. Với hai món đồ chơi bất kỳ chênh nhau một tầng, món nằm bên trái phải ở thấp hơn món nằm bên phải.

Bạn có thể sắp xếp lại bằng các phép đổi chỗ. Trong một phép đổi chỗ, bạn chọn một thanh ngang, tháo những gì đang treo dưới hai đầu trái và phải của thanh, rồi treo chúng vào hai đầu đối diện. Phép đổi chỗ này không thay đổi thứ tự bên trong các phần được treo ở phía dưới.

Hãy xác định số phép đổi chỗ ít nhất để bộ đồ chơi treo thỏa mãn yêu cầu của Ike, hoặc cho biết không thể thực hiện được. Có thể giả sử các món đồ chơi không bao giờ vướng vào nhau.

Dữ liệu vào

Đọc từ đầu vào chuẩn.

Dòng đầu chứa số nguyên \(n\), là số thanh ngang. Các thanh được đánh số từ \(1\) đến \(n\).

Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(l,r\), cách nhau bởi một dấu cách, mô tả vật được treo dưới đầu trái và đầu phải của thanh \(i\). Nếu vật đó là một món đồ chơi thì giá trị tương ứng bằng \(-1\); nếu là một thanh ngang thì giá trị tương ứng là số hiệu thanh đó.

Mọi thanh treo phía dưới thanh \(i\) đều có số hiệu lớn hơn \(i\). Thanh \(1\) là thanh duy nhất ở trên cùng.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa số nguyên là số phép đổi chỗ ít nhất cần thực hiện. Nếu không thể sắp xếp lại theo yêu cầu, in \(-1\).

Ràng buộc

• \(1 \le n \le 100\,000\).
• Dữ liệu mô tả một bộ đồ chơi treo hợp lệ theo các quy tắc trên.

Phân nhóm

Mỗi phân nhóm được chấm độc lập theo kiểu tất cả hoặc không: bạn chỉ nhận điểm khi đúng toàn bộ test trong nhóm.

Ví dụ

6
2 3
-1 4
5 6
-1 -1
-1 -1
-1 -1

2

Nguồn

APIO 2007 — Mobiles.

Bạn điều hành một công ty công nghệ thông tin chuyên sao lưu dữ liệu máy tính cho các văn phòng lớn. Công việc sao lưu không thú vị, nên bạn thiết kế một hệ thống để các văn phòng sao lưu dữ liệu cho nhau, còn bạn có thể ở nhà chơi trò chơi máy tính.

Tất cả các văn phòng nằm dọc theo cùng một con phố. Bạn quyết định ghép các văn phòng thành từng cặp và nối hai tòa nhà trong mỗi cặp bằng một dây cáp mạng để chúng có thể sao lưu dữ liệu cho nhau.

Tuy nhiên, cáp mạng rất đắt. Công ty viễn thông chỉ cung cấp \(k\) dây cáp, nên bạn chỉ có thể thiết lập sao lưu cho đúng \(k\) cặp, gồm tổng cộng \(2k\) văn phòng. Không văn phòng nào được thuộc nhiều hơn một cặp; tức là \(2k\) văn phòng này phải đôi một khác nhau.

Công ty viễn thông tính phí theo số kilômét cáp. Hãy chọn \(k\) cặp sao cho tổng khoảng cách giữa hai văn phòng trong mỗi cặp là nhỏ nhất.

Dữ liệu vào

Đọc từ đầu vào chuẩn.

Dòng đầu chứa hai số nguyên \(n,k\), lần lượt là số văn phòng trên phố và số dây cáp mạng có sẵn.

Mỗi dòng trong \(n\) dòng tiếp theo chứa một số nguyên \(s\), là khoảng cách tính bằng kilômét từ một văn phòng đến đầu phố. Các khoảng cách được cho theo thứ tự tăng dần. Không có hai văn phòng ở cùng một vị trí.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên dương là tổng chiều dài cáp mạng nhỏ nhất cần dùng để nối \(2k\) văn phòng khác nhau thành \(k\) cặp.

Ràng buộc

• \(2 \le n \le 100\,000\).
• \(1 \le k \le \lfloor n/2 \rfloor\).
• \(0 \le s \le 1\,000\,000\,000\).

Phân nhóm

Mỗi phân nhóm được chấm độc lập theo kiểu tất cả hoặc không: bạn chỉ nhận điểm của nhóm khi đúng toàn bộ test trong nhóm. Điểm trong bảng là phần điểm cộng thêm trên LQDOJ; nhóm sau bao gồm lại các test thỏa điều kiện của nhóm trước.

Ví dụ

5 2
1
3
4
6
12

4

Nguồn

APIO 2007 — Backup.

Niềm tự hào của khu vực châu Á – Thái Bình Dương là Đại Sở thú Hình tròn vừa được xây dựng trên một hòn đảo nhỏ giữa Thái Bình Dương. Sở thú gồm các chuồng xếp thành một vòng tròn lớn, mỗi chuồng nuôi một con vật lạ.

Bạn phụ trách quan hệ công chúng của sở thú, nên nhiệm vụ của bạn là làm cho mọi người vui vẻ nhất có thể. Một xe buýt chở học sinh vừa đến, và bạn rất muốn làm các em hài lòng. Nhưng điều này không dễ: có những con vật được một số em yêu thích, lại khiến những em khác sợ hãi. Chẳng hạn, Alex thích khỉ và gấu túi vì chúng dễ thương, nhưng sợ sư tử vì hàm răng sắc nhọn. Ngược lại, Polly thích sư tử vì bộ bờm đẹp, nhưng sợ gấu túi vì chúng rất hôi.

Bạn có thể đưa một số con vật ra khỏi chuồng để các em không sợ. Tuy nhiên, nếu đưa đi quá nhiều con vật, các em sẽ chẳng còn gì để ngắm. Hãy quyết định những con vật cần đưa đi để số trẻ vui vẻ là lớn nhất.

Mỗi em đứng bên ngoài vòng tròn và nhìn thấy đúng năm chuồng liên tiếp. Bạn có danh sách các con vật mỗi em sợ và yêu thích. Một em sẽ vui vẻ nếu ít nhất một trong hai điều sau được thỏa mãn:

• Ít nhất một con vật em sợ được đưa ra khỏi tầm nhìn của em.
• Ít nhất một con vật em yêu thích vẫn ở trong tầm nhìn của em.

Dữ liệu vào

Đọc từ đầu vào chuẩn.

Dòng đầu chứa hai số nguyên \(N,C\), lần lượt là số chuồng và số trẻ. Các chuồng được đánh số \(1,2,\ldots,N\) theo chiều kim đồng hồ.

Mỗi dòng trong \(C\) dòng tiếp theo mô tả một em theo dạng:

• \(E\) là chuồng đầu tiên em nhìn thấy. Em nhìn thấy các chuồng \(E,E+1,E+2,E+3,E+4\). Số hiệu vượt quá \(N\) được quay vòng về đầu; chẳng hạn, nếu \(N=14\) và \(E=13\), em nhìn thấy các chuồng \(13,14,1,2,3\).
• \(F\) là số con vật em sợ, còn \(L\) là số con vật em yêu thích.
• Các chuồng \(X_1,\ldots,X_F\) chứa những con vật em sợ.
• Các chuồng \(Y_1,\ldots,Y_L\) chứa những con vật em yêu thích.
• Các số \(X_1,\ldots,X_F,Y_1,\ldots,Y_L\) đôi một khác nhau và đều là số hiệu các chuồng em nhìn thấy.

Các em được liệt kê theo thứ tự không giảm của \(E\). Nhiều em có thể có cùng chuồng đầu tiên \(E\).

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên là số trẻ vui vẻ lớn nhất có thể đạt được.

Ràng buộc

• \(10 \le N \le 10\,000\).
• \(1 \le C \le 50\,000\).
• \(1 \le E \le N\).
• \(F,L \ge 0\) và \(F+L \le 5\).
• \(1 \le X_i,Y_j \le N\) với mọi chỉ số tương ứng hợp lệ.
• Mỗi danh sách chỉ chứa các chuồng nằm trong năm chuồng liên tiếp mà em đó nhìn thấy, và không lặp chuồng giữa hai danh sách.

Phân nhóm

Mỗi phân nhóm được chấm độc lập theo kiểu tất cả hoặc không: bạn chỉ nhận điểm khi đúng toàn bộ test trong nhóm.

Ví dụ

14 5
2 1 2 4 2 6
3 1 1 6 4
6 1 2 9 6 8
8 1 1 9 12
12 3 0 12 13 2

5

12 7
1 1 1 1 5
5 1 1 5 7
5 0 3 5 7 9
7 1 1 7 9
9 1 1 9 11
9 3 0 9 11 1
11 1 1 11 1

6

Nguồn

APIO 2007 — Zoo.