Նվազեցնել հաջորդականությունը
Տրված է n թվերից բաղկացած հաջորդականություն ։ Ձեր խնդիրն է այն դարձնել հնարավորինս փոքր (լեքսիկոգրաֆիկ իմաստով)։ Հաջորդականությունը կարելի է լեքսիկոգրաֆիկ առումով նվազագույնի հասցնել, եթե փոխանակեք երկու թույլատրելի տարրեր։ Կարող եք կատարել որքան ուզեք փոխանակումներ, բայց որոշ ինդեքսներ հնարավոր է իրար հետ փոխանակել, իսկ որոշներն՝ ոչ:
Լեքսիկոգրաֆիկ համեմատություն երկու հաջորդականությունների միջև
Հաջորդականությունը լեքսիկոգրաֆիկ առումով ավելի փոքր է, քան , եթե և միայն եթե գոյություն ունի ինչ-որ ամբողջ k (1 ≤ k ≤ n), որտեղ , , …, և ։ Այլ կերպ ասած, կա մի ինդեքս k, որի դեպքում փոքր է -ից, մինչդեռ դրան նախորդող բոլոր տարրերը հավասար են:
Ձեզ տրված է թույլատրելի փոխանակումների մատրիցը, և խնդիրը պարզելն է, թե ի՞նչ լեքսիկոգրաֆիկ առումով ամենափոքր հաջորդականություն կարելի է ստանալ исходная հաջորդականությունից։
Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ n (1 ≤ n ≤ 300)։
Հաջորդ տողում տրված են n ամբողջ թվեր (1 ≤ ≤ n), որոնք տարբեր են միմյանցից և ներկայացնում են սկզբնական հաջորդականությունը։
Հաջորդ n տողերը պարունակում են n հատ 0 և 1, որոնք ցույց են տալիս, թե արդյոք երկու ինդեքսների տարրերի փոխանակումը թույլատրելի է։ Եթե i-րդ տողում և j-րդ սյունակում արժեքը 1 է, նշանակում է, որ i-րդ և j-րդ տարրերը կարելի է փոխանակել։ Եթե արժեքը 0 է, ապա փոխանակումը թույլատրելի չէ։
Ելք
Ծրագիրը պետք է տպի ամենափոքր (լեքսիկոգրաֆիկ) հաջորդականությունը, որ հնարավոր է ստանալ սկզբնական հաջորդականությունից։
Օրինակներ
Input | Մուտք |
|---|---|
5 | 1 2 3 4 5 |
7 | 1 2 4 3 6 7 5 |
Բացատրություն
Կարող ենք կատարել հետևյալ փոխանակումները.
↔⇒ 1 2 4 5 3↔⇒ 1 2 4 3 5↔⇒ 1 2 3 4 5
↔⇒ 1 2 4 5 3
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB