APIO 2024

Quảng trường trung tâm Hàng Châu là nơi có một cây cổ thụ nổi tiếng. Có thể xem cây này là một cây có gốc gồm \(N\) nút, được đánh số từ \(0\) đến \(N-1\), trong đó nút \(0\) là nút gốc.

Một nút không có nút con được gọi là nút lá. Mỗi lần rụng lá, cây chọn một nút đang là nút lá để xóa; trong cùng một ngày, cây có thể rụng lá nhiều lần.

Có \(M\) tình nguyện viên, được đánh số từ \(0\) đến \(M-1\), chịu trách nhiệm bảo vệ cây. Mỗi người độc lập ghi lại tình hình rụng lá trong năm nay như sau:

Mỗi ngày, họ thu thập chỉ số của tất cả những lá vừa rụng trong ngày đó (tức là chỉ số của các nút bị xóa trong ngày), rồi ghi các chỉ số này theo một thứ tự bất kỳ vào sau tất cả các chỉ số đã ghi trong những ngày trước.

Ví dụ, nếu trong ngày đầu tiên các lá \(3\) và \(4\) rụng, tình nguyện viên ghi 3, 4 hoặc 4, 3. Nếu trong ngày thứ hai các lá \(1\) và \(2\) rụng, người đó tiếp tục ghi 1, 2 hoặc 2, 1. Bản ghi cuối cùng có thể là một trong các dãy \((3,4,1,2)\), \((4,3,1,2)\), \((3,4,2,1)\) hoặc \((4,3,2,1)\).

Quá trình kéo dài trong \(K\) ngày, mỗi ngày đều có ít nhất một lá mới rụng, cho đến khi chỉ còn lại nút gốc.

Trong một chuyến du lịch, bạn tình cờ ghé thăm Hàng Châu vào mùa đông lạnh giá. Nhìn những cành cây trơ trụi, bạn hình dung khung cảnh lá rơi tuyệt đẹp và muốn biết trong năm nay mình có thể đã ngắm lá rơi nhiều nhất bao nhiêu ngày. Tuy nhiên, bạn chỉ tìm được bản ghi của \(M\) tình nguyện viên.

Hãy suy ra giá trị lớn nhất có thể của \(K\) phù hợp với tất cả các bản ghi.

Chi tiết cài đặt

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

int solve(int N, int M, std::vector<int> F,
          std::vector<std::vector<int>> S);

• \(N\): số nút của cây cổ thụ.
• \(M\): số tình nguyện viên.
• \(F\): mảng số nguyên có độ dài \(N\). Với \(1 \le i \le N-1\), \(F[i]\) là chỉ số nút cha của nút \(i\). Luôn có \(F[0]=-1\).
• \(S\): mảng gồm \(M\) mảng số nguyên, mỗi mảng có độ dài \(N-1\). \(S[i][j]\) là chỉ số thứ \(j\) trong bản ghi của tình nguyện viên \(i\); các chỉ số \(i,j\) đều bắt đầu từ \(0\).

Hàm phải trả về một số nguyên biểu diễn giá trị lớn nhất có thể của \(K\), tức số ngày rụng lá lớn nhất có thể theo các quy tắc trên.

Trong mỗi trường hợp kiểm thử, trình chấm có thể gọi hàm này nhiều lần. Mỗi lời gọi phải được xử lý như một kịch bản mới, hoàn toàn độc lập.

Ví dụ

solve(3, 1, {-1, 0, 0}, {{1, 2}})

solve(5, 2, {-1, 0, 0, 1, 1},
      {{1, 2, 3, 4}, {4, 1, 2, 3}})

Ràng buộc

• \(2 \le N \le 10^5\).
• \(1 \le M \le 5\).
• Tổng \(NM\) qua tất cả các lời gọi không vượt quá \(8 \times 10^5\).
• \(F[0]=-1\).
• Với \(1 \le i \le N-1\), \(0 \le F[i] \le i-1\).
• Với \(1 \le i \le M-1\), mảng \(S[i]\) là một hoán vị của \(1,2,\ldots,N-1\).
• Dữ liệu bảo đảm \(F\) mô tả một cây có gốc với nút \(0\) là nút gốc.

Phân nhóm

1. 11 điểm: \(M=1\), \(N \le 10\), tổng \(N \le 30\).
2. 14 điểm: \(N \le 10\), tổng \(N \le 30\).
3. 5 điểm: \(M=1\), \(N \le 1\,000\), tổng \(N \le 2\,000\), \(F[i]=i-1\).
4. 9 điểm: \(M=1\), \(N \le 1\,000\), tổng \(N \le 2\,000\).
5. 5 điểm: \(N \le 1\,000\), tổng \(N \le 2\,000\), \(F[i]=i-1\).
6. 11 điểm: \(N \le 1\,000\), tổng \(N \le 2\,000\).
7. 9 điểm: \(M=1\), \(F[i]=i-1\).
8. 11 điểm: \(M=1\).
9. 9 điểm: \(F[i]=i-1\).
10. 16 điểm: Không có ràng buộc bổ sung.

Trình chấm mẫu

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

• Dòng \(1\): \(T\).
• Với mỗi trường hợp kiểm thử trong \(T\) trường hợp tiếp theo:
  • Dòng \(1\): \(N\ M\).
  • Dòng \(2\): \(F[1]\ F[2]\ \ldots\ F[N-1]\).
  • Dòng \(3+i\) với \(0 \le i \le M-1\): \(S[i][0]\ S[i][1]\ \ldots\ S[i][N-2]\).

Với mỗi trường hợp kiểm thử, trình chấm mẫu in trên một dòng giá trị do hàm solve trả về.

Nguồn

Olympic Tin học Châu Á - Thái Bình Dương 2024 (APIO 2024), bài September. Đề và gói bài chính thức: APIO 2024 Tasks.

Vào năm 2992, phần lớn công việc đã do robot đảm nhận. Vì thế, nhiều người có rất nhiều thời gian rảnh, và gia đình bạn cũng vậy: họ vừa quyết định thực hiện một chuyến du hành giữa các hành tinh!

Có \(N\) hành tinh có thể đến, được đánh số từ \(0\) đến \(N-1\), cùng \(M\) tuyến tàu liên hành tinh. Tuyến tàu \(i\) (\(0 \le i < M\)) khởi hành từ hành tinh \(X[i]\) vào thời điểm \(A[i]\), đến hành tinh \(Y[i]\) vào thời điểm \(B[i]\) và có giá vé \(C[i]\).

Tàu là phương tiện duy nhất để di chuyển giữa các hành tinh. Vì vậy, bạn chỉ có thể xuống tàu tại hành tinh đích, và chuyến tàu tiếp theo phải khởi hành từ chính hành tinh đó; việc chuyển tuyến không tốn thời gian.

Một dãy tuyến tàu \(q[0],q[1],\ldots,q[P]\) là hợp lệ khi và chỉ khi, với mọi \(1 \le k \le P\):

và

Du hành giữa các hành tinh mất nhiều thời gian, và ngoài tiền vé tàu, chi phí ăn uống cũng rất đáng kể. May thay, các chuyến tàu liên hành tinh cung cấp thức ăn miễn phí không giới hạn. Cụ thể, nếu bạn đi tuyến tàu \(i\), tại bất kỳ thời điểm nào từ \(A[i]\) đến \(B[i]\), kể cả hai đầu mút, bạn có thể dùng miễn phí bao nhiêu bữa ăn tùy ý. Tuy nhiên, khi gia đình bạn ở trên một hành tinh \(i\) để chờ chuyến tàu tiếp theo, mỗi bữa ăn có giá \(T[i]\).

Gia đình bạn cần dùng \(W\) bữa ăn. Bữa ăn thứ \(i\) (\(0 \le i < W\)) có thể được dùng tức thời tại bất kỳ thời điểm nào trong đoạn từ \(L[i]\) đến \(R[i]\), kể cả hai đầu mút.

Tại thời điểm \(0\), gia đình bạn đang ở hành tinh \(0\). Hãy tính tổng chi phí nhỏ nhất để đến hành tinh \(N-1\). Nếu không thể đến đó, câu trả lời là \(-1\).

Chi tiết cài đặt

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

long long solve(int N, int M, int W, std::vector<int> T,
                std::vector<int> X, std::vector<int> Y,
                std::vector<int> A, std::vector<int> B, std::vector<int> C,
                std::vector<int> L, std::vector<int> R);

