IOI 2022 - Ngày 1

Bu Dengklek sở hữu một trang trại nuôi cá da trơn.
Trang trại cá da trơn là một ao bao gồm một lưới \(N \times N\) ô vuông.
Mỗi ô là một hình vuông cùng kích thước.
Các cột của lưới được đánh số từ \(0\) đến \(N - 1\) từ tây sang đông và các hàng được đánh số từ \(0\) đến \(N - 1\) từ nam sang bắc.
Gọi ô nằm ở cột \(c\) và hàng \(r\) của lưới (\(0 \le c \le N - 1\), \(0 \le r \le N - 1\)) là ô \((c, r)\).

Trong ao có \(M\) con cá da trơn, được đánh số từ \(0\) đến \(M - 1\), nằm ở các ô riêng biệt.
Với mỗi \(i\) mà \(0 \le i \le M - 1\), con cá \(i\) nằm ở ô \((X[i], Y[i])\) và nặng \(W[i]\) gam.

Bu Dengklek muốn xây một số cầu để bắt cá da trơn.
Một cầu trong cột \(c\) có chiều dài \(k\) (với mọi \(0 \le c \le N - 1\) và \(1 \le k \le N\)) là một hình chữ nhật kéo dài từ hàng \(0\) đến hàng \(k - 1\), bao gồm các ô \((c, 0), (c, 1), \ldots, (c, k - 1)\).
Đối với mỗi cột, Bu Dengklek có thể chọn xây cầu có độ dài theo ý mình hoặc không xây cầu.

Con cá \(i\) (với mỗi \(i\) sao cho \(0 \le i \le M - 1\)) có thể đánh bắt được nếu có cầu ngay sát phía tây hoặc phía đông ô của nó và không có cầu che ô của nó; nghĩa là, nếu

• ít nhất một trong số các ô \((X[i] - 1, Y[i])\) hoặc \((X[i] + 1, Y[i])\) được che bởi một cầu, và
• không có cầu che ô \((X[i], Y[i])\).

Ví dụ, xét một ao có kích thước \(N = 5\) với \(M = 4\) con cá da trơn:

• Con cá \(0\) nằm ở ô \((0, 2)\) và nặng \(5\) gam.
• Con cá \(1\) nằm ở ô \((1, 1)\) và nặng \(2\) gam.
• Con cá \(2\) nằm ở ô \((4, 4)\) và nặng \(1\) gam.
• Con cá \(3\) nằm ở ô \((3, 3)\) và nặng \(3\) gam.

Sau đây là một cách Bu Dengklek có thể xây dựng các cầu:

Trước khi các cầu được xây dựng	Sau khi các cầu được xây dựng

Con số trong một ô chỉ trọng lượng của con cá da trơn ở ô đó.
Các ô tô đậm là các ô được che bởi các cầu.
Trong trường hợp này, có thể đánh bắt được con cá da trơn \(0\) (tại ô \((0, 2)\)) và con cá da trơn \(3\) (tại ô \((3, 3)\)).
Không thể đánh bắt được con cá da trơn \(1\) (tại ô \((1, 1)\)) vì có một cầu che vị trí của nó, trong khi không thể đánh bắt được con cá da trơn \(2\) (tại ô \((4, 4)\)) vì không có cầu ngay sát phía tây và phía đông ô của nó.

Bu Dengklek muốn xây các cầu sao cho tổng trọng lượng các cá da trơn mà cô có thể bắt được càng lớn càng tốt.
Nhiệm vụ của bạn là tìm tổng trọng lượng lớn nhất các cá da trơn mà Bu Dengklek có thể bắt được sau khi xây các cầu.

Chi tiết cài đặt

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

long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
                      std::vector<int> W);

• \(N\): kích thước của ao.
• \(M\): số lượng cá da trơn.
• \(X\), \(Y\): các mảng \(M\) phần tử mô tả các vị trí cá da trơn.
• \(W\): mảng \(M\) phần tử chứa trọng lượng các cá da trơn.
• Hàm này cần trả về một số nguyên biểu diễn tổng trọng lượng lớn nhất các cá da trơn mà Bu Dengklek có thể bắt được sau khi xây các cầu.
• Hàm này được gọi đúng một lần.

Ví dụ

Xét lời gọi hàm sau:

max_weights(5, 4, [0, 1, 4, 3], [2, 1, 4, 3], [5, 2, 1, 3])

Ví dụ này được minh hoạ trong phần mô tả bài toán ở trên.

Sau khi xây dựng các cầu như mô tả, Bu Dengklek có thể đánh bắt được con cá \(0\) và \(3\), có tổng trọng lượng là \(5 + 3 = 8\) gam.
Vì không có cách nào xây các cầu để bắt các cá da trơn với tổng trọng lượng lớn hơn \(8\) gam, hàm cần trả về \(8\).

Ràng buộc

• \(2 \le N \le 100\;000\)
• \(1 \le M \le 300\;000\)
• \(0 \le X[i] \le N - 1\), \(0 \le Y[i] \le N - 1\) (với mỗi \(i\) sao cho \(0 \le i \le M - 1\))
• \(1 \le W[i] \le 10^9\) (với mỗi \(i\) sao cho \(0 \le i \le M - 1\))
• Không có hai con cá da trơn nào ở chung một ô.
  Nói cách khác, \(X[i] \neq X[j]\) hoặc \(Y[i] \neq Y[j]\) (với mỗi \(i\) và \(j\) sao cho \(0 \le i < j \le M - 1\)).

Phân nhóm

1. (3 điểm) \(X[i]\) là chẵn (với mỗi \(i\) sao cho \(0 \le i \le M - 1\))
2. (6 điểm) \(X[i] \le 1\) (với mỗi \(i\) sao cho \(0 \le i \le M - 1\))
3. (9 điểm) \(Y[i] = 0\) (với mỗi \(i\) sao cho \(0 \le i \le M - 1\))
4. (14 điểm) \(N \le 300\), \(Y[i] \le 8\) (với mỗi \(i\) sao cho \(0 \le i \le M - 1\))
5. (21 điểm) \(N \le 300\)
6. (17 điểm) \(N \le 3000\)
7. (14 điểm) Có tối đa \(2\) con cá da trơn mỗi cột.
8. (16 điểm) Không có ràng buộc gì thêm.

Trình chấm mẫu

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

• dòng \(1\): \(N \; M\)
• dòng \(2 + i\) (\(0 \le i \le M - 1\)): \(X[i] \; Y[i] \; W[i]\)

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

• dòng \(1\): giá trị trả về của max_weights

Nguồn: Đề thi tiếng Việt IOI 2022, giấy phép CC-BY.

Trong một nhà tù có \(500\) tù nhân.
Một ngày kia, quản ngục cho họ một cơ hội để tự giải thoát.
Quản ngục để hai túi tiền, túi A và túi B, trong một căn phòng.
Mỗi túi chứa một số lượng xu nằm trong khoảng từ \(1\) đến \(N\), bao gồm cả hai đầu mút.
Số lượng xu trong túi A khác số lượng xu trong túi B.
Quản ngục đưa ra một thử thách cho các tù nhân.
Mục tiêu của các tù nhân là xác định túi nào chứa ít xu hơn.

Trong căn phòng, cùng với hai túi tiền, còn có một bảng trắng.
Lúc nào trên bảng cũng có ghi một số nguyên.
Ban đầu, trên bảng ghi số \(0\).

Sau đó, quản ngục gọi lần lượt từng tù nhân vào trong phòng.
Mỗi tù nhân khi vào phòng không biết ai hay bao nhiêu tù nhân khác đã vào phòng trước mình.
Mỗi lần một tù nhân vào phòng, anh ta đọc số đang có trên bảng.
Sau khi đọc xong, anh ta phải chọn một trong hai túi A hoặc B.
Sau đó, tù nhân kiểm tra túi được chọn và biết được số lượng xu nằm trong túi đó.
Tiếp theo, tù nhân phải thực hiện một trong hai hành động sau:

• Thay số được ghi trên bảng với một số nguyên không âm và rời khỏi căn phòng.
  Lưu ý rằng họ có thể thay đổi hoặc giữ nguyên số hiện tại. Sau đó, thử thách tiếp tục (trừ khi tất cả \(500\) tù nhân đều đã vào căn phòng).
• Xác định được túi nào là túi có ít xu hơn. Hành động này sẽ kết thúc thử thách.

Quản ngục sẽ không bao giờ yêu cầu một tù nhân đã rời khỏi phòng vào lại phòng lần thứ hai.

Các tù nhân sẽ giành chiến thắng thử thách này nếu một trong số họ xác định chính xác túi nào có ít xu hơn.
Họ sẽ thua nếu bất kì ai trong số họ xác định sai, hoặc tất cả \(500\) tù nhân đều đã vào phòng và không xác định được túi có ít xu hơn.

Trước khi thử thách bắt đầu, các tù nhân tập trung trong sảnh chính của nhà tù và cùng quyết định một chiến thuật chung cho thử thách này với ba bước.

• Họ chọn một số nguyên không âm \(x\), là số lớn nhất mà họ có thể viết lên bảng.
• Họ quyết định, với mỗi số \(i\) được viết lên bảng (\(0 \le i \le x\)), cái túi nào cần được kiểm tra nếu đọc được số \(i\) khi mới vào phòng.
• Họ quyết định, hành động nào tù nhân trong phòng sẽ thực hiện sau khi biết được số lượng xu trong túi được chọn. Cụ thể, với mỗi số \(i\) được viết trên bảng (\(0 \le i \le x\)) và với mỗi số \(j\) là số lượng xu trong túi được kiểm tra (\(1 \le j \le N\)), họ sẽ quyết định
  • một số nguyên trong khoảng \(0\) và \(x\) (bao gồm cả hai đầu mút) cần phải được viết lên bảng, hoặc
  • cái túi nào là túi chứa ít xu hơn.

Nếu như giành chiến thắng thử thách này, quản ngục sẽ thả các tù nhân sau khi họ chịu án thêm \(x\) ngày nữa.

Bạn hãy tạo ra một chiến thuật cho các tù nhân để đảm bảo rằng họ sẽ giành chiến thắng thử thách này (bất kể số lượng xu trong túi A và túi B là bao nhiêu).
Điểm của bạn sẽ phụ thuộc vào giá trị \(x\) (xem chi tiết ở phần Subtask).

Chi tiết cài đặt

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

std::vector<std::vector<int>> devise_strategy(int N);

• \(N\): là số lượng xu tối đa trong mỗi túi.
• Hàm này cần trả về một mảng \(s\) mà mỗi phần tử là một mảng chứa \(N + 1\) số nguyên, thể hiện chiến thuật của bạn.
  Giá trị của \(x\) là độ dài của mảng \(s\) trừ một.
  Với mỗi số \(i\) mà \(0 \le i \le x\), mảng \(s[i]\) thể hiện tù nhân sẽ làm gì nếu họ đọc được số \(i\) ở trên bảng khi mới vào phòng:
  1. Giá trị \(s[i][0]\) bằng \(0\) nếu tù nhân phải kiểm tra túi A, hoặc bằng \(1\) nếu tù nhân phải kiểm tra túi B.
  2. Gọi \(j\) là số lượng xu trong túi được kiểm tra. Tù nhân cần thực hiện hành động:
     • Nếu giá trị của \(s[i][j]\) bằng \(-1\), tù nhân sẽ xác định túi A là túi có ít xu hơn.
     • Nếu giá trị của \(s[i][j]\) bằng \(-2\), tù nhân sẽ xác định túi B là túi có ít xu hơn.
     • Nếu giá trị của \(s[i][j]\) là một số không âm, tù nhân sẽ viết số đó lên bảng. Lưu ý rằng \(s[i][j]\) không được vượt quá \(x\).
• Hàm này sẽ được gọi đúng một lần.

Ví dụ

Xét lời gọi hàm sau:

devise_strategy(3)

Gọi \(v\) là số mà tù nhân đọc được trên bảng khi vào phòng.
Một trong các chiến thuật đúng như sau:

• Nếu \(v = 0\) (bao gồm cả số ban đầu), kiểm tra túi A.
  • Nếu túi A chứa \(1\) xu, xác định túi A là túi có ít xu hơn.
  • Nếu túi A chứa \(3\) xu, xác định túi B là túi có ít xu hơn.
  • Nếu túi A chứa \(2\) xu, viết số \(1\) lên bảng (xoá số \(0\)).
• Nếu \(v = 1\), kiểm tra túi B.
  • Nếu túi B chứa \(1\) xu, xác định túi B là túi có ít xu hơn.
  • Nếu túi B chứa \(3\) xu, xác định túi A là túi có ít xu hơn.
  • Nếu túi B chứa \(2\) xu, viết số \(0\) lên bảng (xoá só \(1\)). Lưu ý rằng trường hợp này sẽ không bao giờ xảy ra vì chúng ta có thể khẳng định cả hai túi đều chứa \(2\) xu, đây là điều không được phép.

Chiến thuật này có thể được xác định bằng cách trả về [[0, -1, 1, -2], [1, -2, 0, -1]].
Độ dài của mảng đươc trả về là \(2\), vì vậy với giá trị trả về này thì giá trị của \(x\) là \(2 - 1 = 1\).

Ràng buộc

• \(2 \le N \le 5000\)

Phân nhóm

1. (5 điểm) \(N \le 500\), giá trị của \(x\) không được vượt quá \(500\).
2. (5 điểm) \(N \le 500\), giá trị của \(x\) không được vượt quá \(70\).
3. (90 điểm) Giá trị của \(x\) không được vượt quá \(60\).

Nếu trong bất cứ test case nào, mảng trả về bởi hàm devise_strategy không thể hiện một chiến thuật đúng, điểm cho lời giải của bạn với subtask đó sẽ là \(0\).

Trong subtask 3, bạn có thể có điểm lẻ.
Gọi \(m\) là giá trị lớn nhất của \(x\) đối với tất cả các test case trong subtask này.
Điểm của bạn cho subtask này sẽ được tính dựa trên bảng sau:

Trình chấm mẫu

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

• dòng \(1\): \(N\)
• dòng \(2 + k\) (\(0 \le k\)): \(A[k] \; B[k]\)
• dòng cuối cùng: \(-1\)

Mỗi dòng trừ dòng đầu và dòng cuối thể hiện một kịch bản.
Kịch bản được ghi trên dòng thứ \(2 + k\) là kịch bản thứ \(k\).
Trong kịch bản \(k\), túi A chứa \(A[k]\) xu và túi B chứa \(B[k]\) xu.

Trình chấm mẫu sẽ gọi hàm devise_strategy(N).
Giá trị của \(x\) là độ dài của mảng trả về trừ đi một.
Sau đó, nếu trình chấm mẫu xác định rằng mảng trả về bởi hàm devise_strategy không tuân theo các ràng buộc được mô tả trong phần Chi tiết cài đặt, trình chấm mẫu sẽ in ra một trong các lỗi sau và kết thúc:

• s is an empty array: \(s\) là một mảng rỗng (không phải là một chiến thuật đúng đắn).
• s[i] contains incorrect length: Tồn tại một chỉ số \(i\) (\(0 \le i \le x\)) mà độ dài của mảng \(s[i]\) không phải là \(N + 1\).
• First element of s[i] is non-binary: Tồn tại một chỉ số \(i\) (\(0 \le i \le x\)) mà \(s[i][0]\) không phải là \(0\) hay \(1\).
• s[i][j] contains incorrect value: Tồn tại cặp chỉ số \(i, j\) (\(0 \le i \le x, 1 \le j \le N\)) mà \(s[i][j]\) có giá trị không nằm trong khoảng \(-2\) và \(x\).

