JOI 2022 - Tuyển chọn mùa xuân - Ngày 2

Công ty JOI nổi tiếng với những "phát minh kỳ lạ". Gần đây, công ty đã phát triển một trình soạn thảo văn bản mang tên "Just Odd Editor".

Trong trình soạn thảo này, ta có thể nhập một xâu ký tự bằng cách thực hiện nhiều lần các thao tác dưới đây. Gọi \(X\) là xâu đang hiển thị trên màn hình và \(Y\) là xâu được lưu trong bộ nhớ tạm. Ban đầu, cả \(X\) và \(Y\) đều là xâu rỗng.

• Thao tác A: Thêm một ký tự vào cuối xâu. Cụ thể, chọn một ký tự \(c\) rồi thay \(X\) bằng \(X+c\).
• Thao tác B: Chọn toàn bộ các ký tự và cắt chúng. Cụ thể, thay \(Y\) bằng \(X\), sau đó đặt \(X\) thành xâu rỗng.
• Thao tác C: Dán xâu trong bộ nhớ tạm vào cuối xâu. Cụ thể, thay \(X\) bằng \(X+Y\).

Với các ký tự hoặc xâu \(x,y\), ký hiệu \(x+y\) là xâu thu được bằng cách nối \(x\) rồi đến \(y\). Thực hiện một lần thao tác A, B, C lần lượt tốn \(A\), \(B\), \(C\) đơn vị thời gian.

Bạn đã cài đặt Just Odd Editor và muốn nhập xâu \(S\) có độ dài \(N\) nhanh nhất có thể. Hãy thực hiện các thao tác sao cho xâu trên màn hình trở thành \(S\) trong thời gian ngắn nhất.

Viết chương trình nhận độ dài \(N\), xâu \(S\) và thời gian thực hiện mỗi thao tác, rồi tính thời gian ít nhất cần để nhập xâu \(S\).

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng sau:

N
S
A
B
C

Dữ liệu ra

Ghi một dòng ra đầu ra chuẩn, chứa thời gian ít nhất cần để nhập xâu \(S\).

Ràng buộc

• \(1\le N\le 2\,500\).
• \(S\) là xâu độ dài \(N\), chỉ gồm các chữ cái tiếng Anh thường từ a đến z.
• \(1\le A\le 1\,000\,000\,000=10^9\).
• \(1\le B\le 1\,000\,000\,000=10^9\).
• \(1\le C\le 1\,000\,000\,000=10^9\).
• \(N,A,B,C\) đều là số nguyên.

Phân nhóm

1. \(1\) điểm: \(N=3\).
2. \(5\) điểm: Mọi ký tự của \(S\) đều là a.
3. \(14\) điểm: \(N\le 30\).
4. \(10\) điểm: \(N\le 200\).
5. \(32\) điểm: \(N\le 1\,000\).
6. \(38\) điểm: Không có ràng buộc bổ sung.

Ví dụ

11
mississippi
10
5
2

88

16
aaaaaaaaaaaaaaaa
1
1
1

9

18
aababbbababbbaabbb
1000000000
100000
10000000

8060200000

Nguồn

JOI 2021/2022 Spring Training Camp, Contest 2, do Japanese Committee for the International Olympiad in Informatics (JCIOI) công bố. Bản dịch tiếng Việt được chuyển ngữ từ đề chính thức và phát hành theo giấy phép CC BY-SA 4.0.

Ở Cộng hòa JOI có \(N\) sân bay, được đánh số từ \(0\) đến \(N-1\), và \(N-1\) đường bay, được đánh số từ \(0\) đến \(N-2\). Đường bay \(i\) (\(0\le i\le N-2\)) nối hai chiều giữa sân bay \(U_i\) và sân bay \(V_i\). Có thể đi từ một sân bay bất kỳ đến bất kỳ sân bay nào khác bằng cách nối tiếp các đường bay. Mỗi sân bay được nối với các sân bay khác bởi nhiều nhất \(3\) đường bay.

Benjamin đang lên kế hoạch du lịch ở Cộng hòa JOI. Vào ngày cuối của chuyến đi, anh muốn đến sân bay có suối nước nóng từ sân bay có công viên giải trí. Công viên giải trí nằm ở sân bay \(x\), còn suối nước nóng nằm ở sân bay \(y\). Vì không biết gì về các đường bay, Benjamin sẽ liên lạc với Ali, một nhân viên của hãng hàng không. Benjamin muốn biết số đường bay ít nhất phải đi để đến sân bay có suối nước nóng từ sân bay có công viên giải trí. Ali biết thông tin về các đường bay, nhưng không biết Benjamin muốn di chuyển giữa những sân bay nào.

1. Ali đặt một mã ID cho mỗi sân bay. Mã ID là số nguyên từ \(0\) đến \(2N+19\), kể cả hai đầu mút.
2. Benjamin nhận mã ID \(X\) của sân bay có công viên giải trí và mã ID \(Y\) của sân bay có suối nước nóng.
3. Benjamin gửi một thư điện tử cho Ali. Nội dung thư là một xâu có độ dài đúng \(20\), mỗi ký tự là 0 hoặc 1.
4. Ali viết một bức thư gửi Benjamin. Nội dung thư là một xâu có độ dài từ \(1\) đến \(300\,000\), kể cả hai đầu mút, mỗi ký tự là 0 hoặc 1.

Hãy viết các chương trình thực hiện chiến lược của nhân viên hàng không Ali và du khách Benjamin. Lưu ý rằng ở bước \(2\), Benjamin chỉ nhận được các mã ID \(X,Y\) của hai sân bay, không nhận được số hiệu sân bay \(x,y\).

Trong hình, Ali đặt ID cho từng sân bay; Benjamin nhận ID của hai địa điểm rồi gửi thư điện tử đúng \(20\) ký tự; Ali gửi lại bức thư. Giới hạn chính xác của bức thư là \(1\le |T|\le 300\,000\) như mô tả trên, bao gồm \(300\,000\).

Chi tiết cài đặt

Bạn cần nộp hai tệp.

Tệp thứ nhất là Ali.cpp, thực hiện chiến lược của Ali. Tệp phải khai báo #include "Ali.h" và cài đặt hai hàm sau:

void Init(int N, std::vector<int> U, std::vector<int> V);
std::string SendA(std::string S);

Hàm Init thực hiện chiến lược đặt mã ID cho các sân bay của Ali. Với mỗi tình huống (xem phần quy trình chấm), hàm này được gọi đúng một lần.

• Tham số N là số sân bay ở Cộng hòa JOI.
• U và V là các mảng có độ dài \(N-1\). Các giá trị U[i] và V[i] là hai sân bay \(U_i,V_i\) được nối bởi đường bay \(i\) (\(0\le i\le N-2\)).

Hàm SendA thực hiện chiến lược gửi thư cho Benjamin của Ali. Với mỗi tình huống, hàm được gọi đúng một lần sau khi hàm SendB bên dưới được gọi.

• Tham số S là xâu độ dài \(20\), chứa thư điện tử Benjamin gửi Ali.
• Hàm phải trả về một xâu, là bức thư Ali gửi Benjamin.
• Độ dài xâu trả về phải nằm trong đoạn từ \(1\) đến \(300\,000\), kể cả hai đầu mút. Nếu không, chương trình bị chấm Wrong Answer [5].
• Mỗi ký tự của xâu trả về phải là 0 hoặc 1. Nếu không, chương trình bị chấm Wrong Answer [6].

Trong mỗi lần gọi Init, chương trình phải gọi hàm sau đúng một lần cho mỗi sân bay, tức tổng cộng \(N\) lần:

void SetID(int p, int value);

• Tham số p chỉ sân bay mà Ali đang đặt mã ID. Phải có \(0\le p\le N-1\); nếu không, chương trình bị chấm Wrong Answer [1].
• Tham số value là mã ID Ali đặt cho sân bay đó. Phải có \(0\le \texttt{value}\le 2N+19\); nếu không, chương trình bị chấm Wrong Answer [2].
• Không được gọi SetID nhiều hơn một lần với cùng tham số p. Nếu vi phạm, chương trình bị chấm Wrong Answer [3].
• Khi Init kết thúc, số lần gọi SetID phải bằng \(N\). Nếu không, chương trình bị chấm Wrong Answer [4].

Khi một lần gọi SetID bị chấm Wrong Answer, chương trình kết thúc ngay lập tức.

Tệp thứ hai là Benjamin.cpp, thực hiện chiến lược của Benjamin. Tệp phải khai báo #include "Benjamin.h" và cài đặt hai hàm sau:

std::string SendB(int N, int X, int Y);
int Answer(std::string T);

Hàm SendB thực hiện chiến lược gửi thư điện tử cho Ali của Benjamin. Với mỗi tình huống, hàm được gọi đúng một lần sau khi Init được gọi.

• Tham số N là số sân bay ở Cộng hòa JOI.
• Tham số X là mã ID của sân bay có công viên giải trí.
• Tham số Y là mã ID của sân bay có suối nước nóng.
• Hàm phải trả về xâu chứa thư điện tử Benjamin gửi Ali.
• Xâu trả về phải có độ dài đúng \(20\). Nếu không, chương trình bị chấm Wrong Answer [7].
• Mỗi ký tự của xâu trả về phải là 0 hoặc 1. Nếu không, chương trình bị chấm Wrong Answer [8].

Hàm Answer tính số đường bay ít nhất Benjamin phải đi để đến sân bay \(y\) từ sân bay \(x\). Với mỗi tình huống, hàm được gọi đúng một lần sau khi SendA được gọi.

• Tham số T là xâu có độ dài từ \(1\) đến \(300\,000\), kể cả hai đầu mút, chứa bức thư Ali gửi Benjamin.
• Hàm phải trả về số đường bay ít nhất cần đi để đến sân bay \(y\) từ sân bay \(x\).

Lưu ý quan trọng

• Chương trình có thể cài đặt thêm các hàm dùng nội bộ và sử dụng biến toàn cục. Các tệp nộp được biên dịch cùng chương trình chấm thành một tệp thực thi. Mọi biến toàn cục và hàm nội bộ cần được khai báo trong một namespace không tên để tránh xung đột với các tệp khác. Khi chấm chính thức, chương trình chạy thành hai tiến trình, của Ali và Benjamin. Hai tiến trình không thể chia sẻ biến toàn cục.
• Chương trình không được sử dụng đầu vào chuẩn hoặc đầu ra chuẩn, và không được giao tiếp với các tệp khác bằng bất kỳ cách nào. Tuy nhiên, chương trình có thể ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

Quy trình chấm

Một bộ kiểm thử gồm \(Q\) tình huống, được đánh số từ \(0\) đến \(Q-1\). Mỗi tình huống xác định các giá trị sau; miền giá trị được nêu trong phần ràng buộc:

• Số sân bay \(N\).
• Số hiệu sân bay \(x\) có công viên giải trí.
• Số hiệu sân bay \(y\) có suối nước nóng.
• Các đường bay \((U_0,V_0),(U_1,V_1),\ldots,(U_{N-2},V_{N-2})\).

Với mỗi tình huống, các hàm Init, SendB, SendA, Answer được gọi. Chương trình phải gọi các hàm thích hợp với tham số hợp lệ và trả về các giá trị thích hợp. Thứ tự thực hiện là:

1. Với \(k=0,1,\ldots,Q-1\), thực hiện lần lượt các bước \(2\) đến \(5\) dưới đây.
2. Gọi Init với các tham số của tình huống \(k\) như mô tả trong phần chi tiết cài đặt.
3. Gọi SendB với các tham số của tình huống \(k\) như mô tả trong phần chi tiết cài đặt.
4. Gọi SendA với các tham số của tình huống \(k\) như mô tả trong phần chi tiết cài đặt.
5. Gọi Answer với các tham số của tình huống \(k\) như mô tả trong phần chi tiết cài đặt.

Nếu chương trình bị chấm Wrong Answer trong quá trình trên, chương trình kết thúc ngay lập tức và được xem là không vượt qua bộ kiểm thử đó.

Mỗi cột trong hình là một tình huống: Init, SendB, SendA, rồi Answer. Hoàn thành tình huống hiện tại trước khi bắt đầu tình huống tiếp theo.

Biên dịch và chạy thử

Tệp đính kèm flights-dist.zip chứa chương trình chấm mẫu và các tệp chương trình mẫu dành cho bạn.

Chương trình chấm mẫu nằm trong grader.cpp. Để thử chương trình, đặt grader.cpp, Ali.cpp, Benjamin.cpp, Ali.h, Benjamin.h trong cùng một thư mục và biên dịch bằng lệnh:

g++ -std=gnu++17 -O2 -o grader grader.cpp Ali.cpp Benjamin.cpp

Nếu biên dịch thành công, tệp thực thi grader được tạo ra.

Chương trình chấm chính thức khác chương trình chấm mẫu. Chương trình chấm mẫu chạy trong một tiến trình duy nhất, đọc dữ liệu từ đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn.

Dữ liệu vào

Chương trình chấm mẫu đọc dữ liệu theo định dạng dưới đây. Tất cả các giá trị đầu vào đều là số nguyên.

Q
(Dữ liệu cho tình huống 0)
(Dữ liệu cho tình huống 1)
...
(Dữ liệu cho tình huống Q-1)

Dữ liệu của mỗi tình huống có định dạng:

N x y
U_0 V_0
U_1 V_1
...
U_{N-2} V_{N-2}

Dữ liệu ra

Nếu chương trình bị chấm một trong các lỗi Wrong Answer [1] đến Wrong Answer [8], chương trình chấm mẫu in loại lỗi, chẳng hạn Wrong Answer [1].

Nếu không có các lỗi đó, chương trình chấm mẫu in giá trị trả về của Answer cho từng tình huống và độ dài lớn nhất của các xâu Ali gửi Benjamin. Chương trình chấm mẫu không kiểm tra giá trị trả về của Answer có đúng hay không. Ví dụ về dạng thông báo:

Scenario 0: Your Answer = 3
Scenario 1: Your Answer = 1
Scenario 2: Your Answer = 4
Scenario 3: Your Answer = 1
Scenario 4: Your Answer = 5
Accepted: Maximum Length = 24

Nếu chương trình vi phạm nhiều loại Wrong Answer, chương trình chấm mẫu chỉ báo một loại. Ngoài ra, nếu tình huống đầu tiên không bị chấm Wrong Answer, chương trình chấm mẫu có thể đã in các kết quả trung gian trước khi báo Wrong Answer [1] đến Wrong Answer [8] ở một tình huống sau, chẳng hạn:

Scenario 0: Your Answer = 3
Scenario 1: Your Answer = 1
Scenario 2: Your Answer = 4
Wrong Answer [8]

Ràng buộc

• \(1\le Q\le 50\).
• \(2\le N\le 10\,000\).
• \(0\le U_i<V_i\le N-1\) với \(0\le i\le N-2\).
• \(0\le x\le N-1\).
• \(0\le y\le N-1\).
• \(x\ne y\).
• Có thể đi từ một sân bay bất kỳ đến bất kỳ sân bay nào khác bằng cách nối tiếp các đường bay.
• Mỗi sân bay được nối với các sân bay khác bởi nhiều nhất \(3\) đường bay.

Phân nhóm

1. \(15\) điểm: \(Q=1\).
2. \(85\) điểm: \(Q\ge 2\).

Cách tính điểm nhóm 1: Nếu có bất kỳ câu trả lời sai nào trong các tình huống thuộc nhóm \(1\), điểm của nhóm là \(0\).

Nếu chương trình trả lời đúng tất cả các bộ kiểm thử của nhóm \(1\), gọi \(L_1\) là độ dài lớn nhất của các xâu Ali gửi Benjamin, xét trên tất cả các bộ kiểm thử của nhóm. Điểm được tính theo bảng sau:

Cách tính điểm nhóm 2: Nếu có bất kỳ câu trả lời sai nào trong các tình huống thuộc nhóm \(2\), điểm của nhóm là \(0\).

Nếu chương trình trả lời đúng tất cả các bộ kiểm thử của nhóm \(2\), gọi \(L_2\) là độ dài lớn nhất của các xâu Ali gửi Benjamin, xét trên tất cả các bộ kiểm thử của nhóm. Đặc biệt, nếu \(L_2\ge 1\,401\) thì điểm của nhóm là \(0\).

Ký hiệu \(\lfloor t\rfloor\) nghĩa là làm tròn xuống số nguyên gần nhất.

Ví dụ giao tiếp

Các giá trị dưới đây là giá trị hàm Answer phải trả về, không phải định dạng đầu ra chuẩn của chương trình dự thi.

Ví dụ 1

Dữ liệu vào của chương trình chấm mẫu:

1
4 0 2
0 1
1 2
2 3

Giá trị Answer phải trả về

2

Ở đây có \(N=4\) sân bay và ba đường bay: nối sân bay \(0\) với \(1\), nối sân bay \(1\) với \(2\), và nối sân bay \(2\) với \(3\).

Từ sân bay \(x=0\) đến sân bay \(y=2\) cần đi ít nhất hai đường bay, nên Answer phải trả về \(2\).

Chú ý các tham số X,Y của SendB là mã ID \((12,25)\), không phải số hiệu sân bay \((x,y)=(0,2)\). Lời gọi trong bảng đã ghi đủ tham số N=4 theo chữ ký hàm.

Ví dụ 2

Dữ liệu vào của chương trình chấm mẫu:

2
10 0 9
0 1
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
15 12 8
0 1
0 2
1 3
1 4
2 5
2 6
3 7
3 8
4 9
4 10
5 11
5 12
6 13
6 14

Giá trị Answer phải trả về theo thứ tự tình huống

9
6

Nguồn

JOI 2021/2022 Spring Training Camp, Contest 2, do Japanese Committee for the International Olympiad in Informatics (JCIOI) công bố. Bản dịch tiếng Việt được chuyển ngữ từ đề chính thức và phát hành theo giấy phép CC BY-SA 4.0.

Có \(N\) chú hải ly tại Đại học JOI. Tất cả đều tham gia lập trình thi đấu. Mỗi chú hải ly có ba năng lực: khả năng tư duy, khả năng cài đặt và may mắn. Giá trị của một năng lực càng lớn thì năng lực đó càng cao. Với mỗi \(i\) (\(1\le i\le N\)), khả năng tư duy, khả năng cài đặt và may mắn của chú hải ly \(i\) lần lượt là \(X_i,Y_i,Z_i\).

Năm nay, các chú hải ly của Đại học JOI sẽ tham gia một cuộc thi lập trình theo đội. Trong cuộc thi, các thí sinh giải các bài toán lập trình và mỗi đội gồm ba chú hải ly. Bitaro là huấn luyện viên của Đại học JOI. Vì tinh thần đồng đội rất quan trọng, Bitaro quyết định chọn ba chú hải ly trong số \(N\) chú để lập một đội thỏa mãn điều kiện sau:

Điều kiện: Mỗi thành viên đều có một thế mạnh. Nghĩa là mỗi thành viên có ít nhất một năng lực với giá trị lớn hơn hẳn giá trị của cùng năng lực đó ở cả hai thành viên còn lại.

Trong số các đội thỏa mãn điều kiện, Bitaro muốn chọn đội có tổng năng lực lớn nhất. Tổng năng lực của một đội được định nghĩa là tổng của ba giá trị: khả năng tư duy lớn nhất, khả năng cài đặt lớn nhất và may mắn lớn nhất trong số các thành viên của đội.

Viết chương trình nhận thông tin về năng lực của mỗi chú hải ly, xác định có thể lập một đội thỏa mãn điều kiện hay không và, nếu có, tính tổng năng lực lớn nhất có thể của đội.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng sau. Tất cả các giá trị đều là số nguyên.

N
X_1 Y_1 Z_1
X_2 Y_2 Z_2
...
X_N Y_N Z_N

Dữ liệu ra

Ghi một dòng ra đầu ra chuẩn, chứa tổng năng lực lớn nhất có thể của một đội. Nếu không thể lập đội thỏa mãn điều kiện, in -1.

Ràng buộc

• \(3\le N\le 150\,000\).
• \(1\le X_i\le 100\,000\,000=10^8\) với \(1\le i\le N\).
• \(1\le Y_i\le 100\,000\,000=10^8\) với \(1\le i\le N\).
• \(1\le Z_i\le 100\,000\,000=10^8\) với \(1\le i\le N\).

Phân nhóm

1. \(8\) điểm: \(N\le 300\).
2. \(29\) điểm: \(N\le 4\,000\).
3. \(9\) điểm: \(X_i,Y_i,Z_i\le 5\) với mọi \(1\le i\le N\).
4. \(9\) điểm: \(X_i,Y_i,Z_i\le 20\) với mọi \(1\le i\le N\).
5. \(9\) điểm: \(X_i,Y_i,Z_i\le 300\) với mọi \(1\le i\le N\).
6. \(9\) điểm: \(X_i,Y_i,Z_i\le 4\,000\) với mọi \(1\le i\le N\).
7. \(27\) điểm: Không có ràng buộc bổ sung.

Ví dụ

5
3 1 4
2 3 1
1 5 5
4 4 2
5 2 3

13

8
1 1 1
1 1 5
1 5 1
5 1 1
1 5 5
5 1 5
5 5 1
5 5 5

15

4
1 2 3
1 2 3
1 2 3
1 2 3

-1

Nguồn

JOI 2021/2022 Spring Training Camp, Contest 2, do Japanese Committee for the International Olympiad in Informatics (JCIOI) công bố. Bản dịch tiếng Việt được chuyển ngữ từ đề chính thức và phát hành theo giấy phép CC BY-SA 4.0.