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

CAVALOS - A lei vai a Cavalo!

A Polícia Montada Real Canadense (Royal Canadian Mounted Police) é uma instituição muito famosa, cujas origens remontam ao século XIX. Sua tarefa é levar a lei aos locais mais longínquos do país continental. Hoje a polícia montada tem um efetivo de 25000 homens e cerca de 5000 cavalos.

Cada sede da RCMP tem um haras em que os animais são muito bem cuidados, e designados aos policiais com quem têm mais afinidade. Esta afinidade é inferida em observações dos oficiais com vários anos de experiência, observando os policiais montando os animais disponíveis. No Fairmont Banff Springs Haras, onde ficam os cavalos montados pelos policiais da região de Banff Springs, é necessário resolver o problema de decidir quais soldados montarão quais cavalos. Note que um cavalo pode ser montado por vários policiais, mas um policial só monta um determinado cavalo. Cada cavalo tem um limite de policiais que podem montá-lo. Ou seja, de posse da afinidade dos vários policiais com os animais que montou nos últimos tempos, deseja-se encontrar uma atribuição dos cavalos aos vários policiais, de tal forma que o maior número possível de policiais tenham um cavalo para montar.

Entrada

A entrada é composta de diversas instâncias. A primeira linha de cada instância consiste em três inteiros n (1 <= n <= 100), m (1 <= m <= 100) e k (1 <= k <= 1000) indicando o número de cavalos, o número de soldados e o número de afinidades. A linha seguinte contêm n inteiros c1,c2,..,cn indicando que no i-ésimo cavalo pode montar ci (1 <= ci <= 100) soldados. Nas k linhas seguintes temos dois inteiros u (1 <= u <= n) e v (1 <= v <= m) indicando que existe afinidade entre o cavalo u e o soldado v.

A entrada termina com final de arquivo.

Saída

Para cada instância, você deverá imprimir um identificador Instancia k, onde k é o número da instância atual. Na linha seguinte imprima o número máximo de policiais que podem ter um cavalo para montar em uma atribuição.

Após cada instância imprima uma linha em branco.

Exemplo

Entrada:
5 3 7
1 1 1 1 1
1 1
1 2
2 1
2 2
2 3
4 3
5 3

Saída:
Instancia 1
3

Adicionado por:Wanderley Guimarăes
Data:2007-08-28
Tempo limite:1s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP JS-RHINO NODEJS PERL6 PY_NBC SCALA TCL VB.NET
Origem:Seletiva para Maratona de Programação do IME - 2007

hide comments
2011-07-09 20:57:16 Gabriel Poesia [UFMG]
Submeti e deu Tempo limite excedido. Testei no Ideone.com com 100 instâncias (repetindo as do exemplo dado) e rodou em 0.04s (Python 3). Alguma sugestăo? :(

Last edit: 2011-07-09 20:58:00
2010-11-21 15:03:21 Ruy Freitas Reis
Onde se pode achar mais exemplos?!?!?
2010-11-17 22:54:13 João Vitor de Sá Hauck
po manda uns exemplos maiores
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.