Ալգորիթմներ և Տվյալների Կառուցվածքներ

Նվազեցնել հաջորդականությունը

Տրված է 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 4 2 1 5 3 00100 00011 10010 01101 01010
1 2 3 4 5
7 5 2 4 3 6 7 1 0001001 0000000 0000010 1000001 0000000 0010000 1001000
1 2 4 3 6 7 5

Բացատրություն

  1. Կարող ենք կատարել հետևյալ փոխանակումները.
    1. ↔  ⇒ 1 2 4 5 3
    2. ↔  ⇒ 1 2 4 3 5
    3. ↔  ⇒ 1 2 3 4 5
  1. ↔ ⇒ 1 2 4 5 3
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue