USACO 2024 - Tháng 2 - Hạng Bạc

Lưu ý: Giới hạn thời gian cho bài này là 2.5s, gấp 1.25 so với mặc định.
Lưu ý: Bài tập có thể sử dụng đến những số rất lớn, nên sử dụng kiểu số nguyên 64-bit (VD: "long long" trong C/C++).

Thế vận hội Moolympics đang đến gần và nông dân John đang gấp rút huấn luyện những con bò của mình bắn cung để đạt được huy chương vàng. Nông dân John đã thiết lập bài luyện tập có thể mô tả trên mặt phẳng toạ độ \(2D\)

• Có tất cả \(N\) (\(1 \leq N \leq 4 \times 10^4\)) mục tiêu hình chữ nhật và \(4\times N\) con bò. Mỗi con bò đều được chỉ định một đỉnh của mục tiêu. Tại thời điểm \(i\) \((1 \leq i \leq N)\) có các sự kiện:
  • Mục tiêu thứ \(i\) xuất hiện
  • \(4\) con bò ở các đỉnh được chỉ định bắn vào mục tiêu.
  • Nếu một con bò bắn vào mục tiêu trước khi bắn vào cạnh của nó hoặc bắn trượt, con bò đó sẽ không vượt qua bài tập.
  • Mục tiêu biến mất và mục tiêu tiếp theo xuất hiện
• Những con bò sẽ đứng bắn từ trục tung(\(x=0\)) của bản đồ nông trại.
• Mục tiêu thứ \(i\) có tọa độ của góc dưới bên trái là (\(X_1, y_1^{(i)}\)) và góc trên bên phải có tọa độ (\(x_2^{(i)},y_2^{(i)}\)). Tọa độ của các mục tiêu thỏa mãn \(1 \leq X_1 < x_2^{(i)} \leq 10^9\) và \(1 \leq y_1^{(i)}< y_2^{(i)}\le 10^9\)(Ghi chú: \(X_1\) giống nhau cho mọi mục tiêu)

Ngoài ra,mỗi con bò có một góc "tập trung" mà chúng đang luyện tập. Theo đó, chúng sẽ quay một góc cố định mỗi khi bắn. Biết rằng nếu cú bắn của chúng bay thẳng từ vị trí của chúng đến cạnh mà chúng được chỉ định, độ dốc đường bay của mũi tên của con bò thứ \(i\) có thể được mô tả bởi \(s_i\) (\(0 < |s_i| < 10^9\))

Để thẩm định kĩ năng của những con bò, nông dân John muốn những con bò đứng sát nhau nhất có thể. Nếu nông dân John chỉ định mục tiêu của những con bò một cách tối ưu và đặt chúng trên trục tung, khoảng cách nhỏ nhất giữa hai con bò cách xa nhau nhất sẽ là bao nhiêu hay chúng sẽ luôn trượt bài luyện tập.

Dữ liệu vào có tất cả \(T\) (\(1 \leq T \leq 10\)) test case riêng biệt. Dữ liệu đảm bảo tổng \(N\) của tất cả các test case không quá \(4 \times 10^4\).

Input:

• Dòng đầu tiên chứa \(T\) \((1 \leq T \leq 10)\)
• Dòng đầu tiên của mỗi test case chứa hai số nguyên \(N\) và \(X_1\) mô tả số lượng mục tiêu và vị trí của cạnh bên trái của những mục tiêu.
• \(N\) dòng tiếp theo chứa ba số nguyên \(y_1^{(i)}, y_2^{(i)}\) và \(x_2^{(i)}\) mô tả hình dạng của mục tiêu.
• Dòng cuối cùng chứa \(4N\) số nguyên \(s_{1}, s_{2}, \ldots, s_{4\times N}\), trong đó \(s_{i}\) là độ dốc đường bay của con bò thứ \(i\).

Output:

• Gồm \(T\) dòng trả lời cho từng test case, mỗi dòng là khoảng cách nhỏ nhất có thể giữa hai con bò ở xa nhau nhất hoặc "-1" nếu những con bò trượt bài tập.

Scoring:

• Subtask 1: \(|s_{i}|\) giống nhau với mọi \(1 \leq i \leq 4\times N\).
• Subtask 2: Tổng số \(N\) trong tất cả các test case không vượt quá \(1000\).
• Subtask 3: Không có ràng buộc gì thêm.

Example

3
2 1
1 3 6
4 6 3
1 -1 2 -2 3 -3 4 -4
2 1
1 3 6
4 6 3
1 1 2 2 3 3 4 4
2 1
1 3 3
4 6 3
1 -1 2 -2 3 -3 4 -4

17
-1
11

Bessie gần đây đã học hóa. Hiện tại, cô có hai loại hóa chất có hai màu khác nhau \(1,2\) và không thể hòa trộn với nhau. Cô có hai ống nghiệm có sức chứa vô hạn được đổ đầy bởi \(N\) (\(1 \leq N \leq 10^5\)) đơn vị của hai chất nói trên. Do hai loại chất lỏng không hòa trộn, khi hai loại chất lắng xuống, chúng chia thành các lớp màu riêng biệt trong hai ống nghiệm và có thể được mô tả bới hai xâu \(f\) và \(s\), trong đó \(f_1, f_2, \ldots, f_N\) mô tả chất lỏng trong ống nghiệm thứ nhất và \(s_1, s_2, \ldots, s_N\) mô tả chất lỏng trong ống nghiệm thứ hai từ dưới lên. Dữ liệu đảm bảo có ít nhất một đơn vị của cả hai chất tồn tại trong 2 ống nghiệm.

Bessie muốn tách hai loại chất lỏng này ra sao cho mỗi ống nghiệm chỉ có duy nhất một loại chất lỏng. Cô tìm thấy một ống nghiệm thứ \(3\) trong nhà kho và sử dụng nó để giúp tách hai chất lỏng ra. Mỗi khi Bessie thực hiện một lần "rót", cô sẽ đổ toàn bộ phần chất lỏng cùng màu phía trên cùng của một ống nghiệm vào một ống nghiệm khác.

Hãy giúp Bessie tính toán số lần đổ ít nhất để tách hai chất lỏng và cách đổ chi tiết. Lưu ý rằng sau khi kết thúc, ống nghiệm thứ \(3\) cần phải rỗng và \(2\) ống nghiệm ban đầu phải chứa \(2\) màu khác nhau.

Bessie có \(T\) (\(1 \leq T \leq 10\)) câu hỏi và có yêu cầu \(P\) cho mỗi câu hỏi như sau:

Giả sử \(M\) là số lần rót ít nhất để tách hai loại chất lỏng:

• Nếu \(P = 1\), Bessie chỉ cần bạn cho biết \(M\).
• Nếu \(P = 2\), Bessie cần bạn cho biết một số nguyên \(A\) sao cho \(M \leq A \leq M+5\), sau đó là \(A\) dòng mô tả cách rót chi tiết (kể cả khi không tối ưu). Mỗi dòng phải mô tả ống rót và ống được rót (\(1\), \(2\) hoặc \(3\)). Ống nguồn phải không trống trước khi di chuyển và không được đổ chất lỏng của một ống nghiệm vào chính nó.
• Nếu \(P = 3\), Bessie cần bạn cho biết \(M\) và một cách rót chi tiết.

Input:

• Dòng đầu tiên chứa \(T\), là số lượng các test case.
• Dòng đầu tiên của mỗi test case chứa hai số nguyên \(N\) và \(P\) mô tả lượng chất lỏng ban đầu của mỗi ống nghiệm và loại câu hỏi Bessie đặt cho bạn.
• Hai tiếp theo của mỗi test case lần lượt gồm \(f_1, f_2, \ldots, f_N\) và \(s_1, s_2, \ldots, f_N\). Cả hai dòng điều chỉ gồm kí tự "\(1\)" và "\(2\)", mô tả hai ống nghiệm theo chiều từ đáy lên.

Output:

• Gồm \(T\) dòng, mỗi dòng là câu trả lời cho từng câu hỏi của Bessie.

Scoring:

• Subtask 1: \(P=1\)
• Subtask 2: \(P=2\)
• Subtask 3: Không có ràng buộc gì thêm.

