APIO 2015

Trên một đường phố chính ở Bali có \(N\) tác phẩm điêu khắc, đánh số liên tiếp từ \(1\) đến \(N\). Tác phẩm thứ \(i\) có tuổi là \(Y_i\).

Chính phủ muốn chia các tác phẩm thành \(X\) nhóm, với \(A\le X\le B\), sao cho:

• Mỗi nhóm chứa ít nhất một tác phẩm và mỗi tác phẩm thuộc đúng một nhóm.
• Các tác phẩm trong cùng một nhóm nằm liên tiếp trên đường phố.

Với mỗi nhóm, tính tổng tuổi của các tác phẩm trong nhóm. Giá trị thẩm mỹ tổng hợp là kết quả phép OR theo bit của tất cả các tổng đó. Hãy tìm giá trị thẩm mỹ tổng hợp nhỏ nhất có thể.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên \(N,A,B\).
• Dòng thứ hai chứa \(N\) số nguyên \(Y_1,Y_2,\ldots,Y_N\).

Dữ liệu ra

In giá trị thẩm mỹ tổng hợp nhỏ nhất.

Ví dụ

6 1 3
8 1 2 1 5 4

11

Giải thích

Chia thành hai nhóm (8 1 2) và (1 5 4). Hai tổng là \(11\) và \(10\), nên giá trị thẩm mỹ là \(11\mathbin{\mathrm{OR}}10=11\).

Phân nhóm

Nguồn

Asia-Pacific Informatics Olympiad 2015, bài Bali Sculptures.

Jakarta có \(N\) tòa nhà chọc trời nằm trên một đường thẳng, đánh số từ \(0\) đến \(N-1\) từ trái sang phải.

Có \(M\) sinh vật gọi là doge, đánh số từ \(0\) đến \(M-1\). Ban đầu doge \(i\) ở tòa nhà \(B_i\) và có năng lượng \(P_i\). Trong một bước nhảy, doge có năng lượng \(p\) đang ở tòa nhà \(b\) có thể nhảy đến \(b+p\) hoặc \(b-p\), miễn là tòa nhà đích có số hiệu trong \([0,N-1]\).

Doge \(0\) cần truyền một tin khẩn cấp tới doge \(1\). Sau khi nhận tin, một doge có thể:

• thực hiện một bước nhảy; hoặc
• truyền tin cho một doge khác đang ở cùng tòa nhà.

Hãy tìm tổng số bước nhảy ít nhất mà tất cả doge phải thực hiện để tin đến được doge \(1\), hoặc cho biết việc đó không thể thực hiện.

Dữ liệu vào

• Dòng đầu chứa \(N,M\).
• \(M\) dòng tiếp theo, dòng thứ \(i\) chứa \(B_i,P_i\).

Dữ liệu ra

In tổng số bước nhảy nhỏ nhất, hoặc -1 nếu không thể truyền tin.

Ràng buộc chung

• \(0\le B_i<N\).
• \(M\ge2\).

Ví dụ

5 3
0 2
1 1
4 1

5

Giải thích

Doge \(0\) nhảy từ tòa nhà \(0\) đến \(2\), rồi đến \(4\) trong hai bước và truyền tin cho doge \(2\). Doge \(2\) nhảy từ \(4\) đến \(3\), \(2\), rồi \(1\) trong ba bước và truyền tin cho doge \(1\). Tổng cộng có năm bước nhảy.

Phân nhóm

Nguồn

Asia-Pacific Informatics Olympiad 2015, bài Jakarta Skyscrapers.

Thành phố Palembang bị sông Musi chia thành hai vùng \(A\) và \(B\). Mỗi vùng có đúng \(1\,000\,000\,001\) tòa nhà dọc bờ sông, đánh số từ \(0\) đến \(1\,000\,000\,000\). Hai tòa nhà liền kề cách nhau một đơn vị; bề rộng sông cũng là một đơn vị. Tòa nhà \(i\) ở vùng \(A\) đối diện tòa nhà \(i\) ở vùng \(B\).

Có \(N\) công dân. Nhà của người \(i\) ở tòa nhà \(S_i\) thuộc vùng \(P_i\), còn nơi làm việc ở tòa nhà \(T_i\) thuộc vùng \(Q_i\). Chính phủ sẽ xây tối đa \(K\) cây cầu. Mỗi cầu nối hai tòa nhà đối diện ở hai vùng, vuông góc với sông, và các cầu không chồng lên nhau.

Sau khi xây cầu, gọi \(D_i\) là khoảng cách lái xe ngắn nhất từ nhà đến nơi làm việc của công dân \(i\). Hãy chọn vị trí cầu để tối thiểu hóa:

Dữ liệu vào

• Dòng đầu chứa \(K,N\).
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa \(P_i,S_i,Q_i,T_i\). Hai giá trị \(P_i,Q_i\) là ký tự A hoặc B; các trường còn lại là số nguyên.

Dữ liệu ra

In tổng khoảng cách nhỏ nhất.

Ràng buộc chung

• \(P_i,Q_i\in\{\texttt{A},\texttt{B}\}\).
• \(0\le S_i,T_i\le1\,000\,000\,000\).
• Nhiều nhà hoặc nơi làm việc có thể nằm trong cùng một tòa nhà.

Ví dụ

1 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

24

2 5
B 0 A 4
B 1 B 3
A 5 B 7
B 2 A 6
B 1 A 7

22

Giải thích

Cấu hình thành phố trong cả hai ví dụ:

{{asset:apio15-bridge-initial}}

Ở ví dụ thứ nhất chỉ có một cách đặt cầu tối ưu:

{{asset:apio15-bridge-sample1}}

Một cách đặt hai cầu tối ưu cho ví dụ thứ hai:

{{asset:apio15-bridge-sample2}}

Phân nhóm

Nguồn

Asia-Pacific Informatics Olympiad 2015, bài Palembang Bridges.