| Ուղարկել | Բոլոր լուծումները | Լավագույն լուծումները | Վերադառնալ ցուցակին |
GM11P2 - ԿՈՂՈՊՈՒՏ |
Գիշեր է։ Անորսալի Ջոնը ներխուժել է երկրի գլխավոր բանկի չհրկիզվող պահարանը։ Այստեղ շարքով տեղադրված են հատ արկղեր (բջիջ), որոնցից յուրաքանչյուրում առկա է ալմաստների որոշակի քանակ։ Հարմարավետության համար համարակալենք արկղերը ձախից աջ 1-ից բնական թվերով։
Ցավոք, Ջոնն անվտանգության համակարգերից վերջինը չէր անջատել։ Սակայն, նա գիտեր վերջինիս կառուցվածքը։ Ամեն րոպե անվտանգության համակարգը յուրաքանչյուր երկու հարևան արկղերում (որոնց համարների տաբերությունը հավասար է 1-ի) որոշում էր նրանցում գտնվող ալմաստների գումարային քանակը։ Արդյունքում ստացվում է (n-1) գումար։ Եթե անգամ նրանցից մեկը տարբերվում է համապատասխան գումարային այն ցուցանիշից, որը ստացվել է նախորդ ստուգման ժամանակ, ապա անվտանգության համակարգը սկսում է աշխատել։
Ջոնը կարող է ալմաստները տեղափոխել միայն անվտանգության համակարգի ստուգումների մեջ ընկած ժամանակահատվածում։ Մեկ րոպեի ընթացքում երկու ստուգումների մեջ ընկած ժամանակահատվածում նա հասցնում է կատարել m հատ տեղափոխությունից ոչ ավելի։ Տեղափոխություն է համարվում հետևյալ երեք գործողություններից մեկը. ալմաստի տեղափոխությունը ցանկացած արկղից այլ արկղ, ալմաստի տեղափոխությունը ցանկացած արկղից Ջոնի գրպան, ալմաստի տեղափոխությունը Ջոնի գրպանից ցանկացած արկղ։ Ի սկզբանե Ջոնի գրպանը դատարկ է: Ցանկացած արկղում և գրպանում տեղավորվում են անսահմանափակ քանակությամբ ալմաստներ։ Նշենք նաև, որ մինչև Ջոնի բոլոր գործողությունների կատարումը, համակարգը գոնե մեկ ստուգում է իրականացնում արկղերում։
Առավոտյան բանկ են գալիս աշխատակիցները, դրա համար Ջոնը պետք է մինչ այդ հեռանա բանկից։ Անվտանգության համակարգի ստուգումների մեջ ընկած ժամանակահատվածում Ջոնն ունի k հատ ընդմիջում, մինչև բանկը լքելը։ Այն ամենը, ինչ կմնա Ջոնի գրպանում, կհամարվի նրա գողոնը։
Որոշեք ալմաստների այն առավելագույն քանակը, որը Ջոնը կարող է տանել իր հետ։ Նշենք նաև, որ անվտանգության համակարգն այդ ամբողջ ընթացքում չպետք է աշխատի (նունիսկ Ջոնի բանկը լքելուց հետո), իսկ Ջոնը բանկը պետք է լքի մինչև լուսաբացը։
Մուտքային տվյալներ
Մուտքի առաջին տողում գտնվում են n, m և k ( 1≤n≤104, 1≤m, k≤109) ամբողջ թվերը։ Հաջորդ տողում գտնվում են թվեր, որոնցից i-րդը հավասար է i-րդ արկղի ալմաստների քանակին ամբողջ թիվ ընկած 0-ից մինչև 105:
Ելքային տվյալներ
Գրել մեկ ամբողջ թիվ ալմաստների այն առավելագույն քանակը, որը կարող է Ջոնն իր հետ դուրս բերել բանկից։
Օրինակներ
|
№ |
stdin |
stdout |
|
1 |
2 3 1 2 3 |
0 |
|
2 |
3 2 2 4 1 3 |
2 |
Ծանոթություն: Երկրորդ օրինակում Ջոնը կարող է գործել հետևյալ կերպ:Ի սկզբանե ալմաստների դասավորությունը 4 1 3 է։ Առաջին ընդմիջման ընթացքում Ջոնը տեղափոխում է մեկ ալմաստ 1-ին արկղից 2-ի մեջ և ևս մեկ ալմաստ 3-րդ արկղից իր գրպանը: Առաջին ընդմիջման ավարտին ալմաստների դասավորությունը 3 2 2 է։ Ստուգման արդյունքում համակարգը փոփոխություններ չի նկատում և անվտագության համակարգը չի գործարկվում։ Երկրորդ ընմիջման ընթացքում Ջոնը տեղափոխում է մեկ ալմաստ 3-րդ արկղից 2-րդ արկղի մեջ և մեկ ալմաստ 1-ին արկղից իր գրպանը։ Ալմաստների դասավորությունը երկրորդ ընդմիջման վերջում՝ 2 3 1 է։ Ստուգման արդյունքում համակարգը փոփոխություններ չի նկատում և անվտագության համակարգը նորից չի գործարկվում։ Ջոնը բանկից դուրս է գալիս գրպանում ունենալով 2 ալմաստ։
| Ավելացրեց. | Հրանտ Հովհաննիսյան |
| Ամսաթիվ. | 2013-10-29 |
| Ժամանակի սահմանափակումը. | 1s |
| Ծրագրի տեքստի սահմանափակումը. | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Լեզուներ. | Բոլորը բացի ASM32 ASM64 GAWK CLPS CLOJURE D ERL FSHARP FORTRAN GOSU HASK ICON ICK NEM NIM OBJC-CLANG PICO PIKE PYPY PYPY3 PY_NBC RUST SCM guile CHICKEN SED TCL WHITESPACE |
| Աղբյուրը. | Գյումրի 2011 |
RSS