| Nộp bài | Các bài nộp | Làm tốt nhất | Về danh sách bài |
P17QPROJ - QUALIFY ROUND 2017 J - PHA CHẾ MATCHA |
Matcha trà xanh là một loại đồ uống khá phổ biến trong giới trẻ hiện nay. Matcha trà xanh được điều chế từ loại bột matcha có sẵn. Tại một quán Matcha gần PTIT, các sinh viên gọi loại matcha trà xanh có nồng độ bằng n. Tuy nhiên, cửa hàng đã pha sẵn k loại matcha có nồng độ a[1], a[2], …, a[k], và vì vậy đã hết lượng bột matcha dự trữ để pha chế mới. Chủ cửa hàng phải trộn các chai matcha có sẵn với nhau, sao cho đạt được nồng độ bằng n.
Giả sử rằng cửa hàng có vô số các chai matcha với mỗi loại nồng độ. Các bạn hãy tính xem cần sử dụng ít nhất bao nhiêu chai matcha có sẵn để tạo ra được loại matcha có nồng độ mà các bạn sinh viên yêu cầu? Nếu không tìm được đáp án, hãy in ra -1.
Input
Dòng đầu tiên gồm 2 số nguyên n và k (1 ≤ n ≤ 1000, 1 ≤ k ≤ 106).
Dòng tiếp theo gồm k số nguyên a[i] (0 ≤ a[i] ≤ 1000).
Output
In ra một số nguyên là số lượng chai matcha ít nhất cần sử dụng.
Example
Test 1:
Input: 400 4
100 300 450 500 Output: 2
Test 2:
Input:
50 2
100 25
Output:
3
Giải thích test 2: Sử dụng 1 chai 100 và 2 chai 25 tạo ra được loại matcha mới có nồng độ bằng (100+25+25)/3 = 50.
| Được gửi lên bởi: | adm |
| Ngày: | 2017-04-17 |
| Thời gian chạy: | 1s |
| Giới hạn mã nguồn: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Ngôn ngữ cho phép: | ASM32-GCC ASM32 ASM64 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-RHINO JS-MONKEY KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA |
