JOI 2021 - Trại huấn luyện mùa xuân - Ngày 4

Tại công viên IOI sắp diễn ra \(N\) sự kiện, được đánh số từ \(1\) đến \(N\). Sự kiện thứ \(i\) bắt đầu vào thời điểm \(L_i+0.1\) và kết thúc vào thời điểm \(R_i-0.1\), trong đó \(L_i\) và \(R_i\) là các số nguyên.

JOI-kun muốn tham dự đúng \(K\) sự kiện. Cậu không được đến sau khi một sự kiện bắt đầu hoặc rời đi trước khi sự kiện đó kết thúc. Bỏ qua thời gian di chuyển giữa các địa điểm tổ chức sự kiện.

JOI-kun muốn ưu tiên những sự kiện có chỉ số nhỏ. Cụ thể, gọi \(a_1,\ldots,a_K\) là các chỉ số sự kiện được chọn, được sắp xếp sao cho \(1\le a_1<\cdots<a_K\le N\). Cậu muốn dãy \((a_1,\ldots,a_K)\) nhỏ nhất có thể theo thứ tự từ điển.

Dãy \((a_1,\ldots,a_K)\) nhỏ hơn dãy \((b_1,\ldots,b_K)\) theo thứ tự từ điển khi và chỉ khi tồn tại \(j\) (\(1\le j\le K\)) sao cho \(a_\ell=b_\ell\) với mọi \(1\le\ell<j\) và \(a_j<b_j\).

Cho thông tin về các sự kiện và số \(K\), hãy xác định JOI-kun có thể tham dự đúng \(K\) sự kiện hay không. Nếu có, hãy tìm các sự kiện cậu cần chọn theo yêu cầu trên.

Dữ liệu vào

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

N K
L_1 R_1
...
L_N R_N

Mọi giá trị đầu vào đều là số nguyên.

Dữ liệu ra

Nếu không thể tham dự đúng \(K\) sự kiện, xuất một dòng chứa -1.

Nếu có thể, xuất \(K\) dòng. Dòng thứ \(j\) chứa \(a_j\), với \(1\le a_1<\cdots<a_K\le N\), sao cho dãy chỉ số này nhỏ nhất theo thứ tự từ điển trong tất cả các cách chọn hợp lệ.

Ràng buộc

• \(1\le N\le 100\,000\).
• \(1\le K\le N\).
• \(1\le L_i<R_i\le 1\,000\,000\,000\) với mọi \(1\le i\le N\).

Phân nhóm

1. \(7\) điểm: \(L_i\le L_{i+1}\) với mọi \(1\le i\le N-1\).
2. \(1\) điểm: \(N\le 20\).
3. \(31\) điểm: \(N\le 3000\).
4. \(61\) điểm: Không có ràng buộc bổ sung.

Ví dụ

5 4
1 3
2 5
8 9
6 8
10 15

1
3
4
5

4 3
1 4
3 5
4 9
7 10

-1

10 6
77412002 93858605
244306432 318243514
280338037 358494212
439397354 492065507
485779890 529132783
571714810 632053254
659767854 709114867
718405631 733610573
786950301 815106357
878719468 899999649

1
2
4
6
7
8

20 16
250732298 258217736
26470443 34965880
252620676 260043105
692063405 697656580
497457675 504191511
391372149 397942668
858168758 867389085
235756850 241022021
585764751 593366541
207824318 217052204
661682908 671226688
886273261 892279963
770109416 778960597
264372562 270395107
176883483 186662376
509929119 519063796
109491630 118520141
162731982 168101507
662727316 668317158
757072772 765493222

1
2
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Nguồn

JOI 2020/2021, Spring Training Camp, Contest 4. Tác giả: 髙谷悠太. Bản Việt hóa từ đề chính thức của Ủy ban Olympic Tin học Nhật Bản, theo CC BY-SA 4.0.

Vương quốc JOI là một hòn đảo được biển bao quanh, có dạng một bảng vuông gồm \(N\) hàng và \(N\) cột. Hướng dọc là Bắc-Nam, hướng ngang là Tây-Đông. Ô ở hàng thứ \(r+1\) tính từ phía Bắc và cột thứ \(c+1\) tính từ phía Tây được ký hiệu là \((r,c)\), với \(0\le r,c\le N-1\).

Nữ hoàng Anna muốn mời Bruno dự tiệc. Cô đã chọn \(K=7\) ô làm địa điểm dự kiến, đánh số từ \(0\) đến \(K-1\); địa điểm dự kiến thứ \(i\) là ô \((R_i,C_i)\). Không có địa điểm dự kiến nào tiếp giáp với biển. Địa điểm tổ chức chính thức chỉ được quyết định vào ngày diễn ra bữa tiệc.

Vào ngày hôm trước, Anna đặt một lá cờ ở mọi ô, mỗi lá cờ ghi một số nguyên từ \(1\) đến \(1\,000\,000\,000\), để giúp Bruno tìm đường.

Vào ngày diễn ra bữa tiệc, Bruno chỉ được thông báo chỉ số \(t\) (\(0\le t\le K-1\)) của địa điểm được chọn. Sau đó, cậu đáp trực thăng xuống một ô không tiếp giáp với biển và bắt đầu đi đến bữa tiệc.

Bruno không biết tọa độ hiện tại của mình, nhưng biết các hướng Bắc, Nam, Đông, Tây. Cậu chỉ nhìn thấy lá cờ ở ô hiện tại và tám ô xung quanh. Cụ thể, khi Bruno ở \((a,b)\), với \(1\le a,b\le N-2\), cậu nhìn thấy chín ô sau, theo thứ tự:

Bruno có thể thực hiện một trong năm hành động:

Bruno không được đến muộn, nên phải đến địa điểm tổ chức bằng số hành động ít nhất có thể. Với các điều kiện của bài toán, điều này bảo đảm cậu không bao giờ đi vào ô tiếp giáp với biển.

Việc viết các số lớn lên cờ rất phiền phức, nên Anna muốn giảm nhỏ nhất có thể giá trị lớn nhất được ghi trên các lá cờ. Hãy cài đặt chiến lược của Anna để ghi số lên cờ và chiến lược của Bruno để đi đến địa điểm tổ chức bằng số hành động ít nhất.

Chi tiết cài đặt

Cần nộp hai tệp Anna.cpp và Bruno.cpp.

Trong Anna.cpp, sử dụng #include "Anna.h" và cài đặt hàm:

void Anna(int N, int K, std::vector<int> R, std::vector<int> C);

Hàm này cài đặt cách Anna ghi số lên cờ và được gọi đúng một lần ở đầu mỗi tình huống:

• N là số hàng và số cột của bảng.
• K là số địa điểm dự kiến, bằng \(7\).
• R và C là hai mảng có độ dài K; R[i], C[i] là tọa độ địa điểm dự kiến thứ \(i\), với \(0\le i\le K-1\).
• Các tham số tuân theo mục Ràng buộc.

Trong mỗi lần gọi Anna, chương trình phải gọi hàm sau đúng \(N^2\) lần, mỗi ô đúng một lần:

void SetFlag(int r, int c, int value);

Hàm này ghi số value lên lá cờ ở ô (r,c).

Nếu một lời gọi SetFlag bị coi là sai, chương trình bị kết thúc ngay lập tức.

Trong Bruno.cpp, sử dụng #include "Bruno.h" và cài đặt hàm:

std::vector<int> Bruno(int K, std::vector<int> value);

Hàm này được gọi đúng một lần cho mỗi tình huống, sau khi Anna đã được gọi:

• K là số địa điểm dự kiến, bằng \(7\).
• value là mảng có độ dài \(9\), chứa các số ghi trên cờ ở ô hiện tại và tám ô xung quanh. Khi vị trí hiện tại là \((a,b)\), các phần tử value[0] đến value[8] tương ứng với chín ô theo đúng thứ tự đã liệt kê ở phần mô tả.
• Với mỗi \(t=0,1,\ldots,K-1\), hàm phải quyết định hành động tiếp theo nếu địa điểm tổ chức là địa điểm dự kiến thứ \(t\).
• Giá trị trả về là mảng có độ dài K. Phần tử thứ \(i+1\) của mảng, tức phần tử có chỉ số \(i\), là hành động khi \(t=i\).

Nếu có nhiều cách đi tối ưu đến một địa điểm, có thể trả về bất kỳ hành động tiếp theo nào thuộc một trong các cách đó.

Mỗi bộ kiểm thử gồm \(Q\) tình huống. Anna và Bruno được gọi luân phiên, mỗi hàm tổng cộng \(Q\) lần, chứ không phải mô phỏng liên tiếp toàn bộ hành trình của Bruno trong một tình huống.

Lưu ý

Có thể cài đặt hàm phụ trợ hoặc khai báo biến toàn cục. Hai tệp nộp được liên kết cù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ộ phải nằm trong không gian tên vô danh để tránh xung đột giữa các tệp. Khi chấm, tệp thực thi được chạy thành hai tiến trình, một cho Anna và một cho Bruno. 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, đầu ra chuẩn hoặc giao tiếp với các tệp khác bằng bất kỳ cách nào. Có thể ghi thông tin gỡ lỗi ra đầu ra lỗi chuẩn.

Trình tự chấm

