IOI 2020 - Ngày 1

Nhà thực vật học Hazel đến tham quan một triển lãm đặc biệt tại Vườn Bách thảo Singapore. Trong triển lãm, \(n\) cây có chiều cao đôi một khác nhau được đặt trên một vòng tròn. Các cây được gán nhãn từ \(0\) đến \(n-1\) theo chiều kim đồng hồ, với cây \(n-1\) nằm bên cạnh cây \(0\).

Với mỗi cây \(i\) (\(0 \le i \le n-1\)), Hazel so sánh cây \(i\) với từng cây trong \(k-1\) cây kế tiếp theo chiều kim đồng hồ, rồi ghi lại số \(r[i]\) là số cây cao hơn cây \(i\) trong số \(k-1\) cây đó. Như vậy, mỗi giá trị \(r[i]\) phụ thuộc vào tương quan chiều cao của một số cây liên tiếp.

Ví dụ, giả sử \(n=5\), \(k=3\) và \(i=3\). Khi đó, \(k-1=2\) cây kế tiếp theo chiều kim đồng hồ tính từ cây \(i=3\) là cây \(4\) và cây \(0\). Nếu cây \(4\) cao hơn cây \(3\) và cây \(0\) thấp hơn cây \(3\), Hazel sẽ ghi lại \(r[3]=1\).

Bạn có thể giả sử Hazel đã ghi các giá trị \(r[i]\) chính xác. Do đó, tồn tại ít nhất một cách gán các chiều cao đôi một khác nhau cho các cây phù hợp với những giá trị này.

Bạn được yêu cầu so sánh chiều cao của \(q\) cặp cây. Đáng tiếc, bạn không thể đến triển lãm. Nguồn thông tin duy nhất của bạn là sổ ghi chép của Hazel, chứa giá trị \(k\) và dãy \(r[0],\ldots,r[n-1]\).

Với mỗi cặp cây khác nhau \(x\) và \(y\) cần so sánh, hãy xác định trường hợp nào trong ba trường hợp sau xảy ra:

• Cây \(x\) chắc chắn cao hơn cây \(y\): với mọi cách gán chiều cao đôi một khác nhau \(h[0],\ldots,h[n-1]\) phù hợp với mảng \(r\), luôn có \(h[x]>h[y]\).
• Cây \(x\) chắc chắn thấp hơn cây \(y\): với mọi cách gán chiều cao đôi một khác nhau \(h[0],\ldots,h[n-1]\) phù hợp với mảng \(r\), luôn có \(h[x]<h[y]\).
• Không thể kết luận: không thuộc trường hợp nào trong hai trường hợp trên.

Chi tiết cài đặt

Bạn cần cài đặt các hàm C++ sau:

void init(int k, std::vector<int> r);

• \(k\): số cây liên tiếp có chiều cao quyết định mỗi giá trị \(r[i]\).
• \(r\): mảng kích thước \(n\), trong đó \(r[i]\) là số cây cao hơn cây \(i\) trong \(k-1\) cây kế tiếp theo chiều kim đồng hồ.
• Hàm này được gọi đúng một lần, trước mọi lời gọi compare_plants.

int compare_plants(int x, int y);

• \(x\), \(y\): nhãn của hai cây cần so sánh.
• Hàm phải trả về \(1\) nếu cây \(x\) chắc chắn cao hơn cây \(y\); \(-1\) nếu cây \(x\) chắc chắn thấp hơn cây \(y\); \(0\) nếu không thể kết luận.
• Hàm này được gọi đúng \(q\) lần.

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): n k q.
• Dòng \(2\): r[0] r[1] ... r[n-1].
• Dòng \(3+i\) (\(0 \le i \le q-1\)): x y cho lời gọi compare_plants thứ \(i\) (đánh số từ \(0\)).

Dữ liệu ra

Trình chấm mẫu in trên dòng \(1+i\) (\(0 \le i \le q-1\)) giá trị trả về của lời gọi compare_plants thứ \(i\).

Ràng buộc

• \(2 \le k \le n \le 200\,000\).
• \(1 \le q \le 200\,000\).
• \(0 \le r[i] \le k-1\) (\(0 \le i \le n-1\)).
• \(0 \le x < y \le n-1\).

Tồn tại ít nhất một cách gán các chiều cao đôi một khác nhau cho các cây phù hợp với mảng \(r\).

Phân nhóm

Ví dụ

init(3, [0, 1, 1, 2])

init(2, [0, 1, 0, 1])

Nguồn

IOI 2020, Ngày 1 — Comparing Plants (plants). Đề chính thức tiếng Anh và bản dịch tiếng Việt.

Gardens by the Bay là một công viên thiên nhiên rộng lớn ở Singapore. Trong công viên có \(n\) tòa tháp, được gọi là siêu cây (supertree). Các tháp được gán nhãn từ \(0\) đến \(n-1\). Ta muốn xây dựng một tập gồm không hoặc nhiều cầu. Mỗi cầu nối hai tháp khác nhau và có thể đi qua theo cả hai chiều. Không được có hai cầu nối cùng một cặp tháp.

