URI PROBLEMA 1248 - Plano de Dieta SOLUÇÃO EM C

URI Online Judge | 1248

Plano de Dieta

Por TopCoder*  EUA

Timelimit: 1

O doutor deu a você a sua dieta, na qual cada caractere corresponde a algum alimento que você deveria comer. Você também sabe o que você tem comido no café da manha e no almoço, nos quais cada caractere corresponde a um tipo de alimento que você deveria ter comido aquele dia. Você decidiu que irá comer todo o restante de sua dieta durante o jantar, e você quer imprimi-la como uma String (ordenada em ordem alfabética). Se você trapaceou de algum modo (ou por comer muito de tipo de alimento, ou por comer algum alimento que não está no plano de dieta), você deveria imprimir a cadeia "CHEATER" (significa trapaceiro), sem as aspas.

Entrada

A entrada contém vários casos de teste. A primeira linha de entrada contém um inteiro N que indica a quantidade de casos de teste. Cada caso de teste é composto por três linhas, cada uma delas com uma string com até 26 caracteres de 'A'-'Z' ou vazia, representando respectivamente os alimentos da dieta, do café da manhã e do almoço.

Saída

Para cada caso de teste imprima uma string que representa os alimentos que você deveria consumir no jantar, ou "CHEATER" caso você tenha trapaceado na sua dieta.

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

void insertionSort(char *array, int length)

{

    int i, j;

    char tmp;

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

        tmp = array[i];

        j = i - 1;

        while (tmp < array[j]) {

            array[j + 1] = array[j];

            --j;

        }

        array[j + 1] = tmp;

    }

}

int main()

{

    int N;

    char diet[28], alreadyEaten[54], dinner[28];

    int dietLength, alreadyEatenLength, dinnerLength;

    int i, j, k, cheater;

    int isInDiet[26], shouldEat[26];

    scanf("%d", &N);

    getchar();

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

        memset(shouldEat, 1, sizeof(shouldEat));

        memset(isInDiet, 0, sizeof(isInDiet));

        fgets(diet, 28, stdin);

        dietLength = strlen(diet) - 1;

        fgets(alreadyEaten, 28, stdin);

        alreadyEatenLength = strlen(alreadyEaten) - 1;

        fgets(alreadyEaten + alreadyEatenLength, 28, stdin);

        alreadyEatenLength = strlen(alreadyEaten) - 1;

        for (j = 0; j < dietLength; ++j)

            isInDiet[diet[j] - 'A'] = 1;

        cheater = 0;

        for (j = 0; j < alreadyEatenLength && !cheater; ++j) {

            k = alreadyEaten[j] - 'A';

            if (!(isInDiet[k] && shouldEat[k]))

                cheater = 1;

            else

                shouldEat[k] = 0;

        }

        if (cheater)

            puts("CHEATER");

        else {

            insertionSort(diet, dietLength);

            dinnerLength = 0;

            for (j = 0; j < dietLength; ++j) {

                if (shouldEat[diet[j] - 'A'])

                    dinner[dinnerLength++] = diet[j];

            }

            dinner[dinnerLength] = '\0';

            puts(dinner);

        }

    }

    return 0;

}