JOI 2014 Final Camp - Ngày 1

Bộ đề bài

Trở lại kỳ thi
# Bài tập Điểm Thời gian: Giới hạn bộ nhớ
1 JOI 2014 - Bus 100 (p) 1.0s 256M
2 JOI 2014 - Growing Vegetables is Fun 100 (p) 1.0s 256M
3 JOI 2014 - Historical Research 100 (p) 4.0s 512M
4 JOI 2014 - Ramen 100 (p) 1.0s 256M

1. JOI 2014 - Bus

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

JOI là một sinh viên đại học đi học bằng xe buýt. Nhà của JOI và trường đại học đều nằm trong thành phố IOI. Thành phố có \(N\) trạm xe buýt, được đánh số từ \(1\) đến \(N\). Trạm gần nhà JOI nhất là trạm \(1\), còn trạm gần trường nhất là trạm \(N\).

Có \(M\) chuyến xe buýt hoạt động trong thành phố. Mỗi chuyến chạy đúng một lần mỗi ngày, xuất phát từ một trạm xác định vào một thời điểm xác định và đến một trạm xác định vào một thời điểm xác định. Không có chuyến nào kéo dài sang ngày hôm sau. JOI không thể lên hoặc xuống xe giữa hành trình của một chuyến.

Mỗi ngày, JOI đi một hoặc nhiều chuyến xe buýt để đến trường. Có thể bỏ qua thời gian cần để chuyển xe: để lên một chuyến xuất phát từ một trạm vào một thời điểm nào đó, JOI chỉ cần đến trạm ấy trước hoặc đúng thời điểm xe xuất phát. JOI cũng có thể đi qua cùng một trạm nhiều lần.

Với những điều kiện trên, JOI muốn biết mình nên rời nhà khi nào để đến trường kịp giờ học. Tuy nhiên, giờ bắt đầu tiết học đầu tiên thay đổi theo từng ngày. Với \(Q\) ngày, đã biết thời điểm muộn nhất JOI phải đến trạm \(N\) để kịp giờ học trong từng ngày. Trong mỗi ngày đó, JOI có thể đến trạm \(1\) muộn nhất vào thời điểm nào mà vẫn kịp giờ học?

Yêu cầu

Cho thông tin về các chuyến xe buýt và thời điểm muộn nhất phải đến trạm \(N\) trong từng ngày của \(Q\) ngày, hãy tìm thời điểm muộn nhất JOI có thể đến trạm \(1\) trong mỗi ngày.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn:

  • Dòng đầu chứa hai số nguyên \(N, M\) cách nhau bởi dấu cách, cho biết thành phố có \(N\) trạm và \(M\) chuyến xe buýt.
  • Trong \(M\) dòng tiếp theo, dòng thứ \(i\) (\(1 \le i \le M\)) chứa bốn số nguyên \(A_i, B_i, X_i, Y_i\) cách nhau bởi dấu cách, với \(1 \le A_i \le N\), \(1 \le B_i \le N\) và \(A_i \ne B_i\). Chuyến xe thứ \(i\) xuất phát từ trạm \(A_i\) vào thời điểm \(X_i\) và đến trạm \(B_i\) vào thời điểm \(Y_i\). Thời điểm được tính bằng số mili giây đã trôi qua kể từ đúng \(0\) giờ.
  • Dòng tiếp theo chứa số nguyên \(Q\), là số ngày được cho thời hạn đến trạm \(N\).
  • Trong \(Q\) dòng tiếp theo, dòng thứ \(j\) (\(1 \le j \le Q\)) chứa số nguyên \(L_j\): trong ngày thứ \(j\), JOI phải đến trạm \(N\) trước hoặc đúng thời điểm \(L_j\).

Dữ liệu ra

Ghi \(Q\) dòng ra đầu ra chuẩn. Dòng thứ \(j\) (\(1 \le j \le Q\)) chứa một số nguyên là thời điểm muộn nhất JOI có thể đến trạm \(1\) trong ngày thứ \(j\) mà vẫn đến trường kịp giờ học. Nếu không thể đến trường kịp giờ, ghi -1.

