JOI 2016 Final Camp - Ngày 1

Bạn đang chuẩn bị mở một cửa hàng bán búp bê Matryoshka. Vì vậy, bạn đã đặt mua \(N\) con búp bê Matryoshka từ một nhà máy. Các con búp bê được đánh số từ \(1\) đến \(N\). Búp bê thứ \(i\) (\(1 \le i \le N\)) có thể được xem là một hình trụ tròn đứng rỗng bên trong, với đường kính đáy \(R_i\) cm và chiều cao \(H_i\) cm.

Các con búp bê Matryoshka có thể được lồng vào nhau để cất giữ. Mỗi con búp bê chỉ có thể chứa trực tiếp một con búp bê khác có cả đường kính đáy và chiều cao nhỏ hơn nó. Con búp bê được chứa bên trong cũng có thể chứa một con búp bê khác.

Một ngày nọ, nhà máy mà bạn đặt mua búp bê liên lạc với bạn. Do không thể chuẩn bị đồng thời tất cả \(N\) con búp bê đã đặt, nhà máy sẽ giao trước tất cả những con búp bê có đường kính đáy ít nhất \(A\) cm và chiều cao không quá \(B\) cm.

Các giá trị \(A, B\) có thể bị thay đổi đột ngột. Vì vậy, với mỗi trong \(Q\) cặp \((A_j, B_j)\) (\(1 \le j \le Q\)), bạn muốn tính trước số lượng nhỏ nhất các con búp bê không nằm trong bất kỳ con búp bê nào khác, khi lồng những con búp bê được giao trước vào nhau để cất giữ.

Yêu cầu

Cho đường kính đáy và chiều cao của từng con búp bê, cùng \(Q\) cặp \((A_j, B_j)\) (\(1 \le j \le Q\)). Hãy viết chương trình, với mỗi cặp, tìm số lượng nhỏ nhất các con búp bê không nằm trong bất kỳ con búp bê nào khác, khi lồng những con búp bê được giao trước vào nhau để cất giữ.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa hai số nguyên \(N, Q\), cách nhau bởi dấu cách. Đây lần lượt là số con búp bê đã đặt mua và số cặp giá trị \(A, B\) được cho.
• Dòng thứ \(i\) (\(1 \le i \le N\)) trong \(N\) dòng tiếp theo chứa hai số nguyên \(R_i, H_i\), cách nhau bởi dấu cách. Búp bê thứ \(i\) có đường kính đáy \(R_i\) cm và chiều cao \(H_i\) cm.
• Dòng thứ \(j\) (\(1 \le j \le Q\)) trong \(Q\) dòng tiếp theo chứa hai số nguyên \(A_j, B_j\), cách nhau bởi dấu cách.

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(j\) (\(1 \le j \le Q\)) chứa số lượng nhỏ nhất các con búp bê không nằm trong bất kỳ con búp bê nào khác, khi lồng những con búp bê được giao trước ứng với cặp \((A_j, B_j)\) vào nhau để cất giữ.

Ràng buộc

Tất cả dữ liệu vào thỏa mãn các điều kiện sau:

• \(1 \le N \le 200\,000\).
• \(1 \le Q \le 200\,000\).
• \(1 \le R_i \le 1\,000\,000\,000\) (\(1 \le i \le N\)).
• \(1 \le H_i \le 1\,000\,000\,000\) (\(1 \le i \le N\)).
• \(1 \le A_j \le 1\,000\,000\,000\) (\(1 \le j \le Q\)).
• \(1 \le B_j \le 1\,000\,000\,000\) (\(1 \le j \le Q\)).

Phân nhóm

1. 11 điểm: \(N \le 10\); \(Q = 1\).
2. 15 điểm: \(N \le 100\); \(Q = 1\).
3. 25 điểm: \(N \le 2\,000\); \(Q \le 2\,000\).
4. 49 điểm: Không có ràng buộc bổ sung.

Ví dụ

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

0
1
2

10 8
14 19
9 16
11 2
7 18
20 16
9 5
10 9
20 6
4 17
13 8
7 14
9 3
9 13
4 19
12 4
19 16
18 10
7 14

3
1
3
5
0
2
1
3

Với mỗi số nguyên từ \(0\) đến \(N - 1\), có đúng hai lá bài mang số đó ở mặt trước. Bạn và JOI đang luyện tập trò chơi lật bài ghi nhớ bằng \(2N\) lá bài này.

Khi bắt đầu luyện tập, các lá bài được đặt úp thành một hàng ngang trên bàn. Lá bài thứ \(i + 1\) từ trái sang (\(0 \le i \le 2N - 1\)) được gọi là lá bài \(i\). Gọi \(A_i\) là số nguyên viết ở mặt trước của lá bài \(i\) (\(0 \le i \le 2N - 1\)). Ban đầu, cả bạn và JOI đều không biết các giá trị \(A_i\) (\(0 \le i \le 2N - 1\)).

