RIDDLE - Bí hiểm
Giới hạn- Thời gian: 0.157s
- Bộ nhớ: 1536MB
- Mã nguồn: 50000 bytes
Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.
Bà của Ellenora thường ra cho cháu gái mình những bài toán đố mà Elly coi là bí hiểm. Buổi tối vừa rồi bà đố Elly bài toán sau:
“ Ở cửa hàng cạnh nhà ta có k mặt hàng với giá khác nhau từ 1 đến k . Bà có n đồng tiền mệnh giá a 1 , a 2 , . . ., a n . Bà định sang bên đấy mua một mặt hàng nào đó, trả đúng giá của nó mà không phải nhận lại tiền thừa. Nhưng bà đã già quá rồi. Bà không muốn mang tất cả tiền của mình đi, có thể lẫn hoặc rơi mất, vì vậy bà chỉ mang theo một số đồng đầu tiên . Vậy bà phải mang theo ít nhất bao nhiêu đồng tiền để mua được mặt hàng bất kỳ? ”
Chỉ mất vài giây Elly đã đưa ra được câu trả lời và nghĩ thầm trong bụng: “ Ôi, bà ơi, lại những bài toán giải thuật quá chuẩn! ”.
Bạn có thể đua tài với Elly bằng cách viết chương trình giải bài toán này được không?
Dữ liệu : Vào từ file văn bản RIDDLE.INP:
- Dòng đầu tiên chứa số nguyên T – số lượng tests trong file,
- Mỗi test cho trên 2 dòng:
- Dòng thứ nhất chứa 2 số nguyên n và k (1 ≤ n ≤ 10 5 , 1 ≤ k ≤ 10 6 ),
- Dòng thứ 2 chứa n số nguyên a 1 , a 2 , . . ., a n , (0 < ai ≤ 10 5 , " i = 1 ÷ n ).
Kết quả : Đưa ra file văn bản RIDDLE.OUT, kết quả mối test đưa ra trên một dòng dưới dạng số nguyên. Nếu không có cách mang thì đưa ra số -1.
Ví dụ:
Input 3 7 10 1 2 3 4 5 6 7 3 3 2 4 1 3 6 3 1 4 Output 4 3 -1
- Người up: songuku95