IOI 2016 - Ngày 1

Petr làm việc cho một công ty đã chế tạo một chiếc máy phát hiện các phân tử. Mỗi phân tử có trọng lượng là một số nguyên dương. Máy có khoảng phát hiện \([l,u]\), trong đó \(l\) và \(u\) là các số nguyên dương. Máy phát hiện được một tập các phân tử khi và chỉ khi tập đó chứa một tập con có tổng trọng lượng thuộc khoảng phát hiện.

Xét \(n\) phân tử có trọng lượng \(w_0,\ldots,w_{n-1}\). Việc phát hiện thành công nếu tồn tại một tập các chỉ số phân biệt \(I=\{i_1,\ldots,i_m\}\) sao cho

Do đặc thù của máy, độ rộng khoảng phát hiện không nhỏ hơn chênh lệch trọng lượng giữa phân tử nặng nhất và nhẹ nhất:

Hãy tìm một tập con bất kỳ có tổng trọng lượng thuộc khoảng phát hiện, hoặc xác định rằng không tồn tại tập con như vậy.

Chi tiết cài đặt

Trong C++, cài đặt hàm khai báo trong molecules.h:

std::vector<int> find_subset(int l, int u, std::vector<int> w);

Trong Java, cài đặt phương thức sau trong lớp molecules:

public int[] find_subset(int l, int u, int[] w)

Trong C, giao diện là:

int find_subset(int l, int u, int* w, int w_len, int* result);

• l, u: hai đầu mút của khoảng phát hiện, đều được tính trong khoảng.
• w: mảng trọng lượng của \(n\) phân tử; trong C, w_len bằng \(n\).
• Với C++ và Java, trả về mảng chỉ số của các phân tử thuộc một tập con thỏa mãn. Nếu không tồn tại, trả về mảng rỗng.
• Với C, ghi \(m\) chỉ số tìm được vào \(m\) phần tử đầu của mảng result được cấp sẵn và trả về \(m\). Nếu không tồn tại, không ghi vào result và trả về \(0\).

Các chỉ số phải đôi một khác nhau, thuộc đoạn \([0,n-1]\), và có thể được trả về theo thứ tự bất kỳ. Nếu có nhiều đáp án đúng, được phép trả về bất kỳ đáp án nào. Nộp phần cài đặt hàm, không viết hàm main; dùng các tệp mẫu tương ứng với ngôn ngữ trong gói đính kèm. Khi nộp bằng C trên LQDOJ, dùng #include "molecules.h" thay cho #include "molecules_c.h" trong tệp mẫu; header dùng chung cung cấp đúng giao diện C ở trên.

Ràng buộc

• \(1 \le n \le 200\,000\).
• \(1 \le w_i,l,u < 2^{31}\), với \(0 \le i < n\).
• \(l \le u\) và \(u-l \ge w_{\max}-w_{\min}\).

Phân nhóm

Mỗi subtask được tính trọn số điểm khi tất cả các test của subtask đó đều đúng; nếu không, subtask được \(0\) điểm. Các ràng buộc chung luôn áp dụng.

Ví dụ

Lời gọi thứ nhất:

find_subset(15, 17, [6, 8, 8, 7])

Ta có \(17-15 \ge 8-6\). Hàm có thể trả về [1, 3] vì \(w_1+w_3=8+7=15\). Các đáp án [1, 2] và [2, 3] cũng đúng, với tổng trọng lượng lần lượt là \(16\) và \(15\).

Lời gọi thứ hai:

find_subset(14, 15, [5, 5, 6, 6])

Ta có \(15-14 \ge 6-5\), nhưng không có tập con nào có tổng trọng lượng thuộc \([14,15]\). Hàm phải trả về mảng rỗng.

Lời gọi thứ ba:

find_subset(10, 20, [15, 17, 16, 18])

Ta có \(20-10 \ge 18-15\). Bất kỳ tập con chỉ chứa một phân tử nào cũng thỏa mãn, nên [0], [1], [2] và [3] đều là đáp án đúng.

Trình chấm mẫu

Trình chấm mẫu đọc dòng đầu chứa \(n,l,u\) và dòng tiếp theo chứa \(n\) số \(w_0,\ldots,w_{n-1}\). Chương trình in số lượng chỉ số được trả về trên dòng đầu, rồi in các chỉ số trên dòng tiếp theo nếu số lượng đó khác \(0\).

4 15 17
6 8 8 7

2
2 1

4 14 15
5 5 6 6

0

4 10 20
15 17 16 18

1
3

Nguồn

IOI 2016, ngày thi thứ nhất, bài Detecting Molecules. Đề tiếng Việt và gói tệp dành cho thí sinh được đính kèm.

Anna làm việc cho một công viên giải trí và được giao xây dựng đường ray cho một tàu lượn cao tốc mới. Cô đã thiết kế \(n\) đoạn đường đặc biệt, đánh số từ \(0\) đến \(n-1\), có tác động đến tốc độ của tàu. Bây giờ cô cần ghép chúng thành đường ray hoàn chỉnh. Trong bài toán này, có thể coi chiều dài của đoàn tàu bằng không.

Đoạn đường đặc biệt \(i\) có hai tính chất:

• Khi đi vào đoạn đường, tốc độ của tàu phải không vượt quá \(s_i\) km/h.
• Khi đi ra, tốc độ của tàu đúng bằng \(t_i\) km/h, không phụ thuộc tốc độ lúc đi vào.

Đường ray hoàn chỉnh gồm tất cả \(n\) đoạn đường đặc biệt theo một thứ tự nào đó, mỗi đoạn được dùng đúng một lần. Hai đoạn liên tiếp được nối bằng một đoạn ray có độ dài là số nguyên không âm, tính bằng mét. Anna cần chọn thứ tự các đoạn đặc biệt và độ dài các đoạn ray nối.

Mỗi mét ray nối làm tốc độ của tàu giảm đi \(1\) km/h. Tàu bắt đầu đi vào đoạn đường đặc biệt đầu tiên với tốc độ \(1\) km/h. Thiết kế phải bảo đảm tàu không vi phạm giới hạn tốc độ đầu vào của bất kỳ đoạn đặc biệt nào và tốc độ luôn dương.

Trong mọi subtask trừ subtask \(3\), hãy tìm tổng độ dài nhỏ nhất có thể của các đoạn ray nối. Trong subtask \(3\), chỉ cần xác định có thể thiết kế sao cho mọi đoạn ray nối đều dài \(0\) hay không.

Chi tiết cài đặt

Trong C++, cài đặt hàm khai báo trong railroad.h:

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t);

Trong Java, cài đặt phương thức sau trong lớp railroad:

public static long plan_roller_coaster(int[] s, int[] t)

Trong C, giao diện là:

long long plan_roller_coaster(int n, int* s, int* t);

• s, t: hai mảng độ dài \(n\), lần lượt chứa giới hạn tốc độ đầu vào và tốc độ đầu ra của các đoạn đặc biệt.
• Trong C, n là số phần tử của mỗi mảng.
• Trong mọi subtask trừ subtask \(3\), trả về tổng độ dài nhỏ nhất của các đoạn ray nối, bằng số nguyên \(64\) bit.
• Trong subtask \(3\), trả về \(0\) nếu có thiết kế mà mọi đoạn ray nối đều dài \(0\); nếu không, trả về một số nguyên dương bất kỳ. Trả về tổng độ dài nhỏ nhất vẫn thỏa mãn yêu cầu này.

Nộp phần cài đặt hàm, không viết hàm main; sử dụng các tệp mẫu của ngôn ngữ tương ứng trong gói đính kèm. Khi nộp bằng C trên LQDOJ, dùng #include "railroad.h" thay cho #include "railroad_c.h" trong tệp mẫu; header dùng chung cung cấp đúng giao diện C ở trên.

Ràng buộc

• \(2 \le n \le 200\,000\).
• \(1 \le s_i \le 10^9\) và \(1 \le t_i \le 10^9\), với mọi \(0 \le i < n\).

Phân nhóm

Mỗi subtask được tính trọn số điểm khi tất cả các test của subtask đó đều đúng; nếu không, subtask được \(0\) điểm. Giới hạn \(1 \le s_i,t_i \le 10^9\) áp dụng cho mọi subtask.

Ví dụ

plan_roller_coaster([1, 4, 5, 6], [7, 3, 8, 6])

Một thiết kế tối ưu dùng các đoạn đặc biệt theo thứ tự \(0,3,1,2\), với các đoạn ray nối dài lần lượt \(1,2,0\) mét:

1. Tàu đi vào đoạn \(0\) với tốc độ \(1\) km/h và đi ra với tốc độ \(7\) km/h.
2. Đi qua \(1\) mét ray nối, tốc độ giảm còn \(6\) km/h. Tàu đi vào đoạn \(3\) và đi ra với cùng tốc độ.
3. Đi qua \(2\) mét ray nối, tốc độ giảm còn \(4\) km/h. Tàu đi vào đoạn \(1\) và đi ra với tốc độ \(3\) km/h.
4. Tàu đi ngay vào đoạn \(2\) qua đoạn ray nối dài \(0\), rồi đi ra với tốc độ \(8\) km/h.

Tổng độ dài các đoạn ray nối là

Do đó hàm trả về \(3\).

Trình chấm mẫu

Trình chấm mẫu đọc dòng đầu chứa \(n\). Dòng \(2+i\), với \(0 \le i < n\), chứa \(s_i,t_i\). Trình chấm mẫu in giá trị trả về của plan_roller_coaster trên một dòng.

4
1 7
4 3
5 8
6 6

3

Nguồn

IOI 2016, ngày thi thứ nhất, bài Roller Coaster Railroad. Đề tiếng Việt và gói tệp dành cho thí sinh được đính kèm.

Pavel có một bộ đồ chơi đường sắt. Đường chính gồm \(n\) trạm, được đánh số từ \(0\) đến \(n-1\) theo thứ tự dọc đường. Khoảng cách giữa trạm \(i\) và \(i+1\) là \(l_i\) cm, với \(0 \le i < n-1\).

