gistfile1.txt

QUESTAO B
Bolos da Maria

Por Fabio Lima, Universidade de São Paulo - São Carlos BR Brazil
Timelimit: 1s

Dona Maria é uma senhora que está aposentada e faz doces. Ela começou a fazer bolos para complementar a renda da família.

Para fazer um bolo, Dona Maria precisa de certa quantidade de alguns ingredientes diferentes. Cada ingrediente tem um custo fixo por unidade. Ela tem uma quantia de dinheiro D máxima para gastar na compra dos ingredientes. Dentre os tipos de bolos que existem, você deve escolher apenas um tipo, de maneira a maximizar a quantia de bolos.

Calcule o número máximo de bolos de um único tipo que podem ser confeccionados.
Entrada

Formato:

Na primeira linha terá um inteiro T indicando o número de casos de teste.

Em cada caso, na primeira linha terão três números inteiros D, I e B indicando o dinheiro que Dona Maria tem, o número de ingredientes existentes e a quantidade de tipo de bolos existentes, respectivamente. Na próxima linha terão I números inteiros indicando o preço da unidade de cada ingrediente. Depois B linhas seguirão descrevendo cada bolo. O i-ésimo bolo é descrito da seguinte maneira. Primeiro há um número Qi que indica quantos ingredientes diferentes serão necessários. Logo em seguida seguirão Qi pares de números indicando o índice do ingrediente e a quantidade necessária, tudo na mesma linha separados por espaços.

Limites:

A quantia de cada ingrediente em um bolo irá de 1 até 1000. Cada unidade de um ingrediente custará entre 1 e 1000. Os ingredientes na descrição de cada bolo serão diferentes. Os identificadores de ingrediente vão de 0 até I-1.

1 ≤ D ≤ 109; T = 100; 1 ≤ I ≤ 100; 1 ≤ B ≤ 100; 1 ≤ Qi ≤ 100.
Saída

Para cada caso imprima o número máximo de bolos do mesmo tipo que podem ser confeccionados.
Exemplo de Entrada 	Exemplo de Saída

3

10 2 2

3 4

1 0 2

1 1 1

10 4 3

10 10 10 10

3 0 1 1 1 2 1

2 0 1 1 1

1 3 1

100 5 3

6 5 3 8 9

5 2 3 3 5 1 1 0 10 4 1

3 2 10 0 10 4 2

4 4 1 3 1 0 1 1 1
	
SAIDA
2

1

3

gistfile2.txt

QUESTAO D

 URI Online Judge | D
Dudu Faz Serviço

Por Rafael Regis, Universidade de São Paulo - São Carlos BR Brazil
Timelimit: 1s

Dudu precisa de um documento para finalizar uma tarefa em seu trabalho. Após pesquisar um pouco, ele descobre que este documento depende de outros documentos que, por sua vez, necessitam de outros documentos e assim por diante.

Dudu chegou a uma lista final com todos os documentos que deverá precisar. Com essa lista em mãos, ele suspeita que a mesma possui loops. Por exemplo, se um documento A depende do documento B que por sua vez depende do documento A, tornaria a tarefa interminável. Veja que neste caso o loop tem apenas dois documentos, pode haver loops com três ou mais!

Dada a lista das dependências entre os documentos, ajude Dudu a saber se um dia conseguirá todos os documentos, ou seja, se não existe um loop na lista.
Entrada

Formato:

Na primeira linha você terá um inteiro T indicando o número de casos de teste.

Na primeira linha de cada caso teremos os números inteiros N e M, indicando o número de documentos e as dependências existentes. Em cada uma das M linhas seguintes, terão dois inteiros A e B, indicando que o documento A depende do documento B. Pode haver dependências repetidas!

Limites:

1 ≤ A, B ≤ N; A != < strong>B.

T = 100, por volta de 90% dos casos de teste os limites serão:

2 ≤ N ≤ 100; 1 ≤ M ≤ 300.

Para os outros casos os limites serão:

2 ≤ N ≤ 104; 1 ≤ M ≤ 3*104​.
Saída

Para cada caso, imprima SIM caso exista pelo menos um loop e NAO caso contrário.
Exemplo de Entrada 	Exemplo de Saída

3

2 1

1 2

2 2

1 2

2 1

4 4

2 3

3 4

4 2

1 3
	

NAO

SIM

SIM

gistfile3.txt

QUESTAO F
 URI Online Judge | E
Elevador Lotado

Por Bruno Adami, Universidade de São Paulo - São Carlos BR Brazil
Timelimit: 1s

Em um prédio de N andares temos um elevador com capacidade para até C pessoas. Os andares são numerados de 0 a N-1. Há um grupo de M pessoas querendo usar o elevador, todas no andar 0. Cada uma deseja ir a um andar específico. Você deve decidir a ordem em que as pessoas devem usar o elevador de forma que a energia utilizada seja a menor possível.

Inicialmente um grupo de tamanho no máximo C pessoas decidido por você entra no elevador no andar 0. Depois você deve decidir a ordem em que os andares são visitados. Logicamente, os andares de todas as pessoas dentro do elevador devem ser visitados. O custo de energia do elevador é apenas no deslocamento, ou seja, a cada andar em que ele sobe ou desce você gasta uma unidade de energia. O processo é repetido até que não se tenha mais pessoas no andar 0. No fim o elevador deve voltar ao andar 0.

