عملات معدنية
Problem
في الأرض المسحورة ، يتم استخدام العملات المعدنية من الفئات A
1 ، A
2 ، ... ، A
M . جاء الرجل السحري إلى المتجر ووجد أن لديه عملات معدنية بالضبط من كل طائفة. يحتاج إلى دفع المبلغ N. اكتب برنامجًا لتحديد ما إذا كان يمكنه الدفع دون تغيير.
إدخال
عند مدخلات البرنامج نبسب؛ يأتي أولاً الرقم N (1 & lt؛ = N & lt؛ = 10 9 ) ، ثم الرقم M (1 & lt؛ = M & lt؛ = 15) ثم M الزوجي الأرقام المميزة A 1 ، A 2 ، ...، A M (1 & lt؛ = A i & lt؛ = 10 9 ).
بصمة
أول طباعة K - عدد العملات التي سيتعين على الرجل السحري تقديمها إذا كان بإمكانه دفع المبلغ المحدد دون تغيير. ثم اطبع أرقام K التي تحدد قيم العملات. إذا كان هناك العديد من الحلول ، فقم بطباعة المتغير الذي يعطي فيه الرجل السحري أصغر عدد ممكن من العملات المعدنية. إذا كان هناك العديد من هذه الخيارات ، فقم بطباعة أي منها.
إذا كنت لا تستطيع الاستغناء عن التغيير ، فقم بطباعة رقم واحد 0. إذا لم يكن لدى Magic Man ما يكفي من المال لدفع المبلغ المحدد ، فقم بطباعة رقم واحد -1 (ناقص واحد).
نبسب ؛
<الجسم>
| إدخال
| الإخراج
|
100 6
11 20 30 40 11 99
| 3
40 30 30
|