Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

EXPRES11 - Expressões

 

Pedrinho e Zezinho estão precisando estudar resolução de expressões matemáticas para uma prova que irão fazer. Para isso, eles querem resolver muitos exercícios antes da prova. Como sabem programar, então decidiram fazer um gerador de expressões matemáticas.

O gerador de expressões que eles criaram funciona em duas fases. Na primeira fase é gerada uma cadeia de caracteres que contém apenas os caracteres '{', '[', '(', '}', ']' e ')'. Na segunda fase, o gerador adiciona os números e operadores na estrutura criada na primeira fase. Uma cadeia de caracteres é dita bem definida (ou válida) se atende as seguintes propriedades:

    1. Ela é uma cadeia de caracteres vazia (não contém nenhum caractere).

    2. Ela é formada por uma cadeia bem definida envolvida por parênteses, colchetes ou chaves. Portanto, se a cadeia S é bem definida, então as cadeias (S), [S] e {S} também são bem definidas.

    3. Ela é formada pela concatenação de duas cadeias bem definidas. Logo, se as cadeias X e Y são bem definidas, a cadeia XY é bem definida.

Depois que Pedrinho e Zezinho geraram algumas expressões matemáticas, eles perceberam que havia algum erro na primeira fase do gerador. Algumas cadeias não eram bem definidas. Eles querem começar a resolver as expressões o mais rápido possível, e sabendo que você é um ótimo programador (e participa da OBI) resolveram pedir que escreva um programa que dadas várias cadeias geradas na primeira fase, determine quais delas são bem definidas e quais não são.

Entrada

A entrada é composta por diversas instâncias. A primeira linha da entrada contém um inteiro T indicando o número de instâncias. Em seguida temos T linhas, cada uma com uma cadeia A.

Saída

Para cada instância imprima uma linha contendo a letra S se a cadeia é bem definida, ou a letra N caso contrário.

Restrições

  • 1 ≤ T ≤ 20.
  • a cadeia de caracteres A tem entre 1 e 100000 caracteres.
  • a cadeia de caracteres A contém apenas caracteres '{', '[', '(', '}', ']' e ')'.

Exemplos

Entrada
12
()
[]
{}
(]
}{
([{}])
{}()[]
()]
{[]
(
(([{}{}()[]])(){}){}
(((((((((({([])}])))))))))

Saída
S
S
S
N
N
S
S
N
N
N
S
N


Adicionado por:Wanderley Guimarăes
Data:2012-03-10
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:OBI 2011 - fase 2 nível 2

hide comments
2014-05-21 05:33:44 Rodolfo Rodovalho
@Raphael Guimarăes

Tem que pensar sobre os contra-exemplos. Experimenta esse: (])
2014-05-21 04:14:24 Raphael Guimarães
"A entrada é composta por diversas instâncias". Faça um looping até scanf("%d",&numm)!=EOF
2014-05-21 04:06:51 Raphael Guimarães
@Jose a gente nunca sabe. É um tiroteio de cegos, tem que ficar adivinhando.
2014-05-21 00:27:46 Rodolfo Rodovalho
@Raphael Guimarăes

olhe novamente as restriçőes do problema, eles săo importantes..
2014-05-19 02:57:56 Raphael Guimarães
Estou com um problema de RunTime Error. Năo consigo entender esse site. Estou muito estressado com isso. Minhas respostas estăo corretas, mas sempre dá isso.

http://pastebin.com/m9LWhPv4




Last edit: 2014-05-19 03:00:22
2014-01-25 15:47:38 Rafael de Abreu
@Marcos Kawakami,
Tu matou a charada
Eu estava tomando TLE por esse motivo também
Valeu pela contribuiçăo :)
2013-02-21 04:35:06 Monael
@Kawakami
(Y) Era isso mesmo. Descuido meu. Valeu :)
2012-11-30 01:13:21 Marcos Kawakami
@Monael
Por acaso vocę colocou na condiçăo do laço algo do tipo i <= strlen(exp) ? Porque dessa forma o código fica N^2, já que a funçăo strlen é linear no tamanho da string!
2012-11-17 16:45:18 Monael
Existe alguma forma de concluir que é bem definida sem percorrer a cadeia toda?
Porque para dizer que năo é basta encontrar a primeira divergęncia entre o i-ésimo e o topo da pilha, porém para dizer que năo devo percorrer até o strlen da cadeia. Contudo, levo TLE nos últimos testes.
2012-10-30 01:21:12 Nilo[UFC]
Nao importa a ordem da saída, Cristhian [UTFPR], só o que importa é que o seu arquivo de saída seja idęntico ao gabarito.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.