IOI 2011 - Ngày 1

Nhà thực vật học Somhed thường xuyên đưa các nhóm học sinh đến một trong những vườn nhiệt đới lớn nhất Thái Lan. Khu vườn có \(N\) đài phun nước, được đánh số từ \(0\) đến \(N-1\), và \(M\) đường mòn. Mỗi đường mòn nối hai đài phun nước khác nhau và có thể đi theo cả hai chiều. Không có hai đường mòn nào nối cùng một cặp đài phun nước. Từ mỗi đài phun nước đều có ít nhất một đường mòn đi ra. Dọc các đường mòn là những bộ sưu tập thực vật đẹp mà Somhed muốn ngắm nhìn. Mỗi nhóm có thể bắt đầu chuyến đi tại bất kỳ đài phun nước nào.

Somhed yêu thích những loài cây nhiệt đới đẹp. Vì vậy, tại mỗi đài phun nước, ông và các học sinh sẽ chọn đường mòn đẹp nhất đi ra từ đó, trừ khi đó chính là đường mòn vừa đi qua và vẫn còn đường khác để chọn. Trong trường hợp ấy, họ chọn đường mòn đẹp thứ hai. Nếu không có lựa chọn nào khác, họ buộc phải quay lại theo đường mòn vừa đi qua. Với con mắt của một nhà thực vật học chuyên nghiệp, Somhed không bao giờ đánh giá hai đường mòn đẹp như nhau.

Các học sinh không mấy quan tâm đến cây cối, nhưng rất muốn ăn trưa tại một nhà hàng cao cấp nằm cạnh đài phun nước số \(P\). Somhed biết rằng mỗi nhóm sẽ đói sau khi đi qua đúng \(K\) đường mòn; giá trị \(K\) có thể khác nhau giữa các nhóm. Ông muốn biết có bao nhiêu lộ trình khác nhau để chọn cho mỗi nhóm, sao cho nhóm có thể xuất phát tại bất kỳ đài phun nước nào, luôn chọn đường theo quy tắc trên và kết thúc tại đài phun nước \(P\) sau khi đi qua đúng \(K\) đường mòn. Một nhóm có thể đi qua \(P\) trước khi kết thúc lộ trình, nhưng vẫn phải ở \(P\) sau đúng \(K\) lần đi qua đường mòn.

Yêu cầu

Cho thông tin về các đài phun nước và đường mòn, hãy tìm câu trả lời cho \(Q\) nhóm học sinh, tương ứng với \(Q\) giá trị của \(K\).

Cài đặt thủ tục sau, được khai báo trong garden.h:

void count_routes(int N, int M, int P, int R[][2], int Q, int G[]);

• N: số đài phun nước, được đánh số từ \(0\) đến \(N-1\).
• M: số đường mòn, được đánh số từ \(0\) đến \(M-1\). Các đường được cho theo thứ tự độ đẹp giảm dần: với \(0 \le i < M-1\), đường \(i\) đẹp hơn đường \(i+1\).
• P: số hiệu đài phun nước cạnh nhà hàng, \(0 \le P < N\).
• R: mảng hai chiều mô tả các đường mòn. Với \(0 \le i < M\), đường \(i\) nối R[i][0] và R[i][1]. Hai đầu mút khác nhau và không có hai đường cùng nối một cặp đài phun nước.
• Q: số nhóm học sinh.
• G: mảng một chiều chứa các giá trị \(K\). Với \(0 \le i < Q\), nhóm \(i\) sẽ đi qua đúng G[i] đường mòn.

Với mỗi \(i\) từ \(0\) đến \(Q-1\), thủ tục phải tính số lộ trình hợp lệ gồm đúng G[i] lần đi qua đường mòn và kết thúc tại \(P\). Để báo một câu trả lời bằng X, gọi thủ tục do trình chấm cung cấp trong gardenlib.h:

void answer(int x);

Phải gọi answer đúng \(Q\) lần, theo đúng thứ tự các nhóm trong mảng G. Nếu một nhóm không có lộ trình hợp lệ, gọi answer(0). Thủ tục count_routes không trả về giá trị.

Ví dụ

6 6 0
1 2
0 1
0 3
3 4
4 5
1 5
1
3
2

Correct.

    ![Hình 1: Các đài phun nước và số hiệu đường mòn trong ví dụ 1](https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_163be40d.png)

    Các đường mòn được liệt kê theo độ đẹp giảm dần: đường $0$ đẹp nhất, đường $1$ đẹp thứ hai, v.v. Chỉ có hai lộ trình hợp lệ gồm đúng $3$ lần đi qua đường mòn:


    - $1 \to 2 \to 1 \to 0$.
    - $5 \to 4 \to 3 \to 0$.

    Lộ trình thứ nhất bắt đầu tại đài phun nước $1$. Đường đẹp nhất từ đây dẫn đến đài phun nước $2$. Tại $2$, nhóm không có lựa chọn nào khác nên phải quay lại theo cùng đường. Khi trở về $1$, nhóm tránh đường $0$ vừa đi và chọn đường $1$, dẫn đến đài phun nước $P=0$. Vì vậy, thủ tục phải gọi `answer(2)`.

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

Correct.

    ![Hình 2: Các đài phun nước và số hiệu đường mòn trong ví dụ 2](https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_d5e5b251.png)

    Với nhóm thứ nhất, chỉ có một lộ trình đến đài phun nước $2$ sau đúng $3$ lần đi qua đường mòn: $1 \to 0 \to 1 \to 2$. Với nhóm thứ hai, có hai lộ trình đến đài phun nước $2$ sau đúng $1$ lần đi qua đường mòn: $3 \to 2$ và $4 \to 2$. Do đó, `count_routes` phải gọi `answer(1)` trước, rồi gọi `answer(2)`.

Ràng buộc

Trong mọi nhóm, \(0 \le P < N\), mỗi đường mòn nối hai đài phun nước phân biệt và mỗi đài phun nước có ít nhất một đường mòn đi ra. Các giới hạn cụ thể của từng nhóm được cho dưới đây.

Phân nhóm

Chi tiết cài đặt

Giới hạn thời gian CPU: 5 giây. Giới hạn bộ nhớ: 256 MB. Không có giới hạn riêng cho bộ nhớ ngăn xếp; bộ nhớ ngăn xếp được tính vào tổng bộ nhớ sử dụng.

Thư mục cài đặt là garden/. Thí sinh cài đặt garden.c, garden.cpp hoặc garden.pas. Giao diện của thí sinh là garden.h hoặc garden.pas; giao diện của trình chấm là gardenlib.h hoặc gardenlib.pas. Trình chấm mẫu được cung cấp trong grader.c, grader.cpp hoặc grader.pas.

Dữ liệu vào

Các tệp đầu vào mẫu là grader.in.1, grader.in.2, … Trình chấm mẫu đọc dữ liệu theo định dạng:

• Dòng \(1\): ba số nguyên \(N\), \(M\), \(P\).
• Các dòng \(2\) đến \(M+1\): mô tả các đường mòn. Dòng \(i+2\) chứa R[i][0] và R[i][1], cách nhau bởi dấu cách, với \(0 \le i < M\).
• Dòng \(M+2\): số nguyên \(Q\).
• Dòng \(M+3\): các phần tử của mảng \(G\), cách nhau bởi dấu cách.
• Dòng \(M+4\): \(Q\) đáp án mong đợi theo thứ tự các nhóm, cách nhau bởi dấu cách.

Dữ liệu ra

Kết quả mong đợi tương ứng nằm trong grader.expect.1, grader.expect.2, … Mỗi tệp này chứa đúng văn bản Correct..

Nguồn

IOI 2011, ngày thi 1, Pattaya, Thái Lan. Đề Tropical Garden, bản tiếng Anh 1.5: PDF chính thức. Nội dung được dịch từ đề chính thức; tất cả các hình minh họa đều lấy từ đề chính thức. Giao diện C/C++ và dữ liệu của trình chấm mẫu được đối chiếu với bộ API gốc.

Nhân dịp IOI, thành phố Pattaya sẽ tổ chức cuộc đua International Olympiad in Racing (IOR) 2011. Với vai trò chủ nhà, chúng ta phải tìm một đường đua tốt nhất có thể.

Trong vùng đô thị Pattaya–Chonburi có \(N\) thành phố được nối bởi mạng lưới gồm \(N-1\) đường cao tốc. Mỗi đường cao tốc đi được theo cả hai chiều, nối hai thành phố khác nhau và có độ dài nguyên tính bằng kilômét. Giữa mỗi cặp thành phố có đúng một đường đi: chỉ có một cách đi từ thành phố này đến thành phố kia qua một dãy đường cao tốc mà không ghé thành phố nào hai lần.

Quy định của IOR yêu cầu đường đua có tổng độ dài đúng \(K\) kilômét, bắt đầu và kết thúc ở hai thành phố khác nhau. Để tránh va chạm, không đường cao tốc nào, và do đó cũng không thành phố nào, được sử dụng hai lần trong đường đua. Để giảm thiểu ảnh hưởng đến giao thông, đường đua phải sử dụng ít đường cao tốc nhất có thể.

