Bài toán: Nỗi lòng của Chu Chỉ Nhược
Trên đời này mọi chuyện đưa đẩy tới làm sao liệu trước được, nàng cũng đừng quá đau lòng.
Chu Chỉ Ngược ngẩng mặt lên nói:
- Vô Kỵ ca ca, thiếp có một câu hỏi, chàng phải thật lòng trả lời , không được che đậy chút nào.
Trương Vô Kỵ nói:
- Được, ta sẽ không dấu gì nàng.
Chu Chỉ Nhược nói:
Cho hai mảng A và B có cùng kích thước n. Biết rằng n là số nguyên dương và không quá 2 vạn.
Ca Ca có thể thưc hiện 1 trong 2 phép toán sau trên mảng A:
Phép toán 1: Đảo ngược mảng A. Tức là giả sử ta có mảng [A_1,A_2,...,A_n] thì nó sẽ thành [A_n,A_(n-1),...,A_1].
Phép toán 2: Thay thế mảng A bởi tổng các tiền tố. Tức là ta thay thế mảng [A_1,A_2,...,A_n] thành [A_1,(A_1+A_2),...,(A_1+A_2+...+A_n)]
Nhiệm vụ của Ca Ca là xác định xem liệu ta có thể thu được mảng B từ mảng A hay không ?
+ Nếu có thể, Ca Ca hãy lưu thứ tự các phép toán (với điều kiện số lần dùng phép toán 2 là ít nhất). Nếu số lượng phép toán 2 mà Ca Ca dùng lớn hơn 2.10^5 thì Ca Ca không cần in ra quá trình mình làm. Còn nếu số lượng phép toán 2 mà Ca Ca dùng không quá 2.10^5 và tổng số phép toán mà Ca Ca dùng nhỏ hơn 5.10^5 thì Ca Ca phải in ra quá trình của mình làm.
Cấu trúc input và output như sau:
INPUT:
+ Dòng thứ nhất chứa số n
+ Dòng thứ hai chứa n số A_1,A_2,...,A_n của mảng A
+ Dòng thứ ba chứa n số B_1,B_2,...,B_n của mảng B
OUTPUT:
+ Nếu không có cách nào thỏa mãn thì in ra "IMPOSSIBLE"
+ Nếu số lượng phép toán 2 mà bạn dùng lớn hơn 2.10^5 thì in ra "BIG". Và dòng tiếp theo in ra số phép toán 2 cần dùng.
+ Nếu số lượng phép toán 2 mà bạn dùng không quá 2.10^5 và tổng số phép toán mà bạn dùng không quá 5.10^5 thì in ra "SMALL". Gọi m là tổng số phép toán mà bạn dùng thì tiếp theo bạn in ra m và dòng kế tiếp bạn in ra m kí tự R,P. Trong đó R: tượng trưng cho phép toán 1 và P: tượng trưng cho phép toán 2.
Ví dụ 1:
2
5 7
5 7
Output 1:
SMALL
0
-----------
Ví dụ 2:
2
1 1
300000 1
Output 2:
BIG
299999
----------
Ví dụ 3:
2
10 1
13 14
Output 3:
SMALL
6
RPPPRP
----------
Ví dụ 4:
3
1 2 1
2 1 2
Output 4:
IMPOSSIBLE
* Giải thích :
Ở ví dụ 1, mảng A và B bằng nhau vì vậy tổng số phép toán cần dùng là 0.
Ở ví dụ 2, ta cần thay thế mảng A thành tổng tiền tố 299999 lần và sau đó đảo ngược mảng.
Vì 299999>2.10^5. Nên ta không cần lưu lại quá trình và chỉ cần in ra số lượng phép toán 2 cần dùng.
Ở ví dụ 4, ta không thể thu được mảng B từ mảng A
-----------------------------
Vô Kỵ Ca Ca đang bí, các bạn hãy giúp Ca Ca một tay nhé.
Chu Chỉ Ngược ngẩng mặt lên nói:
- Vô Kỵ ca ca, thiếp có một câu hỏi, chàng phải thật lòng trả lời , không được che đậy chút nào.
Trương Vô Kỵ nói:
- Được, ta sẽ không dấu gì nàng.
Chu Chỉ Nhược nói:
Cho hai mảng A và B có cùng kích thước n. Biết rằng n là số nguyên dương và không quá 2 vạn.
Ca Ca có thể thưc hiện 1 trong 2 phép toán sau trên mảng A:
Phép toán 1: Đảo ngược mảng A. Tức là giả sử ta có mảng [A_1,A_2,...,A_n] thì nó sẽ thành [A_n,A_(n-1),...,A_1].
Phép toán 2: Thay thế mảng A bởi tổng các tiền tố. Tức là ta thay thế mảng [A_1,A_2,...,A_n] thành [A_1,(A_1+A_2),...,(A_1+A_2+...+A_n)]
Nhiệm vụ của Ca Ca là xác định xem liệu ta có thể thu được mảng B từ mảng A hay không ?
+ Nếu có thể, Ca Ca hãy lưu thứ tự các phép toán (với điều kiện số lần dùng phép toán 2 là ít nhất). Nếu số lượng phép toán 2 mà Ca Ca dùng lớn hơn 2.10^5 thì Ca Ca không cần in ra quá trình mình làm. Còn nếu số lượng phép toán 2 mà Ca Ca dùng không quá 2.10^5 và tổng số phép toán mà Ca Ca dùng nhỏ hơn 5.10^5 thì Ca Ca phải in ra quá trình của mình làm.
Cấu trúc input và output như sau:
INPUT:
+ Dòng thứ nhất chứa số n
+ Dòng thứ hai chứa n số A_1,A_2,...,A_n của mảng A
+ Dòng thứ ba chứa n số B_1,B_2,...,B_n của mảng B
OUTPUT:
+ Nếu không có cách nào thỏa mãn thì in ra "IMPOSSIBLE"
+ Nếu số lượng phép toán 2 mà bạn dùng lớn hơn 2.10^5 thì in ra "BIG". Và dòng tiếp theo in ra số phép toán 2 cần dùng.
+ Nếu số lượng phép toán 2 mà bạn dùng không quá 2.10^5 và tổng số phép toán mà bạn dùng không quá 5.10^5 thì in ra "SMALL". Gọi m là tổng số phép toán mà bạn dùng thì tiếp theo bạn in ra m và dòng kế tiếp bạn in ra m kí tự R,P. Trong đó R: tượng trưng cho phép toán 1 và P: tượng trưng cho phép toán 2.
Ví dụ 1:
2
5 7
5 7
Output 1:
SMALL
0
-----------
Ví dụ 2:
2
1 1
300000 1
Output 2:
BIG
299999
----------
Ví dụ 3:
2
10 1
13 14
Output 3:
SMALL
6
RPPPRP
----------
Ví dụ 4:
3
1 2 1
2 1 2
Output 4:
IMPOSSIBLE
* Giải thích :
Ở ví dụ 1, mảng A và B bằng nhau vì vậy tổng số phép toán cần dùng là 0.
Ở ví dụ 2, ta cần thay thế mảng A thành tổng tiền tố 299999 lần và sau đó đảo ngược mảng.
Vì 299999>2.10^5. Nên ta không cần lưu lại quá trình và chỉ cần in ra số lượng phép toán 2 cần dùng.
Ở ví dụ 4, ta không thể thu được mảng B từ mảng A
-----------------------------
Vô Kỵ Ca Ca đang bí, các bạn hãy giúp Ca Ca một tay nhé.
Nhận xét
Đăng nhận xét