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

Ở vương quốc IOI, đơn vị thời gian là Byou. Một ngày được chia thành \(S\) Byou. Thời điểm sau đầu ngày \(x\) Byou (\(0\le x<S\)) được gọi là thời điểm \(x\). Vương quốc có \(N\) thành phố, đánh số từ \(0\) đến \(N-1\), và \(M\) con đường, đánh số từ \(0\) đến \(M-1\). Có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác qua các con đường.

Con đường \(i\) (\(0\le i\le M-1\)) nối hai thành phố \(A_i,B_i\) theo cả hai chiều. Đi từ một đầu đến đầu kia mất \(L_i\) Byou. Mỗi ngày, con đường này bị kiểm tra an ninh nghiêm ngặt từ thời điểm \(C_i\) đến hết ngày.

Hội JOI là một tổ chức bí mật trong vương quốc. Danh tính thành viên phải được giữ kín, nên họ không được gặp các đợt kiểm tra. Để đi qua đường \(i\), một thành viên phải rời \(A_i\) hoặc \(B_i\) vào thời điểm \(x\) và đến đầu kia vào thời điểm \(x+L_i\), với \(0\le x\le C_i-L_i\). Không có kiểm tra trong các thành phố, nên thành viên có thể ở tại \(A_i\) hoặc \(B_i\) khi đường \(i\) đang bị kiểm tra.

Hội có \(Q\) thành viên, đánh số từ \(0\) đến \(Q-1\). Thành viên \(j\) rời thành phố \(U_j\) vào thời điểm \(T_j\) của một ngày nào đó để đi đến \(V_j\). Họ có thể chờ trong các thành phố trên đường đi. Hành trình có thể kéo dài qua nhiều ngày.

Cho thông tin thành phố, đường đi, các đợt kiểm tra và các thành viên, hãy tính thời gian ít nhất để mỗi thành viên \(j\) đi từ \(U_j\) đến \(V_j\).

Chi tiết cài đặt

Để tăng tốc nhập xuất, bài này sử dụng chương trình chấm (grader). Bạn cần nộp một tệp escape_route.cpp, nạp escape_route.h bằng chỉ thị #include, và cài đặt hàm:

std::vector<long long> calculate_necessary_time(
    int N, int M, long long S, int Q,
    std::vector<int> A, std::vector<int> B,
    std::vector<long long> L, std::vector<long long> C,
    std::vector<int> U, std::vector<int> V, std::vector<long long> T);

Hàm được gọi đúng một lần cho mỗi bộ dữ liệu.

• N, M, S, Q lần lượt là số thành phố, số con đường, số Byou trong một ngày và số thành viên.
• A, B, L, C là các mảng độ dài \(M\). Đường \(i\) nối A[i] với B[i], mất L[i] Byou để đi qua, và bắt đầu bị kiểm tra lúc C[i] mỗi ngày.
• U, V, T là các mảng độ dài \(Q\). Thành viên \(j\) rời U[j] lúc T[j] để đi đến V[j].
• Hàm phải trả về mảng answer kiểu long long, độ dài \(Q\). Với mỗi \(0\le j\le Q-1\), answer[j] là thời gian ít nhất, tính bằng Byou, để thành viên \(j\) đi từ U[j] đến V[j].

Lưu ý quan trọng

• Chương trình của bạn không được sử dụng đầu vào chuẩn, đầu ra chuẩn hoặc trao đổi với các tệp khác bằng bất kỳ cách nào. Được phép ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.
• Grader không kiểm tra định dạng đầu vào. Nếu định dạng sai, hoạt động của grader không được bảo đảm.
• Nếu mảng trả về có độ dài khác \(Q\) hoặc chứa số âm, hoạt động của grader không được bảo đảm.

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

Trang cuộc thi cung cấp một gói gồm grader và tệp chương trình mẫu. Đặt grader.cpp, escape_route.cpp, escape_route.h trong cùng thư mục, rồi biên dịch bằng lệnh:

g++ -std=gnu++17 -O2 -fsigned-char -o grader grader.cpp escape_route.cpp

