Obra: Resolução de problemas/Maratona de programação
Nível: superior
problema seguir referente maratona de programação acm icpc realizada em de setembro de nas seletivas regionais da américa do sul etapa brasil problema que será tratado se localiza na página do arquivo que pode ser baixado pelo link maratona de programação pdf problema curso universitário há alguns anos atrás universidade de pinguinhos introduziu um novo sistema flexível de créditos para os alunos ingressantes de cursos de graduação no novo sistema os alunos podem escolher as disciplinas que desejam cursar em um semestre com única restrição de não poderem cursar uma dada disciplina sem antes terem cursado todas as disciplinas que tiverem sido estabelecidas como pré requisitos de após alguns semestres reitor notou que muitos estudantes estavam sendo reprovados em muitas disciplinas simplesmente porque os estudantes estavam cursando muitas disciplinas por semestre alguns estudantes chegavam se matricular em até quinze disciplinas em um semestre sendo muito sábio este ano reitor introduziu uma regra adicional limitando número de disciplinas que cada estudante pode cursar por semestre um certo valor essa regra adicional no entanto fez com que os alunos ficassem muito confusos na hora de escolher as disciplinas serem cursadas em cada semestre aí que você entra na estória reitor resolveu disponibilizar um programa de computador para ajudar os alunos fazerem suas escolhas de disciplinas solicitou sua ajuda mais precisamente reitor quer que programa sugira as disciplinas serem cursadas durante curso da seguinte forma cada disciplina atribuída uma prioridade se mais do que disciplinas podem ser cursadas em um determinado semestre obedecendo ao sistema de pré requisitos programa deve sugerir que aluno matricule se nas disciplinas de maior prioridade se ou menos disciplinas podem ser cursadas em um determinado semestre programa deve sugerir que aluno matricule se em todas as disciplinas disponíveis portanto dadas descrição de pré requisitos para cada disciplina prioridade de cada disciplina número máximo de disciplinas por semestre seu programa deve calcular número necessário de semestres para concluir curso segundo sugestão do reitor lista de disciplinas que aluno deve matricular se em cada semestre entrada entrada contém vários casos de teste se uma disciplina não tem qualquer pré requisito ela denominada básica caso contrário ela denominada avançada primeira linha de um caso de teste contém dois inteiros indicando respectivamente número de disciplinas avançadas do curso número máximo de disciplinas que podem ser cursadas por semestre cada uma das linhas seguintes tem formato str str str strk onde str nome de uma disciplina avançada número de disciplinas que são pré requisitos de str str str strk são os nomes das disciplinas que são pré requisitos de str nome de uma disciplina uma cadeia com no mínimo um no máximo sete caracteres alfanuméricos maiúsculos note que as disciplinas básicas são aquelas que aparecem apenas como pré requisito de alguma disciplina
e que as disciplinas básicas são aquelas que aparecem apenas como pré requisito de alguma disciplina avançada para concluir curso um aluno deve cursar passar todas as disciplinas básicas avançadas prioridade das disciplinas determinada pela ordem em que elas aparecem pela primeira vez na entrada que aparece primeiro tem maior prioridade que aparece por último tem menor prioridade não há circularidade nos pré requisitos ou seja se disciplina tem como pré requisito disciplina então não tem como pré requisito direta ou indiretamente número total de disciplinas no máximo igual final da entrada indicado por entrada deve ser lida da entrada padrão saída para cada caso de teste da entrada seu programa deve produzir saída na seguinte forma primeira linha deve conter frase formatura em semestres onde número de semestres necessários para concluir curso segundo sugestão do reitor as linhas seguintes devem conter descrição das disciplinas serem cursadas em cada semestre um semestre por linha no formato mostrado no exemplo de saída abaixo para cada semestre lista das disciplinas deve ser dada em ordem lexicográfica definição considere as cadeias de caracteres sa am sb bn sa precede sb em ordem lexicográfica se apenas se sb não vazia uma das seguintes condições verdadeira sa uma cadeia vazia include include using namespace std define max typedef struct int cod char name int grau bool bool ativ bool rem disciplina disciplina vdiscmax int adiscmaxmax int ndisc int listadiscmax int sizelista disciplina semestremax int discsemmax int nsemestre int finddisc char str for int ilistadiscj tmp listadisci listadisci listadiscj listadiscj tmp void ordenar int disciplina tmp for int tmp semestreni semestreni semestrenj semestrenj tmp int main int int char strdisc int posdisc int posdep while true cin if break ndisc for int strdisc posdisc finddisc strdisc if posdisc strcpy vdiscndisc name strdisc posdisc ndisc ndisc cin for int strdisc posdep finddisc strdisc if posdep strcpy vdiscndisc name strdisc posdep ndisc ndisc grau posdep vdiscposdisc grau nsemestre while true sizelista if dfs break ordenar