Page 17 - MATINF Nr. 1

Concursul de Informatic˘a Programming Day 17

Clasele a XI-a s , i a XII-a

Problema 1 – paranteze
La ora de informatic˘a Georgic˘a a ˆınv˘at , at s˘a scrie parantez˘arile corecte folosind N perechi de
paranteze rotunde. O parantezare corect˘a respect˘a regulile din aritmetic˘a. Adˆancimea unei
parantez˘ari este num˘arul maxim de perechi de paranteze una ˆın alta. De exemplu, pentru N = 2,
parantez˘arile corecte sunt ()(), (()). Prima are adˆancimea 1, iar a doua 2. Pentru numerele
N, M s , i k, Georgic˘a vrea s˘a determine num˘arul de parantez˘ari cu M perechi de paranteze cu
adˆancimea cel mult k, precum s , i num˘arul total de parantez˘ari distincte cu 1, 2, ..., N perechi de
paranteze.
Cerint , ˘a
Cunoscˆand numerele N, M s , i k se cere:

1. num˘arul de parantez˘ari cu M perechi de paranteze s , i adˆancimea cel mult k, modulo
60013;
2. num˘arul total de parantez˘ari distincte cu 1, 2, ..., N perechi de paranteze modulo 60013.

Date de intrare
Fis , ierul de intrare paranteze.in cont , ine pe prima linie un num˘ar natural p. Pentru toate
testele de intrare, num˘arul p poate avea doar valoarea 1 sau 2.

Pe linia a doua se afl˘a N, M s , i k cu spat , iu ˆıntre ele.
Date de ies , ire
Dac˘a valoarea lui p este 1, se va rezolva numai punctul 1) din cerint , ˘a.
ˆ
In acest caz, ˆın fis , ierul de ies , ire paranteze.out se va scrie un singur num˘ar natural repre-
zentˆand num˘arul de la cerint , a 1.

Dac˘a valoarea lui p este 2, se va rezolva numai punctul 2) din cerint , ˘a.

ˆ
In acest caz, ˆın fis , ierul de ies , ire paranteze.out se va scrie un singur num˘ar natural repre-
zentˆand num˘arul de la cerint , a 2.
Restrict , ii s , i preciz˘ari

• 1≤N≤1000

• 1≤M≤15

• 1≤k≤M

• x modulo y reprezint˘a restul ˆımp˘art , irii lui x la y

• Pentru rezolvarea corect˘a a fiec˘arei cerint , e se acord˘a 50% din punctaj

Exemple
paranteze.in paranteze.out Explicat , ie
1 1 p = 1
2 2 1 N = 2, M = 2, k = 1. Avem dou˘a pa-
rantez˘ari ()(), (()). Prima are adˆancimea
1, iar a doua adˆancimea 2, astfel se
num˘ar˘a doar prima.