Nếu thành công, tệp thực thi grader được tạo. Trong bài này, grader công khai trên trang cuộc thi giống grader thực tế dùng để chấm trên CMS.

Dữ liệu vào

Grader đọc từ đầu vào chuẩn theo định dạng sau; mọi giá trị đều là số nguyên:

N M S Q
A_0 B_0 L_0 C_0
...
A_{M-1} B_{M-1} L_{M-1} C_{M-1}
U_0 V_0 T_0
...
U_{Q-1} V_{Q-1} T_{Q-1}

Dữ liệu ra

Grader in \(Q\) dòng. Dòng thứ \(k+1\) (\(0\le k\le Q-1\)) chứa answer[k].

Ràng buộc

• \(2\le N\le90\).
• \(N-1\le M\le N(N-1)/2\).
• \(2\le S\le10^{15}\).
• \(1\le Q\le3000000\).
• \(0\le A_i,B_i\le N-1\) và \(A_i\ne B_i\) với mọi \(0\le i\le M-1\).
• Với \(0\le i<k\le M-1\), \((A_i,B_i)\ne(A_k,B_k)\) và \((A_i,B_i)\ne(B_k,A_k)\).
• \(1\le L_i<S\) và \(L_i\le C_i<S\) với mọi \(0\le i\le M-1\).
• Có thể đi từ bất kỳ thành phố nào đến bất kỳ thành phố nào khác qua các con đường.
• \(0\le U_j,V_j\le N-1\), \(U_j\ne V_j\) và \(0\le T_j<S\) với mọi \(0\le j\le Q-1\).

Phân nhóm

• Nhóm 1 (5 điểm): \(N\le40\) và \(Q\le1000\).
• Nhóm 2 (20 điểm): \(N\le40\) và \(U_j=0\) với mọi \(0\le j\le Q-1\).
• Nhóm 3 (10 điểm): \(N\le40\).
• Nhóm 4 (35 điểm): \(N\le60\).
• Nhóm 5 (30 điểm): Không có ràng buộc bổ sung.

Ví dụ giao tiếp

Ví dụ 1

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

4 5 20 6
0 1 3 19
0 2 2 8
1 2 4 15
1 3 5 14
2 3 1 18
0 3 5
0 3 7
0 3 9
2 0 6
3 1 10
1 2 15

Dữ liệu ra của trình chấm mẫu:

3
8
14
2
5
7

Giải thích

Thành viên \(0\) rời thành phố \(0\) lúc \(5\) để đến thành phố \(3\). Đi đường \(1\) từ thành phố \(0\) lúc \(5\) đến thành phố \(2\) lúc \(7\), rồi đi đường \(4\) lúc \(7\) đến thành phố \(3\) lúc \(8\). Đây là thời gian ít nhất, nên answer[0] = 3.

Thành viên \(1\) rời thành phố \(0\) lúc \(7\). Đi đường \(0\) lúc \(7\) đến thành phố \(1\) lúc \(10\); đi đường \(2\) lúc \(10\) đến thành phố \(2\) lúc \(14\); đi đường \(4\) lúc \(14\) đến thành phố \(3\) lúc \(15\). Đây là thời gian ít nhất, nên answer[1] = 8.

Thành viên \(2\) rời thành phố \(0\) lúc \(9\). Chờ ở thành phố \(0\) đến thời điểm \(0\) ngày hôm sau; đi đường \(1\) đến thành phố \(2\) lúc \(2\), rồi đi đường \(4\) đến thành phố \(3\) lúc \(3\). Tổng thời gian là \(14\) Byou và là ít nhất, nên answer[2] = 14.

Ví dụ này thỏa mãn các nhóm \(1,3,4,5\).

Ví dụ 2

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

6 10 100 9
5 3 4 29
1 0 6 26
0 4 2 7
0 5 18 18
2 0 79 82
3 4 35 46
1 2 15 57
2 4 3 6
4 1 21 83
3 2 47 53
0 2 63
0 4 70
0 4 98
0 5 25
0 5 19
0 4 96
0 5 2
0 3 62
0 3 83