Ngược lại, trình chấm mẫu đưa ra hai luồng kết quả đầu ra.

Luồng thứ nhất, trình chấm mẫu in ra kết quả của chiến thuật của bạn theo định dạng như sau:

• dòng \(1 + k\) (\(0 \le k\)): kết quả của chiến thuật của bạn với kịch bản \(k\).
  Nếu thực hiện chiến thuật của bạn dẫn đến việc có một tù nhân xác định túi A chứa ít xu hơn, kết quả sẽ là kí tự A.
  Nếu thực hiện chiến thuật của bạn dẫn đến việc có một tù nhân xác định túi B chứa ít xu hơn, kết quả sẽ là kí tự B.
  Nếu thực hiện chiến thuật của bạn dẫn tới không có tù nhân nào xác định túi chứa ít xu hơn, kết quả sẽ là kí tự X.

Luồng thứ hai, trình chấm mẫu viết ra một file log.txt trong thư mục hiện tại với định dạng như sau:

• dòng \(1 + k\) (\(0 \le k\)): \(w[k][0] \; w[k][1] \; \ldots\)

Dãy số trên dòng thứ \(1 + k\) tương ứng với kịch bản \(k\) mô tả các số được viết trên bảng.
Cụ thể, \(w[k][l]\) là số được viết bởi tù nhân thứ \(l + 1\).

Nguồn: Đề thi tiếng Việt IOI 2022, giấy phép CC-BY.

Có \(N\) tháp phát thanh ở Jakarta. Các tháp nằm dọc theo một đường thẳng và được đánh số từ \(0\) đến \(N - 1\) từ trái sang phải. Với mỗi \(i\) sao cho \(0 \le i \le N - 1\), chiều cao của tháp \(i\) là \(H[i]\) mét. Chiều cao của các tháp là phân biệt.

Đối với một giá trị nhiễu \(\delta\) dương nào đó, một cặp tháp \(i\) và \(j\) (trong đó \(0 \le i < j \le N - 1\)) có thể giao tiếp với nhau khi và chỉ khi có một tháp trung gian \(k\), sao cho

• tháp \(i\) ở bên trái tháp \(k\) và tháp \(j\) ở bên phải tháp \(k\), tức là \(i < k < j\), và
• chiều cao của tháp \(i\) và tháp \(j\) đều cao không quá là \(H[k] - \delta\) mét.

Pak Dengklek muốn thuê một số tháp cho mạng phát thanh mới của mình.
Nhiệm vụ của bạn là trả lời \(Q\) câu hỏi của Pak Dengklek có dạng như sau:
cho trước các tham số \(L, R\) và \(D\) (\(0 \le L \le R \le N - 1\) và \(D > 0\)), số lượng tháp tối đa mà Pak Dengklek có thể thuê là bao nhiêu, giả sử rằng

• Pak Dengklek chỉ có thể thuê các tháp có chỉ số từ \(L\) đến \(R\) (bao gồm cả hai đầu mút), và
• giá trị nhiễu \(\delta\) là \(D\), và
• bất kỳ cặp tháp phát thanh nào mà Pak Dengklek thuê phải có khả năng giao tiếp với nhau.

Lưu ý rằng hai tháp đã thuê có thể giao tiếp bằng cách sử dụng tháp trung gian \(k\), bất kể tháp \(k\) có được thuê hay không.

Chi tiết cài đặt

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

void init(int N, std::vector<int> H);

• \(N\): số lượng tháp phát thanh.
• \(H\): một mảng có độ dài \(N\) mô tả chiều cao của các tháp.
• Hàm này được gọi đúng một lần, trước bất kỳ lệnh gọi nào đến max_towers.

int max_towers(int L, int R, int D);