Ngoài ra, dữ liệu đảm bảo \(T=10\) cho tất cả các input ngoài test mẫu.

6
4 1
1221
2211
4 2
1221
2211
4 3
1221
2211
6 3
222222
111112
4 3
1121
1222
4 2
1121
1222

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

Bessie và Elsie đang chơi một trò chơi tên là Moorbles. Trong trò chơi này, hai cô bò sẽ có một số lượng bi ban đầu nhất định. Sau đó, Bessie nắm chặt \(A\) viên bi trong lòng bàn tay và sau đó Elsie phải đoán xem số lượng bi là lẻ hay chẵn. Nếu Elsie đoán đúng, cô sẽ thắng được số bi trong tay Bessie, ngược lại nếu đoán sai, cô ấy sẽ mất cho Bessie \(A\) viên bi. Trò chơi sẽ tiếp tục đến khi có một người mất toàn bộ số bi.

Sau một vài ván chơi, Elsie còn lại \(N\) (\(1 \leq N \leq 10^9\)). Cô ấy đoán rằng mình không thể chiến thắng nên đã cố gỡ hòa. Sau một hồi chơi, Elsie đã dần đọc vị được Bessie và biết được một số thói quen sau: ở lượt thứ \(i\), Bessie sẽ có tỉ lệ đưa ra \(K\) (\(1 \leq K \leq 4\)) một trong 4 số lượng bi nhất định. Chỉ còn \(M\) (\(1 \leq M \leq 3.10^5\)) lượt chơi nữa Bessie sẽ chán và ngừng chơi, hãy giúp Elsie không thua cho dù Bessie có chơi kiểu gì đi nữa!

Input:

• Dòng đầu tiên chứa một số nguyên \(T\) \((1 \leq T \leq 10)\) là số lượng test case
• Dòng đầu tiên của mỗi test case chứa ba số nguyên \(N\), \(M\) và \(K\), lần lượt là số lượng bi Elsie còn, số lượt còn lại và số lượng lựa chọn của Bessie
• \(M\) dòng tiếp theo, trong đó dòng thứ \(i\) gồm \(K\) số nguyên cách nhau bởi dấu cách \(a_{i,1} a_{i,2} \ldots, a_{i,K}\) (\(1 \leq a_{i,j} \leq 10^3\)) mô tả số lượng bi Bessie có thể đưa ra.
• Dữ liệu đảm bảo tổng \(M\) của tất cả test case không quá \(3 \times 10^5\)

Output:

• Gồm \(K\) dòng, mỗi dòng là câu trả lời cho từng test case, trong đó in ra cách để Elsia không thua theo thứ tự từ điển hoặc "-1" nếu cô ấy chắc chắn sẽ thua. Cách chiến thắng chỉ bao gồm một dòng chứa các từ "Even" hoặc "Odd".

Scoring:

Subtask 1: \(M \leq 16\).
Subtask 2: \(M \leq 1000\).
Subtask 3: Không có ràng buộc gì thêm.

Example

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

Even Even Odd
-1

-Trong test case đầu tiên, chuỗi lượt chơi tối thiểu theo thứ tự từ điển là "Even Even Even", nhưng Bessie có thể làm Elsie thua trong trường hợp này bằng cách đầu tiên chơi 5, làm giảm số bi của Elsie từ 10 còn 5, sau đó chơi 3, làm giảm số bi của Elsie từ 5 còn 2, và cuối cùng chơi 3, làm mất toàn bộ số bi của cô ấy.

-Nếu Elsie chơi theo chuỗi lượt chơi chính xác "Even Even Odd", thì ngay cả khi Bessie chơi theo cách đó, khi cô ấy chơi 3, Elsie sẽ nhận thêm 3 viên bi, làm tăng số bi của cô ấy lên 5. Có thể chứng minh rằng Bessie không thể chơi theo cách khác để lấy hết số bi của Elsie nếu Elsie chơi "Even Even Odd".

-Trong trường hợp thứ hai, có thể chứng minh rằng cho bất kỳ chuỗi lượt chơi nào mà Elsie có thể chọn, Bessie có thể lấy hết số bi của Elsie.