Dữ liệu ra của trình chấm mẫu:

42
32
4
93
99
6
102
60
39

Giải thích

Ví dụ này thỏa mãn các nhóm \(1,2,3,4,5\).

Ví dụ 3

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

8 12 1000000000000000 13
2 0 4451698272827 120985696255786
6 5 78520421713825 342652131468508
2 1 185377268405175 382583457603811
0 4 54350742205838 133614919589507
7 0 68486247989149 651590905094148
0 6 85177550834829 299184420663240
5 2 442329739732459 926608308293721
3 7 78020232822359 913548478810253
1 3 267796317244889 687571310475622
5 4 90590208828121 910324397566584
5 7 8414633059584 17796117322043
4 6 45682367792138 204548471584556
7 2 44779065000162
3 5 79376234836942
4 7 305556687070759
4 3 927935834343174
5 1 663284649258985
2 5 967584209777344
5 2 963749709374595
7 4 484562389171308
1 5 446160773830045
6 4 801452311055604
3 1 744524289545354
0 6 467418420721777
5 6 371181379240653

Dữ liệu ra của trình chấm mẫu:

72937946261976
929038398222642
702857945988825
272921388674172
580895059624855
181808439529442
117602869946965
569788353034530
1181546234307589
244230056736534
513790925121797
617759130113052
674500988551485

Giải thích

Ví dụ này thỏa mãn các nhóm \(1,3,4,5\).

Nguồn

JOI 2020/2021, kỳ thi tuyển chọn mùa xuân, ngày thi thứ 2. Đề của Ủy ban Olympic Tin học Nhật Bản (JCIOI). Bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.

Vương quốc JOI có \(N\) thị trấn, đánh số từ \(1\) đến \(N\). Lãnh thổ được xem là mặt phẳng \(xy\). Thị trấn \(i\) (\(1\le i\le N\)) có tọa độ \((X_i,Y_i)\).

Vương quốc dự định xây \(K\) con đường nối các thị trấn. Chi phí xây một con đường nối thị trấn \(i\) và thị trấn \(j\) (\(i\ne j\)) là \(|X_i-X_j|+|Y_i-Y_j|\) yên. Việc xây đường nối \(i\) với \(j\) và việc xây đường nối \(j\) với \(i\) được xem là cùng một phương án.

Bạn phụ trách dự án và muốn biết chi phí của một số cặp thị trấn để ước tính ngân sách. Trong \(N(N-1)/2\) cặp thị trấn có thể nối bằng đường, bạn muốn biết chi phí của \(K\) con đường rẻ nhất.

Cho tọa độ các thị trấn và \(K\), hãy tính chi phí của \(K\) con đường rẻ nhất.

Dữ liệu vào

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

N K
X_1 Y_1
...
X_N Y_N

Dữ liệu ra

In \(K\) dòng. Dòng thứ \(k\) (\(1\le k\le K\)) chứa chi phí của con đường rẻ thứ \(k\).

Ràng buộc

• \(2\le N\le250000\).
• \(1\le K\le\min(250000,N(N-1)/2)\).
• \(-10^9\le X_i,Y_i\le10^9\) với mọi \(1\le i\le N\).
• \((X_i,Y_i)\ne(X_j,Y_j)\) với mọi \(1\le i<j\le N\).

Phân nhóm

• Nhóm 1 (5 điểm): \(N\le1000\).
• Nhóm 2 (6 điểm): \(Y_i=0\) với mọi \(1\le i\le N\).
• Nhóm 3 (7 điểm): \(K=1\).
• Nhóm 4 (20 điểm): \(K\le10\).
• Nhóm 5 (27 điểm): \(N\le100000\).
• Nhóm 6 (35 điểm): Không có ràng buộc bổ sung.

Ví dụ

3 2
-1 0
0 2
0 0

1
2

5 4
1 -1
2 0
-1 0
0 2
0 -2

2
2
3
3

4 6
0 0
1 0
3 0
4 0

1
1
2
3
3
4

10 10
10 -8
7 2
7 -8
-3 -6
-2 1
-8 6
8 -1
2 4
6 -6
2 -1

3
3
4
5
6
6
6
7
7
7

Nguồn

JOI 2020/2021, kỳ thi tuyển chọn mùa xuân, ngày thi thứ 2. Đề của Ủy ban Olympic Tin học Nhật Bản (JCIOI). Bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.

Cửa hàng JOI bán \(N\) món hàng, đánh số từ \(0\) đến \(N-1\). Giá của món hàng \(i\) là \(P_i\). Hai món hàng bất kỳ có giá khác nhau.

Anna đến mua sắm. Trong các món có chỉ số từ \(L\) đến \(R\), kể cả hai đầu mút, cô muốn mua món rẻ nhất. Anna không biết giá từng món nên sẽ trao đổi với Bruno, nhân viên cửa hàng, để quyết định mua món nào. Bruno biết giá mọi món nhưng không biết \(L,R\).

Anna và Bruno dùng thiết bị viễn thông để gửi các ký tự \(0\) hoặc \(1\). Anna được gửi tối đa \(18\) ký tự cho Bruno; Bruno được gửi tối đa \(10000\) ký tự cho Anna. Bruno muốn gửi càng ít ký tự càng tốt.

Anna được cho \(N,L,R\); Bruno được cho \(N\) và giá mọi món hàng. Hãy viết các chương trình thực hiện chiến lược của Anna và Bruno để Anna xác định chỉ số món hàng cần mua.

Chi tiết cài đặt

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

Tệp Anna.cpp cài đặt chiến lược của Anna, nạp Anna.h bằng chỉ thị #include và cài đặt các hàm:

void InitA(int N, int L, int R);
void ReceiveA(bool x);
int Answer();

• InitA được gọi đúng một lần lúc bắt đầu mỗi bộ dữ liệu. N là số món hàng, L,R xác định đoạn chỉ số mà Anna muốn tìm món rẻ nhất.
• ReceiveA được gọi mỗi khi Bruno gửi một ký tự cho Anna. x là ký tự đó: true biểu diễn \(1\), false biểu diễn \(0\).
• Answer được gọi đúng một lần khi mọi lời gọi trao đổi đã kết thúc. Hàm trả về chỉ số món hàng Anna sẽ mua. Giá trị phải nằm trong đoạn \([L,R]\); nếu không, chương trình bị chấm Wrong Answer [1]. Nếu chỉ số không phải món hàng rẻ nhất cần mua, chương trình bị chấm Wrong Answer [2].

Trong tệp này, bạn có thể gọi hàm sau để Anna gửi một ký tự cho Bruno:

void SendA(bool y);

Tham số y là ký tự gửi đi, với true là \(1\) và false là \(0\).

Tệp Bruno.cpp cài đặt chiến lược của Bruno, nạp Bruno.h bằng chỉ thị #include và cài đặt:

void InitB(int N, std::vector<int> P);
void ReceiveB(bool y);

• InitB được gọi đúng một lần lúc bắt đầu mỗi bộ dữ liệu. N là số món hàng; P là mảng độ dài \(N\), trong đó P[i] là giá món hàng \(i\).
• ReceiveB được gọi mỗi khi Anna gửi một ký tự cho Bruno. y là ký tự đó: true là \(1\), false là \(0\).

Trong tệp này, bạn có thể gọi hàm sau để Bruno gửi một ký tự cho Anna:

void SendB(bool x);

Tham số x là ký tự gửi đi, với true là \(1\) và false là \(0\).

Thứ tự thực hiện

Với mỗi bộ dữ liệu, có hai hàng đợi: \(Q_Y\) chứa các ký tự Anna gửi và \(Q_X\) chứa các ký tự Bruno gửi. Đầu tiên, InitA và InitB được gọi; các ký tự được gửi trong hai hàm này được thêm vào hàng đợi tương ứng. Sau đó, lặp lại quy trình:

• Nếu ít nhất một hàng đợi không rỗng, lấy ký tự ở đầu một hàng đợi không rỗng và gọi ReceiveA hoặc ReceiveB tương ứng. Nếu cả hai đều không rỗng thì không xác định trước hàm nào trong hai hàm sẽ được gọi.
• Khi SendA được gọi trong lúc thực hiện ReceiveA, ký tự gửi đi được thêm vào \(Q_Y\).
• Khi SendB được gọi trong lúc thực hiện ReceiveB, ký tự gửi đi được thêm vào \(Q_X\).
• Khi cả hai hàng đợi đều rỗng, Answer được gọi và chương trình kết thúc.

Anna không được gửi quá \(18\) ký tự; nếu vượt quá thì bị chấm Wrong Answer [3]. Bruno không được gửi quá \(10000\) ký tự; nếu vượt quá thì bị chấm Wrong Answer [4].

Lưu ý quan trọng

• Bạn có thể viết thêm hàm nội bộ hoặc dùng biến toàn cục. Hai tệp nộp được biên dịch cùng grader thành một tệp thực thi. Mọi hàm nội bộ và biến toàn cục cần nằm trong namespace không tên để tránh xung đột với tệp khác. Khi chấm thực tế, Anna và Bruno chạy trong hai tiến trình và không thể chia sẻ biến toàn cục.
• Chương trình không được dùng đầu vào chuẩn, đầu ra chuẩn hoặc trao đổi với các tệp khác bằng bất kỳ cách nào. Được phép ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

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

Trang cuộc thi cung cấp gói gồm grader mẫu và các tệp chương trình mẫu. Đặt grader.cpp, Anna.cpp, Bruno.cpp, Anna.h, Bruno.h trong cùng thư mục, rồi biên dịch:

g++ -std=gnu++17 -O2 -fsigned-char -o grader grader.cpp Anna.cpp Bruno.cpp

Nếu thành công, tệp thực thi grader được tạo. Grader thực tế khác grader mẫu. Grader mẫu chỉ chạy trong một tiến trình, đọc đầu vào chuẩn và ghi kết quả ra đầu ra chuẩn và đầu ra lỗi chuẩn.

Dữ liệu vào

Grader mẫu đọc theo định dạng:

N L R
P_0 P_1 ... P_{N-1}

Dữ liệu ra

Khi chương trình kết thúc bình thường, grader mẫu ghi:

• Nếu đáp án đúng: Accepted: Y X, trong đó \(Y\) là tổng số ký tự Anna gửi cho Bruno và \(X\) là tổng số ký tự Bruno gửi cho Anna.
• Nếu bị chấm sai: loại lỗi, chẳng hạn Wrong Answer [1].

Nếu chương trình thỏa mãn nhiều loại lỗi, grader mẫu chỉ thông báo một loại.

Ràng buộc

• \(1\le N\le1000000\).
• \(0\le L\le R\le N-1\).
• \(1\le P_i\le N\) với mọi \(0\le i\le N-1\).
• \(P_i\ne P_j\) với mọi \(0\le i<j\le N-1\).

Phân nhóm

• Nhóm 1 (1 điểm): \(N\le1000\).
• Nhóm 2 (9 điểm): \(N\le10000\).
• Nhóm 3 (90 điểm): Không có ràng buộc bổ sung. Điểm được tính như dưới đây.

Gọi \(T\) là số ký tự lớn nhất mà Bruno gửi cho Anna trên tất cả bộ dữ liệu của nhóm 3.

Ở đây, \(\lfloor x\rfloor\) là số nguyên lớn nhất không vượt quá \(x\).

Ví dụ giao tiếp

Ví dụ 1

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

4 0 2
3 1 4 2

Lời gọi hàm

Giải thích

Bảng ghi các lời gọi hàm tương ứng với đầu vào mẫu.

Ví dụ này thỏa mãn các nhóm \(1,2,3\).

Nguồn

JOI 2020/2021, kỳ thi tuyển chọn mùa xuân, ngày thi thứ 2. Đề của Ủy ban Olympic Tin học Nhật Bản (JCIOI). Bản dịch tiếng Việt theo giấy phép CC BY-SA 4.0.