IOI 2013 - Ngày 2

Trong khi lạc đường từ ký túc xá đến Trung tâm UQ, bạn tình cờ tìm thấy lối vào một hệ thống hang động bí mật nằm sâu dưới trường. Lối vào bị chặn bởi một hệ thống an ninh gồm \(N\) cánh cửa liên tiếp, cửa này nằm sau cửa kia, và \(N\) công tắc, mỗi công tắc nối với một cánh cửa khác nhau.

Các cửa được đánh số từ \(0\) đến \(N-1\) theo thứ tự, cửa \(0\) gần bạn nhất. Các công tắc cũng được đánh số từ \(0\) đến \(N-1\), nhưng bạn không biết công tắc nào nối với cửa nào.

Tất cả công tắc đều nằm ở lối vào hang. Mỗi công tắc có thể ở vị trí trên hoặc dưới. Với mỗi công tắc, chỉ một vị trí là đúng: ở vị trí đúng, cửa tương ứng mở; ở vị trí sai, cửa tương ứng đóng. Vị trí đúng có thể khác nhau giữa các công tắc và bạn chưa biết chúng.

Bạn có thể đặt các công tắc theo bất kỳ tổ hợp nào, rồi đi vào hang để xem cửa đầu tiên bị đóng. Các cửa không trong suốt: sau khi gặp cửa đầu tiên bị đóng, bạn không thể nhìn thấy bất kỳ cửa nào phía sau nó.

Bạn chỉ có thời gian thử tối đa \(70\,000\) tổ hợp. Hãy xác định vị trí đúng của từng công tắc và cửa mà từng công tắc nối tới.

Cài đặt

Nộp một tệp cài đặt hàm C/C++ sau và dùng #include "cave.h":

void exploreCave(int N);

Trình chấm cung cấp hai hàm sau để chương trình của bạn gọi:

int tryCombination(int S[]);
void answer(int S[], int D[]);

Dữ liệu vào

Tham số N của exploreCave là số cửa và số công tắc. Hàm này phải sử dụng tryCombination để xác định vị trí đúng và kết nối của từng công tắc, rồi kết thúc bằng cách gọi answer.

Trong tryCombination(S), S là mảng độ dài \(N\) mô tả một tổ hợp. S[i] là vị trí của công tắc \(i\): \(0\) là trên, \(1\) là dưới. Hàm trả về chỉ số cửa đầu tiên bị đóng, hoặc \(-1\) nếu tất cả cửa đều mở. Mỗi lời gọi chạy trong thời gian \(O(N)\), tức thời gian chạy trong trường hợp xấu nhất tỷ lệ với \(N\). Bạn được gọi hàm này nhiều nhất \(70\,000\) lần.

Dữ liệu ra

Khi đã xác định được đáp án, gọi answer(S, D). Hai mảng đều có độ dài \(N\). S[i] là vị trí đúng của công tắc \(i\), theo quy ước \(0\) là trên và \(1\) là dưới. D[i] là chỉ số cửa nối với công tắc \(i\).

Hàm answer không trả quyền điều khiển về chương trình của bạn; nó khiến chương trình kết thúc.

Ràng buộc

• Giới hạn thời gian: 2 giây.
• Giới hạn bộ nhớ: 32 MiB.
• \(1 \le N \le 5\,000\).
• Có tối đa \(70\,000\) lời gọi tryCombination.

Phân nhóm

Mỗi nhóm tuân theo các ràng buộc chung và các điều kiện bổ sung sau.

Trình chấm mẫu

Trình chấm mẫu đọc tệp cave.in theo định dạng:

• Dòng 1: N.
• Dòng 2: S[0] S[1] ... S[N-1].
• Dòng 3: D[0] D[1] ... D[N-1].

Ở đây S[i] là vị trí đúng của công tắc \(i\), và D[i] là cửa nối với công tắc \(i\). Những thông tin này dùng để thiết lập trình chấm mẫu; hàm exploreCave nhận tham số N và tìm hiểu hệ thống qua các lời gọi tương tác.

