BOI 2006 - Ngày 1

Trong xử lý tín hiệu, ta đôi khi cần tìm giá trị lớn nhất của một biểu thức chứa các phép toán AND và OR theo bit, khi mỗi biến nguyên chỉ được chọn trong một đoạn cho trước.

Biểu thức gồm \(P\) biểu thức con đặt trong ngoặc và nối với nhau bằng phép AND theo bit (&). Mỗi biểu thức con gồm một hoặc nhiều biến nối với nhau bằng phép OR theo bit (|). Các biến được đánh số theo thứ tự xuất hiện. Chẳng hạn, nếu số biến trong bốn biểu thức con lần lượt là \(3,1,2,2\) thì

Hãy tìm giá trị lớn nhất mà biểu thức có thể nhận.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(N\) và \(P\), lần lượt là tổng số biến và số biểu thức con.

Dòng tiếp theo chứa \(P\) số nguyên \(K_1,K_2,\ldots,K_P\), trong đó \(K_i\) là số biến của biểu thức con thứ \(i\). Mỗi \(K_i\ge 1\) và tổng các \(K_i\) bằng \(N\).

Mỗi dòng trong \(N\) dòng tiếp theo chứa hai số nguyên \(A_j,B_j\), quy định

Dữ liệu ra

In một số nguyên duy nhất: giá trị lớn nhất của biểu thức.

Ràng buộc

• \(1\le P\le N\le 100\).
• \(0\le A_j\le B_j\le 2\,000\,000\,000\).

Phân nhóm

• \(30\%\) số bộ dữ liệu có ít hơn một triệu cách gán các biến.

Ví dụ

8 4
3 1 2 2
2 4
1 4
0 0
1 7
1 4
1 2
3 4
2 3

6

Một quốc gia lưu hành \(N\) mệnh giá tiền xu, trong đó có đồng \(1\) xu, và một loại tiền giấy trị giá \(K\) xu lớn hơn mọi đồng xu. Một nhà sưu tập muốn có một đồng thuộc mỗi mệnh giá. Ông đã có sẵn một số mệnh giá và đang cầm đúng một tờ \(K\) xu.

Cửa hàng bán hàng hóa với mọi mức giá nguyên từ \(1\) đến \(K-1\) xu. Tiền thừa được trả bằng thuật toán tham lam: khi còn phải trả \(A\) xu, cửa hàng chọn đồng có mệnh giá lớn nhất không vượt quá \(A\), đưa đồng đó cho khách, trừ mệnh giá khỏi \(A\), rồi lặp lại đến khi \(A=0\).

Nhà sưu tập mua đúng một món bằng tờ \(K\) xu. Hãy xác định số mệnh giá mới lớn nhất mà ông có thể nhận được, và trong số các món đạt được số lượng ấy, giá món hàng lớn nhất.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(N\) và \(K\).

Mỗi dòng trong \(N\) dòng tiếp theo chứa \(c_i\) và \(d_i\). Giá trị \(c_i\) là mệnh giá đồng xu; \(d_i=1\) nếu nhà sưu tập đã có mệnh giá này, và \(d_i=0\) nếu chưa có. Các mệnh giá tăng nghiêm ngặt:

và \(c_1=1\).

Dữ liệu ra

Dòng đầu in số mệnh giá mới lớn nhất có thể nhận được. Dòng thứ hai in giá lớn nhất của một món hàng khiến tiền thừa chứa đúng số mệnh giá mới lớn nhất đó.

Ràng buộc

• \(1\le N\le 500\,000\).
• \(2\le K\le 1\,000\,000\,000\).
• \(1\le c_i<K\).

Ví dụ

7 25
1 0
2 0
3 1
5 0
10 0
13 0
20 0

3
6

Trên một bản đồ hai chiều có \(n\) thành phố. Thành phố \(i\) nằm tại tọa độ phân biệt \((x_i,y_i)\) và có \(s_i\) binh lính dưới quyền một vị tướng.

Ảnh hưởng của thành phố \(i\) tại vị trí \((x,y)\) bằng \(s_i\) chia cho bình phương khoảng cách từ thành phố ấy đến \((x,y)\). Thành phố \(i\) bị thành phố \(j\) đe dọa nếu ảnh hưởng của \(j\) tại \((x_i,y_i)\) lớn hơn \(s_i\).

• Nếu không bị thành phố nào đe dọa, thành phố \(i\) trở thành kinh đô của một vương quốc.
• Nếu đúng một thành phố \(j\) có ảnh hưởng lớn nhất và ảnh hưởng ấy đe dọa \(i\), thành phố \(i\) đầu hàng \(j\) và từ đó tuân theo cùng kinh đô với \(j\).
• Nếu có ít nhất hai thành phố cùng đạt ảnh hưởng đe dọa lớn nhất, sự nghi kỵ lẫn nhau cứu thành phố \(i\); tuy vậy vị tướng không thể làm vua, nên \(i\) trở thành thủ đô của một nền dân chủ.

Hãy xác định kết quả cuối cùng của mỗi thành phố.

Dữ liệu vào

Dòng đầu chứa số nguyên \(n\). Mỗi dòng thứ \(i\) trong \(n\) dòng tiếp theo chứa ba số nguyên \(x_i,y_i,s_i\).

Dữ liệu ra

In \(n\) dòng. Dòng \(i\) là:

• ký tự K nếu thành phố \(i\) là kinh đô của một vương quốc;
• ký tự D nếu thành phố \(i\) là thủ đô của một nền dân chủ;
• chỉ số \(j\) nếu thành phố \(i\) phải đầu hàng và cuối cùng tuân theo thành phố \(j\) làm kinh đô.

Ràng buộc

• \(1\le n\le 1000\).
• \(0\le x_i,y_i,s_i\le 1000\).
• Mọi cặp tọa độ \((x_i,y_i)\) đôi một khác nhau.

Ví dụ

5
2 5 14
2 3 2
3 2 7
1 1 2
2 1 3

K
D
K
3
3