Các tình huống được đánh số từ \(0\) đến \(Q-1\). Trong mỗi tình huống, các giá trị sau được cố định: kích thước bảng \(N\), số địa điểm dự kiến \(K=7\), các ô \((R_0,C_0),\ldots,(R_{K-1},C_{K-1})\), và vị trí hiện tại \((a,b)\) của Bruno. Các giá trị này thỏa mãn mục Ràng buộc.

Với từng tình huống \(k=0,1,\ldots,Q-1\) theo thứ tự:

1. Gọi Anna với các tham số của tình huống \(k\) như mô tả trong phần cài đặt, để ghi số lên các lá cờ.
2. Gọi Bruno với các tham số của tình huống \(k\) như mô tả trong phần cài đặt, để quyết định các hành động tiếp theo.

Nếu có lỗi Wrong Answer trong quá trình này, chương trình bị kết thúc ngay và bộ kiểm thử đó được coi là sai.

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

Gói tệp hỗ trợ trong phần đính kèm chứa trình chấm mẫu grader.cpp và mã nguồn mẫu của các tệp cần nộp. Đặt grader.cpp, Anna.cpp, Bruno.cpp, Anna.h, Bruno.h trong cùng thư mục và chạy:

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

Nếu biên dịch thành công, tệp thực thi grader được tạo ra. Trình chấm thật khác trình chấm mẫu. Trình chấm mẫu chạy trong một tiến trình, đọ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

Đầu vào của trình chấm mẫu có dạng:

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

Dữ liệu cho mỗi tình huống có dạng:

N K
R_0 C_0
...
R_{K-1} C_{K-1}
a b

Mọi giá trị đầu vào đều là số nguyên. Riêng khi dùng trình chấm mẫu, có thể chọn \(3\le N\le 100\) và \(1\le K\le 7\). Các khoảng này khác với ràng buộc của dữ liệu chấm thật.

Dữ liệu ra

Khi chương trình kết thúc thành công, trình chấm mẫu ghi thông tin sau ra đầu ra chuẩn:

• Nếu đúng, ghi số lớn nhất được Anna viết lên cờ, chẳng hạn Accepted : Maximum value = 12.
• Nếu sai, ghi loại lỗi, chẳng hạn Wrong Answer [1].

Nếu đồng thời vi phạm nhiều loại lỗi, trình chấm mẫu chỉ thông báo một trong các loại đó.

Ràng buộc

• \(1\le Q\le 300\).
• \(5\le N\le 100\).
• \(K=7\).
• \(1\le R_i\le N-2\) với mọi \(0\le i\le K-1\).
• \(1\le C_i\le N-2\) với mọi \(0\le i\le K-1\).
• \((R_i,C_i)\ne(R_j,C_j)\) với mọi \(0\le i<j\le K-1\).
• \(1\le a\le N-2\).
• \(1\le b\le N-2\).

Phân nhóm

Nếu có bất kỳ bộ kiểm thử nào bị chấm Wrong Answer, điểm của toàn bộ bài là \(0\).

Nếu chương trình đúng trên tất cả các bộ kiểm thử, gọi \(L\) là số nguyên lớn nhất được ghi trên các lá cờ trong toàn bộ các bộ kiểm thử. Điểm được tính như sau:

• Nếu \(70\,001\le L\le 1\,000\,000\,000\): \(7\) điểm.
• Nếu \(10\,001\le L\le 70\,000\): \(13\) điểm.
• Nếu \(2001\le L\le 10\,000\): \(19\) điểm.
• Nếu \(21\le L\le 2000\): \(\left\lfloor 50-12.5\log_{10}\left(\frac{L}{20}\right)\right\rfloor\) điểm, tức làm tròn xuống số nguyên gần nhất.

Nếu \(L\le 20\), dùng bảng sau:

Ví dụ giao tiếp

Ví dụ 1

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

1
5 7
1 1
1 2
2 1
2 2
2 3
3 2
3 3
1 1

Các số Anna ghi trên cờ

Trong ví dụ này, giả sử Anna ghi các số sau lên \(25\) lá cờ. Các hàng/cột được liệt kê theo thứ tự từ Bắc xuống Nam và từ Tây sang Đông.

Lời gọi và giá trị trả về

Giải thích

Trong ví dụ này, \((a,b)=(1,1)\). Với các địa điểm dự kiến \(0,1,2,3\), hành động tiếp theo phải như sau:

• Chọn địa điểm \(0\): bữa tiệc ở \((1,1)\), nên phải thực hiện hành động \(4\).
• Chọn địa điểm \(1\): bữa tiệc ở \((1,2)\), nên phải thực hiện hành động \(0\).
• Chọn địa điểm \(2\): bữa tiệc ở \((2,1)\), nên phải thực hiện hành động \(2\).
• Chọn địa điểm \(3\): bữa tiệc ở \((2,2)\), nên có thể thực hiện hành động \(0\) hoặc \(2\).

Ví dụ trả về [4,0,2,2,2,0,0]. Có thể có nhiều cách đi tối ưu; chẳng hạn trả về [4,0,2,0,2,0,2] cũng được coi là đúng.

Ví dụ 2

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

1
100 7
3 21
16 9
44 36
44 78
45 78
67 59
90 22
84 59

Giải thích

Chẳng hạn, hàm Bruno trả về [3,1,1,0,0,3,2] thì được coi là đúng.

Nguồn

JOI 2020/2021, Spring Training Camp, Contest 4. Tác giả: 米田優峻 và 米田寛峻. Bản Việt hóa từ đề chính thức của Ủy ban Olympic Tin học Nhật Bản, theo CC BY-SA 4.0.

Bitaro là một phóng viên chuyên viết bài về các kỳ thi lập trình. Vài ngày nữa sẽ diễn ra một kỳ thi lập trình quốc tế, và Bitaro đang chuẩn bị viết bài về kỳ thi này.

Có \(N\) thí sinh, được đánh số từ \(1\) đến \(N\). Mỗi thí sinh có một điểm xếp hạng, là số nguyên từ \(1\) đến \(1\,000\,000\,000\), thể hiện năng lực lập trình thi đấu của người đó.

Qua phỏng vấn các thí sinh, Bitaro biết rằng với mỗi \(i\) (\(1\le i\le N\)), điểm xếp hạng của thí sinh \(i\) lớn hơn hoặc bằng điểm xếp hạng của thí sinh \(A_i\) (\(1\le A_i\le N\)). Có thể xảy ra \(A_i=i\).

Sau các cuộc phỏng vấn, một công ty quản lý hệ thống xếp hạng gửi cho Bitaro danh sách ghi rằng điểm xếp hạng của thí sinh \(i\) là \(H_i\). Tuy nhiên, khi định viết bài dựa trên các thông tin này, Bitaro nhận ra rằng danh sách có thể chứa lỗi.

Hạn nộp bài đã gần kề nên Bitaro không còn thời gian lấy danh sách chính xác. Cậu quyết định sửa điểm xếp hạng của một số thí sinh trong danh sách để danh sách không mâu thuẫn với bất kỳ thông tin nào thu được từ các cuộc phỏng vấn.

Với chi phí \(C_i\), Bitaro có thể đổi điểm xếp hạng của thí sinh \(i\) trong danh sách thành một số nguyên bất kỳ từ \(1\) đến \(1\,000\,000\,000\). Hãy tính tổng chi phí nhỏ nhất để sửa danh sách sao cho thỏa mãn tất cả các thông tin phỏng vấn.

Dữ liệu vào

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

N
A_1 H_1 C_1
...
A_N H_N C_N

Mọi giá trị đầu vào đều là số nguyên.

Dữ liệu ra

Xuất một dòng chứa tổng chi phí nhỏ nhất.

Ràng buộc

• \(2\le N\le 200\,000\).
• \(1\le A_i\le N\) với mọi \(1\le i\le N\).
• \(1\le H_i\le 1\,000\,000\,000\) với mọi \(1\le i\le N\).
• \(1\le C_i\le 1\,000\,000\,000\) với mọi \(1\le i\le N\).

Phân nhóm

1. \(14\) điểm: \(N\le 5000\), \(A_1=1\) và \(A_i\le i-1\) với mọi \(2\le i\le N\).
2. \(65\) điểm: \(A_1=1\) và \(A_i\le i-1\) với mọi \(2\le i\le N\).
3. \(21\) điểm: Không có ràng buộc bổ sung.

Ví dụ

6
1 6 5
1 3 6
1 8 4
3 4 9
2 2 5
2 5 6

14

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

0

20
1 7 381792936
1 89 964898447
1 27 797240712
3 4 299745243
2 18 113181438
2 20 952129455
4 34 124298446
4 89 33466733
7 40 109601410
5 81 902931267
2 4 669879699
8 23 785166502
8 1 601717183
8 26 747624379
1 17 504589209
9 24 909134233
16 56 236448090
8 94 605526613
5 90 481898834
9 34 183442771

2711043927

20
15 62 418848971
13 5 277275513
14 60 80376452
12 14 256845164
12 42 481331310
6 86 290168639
3 98 947342135
3 19 896070909
16 39 48034188
8 29 925729089
18 97 420006994
13 51 454182928
19 61 822405612
13 37 148425187
15 77 474094143
14 27 272926693
18 43 566552069
9 93 790433300
10 73 61654171
14 28 334498030

4012295156

Nguồn

JOI 2020/2021, Spring Training Camp, Contest 4. Tác giả: 戸髙空. Bản Việt hóa từ đề chính thức của Ủy ban Olympic Tin học Nhật Bản, theo CC BY-SA 4.0.