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

GRCODE - Գրեյի կոդը

Դիտարկենք k երկարությամբ 0 և 1 սիմվոլներով գրվող բոլոր տողերը: Գրեյի կոդը իրենից ներկայացնում է այդ տողերի այնպիսի հաջորդականություն, որում կամայական երկու հաջորդական տող իրարից տարբերվում են ուղիղ մեկ սիմվոլով: Հաջորդական են համարվում նաև առաջին և վերջին տողերը:

k =1 երկարությամբ Գրեյի կոդը հետևյալն է. 0, 1

k =2 երկարությամբ Գրեյի կոդը հետևյալն է.  00, 01, 11, 10

k երկարությամբ Գրեյի կոդից k+1 երկարությամբ Գրեյի կոդ ստանալու համար անհրաժեշտ է k երկարությամբ կոդը նույնությամբ արտագրել, այնուհետև, (2k + 1)–րդ տողից մինչև 2k+1-րդ տողերը լրացնել այնպես, որ (2k + i)-րդ տողում գրված լինի (2k - i + 1)-րդ տողը: Այնուհետև 1,…,2k տողերին անհրաժեշտ է ձախից կցագրել 0, իսկ 2k+1,..,2k+1  տողերին անհրաժեշտ է ձախից կցագրել 1:

Անհրաժեշտ է գրել ծրագիր, որը պատասխանում է երկու տեսակի հարցման: Առաջին տիպի հարցման դեպքում տրված  n և k թվերի համար պետք է արտածել k երկարությամբ Գրեյի կոդի n-րդ տողը: Երկրորդ տիպի հարցման դեպքում տրված տողի համար անհրաժեշտ է արտածել իր կարգահամարը իր երկարությամբ Գրեյի կոդի մեջ:

 

Մուտքը

Առաջին տողում տրված է հարցումների T(1<=T<=100000) քանակը: Հաջորդ T տողերից յուրաքանչյուրը սկսվում է զրոյով կամ մեկով: Եթե հարցումը սկսվում է զրոյով, ապա այն առաջին տիպի է և զրոյին հաջորդում են n և k(1<=k<=30) բնական թվերը, հակառակ դեպքում այն երկրորդ տիպի է և մեկին հաջորդում է ինչ որ երկարությամբ Գրեյի կոդի որևէ տող: 

Ելքը

Անհրաժեշտ է արտածել T տող, i-րդ տողում պետք է լինի i-րդ հարցման պատասխանը (վերջին տողից հետո անհրաժեշտ է արտածել նոր տողի անցման սիմվոլ):

Օրինակ

Մուտքը.
5

0 1 1

0 2 1

1 1

0 6 3

1 111 Ելքը. 0
1
2
111
6

Հեղինակներ
Ռոբերտ Դավթյան և Հրայր Հարությունյան

Ավելացրեց.Andreasyan
Ամսաթիվ.2013-02-18
Ժամանակի սահմանափակումը.1s-2s
Ծրագրի տեքստի սահմանափակումը.50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Լեզուներ.C CSHARP C++ 4.3.2 CPP CPP14 JAVA PAS-GPC PAS-FPC PYTHON3
Աղբյուրը.ֆիզմաթ 2013

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