Dado o tamanho do prédio, a capacidade do elevador e os andares das pessoas que querem utilizar o elevador, monte a melhor estratégia que minimize a energia utilizada. Imprima o valor desta energia.
Entrada

Formato:

Na primeira linha você terá um inteiro T indicando o número de casos de teste.

Na primeira linha de cada caso teremos os números inteiros N, C e M. Na próxima linha teremos M inteiros indicando os andares a serem visitados pelas pessoas.

Limites:

1 ≤ C ≤ M; 1 ≤ N ≤ 104;os inteiros indicando os andares vão de 1 até N-1, inclusive.

T = 100, por volta de 90% dos casos de teste os limites serão:

1 ≤ M ≤ 1000.

Para os outros casos os limites serão:

1 ≤ M ≤ 5*104.
Saída

Para cada caso, imprima em uma única linha o valor da mínima energia necessária.
Exemplo de Entrada 	Exemplo de Saída

3

10 1 3

1 2 3

100 2 4

10 10 10 3

100 2 5

100 1 100 1 100
	
SAIDA

12

40

402

gistfile4.txt

QUESTAO F
 URI Online Judge | F
Formiguinha

Por Bruno Adami, Universidade de São Paulo - São Carlos BR Brazil
Timelimit: 1s

Uma formiguinha está andando sobre um tronco de árvore de tamanho N metros. Podemos considerar que a formiga pode assumir as posições de 0 até N-1. Assuma que ela está no eixo X dos planos coordenados, porém ela começa em uma posição desconhecida. A única coisa que se sabe sobre sua posição inicial é que é um número inteiro.

A formiguinha pode dar um passo para a esquerda ou direita, e este passo a desloca de um metro. Se ela está na posição P e dá um passo para a direita, ela assumirá a posição P+1. Se o passo for para a esquerda, ela assumirá a posição P-1. Se em algum momento ela assumir a posição -1 ou a posição N, ela cairá do tronco! Um passo leva um segundo para ser completado, e a formiga sempre está se movendo.

Considerando que a formiga fará sempre a pior sequência de passos possível, escolha uma posição inicial de modo que maximize o tempo em que a formiga permaneça no tronco. Imprima este tempo.
Entrada

Formato:

Na primeira linha você terá um inteiro T indicando o número de casos de teste.

Para cada caso teremos uma única linha com o número inteiro N indicando o tamanho do tronco da árvore.

Limites:

T = 100; 1 ≤ N ≤ 109.
Saída

Para cada caso, imprima o tempo máximo que a formiguinha pode ficar no tronco.
Exemplo de Entrada 	Exemplo de Saída

3

1

2

4
	

1

1

2

gistfile5.txt

QUESTAO G
 URI Online Judge | G
Goemon em Apuros

Por Filipe Nascimento, Universidade de São Paulo - São Carlos BR Brazil
Timelimit: 1

O lendário Ishikawa Goemon será fervido vivo em um grande caldeirão de ferro se for capturado! Para se esconder dos guardas nosso herói correu para dentro de uma casa que contém algumas paredes. Como é noite e a casa está escura os guardas jogaram uma bomba de luz para localizar o fugitivo. Tudo que for iluminado pela explosão da bomba será visto pelos guardas. A bomba emite infinitos raios de luz, em linha reta, para todas as direções partindo de seu epicentro.

Podemos simplificar este cenário usando um plano cartesiano 2D, onde as paredes da casa são segmentos da reta X = 0. O epicentro da explosão de luz sempre terá coordenada com valor X < 0. Os pontos onde Goemon pode se esconder sempre terão coordenadas com X > 0. A imagem abaixo ilustra o cenário iluminado quando a bomba no ponto E(-12,12) explode:

As paredes são descritas por segmentos de reta, e elas bloqueiam os raios de luz. No exemplo acima temos a parede A que vai do ponto A(0,0) até o ponto A1(0,2), a parede B que vai de B(0,4) até B1(0,6), a parede C que vai de C(0,10) até C1(0,12) e a parade D que vai de D(0,14) até D1(0,16). O epicentro da explosão de luz é o ponto E(-12,12) no exemplo dado, e Goemon tem as opções de ficar nos pontos G1(8,2), G2(12,14) e G3(10,10). Destes três pontos, ele só estará protegido no ponto G3, pois os raios de luz da explosão não alcançam este ponto mas alcançam os outros pontos (inclusive o G1), tornando-os visíveis para os guardas.

Dado o epicentro da explosão, as paredes e os pontos que Goemon pode ficar, calcule quantos destes pontos são seguros para ele se esconder.
Entrada

Formato:

Na primeira linha você terá um inteiro T indicando o número de casos de teste.