• \(N\): số hành tinh.
• \(M\): số tuyến tàu liên hành tinh.
• \(W\): số bữa ăn.
• \(T\): mảng có độ dài \(N\); \(T[i]\) là giá của mỗi bữa ăn trên hành tinh \(i\).
• \(X,Y,A,B,C\): năm mảng có độ dài \(M\); bộ \((X[i],Y[i],A[i],B[i],C[i])\) mô tả tuyến tàu thứ \(i\).
• \(L,R\): hai mảng có độ dài \(W\); cặp \((L[i],R[i])\) mô tả đoạn thời gian có thể dùng bữa ăn thứ \(i\).

Hàm phải trả về chi phí nhỏ nhất để đi từ hành tinh \(0\) đến hành tinh \(N-1\) nếu có thể đến được, và trả về \(-1\) nếu không thể.

Với mỗi trường hợp kiểm thử, hàm này được gọi đúng một lần.

Ví dụ

solve(3, 3, 1, {20, 30, 40}, {0, 1, 0}, {1, 2, 2},
      {1, 20, 18}, {15, 30, 40}, {10, 5, 40}, {16}, {19})

solve(3, 5, 6, {30, 38, 33}, {0, 1, 0, 0, 1}, {2, 0, 1, 2, 2},
      {12, 48, 26, 6, 49}, {16, 50, 28, 7, 54},
      {38, 6, 23, 94, 50}, {32, 14, 42, 37, 2, 4},
      {36, 14, 45, 40, 5, 5})

Hàm trả về `197`.

Ràng buộc

• \(2 \le N \le 10^5\).
• \(0 \le M,W \le 10^5\).
• \(0 \le X[i],Y[i] < N\) và \(X[i] \ne Y[i]\).
• \(1 \le A[i] < B[i] \le 10^9\).
• \(1 \le T[i],C[i] \le 10^9\).
• \(1 \le L[i] \le R[i] \le 10^9\).

Phân nhóm

1. 5 điểm: \(N,M,A[i],B[i],L[i],R[i] \le 10^3\) và \(W \le 10\).
2. 5 điểm: \(W=0\).
3. 30 điểm: Không có hai bữa ăn nào giao nhau về thời gian. Nói cách khác, với mọi thời điểm \(z\) thỏa mãn \(1 \le z \le 10^9\), có nhiều nhất một chỉ số \(i\) (\(0 \le i < W\)) sao cho:

1. 60 điểm: Không có ràng buộc bổ sung.

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\ M\ W\).
• Dòng \(2\): \(T[0]\ T[1]\ \ldots\ T[N-1]\).
• Dòng \(3+i\) với \(0 \le i < M\): \(X[i]\ Y[i]\ A[i]\ B[i]\ C[i]\).
• Dòng \(3+M+i\) với \(0 \le i < W\): \(L[i]\ R[i]\).

Trình chấm mẫu in trên dòng đầu tiên giá trị do hàm solve trả về.

Nguồn

Olympic Tin học Châu Á - Thái Bình Dương 2024 (APIO 2024), bài Train. Đề và gói bài chính thức: APIO 2024 Tasks.

Alice và Bob là những nhà ảo thuật nổi tiếng. Catherine, một người phụ nữ giàu có rất yêu thích các màn trình diễn tuyệt vời của họ, tuyên bố rằng cô sẽ tặng họ một khối tài sản lớn nếu họ thực hiện được trò ảo thuật sau:

1. Bob đi vào một căn phòng hoàn toàn cách biệt với bên ngoài. Bob chỉ có thể trao đổi với Catherine. Sau đó, Alice nói cho Catherine một số \(n\) trong khoảng từ \(2\) đến \(5\,000\).
2. Catherine nói cho Alice một số \(X\) trong khoảng từ \(1\) đến \(10^{18}\).
3. Alice tạo một cây có đúng \(n\) đỉnh và đưa cây đó cho Catherine.
4. Catherine xóa khỏi cây nhiều nhất

cạnh, rồi đưa các cạnh còn lại cho Bob.

1. Bob quan sát kỹ đồ thị nhận được và nói ra số mà Catherine đã nói cho Alice.

Alice và Bob không nghĩ mình đủ thông minh để luôn biểu diễn thành công trò ảo thuật này, nên họ cần bạn giúp đỡ. Hãy viết chương trình cài đặt chiến lược của Alice và chiến lược của Bob để họ vượt qua thử thách của Catherine.

Chi tiết cài đặt

Bạn cần nộp hai tệp chương trình riêng biệt, Alice.cpp và Bob.cpp. Hai chiến lược không thể truyền thông tin cho nhau bằng biến toàn cục hoặc trạng thái dùng chung.

Chương trình của Alice

Tệp Alice.cpp cài đặt chiến lược của Alice và phải khai báo thư viện Alice.h bằng chỉ thị tiền xử lý #include. Bạn cần cài đặt hàm:

std::vector<std::pair<int, int>> Alice();

• Trong mỗi trường hợp kiểm thử, hàm này được gọi đúng một lần ở thời điểm bắt đầu.
• Hàm phải trả về một vector các cặp biểu diễn các cạnh của cây mà Alice tạo ở bước \(3\).
• Các đỉnh của cây phải được đánh số bắt đầu từ \(1\).
• Cây trả về phải hợp lệ: có đúng \(n-1\) cạnh và tất cả các đỉnh đều liên thông.

Hàm Alice() phải gọi hàm sau đúng một lần:

long long setN(int n);

Alice dùng lời gọi này để chọn tham số \(n\) đã nói cho Catherine ở bước \(1\). Hàm setN trả về giá trị \(X\) mà Catherine nói cho Alice ở bước \(2\).

Chương trình của Bob

Tệp Bob.cpp cài đặt chiến lược của Bob và phải khai báo thư viện Bob.h bằng chỉ thị tiền xử lý #include. Bạn cần cài đặt hàm:

long long Bob(std::vector<std::pair<int, int>> V);

• Trong mỗi trường hợp kiểm thử, hàm này được gọi đúng một lần sau lời gọi hàm Alice().
• Tham số \(V\) là danh sách các cạnh của đồ thị mà Catherine đưa cho Bob ở bước \(4\).
• Các cạnh trong \(V\) được sắp xếp như sau:
  • Trong mỗi cạnh, đầu mút có số nhỏ hơn đứng trước.
  • Toàn bộ các cạnh được sắp xếp tăng dần theo đầu mút thứ nhất làm khóa chính, rồi theo đầu mút thứ hai làm khóa phụ.
• Hàm phải trả về một số nguyên biểu diễn giá trị \(X\).

Tương tác mẫu

Trình tự lời gọi và giá trị trả về trong ví dụ là:

Ví dụ này biểu diễn kịch bản sau:

1. Alice nói số \(4\) cho Catherine.
2. Catherine nói số \(3\) cho Alice.
3. Alice tạo một cây gồm \(4\) đỉnh và các cạnh {{1, 2}, {2, 3}, {2, 4}}, rồi đưa cây cho Catherine.
4. Catherine xóa cạnh nối đỉnh \(2\) với đỉnh \(3\), rồi đưa các cạnh còn lại {{1, 2}, {2, 4}} cho Bob.
5. Bob nói số \(3\). Vì câu trả lời đúng, Alice và Bob thực hiện thành công trò ảo thuật.

Ràng buộc

Phân nhóm

1. 5 điểm: \(X \le 5\,000\).
2. 30 điểm: \(X \le 25\,000\,000\).
3. 65 điểm: Không có ràng buộc bổ sung.

Trình chấm mẫu

Trình chấm mẫu đọc ở dòng đầu tiên một giá trị \(T\), trong đó \(T \in \{1,2\}\).

Nếu \(T=1\):

• Dòng \(2\) chứa \(X\) (\(1 \le X \le 10^{18}\)).
• Trình chấm mẫu gọi Alice() rồi in kết quả theo định dạng:
  • Dòng \(1\): \(n\).
  • Dòng \(2+i\) với \(0 \le i \le n-2\): \(u[i]\ v[i]\), biểu diễn một cạnh nối \(u[i]\) và \(v[i]\).

Nếu \(T=2\):

• Dòng \(2\) chứa \(n\ m\), trong đó \(2 \le n \le 5\,000\) và

với $n$ là số đỉnh và $m$ là số cạnh còn lại.

• Dòng \(3+i\) với \(0 \le i \le m-1\) chứa \(u[i]\ v[i]\), biểu diễn một cạnh nối \(u[i]\) và \(v[i]\).
• Trình chấm mẫu gọi Bob() rồi in \(X\) trên dòng đầu tiên.

Nguồn

Olympic Tin học Châu Á - Thái Bình Dương 2024 (APIO 2024), bài Magic Show. Đề và gói bài chính thức: APIO 2024 Tasks.