APIO 2023

Năm 3742 đã đến, và bây giờ đến lượt Cyberland đăng cai APIO. Trong thế giới này có \(N\) quốc gia, được đánh số từ \(0\) đến \(N-1\), cùng với \(M\) con đường hai chiều, được đánh số từ \(0\) đến \(M-1\). Con đường thứ \(i\) (\(0\le i<M\)) nối hai quốc gia khác nhau \(x[i]\) và \(y[i]\), và cần \(c[i]\) đơn vị thời gian để đi hết con đường.

Tất cả thí sinh dự APIO đã đến Cyberland, ngoại trừ người đến từ quốc gia của bạn. Bạn sống ở quốc gia \(0\), còn Cyberland là quốc gia \(H\). Là người thông minh nhất đất nước, bạn được giao nhiệm vụ xác định thời gian nhỏ nhất để đi từ quốc gia của mình đến Cyberland.

Một số quốc gia có khả năng đặc biệt đưa tổng thời gian bạn đã đi về \(0\). Một số quốc gia khác có khả năng đặc biệt chia đôi tổng thời gian bạn đã đi (divide-by-2). Bạn có thể ghé thăm một quốc gia nhiều lần. Mỗi lần đến một quốc gia, bạn có thể chọn có sử dụng khả năng đặc biệt tại đó hay không, nhưng chỉ được sử dụng khả năng ấy nhiều nhất một lần trong lần ghé thăm đó. Vì vậy, nếu ghé thăm một quốc gia nhiều lần, bạn có thể dùng khả năng của quốc gia ấy nhiều lần.

Để tránh bị Tổ chức Hóa học Cyberland bắt, trong toàn bộ hành trình bạn chỉ được dùng khả năng divide-by-2 nhiều nhất \(K\) lần. Ngay khi đến Cyberland, bạn không được tiếp tục di chuyển vì kỳ thi APIO sắp bắt đầu.

Cho mảng arr có độ dài \(N\), trong đó \(arr[i]\) (\(0\le i<N\)) mô tả khả năng đặc biệt của quốc gia \(i\):

• \(arr[i]=0\): đưa tổng thời gian đã đi về \(0\);
• \(arr[i]=1\): giữ nguyên tổng thời gian đã đi;
• \(arr[i]=2\): chia đôi tổng thời gian đã đi.

Luôn có \(arr[0]=arr[H]=1\); nói cách khác, quốc gia của bạn và Cyberland không có khả năng đặc biệt.

Hãy tìm thời gian nhỏ nhất để đến Cyberland. Nếu không thể đến Cyberland, kết quả phải là \(-1\).

Yêu cầu cài đặt

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

double solve(int N, int M, int K, int H,
             std::vector<int> x, std::vector<int> y,
             std::vector<int> c, std::vector<int> arr);

• N: số quốc gia.
• M: số con đường hai chiều.
• K: số lần tối đa được sử dụng khả năng divide-by-2.
• H: chỉ số của quốc gia Cyberland.
• x, y, c: ba mảng độ dài \(M\); bộ ba \((x[i],y[i],c[i])\) biểu diễn con đường vô hướng thứ \(i\), nối \(x[i]\) với \(y[i]\) và có thời gian di chuyển \(c[i]\).
• arr: mảng độ dài \(N\); arr[i] mô tả khả năng đặc biệt của quốc gia \(i\).
• Hàm phải trả về thời gian nhỏ nhất để đi từ quốc gia \(0\) đến Cyberland nếu có thể đến đó, và trả về \(-1\) nếu không thể.
• Hàm có thể được gọi nhiều hơn một lần.

Giả sử giá trị do thí sinh trả về là \(ans_1\) và đáp án chính xác là \(ans_2\). Kết quả được coi là đúng khi và chỉ khi

Do hàm có thể được gọi nhiều lần, bạn phải bảo đảm dữ liệu còn lại từ một lần gọi trước không ảnh hưởng đến lần gọi hiện tại.

Submission phải sử dụng khai báo trong cyberland.h, chỉ cài đặt hàm trên và không tự cài đặt main hay đọc/ghi trực tiếp qua standard input/output.

Ví dụ

solve(3, 2, 30, 2, {1, 2}, {2, 0}, {12, 4}, {1, 2, 1});

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

Ràng buộc

