Só eu não tinha notado até hoje que tinha uma tarefa pra fazer desde a semana passada com data limite para hoje cedo?
Também vi só agora...
Também não vi.
idem aki... =/
É, eu reparei isso hoje a tarde e postei no outro post.
Falta o professor responder. =)
Ah! foi mal, eu li "0 comentários" e interpretei como "0 mensagens", achei que alguém tivesse postado alguma coisa e apagado...
Ele nem deu matéria o suficiente pra a gente fazer esse exercício. (ou deu?...)
ele não ensinou como se faz, mas com a matéria que ele deu dá pra fazer - basta criar e percorrer um grafo.
Salve,
Opss. Desculpem, não tinha me dado conta que havia mensagens no fórum.
Primeiro, eu não avisei sobre a Tarefa 1, pois não tinha falado nas aulas sobre
o que eu achava que devia e nem tinha pensado na data de entrega. O dia 24 que
estava lá só por estar e a Tarefa estava disponível só para vocês irem pensando.
Coloquei a data de entrega para o 11 de março, sexta-feira
de cinzas.
A Tarefa é bem simples.
O programa produzido será bem pequeno, vocês precisam
alterar um pouco o código das funções DIGRAPHpath e pathR.
Ao colocar alguém de um lado da mesa somos forçados a colocar
os "vizinhos" do outro, e os "vizinhos" dos "vizinhos" de um lado, e os
vizinhos dos vizinhos dos vizinhos do outro...
Hmmm. Acho que é só isto.
Opss. Desculpem, não tinha me dado conta que havia mensagens no fórum.
Primeiro, eu não avisei sobre a Tarefa 1, pois não tinha falado nas aulas sobre
o que eu achava que devia e nem tinha pensado na data de entrega. O dia 24 que
estava lá só por estar e a Tarefa estava disponível só para vocês irem pensando.
Coloquei a data de entrega para o 11 de março, sexta-feira
de cinzas.
A Tarefa é bem simples.
O programa produzido será bem pequeno, vocês precisam
alterar um pouco o código das funções DIGRAPHpath e pathR.
Ao colocar alguém de um lado da mesa somos forçados a colocar
os "vizinhos" do outro, e os "vizinhos" dos "vizinhos" de um lado, e os
vizinhos dos vizinhos dos vizinhos do outro...
Hmmm. Acho que é só isto.
Olá,
Eu vou ser o monitor de vocês nessa matéria, então qualquer problema podem me perguntar.
(Não vou fazer plantão de monitoria toda semana, mas quem quiser pode marcar um horário por aqui ou por e-mail - csrgamboa <arroba> gmail <ponto> com)
Sobre as tarefas, sempre tomem cuidado com leitura / escrita. A entrada vem da entrada padrão (ler com scanf, cin, etc) e a saída deve ser impressa na saída padrão (printf, cout, etc) EXATAMENTE como está especificado, ou o spoj pode devolver 'resposta errada'. Não esqueçam de enviar o código aqui no paca depois de serem aprovados lá.
Abraços,
César
Olá,
Não consigo entender como a entrada vem da entrada padrão. Ele diz que são várias intâncias e a entrada termina com o final do arquivo.
Mas como assim, final do arquivo O.õ?!
A entrada é por pipe. Por exemplo,
./foo < entrada
>"Não consigo entender como a entrada vem da entrada padrão."
Um programa executado em Linux q recebe arquivo de entrada na linha de comando usando o operador "<" como, por exemplo,
programa < entrada
recebe esse arquivo da entrada padrão. Outro exemplo é se vc espera algum dado do usuário e o captura no código usando scanf, aí quando vc roda o programa no terminal usando somente
programa
a execução pausa no momento em q o scanf está aguardando aqueles dados.
>"Ele diz que são várias intâncias e a entrada termina com o final do arquivo."
Sim, as várias instâncias são os vários casos. Ele passa todos numa mesma lista. No exemplo, ele diz
"A entrada é composta de diversas instâncias. A primeira linha de cada instância contém dois inteiros n (1 <= n <= 100) e m (0 <= m <= n(n-1)/2), onde n é o número de convidados e m é o número de relações de amizade. Cada uma das m linhas seguintes contém dois inteiros u e v indicando que u é amigo de v e v é amigo de u, onde 1 <= u,v <= n."
Entrada: 3 3 1 2 2 3 1 3 4 3 1 2 1 3 1 4 Saída: Instancia 1 nao Instancia 2 sim
então, a primeira linha (3 3) são as qtds de pessoas e de amizades do 1º caso. As "m linhas seguintes" (no caso, 3) são as relações de amizades desse 1º caso. Passadas as 3 linhas, acaba o 1º caso e vem os dados da 2ª instância: 4 3 indica q este tem 4 pessoas e 3 relações de amizade, que são as 3 linhas seguintes.
>"Mas como assim, final do arquivo O.õ?!"
Quando a lista passada na entrada acabar é o final do arquivo.
Espero ter ajudado!
As instâncias eu já tinha entendido, mais ainda estou confuso com a entrada.
Como faço para o programa receber um arquivo na linha de comando? Fazendo o main receber o nome do arquivo de entrada? Por exemplo:
int main (int argc, char *argv[])
Quanto a rodar com scanf, não entendi como parar a entrada.
"a execução pausa no momento em q o scanf está aguardando aqueles dados."
Quanto ao pipe, bem... não conheço, mas valeu a dica. Vou pesquisar a respeito.
"Como faço para o programa receber um arquivo na linha de comando? "
Você escreve normalmente o seu código para ler da entrada padrão (teclado). Não é preciso fazer o main receber nenhum argumento.
Ao executar o programa com a linha:
./programa < arquivo
você redireciona a entrada padrão para o arquivo especificado.
"Quanto a rodar com scanf, não entendi como parar a entrada."
A função scanf devolve EOF ao terminar de ler a entrada.
Então você pode escrever:
while (scanf("...", ....) != EOF)
para executar um bloco de comando até o final de arquivo.
Espero ter ajudado
Abraços,
Suzana
Você escreve normalmente o seu código para ler da entrada padrão (teclado). Não é preciso fazer o main receber nenhum argumento.
Ao executar o programa com a linha:
./programa < arquivo
você redireciona a entrada padrão para o arquivo especificado.
"Quanto a rodar com scanf, não entendi como parar a entrada."
A função scanf devolve EOF ao terminar de ler a entrada.
Então você pode escrever:
while (scanf("...", ....) != EOF)
para executar um bloco de comando até o final de arquivo.
Espero ter ajudado
Abraços,
Suzana
Entendi... sendo assim, é só usar scanf logo e eu só estou complicando >.<
Obrigado aos três.
É isso mesmo. O scanf devolve o número de elementos que foram lidos, ou EOF caso a entrada tenha acabado, então vocês podem usar tanto
while (scanf("%d %d",...) == 2) quanto while(scanf(...)!=EOF)
Notem que o segundo jeito assume que a entrada está bem formada (o que no nosso caso não tem problemas, mas é bom tomar cuidado ao fazer um programa que depende da inteligencia do usuario ). Se a entrada começar uma letra no lugar de um número por exemplo, o scanf vai devolver zero em vez de EOF. (isso foi só uma observação, os dois jeitos funcionam para as tarefas)
Se vocês quiserem fazer testes digitando em vez de ter que editar o arquivo de entrada toda hora, vocês podem simular um fim de arquivo com Ctrl+d no linux.
Só mais uma observação (por enquanto... :p): sempre terminem o main com um return 0 (zero). Quando um programa devolve algo diferente de zero é um sinal para o sistema de que houve algum erro, então não colocar o 'return 0' pode fazer com que vocês recebam "erro em tempo de execuçăo".
Se alguém ainda está confuso, um jeito (não único) de fazer a estrutura básica do programa é:
int main(){
_while ( scanf("%d %d", &n, &m) == 2){
__//ler m linhas com as arestas e criar o grafo
__//... <- use seus conhecimentos de grafos aqui
__printf("Instancia %d\n", k);
__if (ePossivel) printf("sim\n");
__else printf("nao\n");
__printf("\n");
_}
_return 0;
}
“Nas tarefas vocês devem utilizar as estruturas das notas de aula. ”
Isso quer dizer que nas notas de aula há algum código que eu preciso baixar e usar ou apenas que devo usar uma matriz de adjacência (implementada como eu desejar)?
Isso quer dizer que nas notas de aula há algum código que eu preciso baixar e usar ou apenas que devo usar uma matriz de adjacência (implementada como eu desejar)?
Um pouco mais sobre a tarefa 1.
Eu fiz o programa e ele funcina normalmente com a saida examente como o problema pediu, porem quando vou submeter ao site ele aparece 'resposta errada', eu coloco o codigo no paca mesmo assim?
Outra coisa é que nas especificacoes do problema ele disse que o numero de 'convidados' nao ia ser mair do que 100, mas nao disse como o meu programa deve se comportar caso alguem digite algum valor maior do que 100.
Cleisson, se aparece "resposta errada" é porque seu progama não se comporta como esperado para alguma instância que o juiz online testa (ele testa muito mais do que os exemplos dados na especificação). Pode ser que você só tenha testado instâncias para as quais seu programa dá a resposta certa e tenha esquecido algum tipo de caso.
Além disso, se nas especificações do problema ele diz que o número de convidados será no máximo 100, isso significa que o juiz online vai obedecer a essa condição. Ou seja, você não precisa tratar exceções nem nada; você pode supor que a entrada será "bonitinha".
Tiago, pode implementar do seu jeito, sim (mas tentem manter uma estrutura parecida com a vista em aula e um código bem escrito)
Cleisson, se o spoj marca resposta errada é porque ou a saída não está sendo impressa do jeito pedido ou porque o programa não está correto sempre...
Tenta verificar alguns casos diferentes, principalmente os extremos (o mínimo de nós, o máximo de nós, poucas arestas, muitas arestas, grafos desconexos, etc). Os testes são sempre feitos dentro dos limites do enunciado, não precisa se preocupar com isso (no caso, o programa nunca vai ser testado com mais de 100 vértices ou com um número impossível de arestas)
Se você está realmente confiante no seu código, você pode verificar se a saída está sendo impressa corretamente mesmo.
Cria um arquivo de texto com a entrada e outro com a saída esperada (copiadas do enunciado) e usa o comando diff do linux:
./seuprograma < entrada.txt > suasaida.txt
diff suasaida.txt saidaesperada.txt
Se nada for impresso, significa que o programa está correto para essa entrada. Na verdade é basicamente isso que o juiz faz quando você manda, mas obviamente numa entrada com muito mais casos (é bem útil ir adicionando casos novos a esses arquivos conforme você vai pensando neles, assim você pode perceber fácil se algo que você mudou quebrou um caso que já funcionava)
Eu recebo a mensagem "tempo limite excedido".
zzzz
Isso depois de consertar um segfault que dava para o Spoj mas nao para mim.
Detesto que ele reclama do programa mas nao indica onde/qual é o problema.
(tenta usar as perguntas abaixo nessa ordem)
1 - O programa pára com fim de arquivo? (Ctrl+d após digitar a entrada ou usando um arquivo: './programa < entrada.txt')
2 - Existe algum caso em que o seu programa pode entrar em um loop infinito?
3 - Você está usando uma ideia "boa" para resolver esse problema? (qual a complexidade de tempo no pior caso? isso parece aceitável para os limites desse problema?)
4 - Em último caso (acho bem improvável), o seu programa faz muitas operações desnecessárias? (É possivel melhorar a velocidade mantendo a ideia mas arrumando detalhes de implementação?)
Sobre o Spoj não dizer qual é o problema, eu sei que é chato, mas a ideia é essa... (a parte de não dizer o problema, não o fato de ser chato :p) Vocês tem que fazer um programa que funcione em um tempo aceitável para qualquer caso possível (dentro das especificações da entrada). Um segfault que aparece lá mas não pra você é um problema que existe no seu código e pode aparecer para um usuário.
PS: Não esqueçam de entregar o código no Paca até o fim do prazo.
1- sim
2- Impossível
3- isso já pode estar ruim. creio que meu programa seja O(V^2), nao sei quanto seria "aceitavel", o spoj nao especifica o tempo esperado.... Tmb n acho que devo sair falando como implementei aqui no forum.
4-evidentemente poderia estar mais otimizado já que eu excedo o limite de tempo... Todos os lugares que posso conceber podar alguma coisa poderiam trazer alguma consequencia chatinha (tipo nao verificar se um arco inserido é valido, etc). Deve ter algo que n estou vendo.
A sua resposta me deu uma duvida quanto a mensagem de erro do Spoj de "exedido limite do tempo". Inicialmente eu acreditava que ele estava aceitando minha saida como correta mas reclamando que demorava muito. Se eu enviar um programa que é essencialmente apenas um loop infinito (while(1){}), ele vai dar a mesma mensagem? Tipo, posso aceitar a falta de aviso de segfault ou resposta errada como certeza de que pelo menos certo esta, por mais que ineficiente?
De qq modo acho que vou mudar a estrutura de dados e os algorítimos de DFS que estou usando para ver se melhora... Mas para o EP ser entregue ele precisa msm estar como "aceito" pelo spoj, como esta no enunciado?
vlw pela ajuda.
PS: o prazo mudou? eu jurava que era dia 11.
Olá Reverbel.
Muitas pessoas têm implementado o algoritmo em O(n²). É bem povável que seu algoritmo entre em loop porque em uma das versões o meu também entrava e aparecia esse problema "excedido limite do tempo". Inclusive meu erro foi esquecer de incrementar uma variável que regulava o while.
Isso significa que não necessariamente se o EP entrar em loop vai dar seg. fault.
Acho que faz sentido entregar algo melhor ou tão bom quanto o que vocẽ submeteu no spoj.
Se não der pro seu EP ser aceito no spoj, aí tem que ver com o monitor/professor pra ver como é a correção da tarefinha.
O prazo mudou sim. Era dia 11 mesmo.
Espero ter ajudado em algo.
Abraços,
Jackson.
Esclarecendo os resultados do spoj:
O programa é rodado durante um tempo (no caso desse problema 2 segundos). Se o programa não acabou de rodar (não importa o que ele escreveu durante esse tempo), é tempo limite excedido - então não dá pra dizer nada sobre ele estar respondendo certo... Se ocorreu algum problema como segfault (ou seja, o programa devolveu algo diferente de zero), é erro em tempo de execução. Se o programa terminou durante esse tempo, a resposta é comparada com o esperado e você recebe aceito ou resposta errada.
Realmente, essa complexidade deveria passar a menos que a constante esteja muito alta. Sei que você falou que não acha que é, mas ainda parece provavel que seja um loop infinito (lembrando que isso pode acontecer não só nos while, mas também nas chamadas recursivas - em algum caso a dfs voltar pra um nó ja visto ou até ficar no mesmo nó - ou por um problema nos ponteiros da estrutura se você fez com lista de adjacencia em vez de matriz)
Se não conseguir, entregue o código mesmo assim. Passar o problema no spoj é importante, vocês devem se esforçar para isso (afinal é um sinal de que o ep não está correto), mas é melhor entregar um código que não passa do que não entregar nada. (se quiserem, em caso de problema vocês podem colocar um readme ou um comentário no código explicando o erro / o que vocês tentaram fazer para encontrar/arrumar)
Bem, ainda nao consegui achar o loop infinito, mas enquanto eu brincava de montar uma bateria de testes na tentativa de ver ele aparecer eu me deparei com algums casos que nao sei se estou lidadndo corretamente. Nem sei se sao entradas validas com as quais eu deveria me preocupar, mas vou coloca-las aqui.
0 0
sim
----------- (estou devolvendo sim para uma entrada de zero vertices com zero relacoes de amizade)
5 0
sim
----------- (ta essa me parece correta mesmo. 5 pessoas que nao se conhecem podem sentar na mesa como bem entenderem)
0 5
0 0
0 0
0 0
0 0
0 0
sim
-------------
Daniel,
0 0 e 0 5
são entradas inválidas segundo a descrição do programa:
"A entrada é composta de diversas instâncias. A primeira linha de cada instância contém dois inteiros n (1 <= n <= 100) e m (0 <= m <= n(n-1)/2), onde n é o número de convidados e m é o número de relações de amizade. Cada uma das m linhas seguintes contém dois inteiros u e v indicando que u é amigo de v e v é amigo de u, onde 1 <= u,v <= n."
Agora 5 0, ao meu ver está correta(segue a descrição acima).
Espero ter ajudado
Giancarlo
0 0 e 0 5
são entradas inválidas segundo a descrição do programa:
"A entrada é composta de diversas instâncias. A primeira linha de cada instância contém dois inteiros n (1 <= n <= 100) e m (0 <= m <= n(n-1)/2), onde n é o número de convidados e m é o número de relações de amizade. Cada uma das m linhas seguintes contém dois inteiros u e v indicando que u é amigo de v e v é amigo de u, onde 1 <= u,v <= n."
Agora 5 0, ao meu ver está correta(segue a descrição acima).
Espero ter ajudado
Giancarlo
Ah, claro. Devia ter relido o enunciado antes de perguntar, valeu.
Eu fiquei apanhando do EP durante o feriado inteiro e só agora ele passou.
O que me surpreendeu foi que os tempo limite excedidos não eram causados por um problema no algoritmo, mas sim no jeito que eu usava a memória.
Alguém saberia me explicar porque alocar memória e inicializar com zero a matriz a cada instância é tão mais rápido do que só limpar uma matriz NxN até a posição que eu iria usar?
Não sei se ajuda, mas eu estava passando a matriz por referência.
= ]
Finalmente passou. Era mesmo so alocacao de memoria que estava comendo todo o meu tempo. Valeu pela dica solfer!