Ràng buộc

Tất cả dữ liệu vào thỏa mãn:

  • \(2 \le N \le 100\,000\).
  • \(1 \le M \le 300\,000\).
  • \(0 \le X_i < Y_i < 86\,400\,000\) (\(1 \le i \le M\)).
  • \(1 \le Q \le 100\,000\).
  • \(0 \le L_j < 86\,400\,000\) (\(1 \le j \le Q\)).

Ở đây, \(86\,400\,000 = 24 \times 60 \times 60 \times 1000\).

Phân nhóm

  • Nhóm 1 (20 điểm): \(N \le 2\,000\), \(M \le 2\,000\), \(Q = 1\).
  • Nhóm 2 (15 điểm): \(N \le 2\,000\), \(M \le 2\,000\).
  • Nhóm 3 (15 điểm): \(Q = 1\).
  • Nhóm 4 (50 điểm): Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
5 6
1 2 10 25
1 2 12 30
2 5 26 50
1 5 5 20
1 4 30 40
4 5 50 70
4
10
30
60
100
Output 
-1
5
10
30
Giải thích

Không thể đến trạm \(5\) trước hoặc đúng thời điểm \(10\).

Để đến trước hoặc đúng thời điểm \(30\), JOI có thể lên chuyến xe thứ \(4\) vào thời điểm \(5\).

Để đến trước hoặc đúng thời điểm \(60\), JOI có thể đi như sau:

  • Lên chuyến xe thứ \(1\) vào thời điểm \(10\).
  • Đến trạm \(2\) vào thời điểm \(25\), đợi \(1\) mili giây rồi lên chuyến xe thứ \(3\).
  • Đến trạm \(5\) vào thời điểm \(50\).

Để đến trước hoặc đúng thời điểm \(100\), JOI có thể đi như sau:

  • Lên chuyến xe thứ \(5\) vào thời điểm \(30\).
  • Đến trạm \(4\) vào thời điểm \(40\), đợi \(10\) mili giây rồi lên chuyến xe thứ \(6\).
  • Đến trạm \(5\) vào thời điểm \(70\).

Ví dụ 2

Input 
3 8
1 2 1 5
1 3 0 1
1 3 2 8
2 3 2 3
2 3 3 4
2 3 4 5
2 3 5 6
2 3 6 7
6
3
4
5
6
7
8
Output 
0
0
0
1
1
2

2. JOI 2014 - Growing Vegetables is Fun

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

JOI thích làm vườn và năm nào cũng trồng một loài cây có tên là cây IOI trên mảnh vườn của mình. Mảnh vườn được chia thành \(N\) ô nằm trên một hàng theo hướng đông–tây, đánh số từ \(1\) đến \(N\) theo thứ tự từ phía tây. Có tất cả \(N\) cây IOI, mỗi ô trồng một cây. Đến mùa xuân, cây IOI trồng ở ô \(i\) cao đến độ cao \(h_i\) rồi không cao thêm nữa.

Khi đến thăm vườn vào mùa xuân, JOI phát hiện các cây IOI được bố trí khác với dự định. Cây IOI cần nhiều ánh nắng: nếu ở cả phía có số ô nhỏ hơn và phía có số ô lớn hơn đều có một cây IOI cao hơn nó, cây đó sẽ héo trước khi mùa hè đến. Vì vậy, để không cây IOI nào bị héo, cần thỏa mãn điều kiện sau: với mọi số nguyên \(i\) thỏa mãn \(2 \le i \le N-1\), ít nhất một trong hai điều kiện dưới đây phải đúng.

  • Với mọi số nguyên \(j\) thỏa mãn \(1 \le j \le i-1\), ta có \(h_j \le h_i\).
  • Với mọi số nguyên \(k\) thỏa mãn \(i+1 \le k \le N\), ta có \(h_k \le h_i\).

Cây IOI rất đắt tiền nên JOI quyết định sắp xếp lại chúng để không cây nào bị héo. Vì cây IOI rất lớn và dễ bị tổn thương, JOI chỉ có thể đổi chỗ hai cây kề nhau. Cụ thể, trong một thao tác, JOI chọn một ô \(i\) bất kỳ (\(1 \le i \le N-1\)) rồi đổi chỗ cây ở ô \(i\) với cây ở ô \(i+1\). Mùa hè càng đến gần, nguy cơ cây bị héo càng cao, nên JOI muốn biết số thao tác ít nhất cần thực hiện để không cây IOI nào bị héo.

Yêu cầu

Cho số ô trong vườn và độ cao của từng cây IOI, hãy viết chương trình tìm số thao tác ít nhất cần thực hiện để sắp xếp lại các cây sao cho không cây nào bị héo.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn:

  • Dòng đầu chứa số nguyên \(N\), là số ô trong vườn của JOI.
  • Trong \(N\) dòng tiếp theo, dòng thứ \(i\) (\(1 \le i \le N\)) chứa số nguyên \(D_i\), là độ cao của cây IOI ban đầu được trồng ở ô \(i\) khi mùa xuân đến.

Dữ liệu ra

Ghi ra đầu ra chuẩn một dòng chứa một số nguyên là số thao tác ít nhất cần thực hiện.

Ràng buộc

Tất cả dữ liệu vào thỏa mãn:

  • \(3 \le N \le 300\,000\).
  • \(1 \le D_i \le 1\,000\,000\,000\) (\(1 \le i \le N\)).

Phân nhóm

  • Nhóm 1 (10 điểm): \(N \le 8\).
  • Nhóm 2 (20 điểm): \(N \le 20\).
  • Nhóm 3 (15 điểm): \(N \le 5\,000\).
  • Nhóm 4 (55 điểm): Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
6
2
8
4
5
3
6
Output 
3
Giải thích

Ban đầu, các cây IOI được bố trí như hình dưới đây.

Chẳng hạn, thực hiện các thao tác như hình dưới đây sẽ tạo được một cách bố trí không cây nào bị héo sau \(3\) thao tác: đổi chỗ cây ở ô \(2\) và ô \(3\); đổi chỗ cây ở ô \(3\) và ô \(4\); rồi đổi chỗ cây ở ô \(5\) và ô \(6\). Cách bố trí cuối cùng không làm cây IOI nào bị héo.

Ví dụ 2

Input 
5
4
4
2
4
4
Output 
2
Giải thích

Chỉ cần đưa cây IOI ở ô \(3\) đến ô \(1\) hoặc ô \(5\).

Ví dụ 3

Input 
4
1
3
4
2
Output 
0
Giải thích

Trong ví dụ này, không cần thực hiện thao tác đổi chỗ nào.

3. JOI 2014 - Historical Research

Điểm: 100 (p) Thời gian: 4.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Giáo sư JOI, chuyên gia hàng đầu về lịch sử nước IOI, nhận được một cuốn nhật ký được cho là do một cư dân nước IOI thời cổ đại viết. Để nghiên cứu cuộc sống ở nước IOI thời cổ đại thông qua cuốn nhật ký này, giáo sư quyết định khảo sát các sự kiện được ghi lại trong đó.

Cuốn nhật ký ghi lại các sự kiện xảy ra trong \(N\) ngày, mỗi ngày đúng một sự kiện. Các sự kiện được chia thành nhiều loại. Loại của sự kiện vào ngày thứ \(i\) (\(1 \le i \le N\)) được biểu diễn bằng số nguyên \(X_i\). Giá trị \(X_i\) càng lớn thì sự kiện được xem là có quy mô càng lớn.

Giáo sư JOI quyết định phân tích nhật ký theo cách sau:

  1. Chọn một số ngày liên tiếp trong \(N\) ngày của cuốn nhật ký làm khoảng thời gian cần phân tích.
  2. Định nghĩa độ quan trọng của loại sự kiện \(t\) bằng \(t\) nhân với số sự kiện thuộc loại \(t\) trong khoảng thời gian đó.
  3. Tính độ quan trọng của tất cả các loại sự kiện và lấy giá trị lớn nhất.