Một đường đi từ tháp \(x\) đến tháp \(y\) là một dãy gồm một hoặc nhiều tháp sao cho:

• Phần tử đầu tiên của dãy là \(x\).
• Phần tử cuối cùng của dãy là \(y\).
• Tất cả các phần tử của dãy đôi một khác nhau.
• Mỗi hai phần tử (tháp) liên tiếp trong dãy được nối với nhau bởi một cầu.

Lưu ý rằng theo định nghĩa, có đúng một đường đi từ một tháp đến chính nó; số đường đi khác nhau từ tháp \(i\) đến tháp \(j\) bằng số đường đi khác nhau từ tháp \(j\) đến tháp \(i\).

Kiến trúc sư chính phụ trách thiết kế muốn các cầu được xây dựng sao cho với mọi \(0 \le i,j \le n-1\), có đúng \(p[i][j]\) đường đi khác nhau từ tháp \(i\) đến tháp \(j\), trong đó \(0 \le p[i][j] \le 3\).

Hãy xây dựng một tập các cầu thỏa mãn yêu cầu của kiến trúc sư, hoặc xác định rằng không thể thực hiện được.

Chi tiết cài đặt

Bạn cần cài đặt hàm C++ sau:

int construct(std::vector<std::vector<int>> p);

• \(p\): mảng kích thước \(n\times n\) biểu diễn yêu cầu của kiến trúc sư.
• Nếu có thể xây dựng, hàm phải gọi build (mô tả bên dưới) đúng một lần để báo cáo phương án xây dựng, rồi trả về \(1\).
• Nếu không thể xây dựng, hàm phải trả về \(0\) và không gọi build lần nào.
• Hàm construct được gọi đúng một lần.

Hàm build được định nghĩa như sau:

void build(std::vector<std::vector<int>> b);

• \(b\): mảng kích thước \(n\times n\), với \(b[i][j]=1\) nếu có cầu nối tháp \(i\) và tháp \(j\), và \(b[i][j]=0\) nếu không có.
• Mảng phải thỏa mãn:

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): n.
• Dòng \(2+i\) (\(0 \le i \le n-1\)): p[i][0] p[i][1] ... p[i][n-1].

Dữ liệu ra

Trình chấm mẫu in:

• Dòng \(1\): giá trị trả về của construct.

Nếu giá trị trả về của construct là \(1\), trình chấm mẫu in thêm:

• Dòng \(2+i\) (\(0 \le i \le n-1\)): b[i][0] b[i][1] ... b[i][n-1].

Ràng buộc

• \(1 \le n \le 1000\).
• \(p[i][i]=1\) (\(0 \le i \le n-1\)).
• \(p[i][j]=p[j][i]\) (\(0 \le i,j \le n-1\)).
• \(0 \le p[i][j] \le 3\) (\(0 \le i,j \le n-1\)).

Phân nhóm

Ví dụ

construct([[1, 1, 2, 2], [1, 1, 2, 2], [2, 2, 1, 2], [2, 2, 2, 1]])

build([[0, 1, 0, 0], [1, 0, 1, 1], [0, 1, 0, 1], [0, 1, 1, 0]])

construct([[1, 0], [0, 1]])

build([[0, 0], [0, 0]])

construct([[1, 3], [3, 1]])

Nguồn

IOI 2020, Ngày 1 — Connecting Supertrees (supertrees). Đề chính thức tiếng Anh và bản dịch tiếng Việt.

Ringo đang tham dự một lễ hội ở Singapore. Cậu có một số vé dự thưởng trong túi và muốn sử dụng chúng tại quầy trò chơi có thưởng. Mỗi vé thuộc một trong \(n\) màu và có in một số nguyên không âm. Các số nguyên in trên những vé khác nhau có thể bằng nhau. Theo một luật lệ kỳ quặc của lễ hội, \(n\) được bảo đảm là số chẵn.

Ringo có \(m\) vé mỗi màu trong túi, tổng cộng \(n\cdot m\) vé. Vé \(j\) của màu \(i\) có in số nguyên \(x[i][j]\) (\(0 \le i \le n-1\) và \(0 \le j \le m-1\)).

Trò chơi diễn ra trong \(k\) vòng, đánh số từ \(0\) đến \(k-1\). Mỗi vòng diễn ra theo thứ tự sau:

1. Ringo chọn từ túi một tập gồm \(n\) vé, mỗi màu đúng một vé, rồi đưa tập vé này cho người quản trò.
2. Người quản trò ghi lại các số nguyên \(a[0],a[1],\ldots,a[n-1]\) in trên các vé trong tập. Thứ tự của \(n\) số nguyên này không quan trọng.
3. Người quản trò rút một thẻ đặc biệt từ hộp bốc thăm may mắn và ghi lại số nguyên \(b\) in trên thẻ đó.
4. Người quản trò tính độ chênh lệch tuyệt đối giữa \(a[i]\) và \(b\) với mỗi \(i\) từ \(0\) đến \(n-1\). Gọi \(S\) là tổng các độ chênh lệch tuyệt đối này.
5. Trong vòng này, người quản trò trao cho Ringo phần thưởng có giá trị bằng \(S\).
6. Các vé trong tập bị bỏ đi và không thể sử dụng trong các vòng sau.

