Pessoal,
Já tentei de tudo, mas não consigo passar o ep 6 no UVA de jeito nenhum!
Já testei todos os casos nos quais consegui pensar:
1) Saída=Destino (número mínimo = 0);
2) Número de turistas + guia = número exato de passageiros permitidos (número mínimo = 1);
3) 1 passageiro a mais que o permitido (além do guia) (número mínimo = 2);
4) mudei os arcos para ter que percorrer o maior caminho possível e deu certo;
5) Não existe caminho (número mínimo = 0);
6) Não existem turistas para serem transportados (número mínimo = 0)
7) e, só pra ter certeza de que a interpretação do item 6 acima estava correta, tentei até o caso em que não existem turistas, mas o guia vai sozinho (número mínimo = 1).
Não consigo pensar em mais nenhum caso! Alguém sabe de algum outro caso bizarro que eu deveria testar? Qualquer exemplo que vocês possam me passar já ajuda!
Veja se o seu algoritmo toma o valor calculado pra cada vértice já visitado como garantido. Se for o caso, repense... Isso me prendeu por um tempo. É pra ser uma variante do Dijkstra, mas com certas ressalvas.
Já tentei também levar em conta uma cidade cujos caminhos tenham número de passageiros máximo iguais a 0 e 1! (ou seja, não dá pra ir ninguém ou só dá pra ir o guia! A que ponto de apelação estou chegando! rs)
Eu não testei esses casos bizarros e passei minha tarefa.
Deve ser algum erro bobo ou um detalhe como
"Print a blank line after the output of each test case"
Recebi WA só por causa disso
Deve ser algum erro bobo ou um detalhe como
"Print a blank line after the output of each test case"
Recebi WA só por causa disso
Valeu, mas já verifiquei tudo o que estou imprimindo na saída e não parece estar errado (inclusive a linha em branco que deve ser impressa logo após cada caso teste).
Será que ninguém tem algum exemplo (diferente do da página do UVA) que tenha testado e que possa me passar? Todos os exemplo em que consegui pensar deram certo com meu programa!
Debora,
Este site permite avaliar o output que um programa "accepted" geraria a partir do input que vc definir:
http://uva.xgd.dk/problemssolve.php
Basta procurar pelo problema 10099, colocar o input que vc está testando e ver a saída correta.
Eu tive mais facilidade em usar o algoritmo Floyd-Warshall para esta tarefa. Não é complexo nem longo e reescrever o ep para utilizá-lo não me tomou mais de 40 minutos.
Boa sorte.
Fiz por Floyd-Warshall e não passa...
Carlos,
Usando Floyd-Warshall, só teseti se v == w -> Trip = 0 e passou!
(1) Você está mandando \n após imprimir o numero de viagens?
Tipo: "Minimu blah bla = %d\n\n"
(2) Não se esqueça de contar o motorista/guia, reduzindo um da capacidade de escoamento/transporte.
Valeu!
Eu já havia feito essas duas coisas. Obrigado pela ajuda.
Só uma coisa: quando vcs dividem o nº de pessoas pelo resultado (resultado-1, já q tem o guia, mas isso n vem ao caso), vcs estão pegando a resposta certa? Se a divisão é exata, a resposta está certa, mas se for quebrado, tem q somar 1, para a viagem do restante das pessoas.
Exatamente. Se NumeroTransportados % CapacidadeMinia != 0 -> Viagens++
Carlos, voce simulou no exemplo que esta no UVa? "Deu" 25?
Viagens = 99 / (25 - 1) = 4 ; 99 % (25 - 1) = 3 != 0 -> Viagens = 5;
Flw!!
Pessoal,
O site que o Nilo citou acima parece bem legal mesmo. O meu programa estava retornando respostas diferentes das do site para os casos bizarros. Para todos os casos normais que eu testei, estava correto. Se consegui um "Accepted"? Não sei: o UVA está completamente fora do ar! Aliás, preciso abrir um tópico a respeito...
Bom, pra quem quiser, os meus "casos bizarros" e as respostas que obtive do tal site estão abaixo:
Caso 1) S = D (Saída=Destino) -> Output = 1
7 10
1 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
1 1 99
(É, também achei isso estranho... muitas pessoas disseram que deveria ser 0 e logicamente, concordo. Todo caso, testem dos dois jeitos)
Caso 2) T = 0 (Turistas = 0) -> Output = 0
7 10
1 2 30
1 3 15
1 4 10
2 4 25
2 5 60
3 4 40
3 6 20
4 7 35
5 7 20
6 7 30
1 6 0
Caso 3) Não existe caminho do S até D -> Output = -T, onde T=número de turistas
7 7
1 2 30
1 3 15
1 4 10
2 4 25
3 4 40
5 7 20
6 7 30
1 7 99
Caso 4) Arcos até a cidade destino são zerados (ou seja, o máximo que dá pra levar até o destino são 0 turistas!) -> Output = -T
7 10
1 2 30
1 3 15
1 4 0
2 4 0
2 5 60
3 4 0
3 6 20
4 7 0
5 7 20
6 7 30
1 4 99
Caso 5) Zero estradas (caso estúpido, eu sei... mas o desespero faz isso com a gente! rs) -> Output = -T
7 0
2 1 99
Caso 6) Zero cidades (idem!) -> Output = -T
0 10
2 1 99
0 0
Tomara que possa ajudar! De novo: não consegui passar meu programa com esses resultados acima porque o Judge está fora do ar para manutenção. Se quiserem arriscar...
Legal seus testes! Resolvi o meu problema com a ajuda de um gerador de casos que o Piva fez. Depois ele achou um typo no meu código e agora parece que funciona (terei certeza quando o uva voltar). Um 'i' disfarçado de 'j'... 
Depois tirei um monte de coisas que havia acrescentado e continua funcionando. Portanto, Débora, sugiro que, ao invés de ficar se preocupando com detalhezinhos (como eu fiquei), procure por erros de digitação e experimente deixar outra pessoa lê-lo. Ela achará o erro provavelmente mais rápido que você.
Depois tirei um monte de coisas que havia acrescentado e continua funcionando. Portanto, Débora, sugiro que, ao invés de ficar se preocupando com detalhezinhos (como eu fiquei), procure por erros de digitação e experimente deixar outra pessoa lê-lo. Ela achará o erro provavelmente mais rápido que você.