Թաքցված խնդիր
|Այս խնդիրը թաքցված է խմբագրական խրհրդի անդամի կողմից քանի որ կամ այն ոչ ճիշտ լեզվով է գրված,|կամ թեստային տվյալներն են սխալ, կամ խնդրի ձևակերպումը պարզ չէ։|

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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.