Các vé còn lại trong túi Ringo sau \(k\) vòng chơi cũng bị bỏ đi.

Quan sát kỹ, Ringo nhận ra trò chơi đã bị gian lận! Thực ra có một máy in bên trong hộp bốc thăm may mắn. Trong mỗi vòng, người quản trò tìm một số nguyên \(b\) làm cho giá trị phần thưởng của vòng đó nhỏ nhất. Giá trị được chọn được in lên thẻ đặc biệt của vòng đó.

Biết tất cả những thông tin này, Ringo muốn phân bổ vé cho các vòng chơi. Cụ thể, cậu muốn chọn tập vé sử dụng trong mỗi vòng để tổng giá trị các phần thưởng là lớn nhất.

Chi tiết cài đặt

Bạn cần cài đặt hàm C++ sau:

long long find_maximum(int k, std::vector<std::vector<int>> x);

• \(k\): số vòng chơi.
• \(x\): mảng kích thước \(n\times m\) mô tả số nguyên in trên từng vé. Các vé của mỗi màu được sắp xếp theo thứ tự không giảm của số nguyên in trên vé.
• Hàm này được gọi đúng một lần.
• Hàm phải gọi allocate_tickets (mô tả bên dưới) đúng một lần, mô tả \(k\) tập vé, mỗi tập cho một vòng. Cách phân bổ phải làm tổng giá trị các phần thưởng lớn nhất.
• Hàm phải trả về tổng giá trị phần thưởng lớn nhất.

Hàm allocate_tickets được định nghĩa như sau:

void allocate_tickets(std::vector<std::vector<int>> s);

• \(s\): mảng kích thước \(n\times m\). Giá trị \(s[i][j]\) phải bằng \(r\) nếu vé \(j\) của màu \(i\) được sử dụng trong tập vé của vòng \(r\), hoặc bằng \(-1\) nếu vé đó không được sử dụng.
• Với mỗi \(0 \le i \le n-1\), trong các phần tử \(s[i][0],s[i][1],\ldots,s[i][m-1]\), mỗi giá trị \(0,1,2,\ldots,k-1\) phải xuất hiện đúng một lần; tất cả các phần tử còn lại phải bằng \(-1\).
• Nếu có nhiều cách phân bổ đạt tổng giá trị phần thưởng lớn nhất, bạn có thể báo cáo bất kỳ cách nào.

Dữ liệu vào

Trình chấm mẫu đọc dữ liệu theo định dạng sau:

• Dòng \(1\): n m k.
• Dòng \(2+i\) (\(0 \le i \le n-1\)): x[i][0] x[i][1] ... x[i][m-1].

Dữ liệu ra

Trình chấm mẫu in câu trả lời theo định dạng sau:

• Dòng \(1\): giá trị trả về của find_maximum.
• Dòng \(2+i\) (\(0 \le i \le n-1\)): s[i][0] s[i][1] ... s[i][m-1].

Ràng buộc

• \(2 \le n \le 1500\), trong đó \(n\) là số chẵn.
• \(1 \le k \le m \le 1500\).
• \(0 \le x[i][j] \le 10^9\) (\(0 \le i \le n-1\), \(0 \le j \le m-1\)).
• \(x[i][j-1] \le x[i][j]\) (\(0 \le i \le n-1\), \(1 \le j \le m-1\)).

Phân nhóm

Ví dụ

find_maximum(2, [[0, 2, 5], [1, 1, 3]])

    - Ở vòng $1$, Ringo chọn vé $2$ của màu $0$ (in số $5$) và vé $1$ của màu $1$ (in số $1$). Giá trị phần thưởng nhỏ nhất có thể trong vòng này là $4$. Ví dụ, người quản trò có thể chọn $b=3$:

    - Vì vậy, tổng giá trị phần thưởng là:

    Để báo cáo cách phân bổ này, hàm `find_maximum` phải thực hiện lời gọi `allocate_tickets` sau:

    ```text
    allocate_tickets([[0, -1, 1], [-1, 1, 0]])
    ```

    Cuối cùng, hàm `find_maximum` phải trả về $7$.

find_maximum(1, [[5, 9], [1, 4], [3, 6], [2, 7]])

    Để báo cáo phương án này, hàm `find_maximum` phải thực hiện lời gọi `allocate_tickets` sau:

    ```text
    allocate_tickets([[-1, 0], [0, -1], [0, -1], [-1, 0]])
    ```

    Cuối cùng, hàm `find_maximum` phải trả về $12$.

Nguồn

IOI 2020, Ngày 1 — Carnival Tickets (tickets). Đề chính thức tiếng Anh và bản dịch tiếng Việt.