PUC-Rio
Departamento de Informática
Profs. Marcus Vinicius S. Poggi de Aragão
Período: 2004.2
Horário: 3as-feiras e 5as-feiras de 15-17
21 de outubro de 2004
Data da Entrega: 11 de novembro de 2004

ESTRUTURAS DISCRETAS (INF 1631)

1^o Trabalho de Implementação

Descrição

Este trabalho prático consiste em desenvolver um código para resolver o problema descrito abaixo. O desenvolvimento deste código deve seguir o seguinte roteiro:

Demonstrar o entendimento do problema, explicando em detalhe o resultado que o algoritmo deve obter.
Descrever o algoritmo proposto para a sua resolução.
Explicar a fundamentação do algoritmo e justificar a sua corretude. Preferencialmente, prove por indução matemática que o algoritmo obtém a resposta desejada.
Documente o arquivo contendo o código fonte de modo que cada passo do algoritmo esteja devidamente identificado e deixe claro como este passo é executado.

A descrição do problema, abaixo, contém a especificação do arquivo de entrada e da saída desejada. A corretude código será testada sobre um arquivo de entrada que será distribuido após a entrega do trabalho. O trabalho entregue deve conter:

Um documento contendo o roteiro de desenvolvimento do algoritmo (e do código), comentários e análises sobre a implementação e os testes realizados (papel).
A impressão do código fonte (papel).
Um e-mail ou disquete contendo o código fonte e o executável correspondente (no caso do e-mail é obrigatório o uso do assunto (ou subject) ED042T1).

Go Easy

Uma cidade acaba de implantar um novo sistema de cobrança dos transportes públicos urbanos. O sistema de transportes opera com trens e ônibus. A tarifação é feita em unidades de transporte UTs (uma espécie de vale transporte com valor fixo). Para o ônibus cada viagem é paga. A tarifa para os trens é baseada nas zonas das estações de entrada e de saída do trem. O valor é determinado seguindo as regras:

Paga-se 2 UTs toda vez que se entra no sistema de transportes, seja em um trem ou em um ônibus.
Se passageiro pegou um trem, ele paga 4 UTs se as zonas da estações de origem e destino forem diferentes, caso contrário nenhuma UT adicional é paga.
Para cada ônibus que o passageiro pega ele paga 1 UT.

Um mapa do sistema de transportes é fornecido como entrada. Nele encontra-se uma lista das estações com suas respectivas zonas (que são usadas pelos trens e pelos ônibus, por exemplo, um ponto de ônibus é uma estação sem trem). Encontra-se também os itinerários dos trens e dos ônibus dados por sequências de estações.

Os trens e os ônibus movem-se nos dois sentidos em cada itinerário e nenhum trem ou ônibus passa duas vezes em uma mesma estação durante uma ÚNICA viagem (ao final de cada viagem os passageiros devem descer do trem ou ônibus).

O objetivo do trabalho é implementar um algoritmo que, dados o mapa do sistema de transportes, os itinerários dos trens e dos ônibus, a origem e o destino do passageiro, encontre os ônibus e trens que o passageiro deve pegar, explicitando onde este deve trocar de ônibus ou de trem, de modo que o custo em UTs seja mínimo.

Um arquivo contendo várias entradas de dados (os descritos acima) será disponibilizado. Em todas as entradas (mapas) existem meios para se transportar entre qualquer par de estações. Outra observação importante é de que as regras são estritas, se um passageiro pega duas vezes o mesmo ônibus ele paga as duas vezes, se ele entra duas vezes na mesma zona (em viagens diferentes) ele paga as duas vezes.

Descrição do Arquivo de Entrada

A primeira linha contém dois inteiros Z e S, que indicam respectivamente o número de zonas (1£ Z £ 30) e o número de estações de trem/ônibus na cidade (1£ S £ 100). Cada estação tem um identificador único (de 1 a S) pertence a exatamente uma zona. As próximas Z linhas descrevem as estações que pertencem a cada zona. As linhas começam com um inteiro K indicando o número de estações na zona, seguido por K inteiros representando as estações nesta zona. Em seguida, o arquivo contém um linha com dois inteiros T e B, representando respectivamente o número de itinerários de trem (1£ T £ 50) e ônibus (1£ B £ 50). Nas T+B linhas seguintes estão os T itinerários de trem seguidos dos B itinerários de ônibus. A descrição de cada itinerário começa com um inteiro L (2 £ L £ S) indicando o número de estações no itinerário, seguido por L inteiros representando a sequência das estações que definem o itinerário. Finalmente, vem um linha com dois inteiros X e Y (1£ X £ S, 1£ Y £ S e X ¹ Y) indicando as estações de origem e de destino do passageiro respectivamente. O final o arquivo é indicado pelo inteiros Z e S com valor zero.

Descrição do Arquivo de Saída

Para cada entrada do arquivo acima você deve imprimir o custo mínimo do transporte entre a origem e o destino dados assim como as ações do passageiro para obter esse custo.

This document was translated from L^AT_EX by H^EV^EA.