Ջրային դույլեր
Ձեզ տրված են միայն երկու դույլ, որոնց ծավալները
x և y են։ Անհրաժեշտ է ստանալ այդ երկու դույլերում գոյացած ջրի այնպիսի ընդհանուր քանակ, որը հնարավորինս մոտ է թիրախային s արժեքին։Թույլատրվում է կատարել առավելագույնը
k գործողություն հետևյալ տեսակներից.- Լեցնել դույլերից մեկը մինչև վերև
- Դատարկել դույլերից մեկը
- Մեկ դույլի պարունակությունը լցնել մյուս դույլի մեջ, դադարեցնելով, երբ երկրորդ դույլը լցվի կամ առաջին դույլը լրիվ թափայնի (կախված թե որը նախկինում տեղի կունենա)
Սկզբում երկու դույլերն էլ դատարկ են։
Բնորոշ է, որ միշտ չէ, որ հնարավոր է հասնել
s քանակին։ Ուստի խնդրվում է գտնել ամենափոքր |s - s’| արժեքը, որտեղ s’ը երկու դույլերում եղած ջրի ընդհանուր քանակն է:Մուտք
Մուտքի միակ տողում տրված են 4 ամբողջ թվեր
x, y (1 ≤ x, y ≤ 100), k (1 ≤ k ≤ 100), և s (1 ≤ s ≤ 200):Ելք
Ծրագիրը պետք է արտածի այն ամենափոքր տարբերությունը, որը հնարավոր է ստանալ, եթե կատարենք最多
k գործողություն:Օրինակներ
Input | Մուտք |
14 50 2 32 | 18 |
Բացատրություն
Թույլատրելի է կատարել միայն 2 գործողություն։ Ահա 2 գործողության արդյունքով հնարավոր որոշ փոխացումներ.
- (0, 0) → 0 միավոր
- (14, 0) → 14 միավոր
- (0, 50) → 50 միավոր
- (0, 14) → 14 միավոր
- (14, 36) → 50 միավոր
- (14, 50) → 64 միավոր
Այս բոլոր տարբերակներից 32-ի նկատմամբ ամենամոտը 14-ն է, և տարբերությունը հավասար է 18-ի։
Նկատի ունեցեք, որ (14, 36)-ից հետո, դատարկելով առաջին դույլը, կարելի էր ստանալ 36, բայց դա կպահանջեր 3 գործողություն, մինչդեռ թույլատրվում է最多 2։
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB