URI PROBLEMA 1119 - A Fila de Desempregados SOLUÇÃO EM C

URI Online Judge | 1119

A Fila de Desempregados

Autor Desconhecido

Timelimit: 1

Em uma séria tentativa de reduzir a fila de desempregados, o novo Partido Nacional Trabalhista dos Rinocerontes Verdes decidiu uma estratégia pública. Todos os dias, todos os candidatos desempregados serão colocados em um grande círculo, voltados para dentro. Alguém é escolhido arbitrariamente como número 1, e os outros são numerados no sentido horário até N (os quais estarão à esquerda do 1°). Partindo do 1° e movendo-se no sentido horário, um contador oficial do laboratório conta k posições e retira um candidato, enquanto outro oficial começa a partir de N e se move no sentido anti-horário, contando m posições e retirando outro candidato. Os dois que são escolhidos são então enviados como estagiários para a reciclagem e se ambos os funcionários escolherem a mesma pessoa, ela (ele) é enviado para se tornar um político. Cada funcionário, em seguida, começa a contar novamente com a pessoa próxima disponível e o processo continua até que não reste ninguém. Note-se que as duas vítimas (desculpe, estagiários) deixam o anel ao mesmo tempo, por isso é possível que um funcionário conte a pessoa já selecionado pelo outro funcionário.

Entrada

Escreva um programa que leia sucessivamente três números (N, k e m; k, m > 0, 0 < N < 20) e determina a ordem no qual os candidatos são retirados para treinamento . Cada conjunto de três números estará em uma linha distinta e o final da entrada de dados é sinalizado por três zeros (0 0 0).

Saída

Para cada conjunto de três números de entrada, imprima uma linha de números especificando a ordem na qual as pessoas são escolhidas. Cada número pode ter até 3 dígitos. Liste o par escolhido partindo da pessoa escolhida pelo contador do sentido horário. Os pares sucessivos são separados por vírgula (mas não deverá haver vírgula após o último escolhido.

#include <stdio.h>

struct cell_t {

    int value;

    int prev;

    int next;

};

int main()

{

    int N, k, m;

    while (1) {

        struct cell_t applicants[21];

        int i, j1, j2;

        int remaining;

        scanf("%d%d%d", &N, &k, &m);

        if (!(N || k || m))

            break;

        for (i = 1; i <= N; ++i) {

            applicants[i].value = i;

            applicants[i].prev = (i == 1) ? N : i - 1;

            applicants[i].next = (i == N) ? 1 : i + 1;

        }

        applicants[0].next = 1;

        applicants[N + 1].prev = N;

        remaining = N;

        j1 = 0;

        j2 = N + 1;

        while (1) {

            for (i = 0; i < k; ++i)

                j1 = applicants[j1].next;

            for (i = 0; i < m; ++i)

                j2 = applicants[j2].prev;

            printf("%3d", applicants[j1].value);

            --remaining;

            if (j1 != j2) {

                printf("%3d", applicants[j2].value);

                --remaining;

            }

            if (applicants[j1].prev == j2 || applicants[j1].next == j2) {

                if (applicants[j1].prev == j2) {

                    applicants[j1].prev = applicants[j2].prev;

                    applicants[j2].next = applicants[j1].next;

                }

                if (applicants[j1].next == j2) {

                    applicants[j1].next = applicants[j2].next;

                    applicants[j2].prev = applicants[j1].prev;

                }

            }

            applicants[applicants[j1].prev].next = applicants[j1].next;

            applicants[applicants[j1].next].prev = applicants[j1].prev;

            if (j1 != j2) {

                applicants[applicants[j2].prev].next = applicants[j2].next;

                applicants[applicants[j2].next].prev = applicants[j2].prev;

            }

            if (remaining > 0)

                putchar(',');

            else {

                putchar('\n');

                break;

            }

        }

    }

    return 0;

}