Ví dụ

4
1 1 1 0
3 1 0 2

answer([1, 1, 1, 0], [3, 1, 0, 2])

Cậu em nhỏ của Marita thường bỏ bừa bãi đồ chơi trên sàn phòng khách. May mắn là Marita đã chế tạo các robot đặc biệt để dọn đồ chơi. Cô cần bạn giúp xác định robot nào dọn đồ chơi nào.

Có \(T\) đồ chơi. Đồ chơi \(i\) có trọng lượng nguyên W[i] và kích thước nguyên S[i]. Có hai loại robot:

• \(A\) robot yếu. Robot yếu \(i\) có hạn chế trọng lượng X[i], chỉ dọn được đồ chơi có trọng lượng nhỏ hơn hẳn X[i]. Kích thước đồ chơi là tùy ý.
• \(B\) robot nhỏ. Robot nhỏ \(i\) có hạn chế kích thước Y[i], chỉ dọn được đồ chơi có kích thước nhỏ hơn hẳn Y[i]. Trọng lượng đồ chơi là tùy ý.

Mỗi robot mất một phút để dọn một đồ chơi. Các robot khác nhau có thể đồng thời dọn các đồ chơi khác nhau.

Hãy xác định liệu các robot có thể dọn sạch tất cả đồ chơi hay không. Nếu có, hãy tìm thời gian nhỏ nhất để hoàn thành công việc.

Cài đặt

Bạn cần nộp một tệp cài đặt hàm C/C++ sau và phải dùng #include "robots.h":

int putaway(int A, int B, int T,
        int X[], int Y[], int W[], int S[]);

Dữ liệu vào

A là số robot yếu, B là số robot nhỏ và T là số đồ chơi. X là mảng độ dài \(A\) chứa hạn chế trọng lượng của các robot yếu; Y là mảng độ dài \(B\) chứa hạn chế kích thước của các robot nhỏ. W và S là các mảng độ dài \(T\), lần lượt chứa trọng lượng và kích thước của các đồ chơi. Chỉ số của các phần tử bắt đầu từ \(0\).

Dữ liệu ra

Hàm putaway trả về số phút nhỏ nhất cần để dọn sạch tất cả đồ chơi, hoặc \(-1\) nếu không thể dọn sạch.

Ràng buộc

• Giới hạn thời gian: 3 giây.
• Giới hạn bộ nhớ: 64 MiB.
• \(1 \le T \le 1\,000\,000\).
• \(0 \le A,B \le 50\,000\) và \(1 \le A+B\).
• \(1 \le X[i],Y[i],W[i],S[i] \le 2\,000\,000\,000\) trên các chỉ số hợp lệ của từng mảng.

Phân nhóm

Mỗi nhóm tuân theo các ràng buộc chung và các điều kiện bổ sung sau.

Trình chấm mẫu

Trình chấm mẫu đọc tệp robots.in theo định dạng:

• Dòng 1: A B T.
• Dòng 2: X[0] ... X[A-1].
• Dòng 3: Y[0] ... Y[B-1].
• \(T\) dòng tiếp theo: mỗi dòng chứa W[i] S[i], theo thứ tự \(i=0,\ldots,T-1\).

Nếu \(A=0\) hoặc \(B=0\), dòng tương ứng (dòng 2 hoặc dòng 3) là dòng rỗng.

Ví dụ

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

3

A = 2
B = 1
T = 3
X = [2, 5]
Y = [2]
W = [3, 5, 2]
S = [1, 3, 2]

-1

Bazza và Shazza chơi trên một lưới gồm \(R\) hàng, đánh số từ \(0\) đến \(R-1\), và \(C\) cột, đánh số từ \(0\) đến \(C-1\). Ô ở hàng \(P\), cột \(Q\) được ký hiệu là \((P,Q)\). Mỗi ô chứa một số nguyên không âm; ban đầu tất cả đều bằng \(0\).