Yêu cầu

Cài đặt hàm sau, được khai báo trong race.h:

int best_path(int N, int K, int H[][2], int L[]);

• N: số thành phố, được đánh số từ \(0\) đến \(N-1\).
• K: độ dài cần có của đường đua.
• H: mảng hai chiều mô tả các đường cao tốc. Với \(0 \le i < N-1\), đường cao tốc \(i\) nối thành phố H[i][0] và thành phố H[i][1].
• L: mảng một chiều chứa độ dài các đường cao tốc. Với \(0 \le i < N-1\), đường cao tốc \(i\) có độ dài L[i].

Mọi phần tử của H nằm trong đoạn từ \(0\) đến \(N-1\), và các đường cao tốc nối tất cả thành phố đúng như mô tả ở trên. Mọi phần tử của L là số nguyên trong đoạn từ \(0\) đến \(1\,000\,000\), kể cả hai đầu; đường cao tốc có thể có độ dài bằng \(0\).

Hàm phải trả về số đường cao tốc ít nhất trong một đường đua hợp lệ có tổng độ dài đúng \(K\). Nếu không tồn tại đường đua như vậy, trả về -1. Không có thủ tục gọi lại để báo đáp án; trình chấm sử dụng giá trị trả về của best_path.

Ví dụ

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

Correct.

3 3
0 1 1
1 2 1
-1

Correct.

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

Correct.

Ràng buộc

Trong mọi nhóm, \(0 \le L[i] \le 1\,000\,000\) với \(0 \le i < N-1\); các đường cao tốc tạo thành mạng lưới như mô tả ở trên.

Phân nhóm

Chi tiết cài đặt

Giới hạn thời gian CPU: 3 giây. Giới hạn bộ nhớ: 256 MB. Không có giới hạn riêng cho bộ nhớ ngăn xếp; bộ nhớ ngăn xếp được tính vào tổng bộ nhớ sử dụng.

Thư mục cài đặt là race/. Thí sinh cài đặt race.c, race.cpp hoặc race.pas. Giao diện của thí sinh là race.h hoặc race.pas; giao diện của trình chấm là race.h hoặc racelib.pas. Trình chấm mẫu được cung cấp trong grader.c, grader.cpp hoặc grader.pas.

Dữ liệu vào

Các tệp đầu vào mẫu là grader.in.1, grader.in.2, … Trình chấm mẫu đọc dữ liệu theo định dạng:

• Dòng \(1\): hai số nguyên \(N\) và \(K\).
• Các dòng \(2\) đến \(N\): thông tin về các đường cao tốc. Dòng \(i+2\) chứa H[i][0], H[i][1] và L[i], cách nhau bởi dấu cách, với \(0 \le i < N-1\).
• Dòng \(N+1\): đáp án mong đợi.

Dữ liệu ra

Kết quả mong đợi tương ứng nằm trong grader.expect.1, grader.expect.2, … Mỗi tệp này chứa đúng văn bản Correct..

Nguồn

IOI 2011, ngày thi 1, Pattaya, Thái Lan. Đề Race, bản tiếng Anh 1.3: PDF chính thức. Nội dung được dịch từ đề chính thức; tất cả các hình minh họa đều lấy từ đề chính thức. Giao diện C/C++ và dữ liệu của trình chấm mẫu được đối chiếu với bộ API gốc.

Ở vùng nông thôn có một con đường dài và thẳng được gọi là Con đường Lúa. Dọc theo con đường có \(R\) cánh đồng lúa. Mỗi cánh đồng nằm tại một tọa độ nguyên từ \(1\) đến \(L\), kể cả hai đầu. Các cánh đồng được cho theo thứ tự tọa độ không giảm. Cụ thể, với \(0 \le i < R\), cánh đồng \(i\) nằm tại tọa độ \(X[i]\), và:

Nhiều cánh đồng có thể cùng nằm tại một tọa độ.

Chúng ta dự định xây dựng một kho lúa duy nhất để tập trung và cất giữ nhiều lúa thu hoạch nhất có thể. Kho phải nằm tại một tọa độ nguyên từ \(1\) đến \(L\), kể cả hai đầu. Có thể đặt kho ở bất kỳ vị trí nào trong phạm vi này, kể cả vị trí đã có một hoặc nhiều cánh đồng.

Mỗi cánh đồng thu hoạch được đúng một xe tải lúa trong mỗi vụ. Để đưa lúa về kho, thành phố phải thuê tài xế xe tải. Chi phí vận chuyển một xe tải lúa là \(1\) Baht cho mỗi đơn vị quãng đường từ cánh đồng đến kho. Nói cách khác, nếu kho ở tọa độ \(h\), chi phí chở lúa từ cánh đồng \(i\) về kho là \(|X[i]-h|\) Baht.

Ngân sách của vụ mùa này hạn hẹp: chúng ta chỉ được chi tối đa \(B\) Baht cho việc vận chuyển. Hãy chọn vị trí kho sao cho có thể tập trung được nhiều lúa nhất trong phạm vi ngân sách.

Yêu cầu

Cài đặt hàm sau, được khai báo trong ricehub.h:

int besthub(int R, int L, int X[], long long B);

• R: số cánh đồng, được đánh số từ \(0\) đến \(R-1\).
• L: tọa độ lớn nhất.
• X: mảng một chiều các số nguyên được sắp xếp theo thứ tự không giảm. Với \(0 \le i < R\), cánh đồng \(i\) nằm tại tọa độ X[i].
• B: ngân sách vận chuyển.

Hàm phải xác định cách đặt kho tối ưu và trả về số xe tải lúa lớn nhất có thể vận chuyển về kho mà tổng chi phí không vượt quá \(B\). Chỉ trả về số xe tải, không trả về tọa độ kho. Không có thủ tục gọi lại để báo đáp án; trình chấm sử dụng giá trị trả về của besthub.

Tổng chi phí vận chuyển có thể rất lớn. Ngân sách được cho bằng số nguyên \(64\) bit; nên dùng số nguyên \(64\) bit trong các phép tính. Trong C/C++, dùng kiểu long long; trong Pascal, dùng kiểu Int64.

Ví dụ

5 20 6
1
2
10
12
14
3

Correct.

    ![Vị trí các cánh đồng và một cách đặt kho lúa tối ưu](https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_6da42cbf.png)

    Có nhiều vị trí tối ưu để đặt kho: có thể đặt tại bất kỳ tọa độ nguyên nào từ $10$ đến $14$, kể cả hai đầu. Hình trên minh họa một vị trí như vậy. Khi đó có thể vận chuyển lúa từ các cánh đồng ở tọa độ $10$, $12$ và $14$ về kho. Với mỗi vị trí tối ưu, tổng chi phí vận chuyển số lúa này không quá $6$ Baht. Không có vị trí nào cho phép thu gom lúa từ hơn ba cánh đồng, nên phương án này là tối ưu và `besthub` phải trả về `3`.

Ràng buộc

Trong mọi nhóm, \(1 \le X[0] \le \cdots \le X[R-1] \le L\). Nhiều cánh đồng có thể cùng tọa độ, trừ khi nhóm quy định khác.

Phân nhóm

Chi tiết cài đặt

Giới hạn thời gian CPU: 1 giây. Giới hạn bộ nhớ: 256 MB. Không có giới hạn riêng cho bộ nhớ ngăn xếp; bộ nhớ ngăn xếp được tính vào tổng bộ nhớ sử dụng.

Thư mục cài đặt là ricehub/. Thí sinh cài đặt ricehub.c, ricehub.cpp hoặc ricehub.pas. Giao diện của thí sinh là ricehub.h hoặc ricehub.pas. Trình chấm mẫu được cung cấp trong grader.c, grader.cpp hoặc grader.pas.

Dữ liệu vào

Các tệp đầu vào mẫu là grader.in.1, grader.in.2, … Trình chấm mẫu đọc dữ liệu theo định dạng:

• Dòng \(1\): ba số nguyên \(R\), \(L\) và \(B\).
• Các dòng \(2\) đến \(R+1\): vị trí các cánh đồng. Dòng \(i+2\) chứa X[i], với \(0 \le i < R\).
• Dòng \(R+2\): đáp án mong đợi.

Dữ liệu ra

Kết quả mong đợi tương ứng nằm trong grader.expect.1, grader.expect.2, … Mỗi tệp này chứa đúng văn bản Correct..

Nguồn

IOI 2011, ngày thi 1, Pattaya, Thái Lan. Đề Rice Hub, bản tiếng Anh 1.4: PDF chính thức. Nội dung được dịch từ đề chính thức; tất cả các hình minh họa đều lấy từ đề chính thức. Giao diện C/C++ và dữ liệu của trình chấm mẫu được đối chiếu với bộ API gốc.