• \(2\le N\le10^5\), và tổng \(N\) qua mọi lần gọi không vượt quá \(10^5\).
• \(0\le M\le\min\left\{10^5,\frac{N(N-1)}2\right\}\), và tổng \(M\) qua mọi lần gọi không vượt quá \(10^5\).
• \(1\le K\le10^6\).
• \(1\le H<N\).
• \(0\le x[i],y[i]<N\) và \(x[i]\ne y[i]\).
• \(1\le c[i]\le10^9\).
• \(arr[i]\in\{0,1,2\}\).
• Mỗi cặp quốc gia được nối với nhau bởi nhiều nhất một con đường.

Phân nhóm

Trình chấm mẫu

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

• Dòng đầu chứa \(T\).
• Với mỗi trường hợp thử:
  • dòng đầu chứa \(N\), \(M\), \(K\);
  • dòng tiếp theo chứa \(H\);
  • dòng tiếp theo chứa \(arr[0],arr[1],\ldots,arr[N-1]\);
  • với mỗi \(i\) từ \(0\) đến \(M-1\), dòng tiếp theo chứa \(x[i]\), \(y[i]\), \(c[i]\).

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

Phần này chỉ mô tả giao diện của trình chấm mẫu; submission vẫn phải cài đặt hàm solve như ở trên.

Nguồn

Kho đề và dữ liệu chính thức APIO 2023, bài Cyberland. Gói nguồn được phát hành theo giấy phép CC0 1.0.

Trong thế giới đầy mê hoặc của APIO có một học sinh trẻ tuổi và thông minh tên Alice. Alice rất thích giải những bài toán thú vị thử thách năng lực toán học. Một ngày nọ, cô bắt gặp một dãy số bí ẩn có độ dài \(N\),

và muốn khám phá những bí mật của nó.

Trước hết, ta đưa ra một số định nghĩa. Ký hiệu

là số lần giá trị \(x\) xuất hiện trong đoạn \(A[l],A[l+1],\ldots,A[r]\). Ở đây, \(I[P]\) bằng \(1\) nếu mệnh đề \(P\) đúng và bằng \(0\) nếu \(P\) sai.

Với một dãy số nguyên không rỗng \(B[0],B[1],\ldots,B[k-1]\), gọi \(S(\{B[0],B[1],\ldots,B[k-1]\})\) là tập các trung vị của dãy. Tập này được xác định như sau:

1. Sắp xếp các phần tử của \(B\) theo thứ tự không giảm để thu được dãy \(C[0],C[1],\ldots,C[k-1]\).

2. Khi đó

   \[ S(\{B[0],B[1],\ldots,B[k-1]\})= \left\{C\!\left[\left\lfloor\frac{k-1}{2}\right\rfloor\right], C\!\left[\left\lceil\frac{k-1}{2}\right\rceil\right]\right\}. \]

Ví dụ:

Ký hiệu \(S(l,r)\) là tập các trung vị của đoạn \(A[l],A[l+1],\ldots,A[r]\). Alice muốn tìm giá trị lớn nhất của

trên mọi cặp chỉ số \(0\le l\le r\le N-1\). Alice đã có đáp án và nhờ bạn viết chương trình để kiểm chứng đáp án đó.

Yêu cầu cài đặt

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

int sequence(int N, std::vector<int> A);

• N: độ dài của dãy A.
• A: mảng độ dài \(N\) mô tả dãy.
• Hàm phải trả về giá trị lớn nhất trên mọi cặp \((l,r)\) hợp lệ như đã định nghĩa ở trên.
• Hàm được gọi đúng một lần.

Submission phải sử dụng khai báo trong sequence.h, chỉ cài đặt hàm trên và không tự cài đặt main hay đọc/ghi trực tiếp qua standard input/output.

Ví dụ

sequence(7, {1, 2, 3, 1, 2, 1, 3});

sequence(9, {1, 1, 2, 3, 4, 3, 2, 1, 1});

sequence(14, {2, 6, 2, 5, 3, 4, 2, 1, 4, 3, 5, 6, 3, 2});

Ràng buộc

• \(1\le N\le5\times10^5\).
• \(1\le A[i]\le N\).

Phân nhóm

Trình chấm mẫu

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

• Dòng đầu chứa \(N\).
• Dòng thứ hai chứa \(A[0],A[1],\ldots,A[N-1]\).

Trình chấm mẫu in trên một dòng giá trị mà hàm sequence trả về.

Phần này chỉ mô tả giao diện của trình chấm mẫu; submission vẫn phải cài đặt hàm sequence như ở trên.

Nguồn

Kho đề và dữ liệu chính thức APIO 2023, bài Sequence. Gói nguồn được phát hành theo giấy phép CC0 1.0.

