Cấm Tám

Xem dạng PDF

Gửi bài giải

Điểm: 1,50 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout

Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

To read the problem statement in English, choose the language using the flag on the navigation bar.

Ngày xửa ngày xưa, có hai chị em cùng cha khác mẹ tên là Cấm và Tám. Mẹ Cấm mất sớm, còn cha Cấm cưới thêm mẹ Tám. Tuy nhiên cha Cấm vô cùng hết mực yêu thương cô. Không may thay, cha Cấm lâm bệnh nặng, không lâu sau đó thì qua đời. Cấm phải sống chung với mẹ ghẻ là mẹ của Tám. Bà mẹ ghẻ là người cay nghiệt, hàng ngày bắt Cấm phải làm việc quần quật, phải làm cho hết mọi công việc trong nhà. Còn Tám thì ngược lại, được mẹ nuông chiều, không những không phải làm gì, mà ngày nào cũng đi chơi la cà, thậm chí còn hay bắt nạt Cấm.

Đến một ngày nọ, nhà Vua có mở hội linh đình, mời tất cả mọi người đến xem hội. Mẹ con Tám đã chuẩn bị tươm tất chuẩn bị đi hội. Nhưng cũng lường trước rằng Cấm cũng sẽ định xin đi cùng, mẹ con Tám đã nghĩ ra mưu kế nhằm không cho Cấm đi. Mẹ ghẻ sai Tám lấy ~n~ cái hũ có nhãn được đánh số từ ~1~ đến ~n~, cái hũ thứ ~i~ đong vào chính xác ~a_i~ hạt gạo. Lúc Cấm xin, mẹ ghẻ thách thức Cấm, bắt Cấm đong đi đong lại các hạt gạo trong ~n~ cái hũ đã cho, sao cho cuối cùng cái hũ thứ ~i~ phải chứa ~b_i~ hạt gạo. Nói xong, mẹ con Tám tức tốc bỏ đi hội, bỏ Cấm ở nhà một mình.

Tưởng chừng lời thách thức đơn giản, xong trong các hũ có rất nhiều gạo, đòi hỏi sự cân đo đong đếm chính xác hơn người để thực hiện. Hiểu được rằng đây là mưu kế bày ra để ngăn mình không đi hội, Cấm bật khóc. Lúc đó ông Bụt hiện lên, hỏi han Cấm. Sau khi nắm được tình hình, ông Bụt bảo Cấm xếp các hũ thành một vòng tròn, sao cho hũ đàu tiên nằm ở bên trái hũ thứ hai, hũ thú hai ở ở bên trái hũ thứ ba, ..., hũ thứ ~n~ ở ở bên trái hũ đầu tiên. Sau đó Bụt gọi hai chú chim xuống giúp Cấm di chuyển gạo. Trong một tích tắc, hai chú chim sẽ cùng nhau thực thao tác sau:

  • Chú chim đầu tiên sẽ chọn một hạt gạo trong một hũ bất kì, và di chuyển hạt gạo này sang hũ kế tiếp nằm bên trái.

  • Cùng lúc đó, chú chim thứ hai sẽ chọn một hạt gạo khác trong một hũ bất kì (có thể cùng với hũ mà chú chim đầu tiên đã chọn), và di chuyên hạt gạo này sang hũ kế tiếp nằm bên phải.

Di chuyển duy nhất một hạt gạo là một hành động chậm chạp đối với con người, xong đây là công việc mà hai chú chim có thể làm thoăn thoắt, với độ chính xác tuyệt đối. Chẳng mấy chốc mà hai chú chim có thể giúp Cấm sắp xếp lại các hột thóc thỏa mãn yêu cầu của mẹ ghẻ.

Tuy nhiên, vẫn có trường hợp mà chỉ dựa vào sự giúp đỡ của những chú chim vẫn không thể hoàn thành được thử thách mà mẹ ghẻ đã giao. Cho danh sách lượng gạo ban đầu trong các hũ, và danh sách lượng gạo cần phải đong vào từng cái hũ, hãy giúp Cấm kiểm tra xem có thể đong gạo chỉ với sự trợ giúp của hai chú chim hay không. Trong trường hợp có thể, hãy giúp Cấm tìm số lượng thao tác ít nhất mà hai chú chim cần thực hiện để đong gạo chính xác theo yêu cầu mà mẹ ghẻ đã giao, để Cấm sắp xếp chuẩn bị đi hội.

Input

Mỗi test bao gồm nhiều test case. Dòng đầu tiên chứa số ~t~ (~1 \le t \le 100~) là số lượng test case. Mỗi test case có mô tả như sau.

Dòng đầu tiên của test case chứa số nguyên ~n~ và số ~k~ (~1 \le n \le 10^5~, ~k \in \{0, 1\}~) là số lượng hũ gạo và chỉ số đặc biệt:

  • khi ~k = 0~, Cấm chỉ muốn kiểm tra xem có cách để hai chú chim tha gạo thỏa mãn yêu cầu của mẹ ghẻ không.

  • khi ~k = 1~, Cấm muốn tìm số thao tác tối thiểu mà chú chim cần thực hiện để thỏa mãn yêu cầu của mẹ ghẻ.

Hãy xem phần Output để biết thêm thông tin chi tiết.

Dòng tiếp theo chứa ~n~ số nguyên ~a_1, a_2, \ldots, a_n~ (~0 \le a_i \le 10^9~) là số lượng gạo ban đầu trong từng hũ.

Dòng tiếp theo chứa ~n~ số nguyên ~b_1, b_2, \ldots, b_n~ (~0 \le b_i \le 10^9~) là số lượng gạo cần phải đong vào từng hũ.

Dữ liệu đảm bảo tổng số hũ gạo của tất cả các test case trong cùng một test không quá ~10^6~.

Output

Với mỗi test case, nếu như không thể đong gạo chỉ với sự trợ giúp của hai chú chim, hãy in ra ~-1~. Ngược lại:

  • nếu ~k = 0~, hãy in ra số nguyên không âm bất kì.

  • nếu ~k = 1~, hãy in ra số thao tác ít nhất mà hai chú chim cần thực hiện để đong gạo thỏa mãn yêu cầu của mẹ ghẻ.

Scoring

  • Subtask 1, tương ứng với ~60~ điểm, có ~n \le 6~, và tổng số hạt thóc trong tât cả các hũ không quá ~6~.

  • Subtask 2, tương ứng với ~120~ điểm, có ~k = 0~.

  • Subtask 2, trương ứng với ~234~ điểm, không có ràng buộc gì thêm.

Tổng cộng bài toán có ~414~ điểm.

Sample Input 1

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

Sample Output 1

1
-1
0
2
1

Notes

Trong test case đầu tiên có duy nhất ~n = 2~ cái hũ, và Cấm muốn tìm số thao tác tối thiểu. Ban đầu chỉ có hũ thứ nhất chứa hai hạt gạo, và cần phải làm cho chỉ duy nhất hũ thứ hai chứa hai hạt gão. Hai chú chim có thể trong một bước di chuyển hai hạt gão này từ hũ thứ nhất sang hũ thứ hai.

Test case thứ hai cũng tương tự như test case thứ nhất, nhưng cần phải làm cho mỗi hũ có duy nhất một hạt gạo. Có thể thấy rằng, ngoài hai trạng thái ~[2, 0]~ và ~[0, 2]~ là hai trạng thái duy nhất có thể của các hũ gạo nếu bắt đầu đong tạo từ trạng thái ~[2, 0]~, nên ở test case này không có cách nào để thỏa mãn yêu cầu của mẹ ghẻ.

Ở test case thứ ba, số lượng gạo trong hũ ban đầu cũng đã khớp với lượng gạo cần đong, nên không cần thực hiện theo tác nào cả.

Tesst case thứ tư và cuối cùng là hai test case tương tự nhau, nhưng test case thứ tư yêu cầu tìm đáp án tối thiểu, trong khi test case thứ năm chỉ yêu cầu kiểm tra xem có cách thỏa mãn yêu cầu của mẹ ghẻ hay không. Cả hai test case đều có ~n = 3~ hũ. Ban đầu các hũ có lượng gạo là ~[1, 1, 4]~, và cần phải đong gạo để cuối cùng các hũ có lượng gạo là ~[4, 1, 1]~. Hai chú chim có thể di chuyển gạo như sau:

Bước Hũ gạo chú chim 1 chọn Hũ gạo chú chim 2 chọn Lượng gạo trong hũ
(Trước khi bắt đầu) ~[1, 1, 4]~
1 Hũ ~3~ Hũ ~3~ ~[2, 2, 2]~
2 Hũ ~2~ Hũ ~3~ ~[4, 1, 1]~

Fun fact: Câu truyện mô tả trong đề là câu truyện dựa trên câu chuyện cổ tích Việt Nam Tấm Cám. Song câu chuyện này cũng có nhiều nét tương đồng với câu chuyện Cô bé lọ lem ở châu Âu.


Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.