Na primeira linha de cada caso de teste terá a coordenada (x, y) do epicentro da explosão de luz. Na próxima linha terá um inteiro P, indicando o número de paredes existentes. Nas próximas P linhas seguirão pares de inteiros indicando as posições das paredes, onde começa e termina uma parede (lembre-se que elas ficam no eixo Y, ou seja, X = 0). Depois haverá um inteiro G indicando os pontos candidatos para Goemon se esconder. Depois G linhas seguirão com pares de coordenadas (x, y) indicando as coordenadas dos pontos.

Limites:

Todas as coordenadas irão de -104 até 104 e serão números inteiros. O centro da explosão terá X < 0 e as posições de Goemon X > 0. O Y inicial de uma parede sempre será estritamente menor do que o final. As paredes não estarão ordenadas. As paredes não se intersectarão, e não podem compartilhar um ponto inicial ou final. Pode ter posições repetidas de Goemon.

T = 100, por volta de 90% dos casos de teste os limites serão:

1 ≤ P,G ≤ 100.

Para os outros casos os limites serão:

1 ≤ P,G ≤ 104.
Saída

Para cada caso imprima o número de pontos que são seguros para Goemon ficar.
Exemplo de Entrada 	Exemplo de Saída

2

-12 12

4

0 2

4 6

10 12

14 16

3

8 2

10 10

12 14

-4 -4

3

10 11

-8 8

20 30

5

1 0

1 4

1 -4

1 100

1 -100
	

SAIDA 
1

3

gistfile6.txt

QUESTAO H
 URI Online Judge | H
Helpeie o Turista

Por Daniel Chino, Universidade de São Paulo - São Carlos BR Brazil
Timelimit: 1

Luís está de férias e gostaria de conhecer os pontos turísticos de Manhattan nos próximos K dias. Através de um mapa, ele sabe a localização dos N pontos turísticos e das M estações de metrô da cidade. Para apreciar bastante os passeios, ele irá visitar apenas um ponto por dia. Entretanto, ele é bastante preguiçoso e gostaria de caminhar a menor distância possível entre o ponto turístico e uma estação de metrô.

Em outras palavras, encontre K pares distintos de pontos turísticos e estações de metrô, de forma que a soma das distâncias destes pares seja o mínimo possível. A distância é medida usando-se a métrica de Manhattan, ou seja, dado um ponto A e outro B, a distância entre eles é definida por: D(A,B) = |A_x - B_x| + |A_y - B_y|. Mais informações sobre esta distância: http://en.wikipedia.org/wiki/Taxicab_geometry .
Entrada

Formato:

Na primeira linha você terá um inteiro T indicando o número de casos de teste.

Na primeira linha de cada caso de teste estarão três números inteiros N, M e K. Nas próximas N linhas estarão as localizações dos pontos turísticos e nas próximas M linhas as localizações das estações de metrô, todas dadas por um par de inteiros (x, y). Não há pontos turísticos ou estações de metrô na mesma localização.

Limites:

T = 100, por volta de 90% dos casos de teste os limites serão:

0 <= x,y <= 1000; 1 ≤ N,M ≤ 100; 1 ≤ K ≤ min(10, N*M).

Para os outros casos os limites serão:

0 <= x,y <= 105; 1 ≤ N,M ≤ 1000; 1 ≤ K ≤ min(10, N*M).
Saída

Imprima a soma das distâncias percorridas por Luís em cada caso. Lembre-se que você deve minimizar este valor.
Exemplo de Entrada 	Exemplo de Saída

3

1 2 1

0 0

2 2

1 1

2 1 2

2 2

2 3

2 4

5 4 5

1 1

2 3

4 2

5 4

6 1

1 2

2 1

2 6

4 4
	
SAIAD 
2

3

7

gistfile7.txt

 URI Online Judge | I
Insatisfação nas Eleições

Por Bruno Adami, Universidade de São Paulo - São Carlos BR Brazil
Timelimit: 1

Uma eleição foi feita em uma pequena cidade de M habitantes, onde havia N candidatos. As pessoas escreviam o número do candidato em um pedaço de papel, e inseriam na urna.

Ao final da eleição, se um candidato receber uma quantidade estritamente maior do que 50% dos votos, ele é considerado o vencedor. Caso contrário um segundo turno de eleições é feito.

Como o processo de contagem manual é muito lento, você deve desenvolver um programa que decide qual o candidato vencedor ou se nenhum recebeu votos suficientes e um segundo turno será necessário.
Entrada

Formato:

Na primeira linha você terá um inteiro T indicando o número de casos de teste.

Para cada caso de teste, na primeira linha você terá os números inteiros N e M. Na próxima linha, M inteiros seguirão separados por espaços, indicando o candidato em que cada pessoa votou, ou seja, o número escrito em cada pedaço de papel dentro da urna.

Limites:

1 ≤ N ≤ 10.

T = 100, por volta de 90% dos casos de teste os limites serão:

1 ≤ M ≤ 103.

Para os outros casos os limites serão:

1 ≤ M ≤ 5*104.
Saída

Para cada caso, imprima o número do candidato vencedor, ou -1 caso haverá segundo turno.
Exemplo de Entrada 	Exemplo de Saída

3

2 3

1 1 2

2 5

1 2 2 1 2

3 4

1 2 3 1

SAIDA	

1

2

-1