Tổ chức Cyberland Circuit có \(n\) thành viên. Mỗi thành viên có một tên riêng duy nhất và một con số yêu thích; các con số yêu thích không nhất thiết khác nhau.

Có \(m\) bức thư đã được gửi giữa các thành viên. Mỗi bức thư có một người gửi và một người nhận, còn nội dung bức thư chính là con số yêu thích của người gửi.

Mỗi thành viên cộng nội dung của tất cả thư mình nhận được, rồi lấy phần dư theo \(65536=2^{16}\) để thu được số kết quả của mình. Nhiệm vụ của bạn là xác định số kết quả của mọi thành viên.

Tuy nhiên, Alice, Bob và Circuit quyết định giải bài toán theo một cách phức tạp hơn:

• Alice biết đầy đủ \(n\) thành viên, gồm tên và số yêu thích của họ, nhưng không biết gì về các bức thư. Cô phải gửi cho Circuit một chuỗi nhị phân có độ dài không quá \(10^5\).
• Bob biết đầy đủ \(m\) bức thư, gồm tên người gửi và người nhận, nhưng không biết gì về các thành viên. Anh phải gửi cho Circuit một chuỗi nhị phân có độ dài không quá \(10^5\).
• Circuit nhận hai chuỗi nhị phân của Alice và Bob, rồi tạo ra một chuỗi nhị phân gồm \(16n\) bit làm kết quả. Do năng lực tính toán hạn chế, Circuit chỉ thực hiện được các phép toán logic cơ bản.

Chi tiết về mạch

Cổng là phần tử cơ bản của mạch. Tùy loại, một cổng có không đầu vào hoặc có hai đầu vào boolean, và luôn có một đầu ra boolean. Có hai loại cổng: cổng dữ liệu vào và cổng tính toán.

Cổng dữ liệu vào không có đầu vào và biểu diễn các bit trong chuỗi nhị phân của Alice và Bob.

• Có \(l_A+l_B\) cổng dữ liệu vào, mang nhãn từ \(0\) đến \(l_A+l_B-1\), trong đó \(l_A\) và \(l_B\) lần lượt là độ dài chuỗi của Alice và Bob.
• Với \(0\le i<l_A\), đầu ra của cổng \(i\) là bit thứ \(i\) trong chuỗi của Alice.
• Với \(0\le i<l_B\), đầu ra của cổng \(i+l_A\) là bit thứ \(i\) trong chuỗi của Bob.

Cổng tính toán có hai đầu vào và biểu diễn quá trình tính toán.

• Nhãn của các cổng tính toán bắt đầu từ \(l_A+l_B\).
• Với mỗi cổng tính toán, bạn phải cho biết nhãn của hai cổng mà nó phụ thuộc vào và loại phép toán \(p\), với \(0\le p\le15\).
• Để không có phụ thuộc vòng, nhãn của cả hai cổng phụ thuộc phải nhỏ hơn nhãn của cổng hiện tại.
• Nếu đầu ra của hai cổng phụ thuộc lần lượt là \(x_0\) và \(x_1\), trong đó \(x_0,x_1\in\{0,1\}\), thì đầu ra của cổng tính toán là

Công thức trên xác định đầy đủ cả \(16\) loại phép toán:

Một số phép toán thường dùng có bảng chân trị sau:

Yêu cầu cài đặt

Mọi chỉ số mảng đều bắt đầu từ \(0\). Chẳng hạn, với mảng a có độ dài \(n\), các phần tử hợp lệ là a[0] đến a[n-1]; truy cập ngoài phạm vi có thể gây lỗi. Mọi chuỗi ký tự đều kết thúc bằng ký tự null \0.

Submission phải sử dụng các khai báo trong abc.h, cài đặt đủ ba hàm dưới đây và không tự cài đặt main hay giao tiếp trực tiếp qua standard input/output. Alice, Bob và Circuit được chấm như các vai trò tách biệt; thông tin duy nhất mà hàm circuit nhận trực tiếp là độ dài hai chuỗi nhị phân.

Alice

int alice(const int n, const char names[][5],
          const unsigned short numbers[], bool outputs_alice[]);