Ở mỗi bước, Bazza có thể thực hiện một trong hai thao tác:

• Cập nhật ô \((P,Q)\) bằng cách gán một số nguyên cho ô đó.
• Yêu cầu Shazza tính ước chung lớn nhất (ƯCLN) của tất cả các số nguyên trong hình chữ nhật có hai góc đối diện \((P,Q)\) và \((U,V)\), bao gồm cả các ô ở biên và hai ô góc.

Bazza thực hiện \(N_U+N_Q\) bước, gồm \(N_U\) lần cập nhật và \(N_Q\) lần yêu cầu tính toán, trước khi chán trò chơi và ra ngoài chơi cricket. Hãy tính đúng các câu trả lời cho Shazza.

Cài đặt

Nộp một tệp cài đặt các hàm C/C++ sau và dùng #include "game.h":

void init(int R, int C);
void update(int P, int Q, long long K);
long long calculate(int P, int Q, int U, int V);

Các tệp mẫu game.c và game.cpp có hàm gcd2(X, Y) tính ƯCLN của hai số nguyên không âm. Khi \(X=Y=0\), hàm này trả về \(0\). Hàm đủ nhanh để đạt toàn bộ số điểm; thời gian chạy trong trường hợp xấu nhất tỷ lệ với \(\log(X+Y)\).

Các số trong lưới có thể rất lớn, vì vậy người dùng C/C++ được khuyến cáo dùng kiểu long long.

Dữ liệu vào

init(R, C) cung cấp số hàng R và số cột C của lưới, cho phép khởi tạo biến toàn cục và cấu trúc dữ liệu. Hàm được gọi đúng một lần, trước mọi lời gọi update hoặc calculate.

update(P, Q, K) được gọi khi Bazza gán giá trị K cho ô \((P,Q)\). Các tham số thỏa mãn \(0 \le P \le R-1\), \(0 \le Q \le C-1\), \(0 \le K \le 10^{18}\). Giá trị mới có thể trùng với giá trị đang có.

calculate(P, Q, U, V) yêu cầu ƯCLN của tất cả các số trong hình chữ nhật có góc trên trái \((P,Q)\) và góc dưới phải \((U,V)\), bao gồm cả biên. Các tham số thỏa mãn \(0 \le P \le U \le R-1\) và \(0 \le Q \le V \le C-1\).

Dữ liệu ra

Mỗi lời gọi calculate phải trả về ƯCLN của tất cả các số trong hình chữ nhật được yêu cầu. Nếu tất cả các số đó bằng \(0\), hàm phải trả về \(0\). Các hàm init và update không trả về giá trị.

Ràng buộc

• \(1 \le R,C \le 10^9\).
• \(0 \le K \le 10^{18}\) với mọi giá trị được gán vào một ô.
• Giới hạn số thao tác, thời gian và bộ nhớ được cho trong bảng phân nhóm dưới đây.

Phân nhóm

Các cột \(N_U\) và \(N_Q\) lần lượt giới hạn tổng số lần cập nhật và tổng số lần yêu cầu tính toán. Mỗi nhóm tuân theo các ràng buộc chung và toàn bộ giới hạn trên cùng một hàng.

Trình chấm mẫu

Trình chấm mẫu đọc tệp game.in. Dòng đầu chứa R C N, trong đó \(N=N_U+N_Q\). Tiếp theo là \(N\) dòng, mỗi dòng mô tả một thao tác theo đúng thứ tự thực hiện:

• 1 P Q K tương ứng với update(P, Q, K).
• 2 P Q U V tương ứng với calculate(P, Q, U, V).

Ví dụ

2 3 9
1 0 0 20
1 0 2 15
1 1 1 12
2 0 0 0 2
2 0 0 1 1
1 0 1 6
1 1 1 14
2 0 0 0 2
2 0 0 1 1

5
4
1
2