• \(L\), \(R\): ranh giới của các tháp.
• \(D\): giá trị của \(\delta\).
• Hàm này sẽ trả lại số lượng lớn nhất các tháp phát thanh mà Pak Dengklek có thể thuê cho mạng phát thanh mới của mình nếu anh ta chỉ được phép thuê các tháp giữa tháp \(L\) và tháp \(R\) (bao gồm cả hai đầu mút) và giá trị của \(\delta\) là \(D\).
• Hàm này được gọi đúng là \(Q\) lần.

Ví dụ

Hãy xem xét dãy các lời gọi sau:

init(7, [10, 20, 60, 40, 50, 30, 70])

max_towers(1, 5, 10)

Pak Dengklek có thể thuê tháp \(1\), \(3\) và \(5\).
Ví dụ được minh họa trong hình sau, trong đó các hình thang được tô đậm thể hiện cho các tháp được thuê.

Tháp \(3\) và \(5\) có thể giao tiếp bằng cách sử dụng tháp \(4\) làm trung gian, vì \(40 \le 50 - 10\) và \(30 \le 50 - 10\). Các tháp \(1\) và \(3\) có thể giao tiếp bằng cách sử dụng tháp \(2\) làm trung gian. Tháp \(1\) và \(5\) có thể giao tiếp bằng cách sử dụng tháp \(3\) làm trung gian.
Không có cách nào để thuê được nhiều hơn \(3\) tháp, do đó hàm phải trả lại \(3\).

max_towers(2, 2, 100)

Có duy nhất tháp \(1\) trong phạm vi, do đó Pak Dengklek chỉ có thể thuê tháp \(1\).
Vì vậy, thủ tục sẽ trả về \(1\).

max_towers(0, 6, 17)

Pak Dengklek có thể thuê tháp \(1\) và \(3\).
Các tháp \(1\) và \(3\) có thể giao tiếp bằng cách sử dụng tháp \(2\) làm trung gian, vì \(20 \le 60 - 17\) and \(40 \le 60 - 17\). Không có cách nào để thuê nhiều hơn \(2\) tháp, do đó hàm phải trả lại \(2\).

Ràng buộc

• \(1 \le N \le 100\;000\)
• \(1 \le Q \le 100\;000\)
• \(1 \le H[i] \le 10^9\) (với mỗi \(i\) sao cho \(0 \le i \le N - 1\))
• \(H[i] \ne H[j]\) (với mỗi \(i\) và \(j\) sao cho \(0 \le i < j \le N - 1\))
• \(0 \le L \le R \le N - 1\)
• \(1 \le D \le 10^9\)

Phân nhóm

1. (4 điểm) Tồn tại một tháp \(k\) (\(0 \le k \le N - 1\)) sao cho
   • với mỗi \(i\) sao cho \(0\le i\le k-1\): \(H[i] < H[i + 1]\), và
   • với mỗi \(i\) sao cho \(k \le i \le N - 2\): \(H[i] > H[i + 1]\).
2. (11 điểm) \(Q = 1\), \(N \le 2000\)
3. (12 điểm) \(Q = 1\)
4. (14 điểm) \(D = 1\)
5. (17 điểm) \(L = 0\), \(R = N - 1\)
6. (19 điểm) Giá trị của \(D\) giống nhau trong tất cả các lần gọi hàm max_towers.
7. (23 điểm) Không có ràng buộc nào thêm.

Trình chấm mẫu

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

• dòng \(1\): \(N \; Q\)
• dòng \(2\): \(H[0] \; H[1] \; \ldots \; H[N - 1]\)
• dòng \(3 + j\) (\(0 \le j \le Q - 1\)): \(L \; R \; D\) với câu hỏi \(j\)

Trình chấm mẫu in các kết quả của bạn theo định dạng:

• dòng \(1 + j\) (\(0 \le j \le Q - 1\)): giá trị trả về của max_towers cho câu hỏi \(j\)

Nguồn: Đề thi tiếng Việt IOI 2022, giấy phép CC-BY.