Giáo sư JOI giao cho bạn viết một chương trình phục vụ việc phân tích. Chương trình cần tìm được độ quan trọng lớn nhất khi được cho một khoảng thời gian cần phân tích.

Yêu cầu

Cho loại sự kiện của \(N\) ngày trong nhật ký và \(Q\) truy vấn, mỗi truy vấn chỉ định một khoảng thời gian trong nhật ký. Hãy viết chương trình tìm độ quan trọng lớn nhất của các loại sự kiện đối với từng truy vấn.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn:

  • Dòng đầu chứa hai số nguyên \(N, Q\) cách nhau bởi dấu cách, cho biết nhật ký có \(N\) ngày và có \(Q\) truy vấn.
  • Dòng tiếp theo chứa \(N\) số nguyên \(X_1, \ldots, X_N\) cách nhau bởi dấu cách. \(X_i\) (\(1 \le i \le N\)) là loại sự kiện của ngày thứ \(i\).
  • Trong \(Q\) dòng tiếp theo, dòng thứ \(j\) (\(1 \le j \le Q\)) chứa hai số nguyên \(A_j, B_j\) cách nhau bởi dấu cách, với \(1 \le A_j \le B_j \le N\). Truy vấn thứ \(j\) xét khoảng thời gian từ ngày thứ \(A_j\) đến hết ngày thứ \(B_j\).

Dữ liệu ra

Ghi \(Q\) dòng ra đầu ra chuẩn. Dòng thứ \(j\) (\(1 \le j \le Q\)) chứa một số nguyên là độ quan trọng lớn nhất đối với truy vấn thứ \(j\).

Ràng buộc

Tất cả dữ liệu vào thỏa mãn:

  • \(1 \le N \le 100\,000\).
  • \(1 \le Q \le 100\,000\).
  • \(1 \le X_i \le 1\,000\,000\,000\) (\(1 \le i \le N\)).

Phân nhóm

  • Nhóm 1 (5 điểm): \(N \le 100\), \(Q \le 100\).
  • Nhóm 2 (10 điểm): \(N \le 5\,000\), \(Q \le 5\,000\).
  • Nhóm 3 (25 điểm): Không tồn tại \(i, j\) với \(1 \le i,j \le Q\), \(i \ne j\) sao cho \(A_i \le A_j \le B_j \le B_i\).
  • Nhóm 4 (60 điểm): Không có ràng buộc bổ sung.

Ví dụ

Ví dụ 1

Input 
5 5
9 8 7 8 9
1 2
3 4
4 4
1 4
2 4
Output 
9
8
8
16
16
Giải thích
  • Nhật ký có \(5\) ngày; mỗi sự kiện thuộc một trong các loại \(7, 8, 9\).
  • Từ ngày \(1\) đến ngày \(2\), độ quan trọng của loại \(7\) là \(7 \times 0 = 0\), của loại \(8\) là \(8 \times 1 = 8\), của loại \(9\) là \(9 \times 1 = 9\). Giá trị lớn nhất là \(9\).
  • Từ ngày \(3\) đến ngày \(4\), độ quan trọng của loại \(7\) là \(7 \times 1 = 7\), của loại \(8\) là \(8 \times 1 = 8\), của loại \(9\) là \(9 \times 0 = 0\). Giá trị lớn nhất là \(8\).
  • Trong ngày \(4\), độ quan trọng của loại \(7\) là \(7 \times 0 = 0\), của loại \(8\) là \(8 \times 1 = 8\), của loại \(9\) là \(9 \times 0 = 0\). Giá trị lớn nhất là \(8\).
  • Từ ngày \(1\) đến ngày \(4\), độ quan trọng của loại \(7\) là \(7 \times 1 = 7\), của loại \(8\) là \(8 \times 2 = 16\), của loại \(9\) là \(9 \times 1 = 9\). Giá trị lớn nhất là \(16\).
  • Từ ngày \(2\) đến ngày \(4\), độ quan trọng của loại \(7\) là \(7 \times 1 = 7\), của loại \(8\) là \(8 \times 2 = 16\), của loại \(9\) là \(9 \times 0 = 0\). Giá trị lớn nhất là \(16\).

Ví dụ 2

Input 
8 4
9 9 19 9 9 15 9 19
1 4
4 6
3 5
5 8
Output 
27
18
19
19
Giải thích

Dữ liệu vào này thỏa mãn ràng buộc của subtask \(3\).

Ví dụ 3

Input 
12 15
15 9 3 15 9 3 3 8 16 9 3 17
2 7
2 5
2 2
1 12
4 12
3 6
11 12
1 7
2 6
3 5
3 10
7 10
1 4
4 8
4 8
Output 
18
18
9
30
18
15
17
30
18
15
18
16
30
15
15

4. JOI 2014 - Ramen

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

JOI và IOI đều thích mì ramen. JOI thích ramen có vị thanh nhẹ, còn IOI thích ramen có vị đậm béo. Thị trấn nơi hai bạn sống có \(N\) quán ramen, được đánh số từ \(0\) đến \(N-1\).

Hai bạn chưa biết quán nào bán ramen đậm béo, quán nào bán ramen thanh nhẹ. Vì vậy, JOI và IOI quyết định đi ăn thử ở các quán trong thị trấn để xác định quán bán ramen thanh nhẹ nhất và quán bán ramen đậm béo nhất.

Mỗi quán có một độ đậm béo xác định cho món ramen của mình. Độ đậm béo là một số nguyên từ \(0\) đến \(N-1\), và độ đậm béo của các quán đôi một khác nhau. Mỗi ngày, JOI và IOI có thể đến hai quán, nếm thử và so sánh để biết quán nào trong hai quán có độ đậm béo cao hơn.

Vì sức khỏe, hai bạn muốn giới hạn số ngày ăn thử và so sánh ramen ở mức không quá \(600\) ngày.

Yêu cầu

Cho số quán ramen \(N\) trong thị trấn, hãy viết chương trình xác định quán có độ đậm béo thấp nhất và quán có độ đậm béo cao nhất trong số \(N\) quán, bằng cách ăn thử và so sánh trong không quá \(600\) ngày.

Chi tiết cài đặt

Bạn cần viết một chương trình cài đặt cách xác định hai quán nói trên bằng không quá \(600\) lần so sánh. Gói chương trình được cung cấp có tệp tiêu đề ramen.h; mã nguồn của bạn khai báo:

C++
#include "ramen.h"

Chương trình phải cài đặt hàm sau:

C++
void Ramen(int N);

Hàm này được gọi đúng một lần cho mỗi bộ dữ liệu. Tham số N là số quán ramen trong thị trấn. Hàm phải dùng các lời gọi Compare để xác định quán có độ đậm béo thấp nhất và quán có độ đậm béo cao nhất, rồi kết thúc bằng cách gọi Answer.

Chương trình của bạn có thể gọi hàm sau:

C++
int Compare(int X, int Y);

Hàm này thực hiện một lần ăn thử và so sánh ramen. Các tham số X, Y là số hiệu của hai quán được so sánh.

  • X và Y phải là hai số nguyên khác nhau, đều thuộc đoạn từ \(0\) đến \(N-1\). Nếu gọi Compare với tham số không thỏa mãn điều kiện này, chương trình bị đánh giá Wrong Answer [1] và kết thúc.
  • Hàm trả về 1 nếu độ đậm béo của quán X lớn hơn độ đậm béo của quán Y.
  • Hàm trả về -1 nếu độ đậm béo của quán X nhỏ hơn độ đậm béo của quán Y.
  • Nếu gọi Compare quá \(600\) lần, chương trình bị đánh giá Wrong Answer [2] và kết thúc.

Hàm Ramen phải kết thúc bằng cách gọi hàm sau. Nếu Ramen không gọi Answer, chương trình bị đánh giá Wrong Answer [3] và kết thúc.

C++
void Answer(int X, int Y);