• n: số thành viên, \(0\le n\le700\).
• names: mảng độ dài \(n\) chứa tên các thành viên. Mọi tên đều khác nhau, chỉ gồm chữ cái tiếng Anh viết thường và dài nhiều nhất \(4\) ký tự.
• numbers: mảng độ dài \(n\) chứa số yêu thích của từng thành viên; mỗi số nằm trong đoạn từ \(0\) đến \(65535\).
• outputs_alice: ghi chuỗi nhị phân độ dài \(l_A\) mà Alice gửi cho Circuit.
• Hàm trả về \(l_A\). Bạn phải bảo đảm \(0\le l_A\le10^5\), và với cùng một giá trị \(n\), độ dài \(l_A\) phải luôn cố định.

Bob

int bob(const int m, const char senders[][5],
        const char recipients[][5], bool outputs_bob[]);

• m: số bức thư, \(0\le m\le1000\).
• senders: mảng độ dài \(m\) chứa tên người gửi của từng bức thư.
• recipients: mảng độ dài \(m\) chứa tên người nhận của từng bức thư.
• Mọi tên xuất hiện trong senders và recipients đều xuất hiện trong đầu vào names của Alice.
• outputs_bob: ghi chuỗi nhị phân độ dài \(l_B\) mà Bob gửi cho Circuit.
• Hàm trả về \(l_B\). Bạn phải bảo đảm \(0\le l_B\le10^5\), và với cùng một giá trị \(m\), độ dài \(l_B\) phải luôn cố định.

Circuit

Để quá trình tính toán thật sự là một mạch tổng quát, hàm circuit không được nhận trực tiếp hai chuỗi nhị phân của Alice và Bob. Hàm chỉ biết độ dài của chúng và phải mô tả cấu trúc mạch.

int circuit(const int la, const int lb, int operations[],
            int operands[][2], int outputs_circuit[][16]);

• la và lb lần lượt là \(l_A\) và \(l_B\).
• operations có độ dài \(l\); operations[g] là loại phép toán từ \(0\) đến \(15\) của cổng tính toán mang nhãn \(g\).
• operands có độ dài \(l\); operands[g][0] và operands[g][1] là nhãn hai cổng đầu vào của cổng \(g\), và cả hai nhãn phải nhỏ hơn \(g\).
• outputs_circuit có độ dài \(n\). outputs_circuit[i][j] là nhãn cổng tạo ra bit thứ \(j\), đếm từ bit có trọng số thấp nhất, trong số kết quả cuối cùng của thành viên thứ \(i\). Thứ tự thành viên giống thứ tự trong đầu vào của Alice. Mọi nhãn đầu ra phải nằm trong đoạn từ \(0\) đến \(l-1\).
• Hàm trả về \(l\), tổng số cổng kể cả cổng dữ liệu vào. Do đó \(l\ge l_A+l_B\), và bạn phải bảo đảm \(l\le2\times10^7\).

Bạn có thể sửa các phần tử của operations và operands có chỉ số nhỏ hơn \(l_A+l_B\), nhưng trình chấm sẽ bỏ qua các sửa đổi này vì đó là các cổng dữ liệu vào.

Ví dụ

Xét hai lời gọi:

alice(3, {"alic", "bob", "circ"},
      {10000, 20000, 30000}, outputs_alice);
bob(5, {"alic", "bob", "bob", "circ", "circ"},
       {"circ", "circ", "alic", "circ", "circ"}, outputs_bob);

Các lời gọi này biểu diễn tình huống sau:

• Alice biết có \(3\) thành viên: alic có số yêu thích \(10000\), bob có số yêu thích \(20000\), và circ có số yêu thích \(30000\). Một kết quả có thể có của alice là trả về \(2\), tức \(l_A=2\), đồng thời đặt outputs_alice[0] = 1 và outputs_alice[1] = 0, tạo thành chuỗi 10.
• Bob biết có \(5\) bức thư; bức thư đầu tiên được gửi từ alic đến circ, v.v. Một kết quả có thể có của bob là trả về \(3\), tức \(l_B=3\), đồng thời đặt outputs_bob[0] = 1, outputs_bob[1] = 1, outputs_bob[2] = 0, tạo thành chuỗi 110.

Từ hai độ dài trên, Circuit được gọi như sau:

circuit(2, 3, operations, operands, outputs_circuit);

Một kết quả đúng của hàm này là trả về \(7\), tức thêm hai cổng tính toán mang nhãn \(5\) và \(6\), và thiết lập:

operations = {-1, -1, -1, -1, -1, 8, 14};

operands = {
    {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1},
    {0, 4}, {2, 5}
};

outputs_circuit = {
    {5, 5, 5, 5, 5, 6, 5, 5, 5, 6, 6, 6, 5, 5, 6, 5},
    {5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5},
    {5, 5, 5, 5, 6, 5, 5, 6, 6, 6, 6, 6, 6, 5, 6, 5}
};

