Հազվագյուտ մետաղադրամ
Դավիթն ունի N մետաղադրամների հավաքածու, որոնցից յուրաքանչյուրն ունի որոշակի անվանական
Բացի այս առաջնահերթ նպատակից, որ Դավիթը ցանկանում է ամեն գնով իրականացնել, նա ուզում է, որպեսզի այն մետաղադրամների արժեքների գումարը, որոնք կփոխանակվեն ցանկալի մետաղադրամի հետ, հնարավորինս փոքր լինի: Գրեք ծրագիր, որն օգնում է նրան կատարել այս դժվար ընտրությունը:
Մուտքային տվյալներ
Առաջին տողում տրված են երկու ամբողջ թիվ N և P
Ելքային տվյալներ
Ելքի առաջին տողում արտածեք երկու ամբողջ թվեր D և S (S ≥ P)՝ տարբեր անվանական արժեքների թիվը, որոնք մնում են Դավիթի մոտ, և փոխանակման ժամանակ օգտագործված մետաղադրամների արժեքների գումարը:
Օրինակ
Մուտք | Ելք |
8 21
1 5 5 5 0 7 4 7 9 | 4 21 |
7 100
90 2 2 3 3 6 6 | 3 101 |
Բացատրություն
Առաջին օրինակում մնում են {0, 4, 5, 5, 7} մետաղադրամները, որոնցում կան 4 տարբեր արժողությամբ մետաղադրամներ։ Կա այլընտրանքային լուծում՝ {4, 5, 5, 7}:
Երկրորդ օրինակում մնում են {2, 3, 6} երեք մետաղադրամները։ Իսկ տրվող մինիմալ գումարը 101 է։
Ենթախնդիրներ
- Ենթախնդիր 0 (0 միավոր) Օրինակը,
- Ենթախնդիր 1 (15 միավոր)
- Ենթախնդիր 2 (25 միավոր)
բոլորհամար,
- Ենթախնդիր 3 (25 միավոր)
- Ենթախնդիր 4 (35 միավոր) Լրացուցիչ սահմանափակումներ չկան:
Constraints
Time limit: 0.6 seconds
Memory limit: 512 MB
Output limit: 1 MB