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.|

DIGRAFMG - Digrafos simples

Um digrafo simples é um grafo dirigido sem arestas repetidas. Note que um digrafo simples pode ter laços (no máximo 1 por vértice) e que se a aresta (u, v) existe, a aresta (v, u) também pode existir, mas não podem haver duas ou mais arestas (u, v).

Sejam e=e1, e2, ..., en e s=s1, s2, ..., sn duas sequências de inteiros não-negativos. Determine se existe ou não um digrafo simples de exatamente n vértices tal que o grau de entrada do i-ésimo vértice é ei e o grau de saída do i-ésimo vértice é si.

Entrada

Há vários casos de teste.

Cada caso de teste começa com uma linha contendo um inteiro positivo n (0 < n ≤ 1000), o número de elementos nas sequências e e s. A segunda linha contém n inteiros não-negativos e1, e2, ..., en (0 ≤ ei ≤ 1000, para todo i). A terceira linha contém n inteiros não-negativos s1, s2, ..., sn (0 ≤ si ≤ 1000, para todo i).

A entrada termina com n = 0, que não deve ser processado.

Saída

Para cada caso de teste, imprima uma linha contendo E se existe um digrafo simples que obedece às restrições propostas ou N caso contrário.

Exemplos

Entrada:
1
1
1
0

Saída:
E

O seguinte digrafo possui os graus pedidos:

Entrada:
2
0 2
0 2
0

Saída:
N

O grau de saída do segundo vértice é 2, e o grafo possui dois vértices. Logo, ele necessariamente tem que estar ligado a ambos. Mas o grau de entrada do primeiro vértice é zero, logo há uma contradição.

Entrada:
4
0 2 3 3
4 1 1 1
0

Saída:
N

A soma dos graus de entrada é 8. A soma dos graus de saída é 7. Em todo digrafo simples válido, a soma dos graus de entrada tem que ser igual à soma dos graus de saída.

Entrada:
4
3 2 1 1
4 1 1 1
0

Saída:
E

O seguinte digrafo possui os graus desejados:

Entrada:
4
1 1 2 3
0 0 3 4
3
0 2 2
2 1 1
0

Saída:
N
E

Adicionado por:Wanderley Guimarăes
Data:2012-03-14
Tempo limite:1.228s
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:Seletiva UFMG 2011

hide comments
2012-08-11 19:38:10 Bruno Henrique [UFOP]
baixem o pdf que possui as imagens
2012-05-12 22:13:12 Wisllay Vitrio [INF-UFG]
As imagens estăo corrompidas
2012-04-04 19:14:50 Ricardo Oliveira [UFPR]
Parece faltar uma imagem no primeiro exemplo de saída.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.