Օղակաձև ճանապարհ

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

Այդ մարզում կան քաղաքներ՝ -ից համարակալված, և որոնց հարթության վրա կոորդինատները հայտնի են։ Ռոբերտը ցանկանում է ընտրել որևէ հաջորդականություն բաղկացած չկրկնվող -ից թվերից, և ուղիղ ճանապրահով միացնել ու քաղաքները, որտեղ , և ու քաղաքները։ Արդյունքում կստացվի որևէ փակ բեկյալ հիշեցնող ճանապարհների համակարգ։ Սակայն Ռոբերտը ցանկանում է որ այդ բեկյալը լինի ուռուցիկ բազմանկյուն (դրական մակերեսով)՝ մարզի գեղագիտական մակարդակը պահպանելու համար։

-րդ քաղաքը ունի պահանջարկ լինելու օղակաձև ճանապարհի մաս լինելու։ Հարկավոր է գրել ծրագիր, որը կվերադարձնի մեկ օղակաձև ճանապարհ կառուցելու արդյունքում մաքսիմալ հնարավոր բավարարված պահանջարկը։

Մուտքային տվյալներ

Ստանդարտ մուտքի առաջին տողում տրված է թեստերի քանակը։ Ապա տրված են հատ մուտքային տվյալների հավաքածուներ։

Յուրաքանչյուր հավաքածուի առաջին տողում տրված է քաղաքների քանակը։ Հաջորդ տողերում տրված են ամբողջ թվերը՝ հերթական քաղաքի կոորդինատները և ցանցի մաս լինելու պահանջարկը։ Բոլոր քաղաքների կոորդինատները տարբեր են, և ոչ մի երեք քաղաք մեկ ուղղի վրա չեն գտնվում։

-ով նշանակենք բոլոր թեստերում -երի գումարը: Երաշխավորվում է, որ :

Ելքային տվյալներ

Ամեն թեստի համար պետք է արտածել մեկ թիվ՝ մաքսիմալ հնարավոր բավարարված պահանջարկը։

Օրինակ

Առաջին թեստում կառուցման տարբերակ․

Երկրորդ թեստում կառուցման տարբերակ․

Ենթախնդիրներ