Fişierul intrare/ieşire:trasee2.in, trasee2.outSursăLot Seniori Campulung 2018, baraj 4
AutorAdrian PanaeteAdăugată deandreicoman299Coman Andrei andreicoman299
Timp execuţie pe test0.5 secLimită de memorie524288 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Trasee2

Doi copii, Tren şi Bus, se plimbă de mână printr-o matrice cu N linii şi M coloane. Iniţial ei se găsesc în colţul din stânga–sus al matricei. Lui Bus îi place să meargă spre dreapta, iar lui Tren în jos. Astfel traseul celor doi va fi format numai din deplasări în poziţia vecină spre dreapta sau în jos. Visul lor este să treacă prin toate poziţiile matricei şi să revină în poziţia iniţială.
Atunci când se găsesc pe ultima coloană şi se deplasează spre dreapta, ei vor ajunge pe prima coloană a aceleiaşi linii, iar dacă se deplasează în jos de pe ultima linie, vor ajunge pe prima linie a aceleiaşi coloane. La fiecare deplasare ei notează pe o foaie litera B dacă deplasarea este spre dreapta, şi litera T dacă deplasarea este în jos.
Cunoscând N, M şi un număr natural K să se determine al K-lea traseu în ordine lexicografică care pleacă din colţul din sânga-sus, trece exact o dată prin fiecare poziţie şi revine în poziţia iniţială a matricei.

Date de intrare

Fişierul de intrare trasee.in conţine pe prima linie numerele N, M şi K cu semnificaţia din enunţ.

Date de ieşire

Fişierul de ieşire trasee.out trebuie să conţină un şir de N*M caractere format din literele B sau T reprezentând codificarea traseului cerut.

Restricţii

  • 1 ≤ N*M ≤ 1.000.000
  • 1 ≤ K ≤ 1018
  • pentru teste în valoare de 5 puncte se asigură că N*M ≤ 25
  • pentru alte teste în valoare de 10 puncte se asigură că N, M ≤ 15
  • pentru alte teste în valoare de 20 puncte se asigură că N = M, număr prim
  • pentru alte teste în valoare de 35 puncte se asigură că N = M
  • pentru toate testele există soluţie
  • Tren şi Bus în orice moment se află în aceeaşi celulă

Exemplu

trasee2.intrasee2.out
2 2 2
TBTB
1 6 1
BBBBBB
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?