Nosaukums
Īstās iekavu izteiksmes (iekavas4)
Laika limits
1.00s
Atmiņas limits
256.0 MB

Definīcija

Korektu iekavu izteiksmi definē šādi:

  • () ir korekta iekavu izteiksme;
  • ja A ir korekta iekavu izteiksme, tad (A) arī ir korekta iekavu izteiksme;
  • ja A un B ir korektas iekavu izteiksmes, tad AB arī ir korekta iekavu izteiksme.


Tā, piemēram, (()()) un ()()((())) ir korektas iekavu izteiksmes, bet )( un ()) -nav.

Aplūkosim visas korektās iekavu izteiksmes garumā 2N. Sakārtosim tās leksikogrāfiski augošā secībā, uzskatot, ka atverošā iekava mazāka par aizverošo, un sanumurēsim, sākot ar 1. Uzdevums – uzrakstīt programmu, kas atrod K-to izteiksmi šajā sakārtojumā.


Ievaddatu raksturojums

Ievaddatu pirmajā rindā dots skaitlis N (1 ≤ N ≤ 100), bet otrajā – K (1 ≤ K ≤ 101000+255), meklējamās izteiksmes kārtas numurs. Skaitļa K pieraksta sākumā var būt liekas nulles un tā pieraksta kopējais garums var pārsniegt 1001 simbolu.


Izvaddatu raksturojums

Izvaddatu vienīgajā rindā izvadiet K-to korekto iekavu izteiksmi garumā 2N. Izteiksme nedrīkst saturēt nekādus tukšumsimbolus.

Ja korekto iekavu izteiksmju skaits ir mazāks par K, izvadiet vārdu "NAV".


Piezīmes

No Krievijas informātikas olimpiāžu treniņsacensībām 2001. g.


Paraugdati

Stdin
2
20
Stdout
NAV

Stdin
2
2
Stdout
()()

Stdin
2
1
Stdout
(())

Uzdevums tiek aizsargāts ar autortiesībām un tā kopēšana vai neatļauta izmantošana ir aizliegta.