Trong operations và operands, giá trị \(-1\) chỉ biểu diễn thông tin bị bỏ qua ở các cổng dữ liệu vào. Quá trình tính toán là:

• Cổng \(5\) có loại phép toán \(8\), nhận đầu vào từ cổng \(0\) và \(4\). Cổng \(0\) cho bit thứ \(0\) của chuỗi Alice, bằng \(1\); cổng \(4\) cho bit thứ \(2\) của chuỗi Bob, bằng \(0\). Vì vậy \(f(8,1,0)=1\mathbin{\mathrm{AND}}0=0\).
• Cổng \(6\) có loại phép toán \(14\), nhận đầu vào từ cổng \(2\) và \(5\). Cổng \(2\) cho bit thứ \(0\) của chuỗi Bob, bằng \(1\); cổng \(5\) cho \(0\). Vì vậy \(f(14,1,0)=1\mathbin{\mathrm{OR}}0=1\).
• outputs_circuit[0] biểu diễn số kết quả của alic:

`alic` chỉ nhận một bức thư từ `bob`, nên kết quả đúng là $20000$.

• bob không nhận bức thư nào nên kết quả là \(0\).
• Kết quả của circ là

Tệp mẫu abc.cpp trong gói đính kèm vượt qua ví dụ này, nhưng không được bảo đảm sẽ vượt qua các trường hợp thử khác.

Ràng buộc

Trong mọi trường hợp thử:

• \(0\le n\le700\), \(0\le m\le1000\).
• Mọi tên thành viên đều khác nhau, chỉ gồm chữ cái tiếng Anh viết thường và dài nhiều nhất \(4\) ký tự.
• Số yêu thích của mỗi thành viên nằm trong đoạn từ \(0\) đến \(65535\).
• Tên của mọi người gửi và người nhận đều xuất hiện trong mảng names ở đầu vào của Alice.
• alice và bob đều có giới hạn bộ nhớ \(2048\ \mathrm{MiB}\) và giới hạn thời gian \(0{,}02\) giây.
• circuit có giới hạn bộ nhớ \(2048\ \mathrm{MiB}\) và giới hạn thời gian \(7\) giây.

Trong lần chấm chính thức, alice và bob có thể được gọi nhiều lần trong cùng một trường hợp thử. Giới hạn \(0{,}02\) giây áp dụng riêng cho mỗi lần gọi. Điều kiện độ dài cố định của \(l_A\) theo \(n\) và của \(l_B\) theo \(m\) vẫn phải được thỏa mãn giữa các lần gọi.

Phân nhóm và chấm điểm

Có chín subtask, được chia thành ba loại. Các điều kiện trong bảng dưới đây là đầy đủ đối với từng subtask, ngoài các ràng buộc chung đã nêu trên.

Tổng điểm của loại A là \(12\), loại B là \(54\), và loại C là \(34\).

Trình chấm mẫu

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

• Dòng đầu chứa \(n\) và \(m\).
• Với mỗi \(i\) từ \(0\) đến \(n-1\), dòng thứ \(2+i\) chứa names[i] và numbers[i].
• Với mỗi \(i\) từ \(0\) đến \(m-1\), dòng thứ \(2+n+i\) chứa senders[i] và recipients[i].

Nếu chương trình kết thúc thành công, trình chấm mẫu in \(n\) dòng, mỗi dòng chứa số kết quả cuối cùng do các hàm của bạn tính cho một thành viên. Nếu không, trình chấm không ghi gì ra standard output và ghi thông báo lỗi vào tệp abc.log trong thư mục hiện tại. Trình chấm mẫu còn ghi các giá trị \(l_A\), \(l_B\), \(l\) và thời gian chạy của từng hàm vào abc.log.

Trình chấm mẫu không kiểm tra giới hạn bộ nhớ, cũng không kiểm tra điều kiện rằng với cùng \(n\) hoặc \(m\), các độ dài tương ứng \(l_A\) hoặc \(l_B\) phải bằng nhau. Những điều kiện này vẫn được kiểm tra khi chấm chính thức.

Phần này chỉ mô tả giao diện của trình chấm mẫu; submission vẫn phải cài đặt ba hàm trong abc.h như ở trên.

Nguồn

Kho đề và dữ liệu chính thức APIO 2023, bài Alice, Bob and Circuit. Gói nguồn được phát hành theo giấy phép CC0 1.0.