| Ուղարկել | Բոլոր լուծումները | Լավագույն լուծումները | Վերադառնալ ցուցակին |
KHPA - Կարենի և Հարրի Փոթերի արկածները |
Կարենը սիրում է ժամանակ առ ժամանակ համալսարանից հետո տուն գնալ ոտքով, և այսօր այդ օրերից մեկն է: Համալսարանը գտնվում է կոորդինատային ուղղի 0 կոորդինատով կետում, իսկ Կարենի տունը՝ L կոորդինատով կետում։ Կարենը չի գնում 0 կետից ձախ և իր տնից աջ, այսինքն քայլում է միայն [0, L] հատվածում: Նա սկսում է իր ճանապարհորոդությունը ամբողջ կոորդինատով կետից, կարող է շարժվել միայն աջ կամ ձախ և կարող է փոխել իր ուղղությունը միայն ամբողջ կոորդինատով կետերում։
Ինչպես բոլորս գիտենք՝ Հարրի Փոթերը հայտնի հրաշագործ է և փորձում է ամեն գնով հաղթել Վոլդեմորտին: [1, L]հատվածի ամբողջ կոորդինատով կետերում կան հորքրուքսներ, որոնք Հարրին ցանկանում է ձեռք բերել՝ Վոլդեմորտին հաղթելու համար: X կոորդինատով կետում կա ai հատ հորքրուքս, բայց կան նաև անպետք իրեր։ Հարրին ցանկանում է Կարենի օգնությամբ հավաքել որոշ հորքրուքսներ, իսկ մնացած հորքրուքսները հավաքել ինքնուրույն: Քանի որ Հարրին հրաշագործ է, նա կարող է Կարենին ուղարկել [0, L] հատվածի կամայական ամբողջ կոորդինատով կետ, իսկ հետո նաև ղեկավարել Կարենի շարժը:
Երբ Կարենը անցնում է X – 0.5 (որտեղ X-ը ամբողջ թիվ է) կոորդինատով կետով, Կարենի մոտ ավելանում է Xկոորդինատով կետում գտնվող իր։ Եթե X կոորդինատով կետում դեռ կա հորքրուքս, ապա Կարենի մոտ հայտնվում է այդ հորքրուքսը։ Հակառակ դեպքում՝ անպետք իր: Ճանապարհորդության ավարտին Հարրին վերցնում է Կարենի հավաքած բոլոր իրերը։
Հարրին այժմ ցանկանում է իմանալ, թե նվազագույնը ինչքան էներգիա նա պետք է ծախսի, որպեսզի Կարենի մոտից իրարը վերցնելուց հետո նա ունենա բոլոր հորքրուքսնեը, և չունենա անպետք իրեր:
Կարնեի մոտից իրերը վերցնելուց հետո Հարրին կարող է օգտագրծել հետևյալ 2 կախարդանքներից յուրաքանչյուրը ինչքան ցանկանա, սակայն ամեն անգամ որևէ կախարդանք օգտագործելը նրանից տանում է 1 էներգիա.
-
1. Նա կարող է վերացնել անպետք իր,
-
2. Նա կորող է իր մոտ բերել Կարենի չհավաքած հորքրուքսներից որևէ մեկը։
Մուտքային տվյալներ
Տրված են L-ը (1 ≤ L ≤ 2 · 105) և L հատ թիվ, որտեղ ai - ն (1 ≤ i ≤ L) i կոորդինատով կետում հորքրուքսների քանակն է (0 ≤ ai ≤ 109):
Ելքային տվյալներ
Պետք է արտածել, թե նվազագույնը ինչքան էներգիա պետք է ծախսի Հարրին՝ իր նպատակին հասնելու համար:
Օրինակներ
Մուտք. 4 1 0 2 3 Ելք. 1 Մուտք. 8 2 0 0 2 1 3 4 1 Ելք. 3
| Ավելացրեց. | Andreasyan |
| Ամսաթիվ. | 2019-03-18 |
| Ժամանակի սահմանափակումը. | 0.100s |
| Ծրագրի տեքստի սահմանափակումը. | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Լեզուներ. | C CSHARP C++ 4.3.2 CPP CPP14 JAVA PAS-GPC PAS-FPC PYTHON3 |
| Աղբյուրը. | Մարզային 2019 |
RSS