Chỉ gọi hàm này khi các phép so sánh đã xác định được quán có độ đậm béo thấp nhất và quán có độ đậm béo cao nhất. X là số hiệu quán có độ đậm béo thấp nhất; Y là số hiệu quán có độ đậm béo cao nhất.

  • X và Y đều phải là số nguyên từ \(0\) đến \(N-1\). Nếu tham số không thỏa mãn điều kiện này, chương trình bị đánh giá Wrong Answer [4].
  • Nếu chỉ có duy nhất một cặp đáp án không mâu thuẫn với kết quả của các lời gọi Compare, và bạn gọi Answer với đúng cặp đáp án đó, chương trình được chấp nhận. Nếu không, chương trình bị đánh giá Wrong Answer [5].
  • Khi Answer được gọi, chương trình kết thúc.

Lưu ý về chấm điểm

Khi chấm bài, nếu kết quả của các lời gọi Compare chưa xác định duy nhất đáp án, chương trình sẽ bị đánh giá Wrong Answer [5], bất kể các tham số truyền vào Answer là gì.

Trong một số bộ dữ liệu chấm, giá trị trả về của Compare có thể thay đổi tùy theo các lời gọi Compare trước đó. Ngay cả trong trường hợp này, giá trị trả về vẫn không mâu thuẫn với kết quả của bất kỳ lời gọi Compare nào trước đó.

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

Gói dữ liệu chính thức chứa trình chấm mẫu để kiểm thử chương trình của bạn, cùng với các tệp mã nguồn mẫu cần nộp. Các tệp dành cho bài này nằm trong thư mục ramen/dist/ của gói dữ liệu.

Trình chấm mẫu gồm một tệp: grader.c hoặc grader.cpp. Chẳng hạn, nếu chương trình của bạn được lưu trong Ramen.c hoặc Ramen.cpp, hãy đặt tệp chương trình, tệp trình chấm tương ứng và ramen.h trong cùng thư mục rồi biên dịch như sau.

Với C:

Bash
gcc -O2 -lm grader.c Ramen.c -o grader

Với C++:

Bash
g++ -O2 grader.cpp Ramen.cpp -o grader

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

Lưu ý rằng trình chấm thật khác với 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

Trình chấm mẫu đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

  • Dòng đầu chứa hai số nguyên \(N, T\) cách nhau bởi dấu cách. \(N\) là số quán ramen. Trình chấm mẫu chỉ xử lý dữ liệu có \(T = 1\).
  • Trong \(N\) dòng tiếp theo, dòng thứ \(i+1\) (\(0 \le i \le N-1\)) chứa số nguyên \(A_i\) (\(0 \le A_i \le N-1\)), là độ đậm béo của quán \(i\). Các giá trị \(A_i\) đôi một khác nhau.

Dữ liệu ra

Nếu quá trình thực thi kết thúc bình thường, trình chấm mẫu ghi một dòng thông tin sau ra đầu ra chuẩn, không kèm dấu ngoặc kép:

  • Nếu đáp án đúng, ghi Accepted.
  • Nếu đáp án sai, ghi loại lỗi, chẳng hạn Wrong Answer [2].

Lưu ý: nếu gọi Answer(X, Y) với \(A_X = 0\) và \(A_Y = N-1\), trình chấm mẫu vẫn chấp nhận ngay cả khi trường hợp đó thuộc lỗi Wrong Answer [5] do các phép so sánh chưa xác định duy nhất đáp án. Hành vi này khác với trình chấm thật.

Ràng buộc

Tất cả dữ liệu thỏa mãn \(1 \le N \le 400\).

Phân nhóm

  • Nhóm 1 (20 điểm): \(N \le 30\).
  • Nhóm 2 (30 điểm): \(N \le 300\).
  • Nhóm 3 (50 điểm): Không có ràng buộc bổ sung.

Ví dụ giao tiếp

Dưới đây là một ví dụ dữ liệu vào của trình chấm mẫu và một dãy lời gọi hàm tương ứng.

3 1
1
2
0

Các lời gọi hàm

Lời gọi Giá trị trả về
Compare(0, 1) -1
Compare(0, 2) 1
Answer(2, 1) Chương trình kết thúc.