Bạn và JOI có thể lặp lại quá trình trao đổi sau nhiều nhất \(K\) lần:

1. Bạn chỉ định hai trong số \(2N\) lá bài.
2. JOI lật hai lá bài được chỉ định và bí mật xem các số viết ở mặt trước để bạn không nhìn thấy. Nếu hai số bằng nhau, JOI ghi nhớ số đó và cho bạn biết. Nếu hai số khác nhau, JOI ghi nhớ số mà mình thấy dễ nhớ hơn trong hai số đó và cho bạn biết số này.

Mức độ dễ nhớ của các số đối với JOI được biểu diễn bằng \(N\) số nguyên \(P_0, P_1, \ldots, P_{N-1}\). Các số nguyên này thỏa mãn hai điều kiện:

• \(0 \le P_i \le N - 1\) (\(0 \le i \le N - 1\)).
• \(P_i \ne P_j\) (\(0 \le i < j \le N - 1\)).

JOI thấy số \(i\) dễ nhớ hơn số \(j\) khi và chỉ khi \(P_i < P_j\).

Nhiệm vụ của bạn là xác định số viết trên từng lá bài bằng cách trao đổi với JOI không quá \(K\) lần. Tuy nhiên, bạn không biết các giá trị \(P_0, P_1, \ldots, P_{N-1}\) biểu diễn mức độ dễ nhớ của các số đối với JOI.

Yêu cầu

Hãy viết chương trình trao đổi với JOI để xác định số nguyên viết trên từng lá bài.

Chi tiết cài đặt

Bạn phải viết một chương trình C++ cài đặt phương pháp xác định số nguyên trên từng lá bài. Chương trình phải include tệp memory2.h được đính kèm theo bài.

Bạn phải cài đặt hàm sau:

void Solve(int T, int N)

Hàm này được gọi đúng một lần cho mỗi bộ kiểm thử. Tham số T là số thứ tự của subtask; tham số N cho biết có \(2N\) lá bài.

Hàm này phải gọi Flip để xác định các số viết trên những lá bài, rồi gọi Answer để báo kết quả.

Trong chương trình, bạn có thể gọi các hàm sau.

Hàm Flip

int Flip(int I, int J)

Gọi hàm này để chỉ định các lá bài cho JOI. Hai tham số I, J là chỉ số của hai lá bài mà JOI sẽ lật.

I và J phải là hai số nguyên khác nhau, cùng nằm trong đoạn từ \(0\) đến \(2N - 1\). Nếu gọi Flip với các tham số không thỏa mãn điều kiện này, bài làm bị chấm Sai đáp án [1].

Nếu \(A_I = A_J\), hàm trả về giá trị đó. Nếu không, hàm trả về số mà JOI thấy dễ nhớ hơn trong hai số \(A_I\) và \(A_J\).

Nếu gọi hàm này quá \(K\) lần, bài làm bị chấm Sai đáp án [2].

Hàm Answer

void Answer(int I, int J, int X)

Gọi hàm này để báo rằng bạn đã xác định được chỉ số của hai lá bài có số \(X\) viết ở mặt trước.

Các tham số I, J, X phải thỏa mãn tất cả các điều kiện sau:

• \(0 \le I \le 2N - 1\).
• \(0 \le J \le 2N - 1\).
• \(I \ne J\).
• \(A_I = A_J = X\).

Nếu gọi Answer với các tham số không thỏa mãn các điều kiện này, bài làm bị chấm Sai đáp án [3].

Tham số X phải khác với tham số X của mọi lần gọi Answer trước đó. Nếu không, bài làm bị chấm Sai đáp án [4].

Bạn phải gọi hàm này đúng \(N\) lần. Nếu không, bài làm bị chấm Sai đáp án [5].

Bạn được tự do cài đặt các hàm khác và khai báo biến toàn cục để sử dụng nội bộ. Tuy nhiên, bài nộp không được đọc hay ghi đầu vào chuẩn, đầu ra chuẩn hoặc bất kỳ tệp nào khác bằng bất kỳ cách nào.

Cách nộp bài

Nộp một tệp mã nguồn C++ chứa hàm Solve và include memory2.h. Không viết hàm main, không đọc đầu vào chuẩn và không ghi đầu ra chuẩn. Hệ thống chấm sẽ cung cấp các hàm Flip và Answer, đồng thời gọi Solve đúng một lần cho mỗi bộ kiểm thử.

Ràng buộc

Tất cả dữ liệu vào thỏa mãn các điều kiện sau:

• \(1 \le N \le 50\).
• \(0 \le P_i \le N - 1\) (\(0 \le i \le N - 1\)).
• \(P_i \ne P_j\) (\(0 \le i < j \le N - 1\)).
• \(0 \le A_i \le N - 1\) (\(0 \le i \le 2N - 1\)).
• Với mỗi \(x\) (\(0 \le x \le N - 1\)), có đúng hai chỉ số \(i\) (\(0 \le i \le 2N - 1\)) thỏa mãn \(A_i = x\).

Phân nhóm

1. 10 điểm: \(T = 1\); \(K = 10\,000\); \(P_i = i\) (\(0 \le i \le N - 1\)).
2. 50 điểm: \(T = 2\); \(K = 400\); \(P_i = i\) (\(0 \le i \le N - 1\)).
3. 40 điểm: \(T = 3\); \(K = 300\).

Ví dụ giao tiếp

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

1 3 10000
0 1 2
1 0 2 0 1 2

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

Cột bên trái là lời gọi hàm, cột bên phải là giá trị trả về. Hàm Answer không trả về giá trị.

Lưu ý rằng các lời gọi hàm trong ví dụ này không nhất thiết đều có ý nghĩa.

JOI đang chơi một trò chơi với một bàn cờ dạng lưới gồm \(3\) hàng và \(N\) cột, cùng một số quân cờ. Trong trạng thái ban đầu, có ít nhất một ô đã được đặt quân và ít nhất một ô chưa được đặt quân.

Mục tiêu của trò chơi là lần lượt đặt thêm từng quân vào các ô chưa có quân, sao cho cuối cùng mọi ô trên bàn cờ đều có quân. Tuy nhiên, chỉ được đặt quân vào một ô khi ít nhất một trong hai điều kiện sau được thỏa mãn:

• Cả ô ngay phía trên và ô ngay phía dưới ô đó đều đã có quân.
• Cả ô ngay bên trái và ô ngay bên phải ô đó đều đã có quân.

JOI muốn biết có tất cả bao nhiêu thứ tự đặt quân để đi từ trạng thái ban đầu đến khi đạt được mục tiêu. Tuy nhiên, số lượng này có thể rất lớn.

Nhiệm vụ của bạn là thay JOI tính số lượng các thứ tự đặt quân từ trạng thái ban đầu đến khi đạt được mục tiêu, lấy dư cho \(1\,000\,000\,007\).

Yêu cầu

Cho trạng thái ban đầu của trò chơi, hãy viết chương trình tính số lượng các thứ tự đặt quân để đạt được mục tiêu, lấy dư cho \(1\,000\,000\,007\).

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa số nguyên \(N\), cho biết bàn cờ có \(3\) hàng và \(N\) cột.
• Mỗi trong \(3\) dòng tiếp theo chứa một chuỗi gồm \(N\) ký tự. Mỗi ký tự là o hoặc x. Ký tự thứ \(j\) từ trái sang (\(1 \le j \le N\)) của dòng thứ \(i\) trong ba dòng này (\(1 \le i \le 3\)) biểu diễn trạng thái ban đầu của ô ở hàng thứ \(i\) từ trên xuống và cột thứ \(j\) từ trái sang. Ký tự o cho biết ô đó đã có quân ở trạng thái ban đầu; ký tự x cho biết ô đó chưa có quân ở trạng thái ban đầu.

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa số lượng các thứ tự đặt quân để đạt được mục tiêu, lấy dư cho \(1\,000\,000\,007\).

Ràng buộc

Tất cả dữ liệu vào thỏa mãn \(1 \le N \le 2\,000\).

Phân nhóm

1. 10 điểm: Ban đầu có không quá \(16\) ô chưa có quân; \(N \le 30\).
2. 12 điểm: Với mỗi ô chưa có quân ở trạng thái ban đầu, trong các ô kề ngay phía trên, phía dưới, bên trái và bên phải của nó, có không quá \(2\) ô chưa có quân.
3. 20 điểm: Ở trạng thái ban đầu, không có \(3\) ô chưa có quân liên tiếp theo chiều dọc; \(N \le 30\).
4. 38 điểm: \(N \le 300\).
5. 20 điểm: Không có ràng buộc bổ sung.

Ví dụ

3
oxo
xxo
oxo

14

10
ooxooxoxoo
xooxxxoxxx
oxoxoooooo

149022720

10
ooxoxxoxoo
oxxxxxoxxx
oxooxoxoxo

0

20
oxooxoxooxoxooxoxoxo
oxxxoxoxxxooxxxxxoox
oxooxoxooxooxooxoxoo

228518545