Ngoài đường chính có thể có một số đường nhánh. Mỗi đường nhánh nối một trạm trên đường chính với một trạm mới không nằm trên đường chính. Các trạm mới không được đánh số. Từ mỗi trạm trên đường chính có nhiều nhất một đường nhánh. Đường nhánh xuất phát từ trạm \(i\) dài \(d_i\) cm; \(d_i=0\) biểu thị rằng không có đường nhánh từ trạm đó.

Pavel dự định xây một đường tắt nối hai trạm khác nhau trên đường chính. Hai trạm này có thể kề nhau. Đường tắt luôn dài đúng \(c\) cm, bất kể hai trạm được chọn.

Mọi đoạn đường sắt, kể cả đường tắt mới, đều có thể đi theo cả hai chiều. Khoảng cách giữa hai trạm là độ dài ngắn nhất của một tuyến đường nối chúng dọc theo mạng đường sắt. Đường kính của mạng là khoảng cách lớn nhất giữa mọi cặp trạm, bao gồm cả các trạm ở cuối đường nhánh. Tương đương, đó là số nhỏ nhất \(t\) sao cho khoảng cách giữa bất kỳ hai trạm nào cũng không vượt quá \(t\).

Hãy tìm đường kính nhỏ nhất có thể sau khi Pavel xây đường tắt.

Chi tiết cài đặt

Trong C++, cài đặt hàm khai báo trong shortcut.h:

long long find_shortcut(int n, std::vector <int> l, std::vector <int> d, int c);

Trong Java, cài đặt phương thức sau trong lớp shortcut:

public long find_shortcut(int n, int[] l, int[] d, int c)

Trong C, giao diện là:

long long find_shortcut(int n, int* l, int* d, int c);

• n: số trạm trên đường chính.
• l: mảng độ dài \(n-1\) chứa độ dài các đoạn đường chính.
• d: mảng độ dài \(n\) chứa độ dài các đường nhánh, hoặc \(0\) nếu không có nhánh.
• c: độ dài đường tắt mới.
• Hàm trả về đường kính nhỏ nhất sau khi thêm đường tắt, bằng số nguyên \(64\) bit.

Nộp phần cài đặt hàm, không viết hàm main; sử dụng các tệp mẫu của ngôn ngữ tương ứng trong gói đính kèm. Khi nộp bằng C trên LQDOJ, dùng #include "shortcut.h" thay cho #include "shortcut_c.h" trong tệp mẫu; header dùng chung cung cấp đúng giao diện C ở trên.

Ràng buộc

• \(2 \le n \le 1\,000\,000\).
• \(1 \le l_i \le 10^9\), với \(0 \le i < n-1\).
• \(0 \le d_i \le 10^9\), với \(0 \le i < n\).
• \(1 \le c \le 10^9\).

Phân nhóm

Mỗi subtask được tính trọn số điểm khi tất cả các test của subtask đó đều đúng; nếu không, subtask được \(0\) điểm. Các giới hạn chung đối với \(l_i,d_i,c\) áp dụng cho mọi subtask.

Ví dụ

Lời gọi thứ nhất tương ứng với mạng đường sắt ở hình trên:

find_shortcut(4, [10, 20, 20], [0, 40, 0, 30], 10)

Phương án tối ưu nối trạm \(1\) và trạm \(3\) như hình sau. Đường kính của mạng mới là \(80\) cm, nên hàm trả về \(80\).

Lời gọi thứ hai:

find_shortcut(9, [10, 10, 10, 10, 10, 10, 10, 10], [20, 0, 30, 0, 0, 40, 0, 40, 0], 30)

Nối trạm \(2\) và \(7\) là tối ưu; hàm trả về \(110\).

Lời gọi thứ ba:

find_shortcut(4, [2, 2, 2], [1, 10, 10, 1], 1)

Nối trạm \(1\) và \(2\) là tối ưu, làm đường kính giảm còn \(21\). Hàm trả về \(21\).

Lời gọi thứ tư:

find_shortcut(3, [1, 1], [1, 1, 1], 3)

Nối bất kỳ hai trạm nào bằng đường tắt dài \(3\) cũng không cải thiện đường kính ban đầu là \(4\). Hàm trả về \(4\).

Trình chấm mẫu

Trình chấm mẫu đọc dữ liệu theo định dạng:

• Dòng \(1\): \(n,c\).
• Dòng \(2\): \(l_0,l_1,\ldots,l_{n-2}\).
• Dòng \(3\): \(d_0,d_1,\ldots,d_{n-1}\).

Trình chấm mẫu in giá trị trả về của find_shortcut trên một dòng.

4 10
10 20 20
0 40 0 30

80

9 30
10 10 10 10 10 10 10 10
20 0 30 0 0 40 0 40 0

110

4 1
2 2 2
1 10 10 1

21

3 3
1 1
1 1 1

4

Nguồn

IOI 2016, ngày thi thứ nhất, bài Shortcut. Đề tiếng Việt và gói tệp dành cho thí sinh được đính kèm.