Ձևափոխման ալգորիթմ
Տրված է երկչափ զանգված (մատրից), որի տողերի և սյուների քանակները հավասար են, և տրված են x, y, z թվեր։ Ստորև ներկայացված է ալգորիթմ, որը ձևափոխում է տրված մատրիցը՝ ելնելով x, y, z թվերի արժեքներից։
Շրջել առաջին տողը։
Այնուհետև շրջել առաջին սյունը։
Հետո շրջել երկրորդ տողը։
Հետո շրջել երկրորդ սյունը։
Այդպես շարունակ, մինչև վերջին տող և սյուն։
Ստուգել արդյոք մատրիցի
x-րդ տողիy-րդ վանդակում (համարակալած 1-ից) գրված էz։ Եթե այո, ապա ավարտել ալգորիթմը, եթե ոչ, ապա վերադառնալ առաջին քայլին, և կրկնել ալգորիթմը ստացված նոր մատրիցի վրա։
Շրջել ասելով հասկանում ենք տողի կամ սյան առաջին և վերջին արժեքների տեղափոխումը, երկրորդ և նախավերջին արժեքների տեղափոխումը, և այդպես շարունակ։ Օրինակ՝ [4, 2, 41, 513, 80, 9, 10] - ի շրջումը կլինի՝ [10, 9, 80, 513, 41, 2, 4]։
Եթե տրված մատրիցի և տրված x, y, z թվերի համար կիրառված ալգորիթմը անվերջ կշարունակվի, անհրաժեշտ է արտածել impossible։ Այլապես պետք է արտածել ստացված մատրիցը ձևափոխությունն ավարտելուց հետո։
Մուտքային տվյալներ
Մուտքի առաջին տողում տրված են n, x, y, z (1 ≤ n, z ≤ 1000, 1 ≤ x, y ≤ n) բնական թվերը։
Մատրիցը տրված է հետևյալ կերպ՝ հաջորդ n տողերից յուրաքանչյուրում գրված են n հատ բնական թվեր՝ առանձնացված մեկական բացատով։ Այս թվերը նույնպես չեն գերազանցում 1000-ը։
Ելքային տվյալներ
Ելքում պետք է արտածել ստացված մատրիցը, եթե ալգորիթմը ի վերջո ավարտվում է, և impossible` հակառակ դեպքում։ Մատրիցը պետք է արտածել նույն ձևաչափով, ինչ մուտքում է՝ n տող, որում գրված n թվերը առանձնացած են մեկական բացատով։
Օրինակներ
Մուտք | Ելք |
3 1 1 6 | 6 2 1 |
3 1 1 10 | impossible |
Օրինակներում մատրիցը հետևյալն է՝
6 7 1
5 4 8
7 2 1Դժվար չէ նկատել, որ շրջումներից հետո նոր թիվ չի ավելանում մատրիցում, հետևաբար, քանի որ 10 չկա սկզբնական մատրիցում, երկրորդ օրինակի պատասխանը impossible է։ Դիտարկենք առաջին օրինակը։
Առաջին տողը շրջելուց հետո այն կդառնա՝
1 7 6
5 4 8
7 2 1Առաջին սյունը շրջելուց հետո՝
7 7 6
5 4 8
1 2 1Երկրորդ տողն ու սյունը, ինչպես նաև երրորդ տողն ու սյունը շրջելուց հետո կստացվի՝
7 2 1
8 4 5
1 7 6Առաջին տողի առաջին սյունում գրված չէ 6 (գրված է 7), հետևաբար ալգորիթմը շարունակվում է առաջին կետից։ Հաջորդ անգամ ալգորիթմի 6-րդ կետին հասնելիս մատրիցը դառնում է՝
1 7 1
5 4 8
6 2 7Կրկին, պետք է ալգորիթմը շարունակել առաջին կետից։ Այս անգամ 6-րդ կետին հասնելիս ստացվում է առաջին օրինակի ելքում նշված մատրիցը, որը և բավարարում է ալգորիթմի ավարտի պայմանին։
Constraints
Time limit: 10 seconds
Memory limit: 512 MB
Output limit: 10 MB