Jogando cartas fora (ESTRUTURA DA DADOS)
Dada uma pilha de n cartas enumeradas de 1 até n com a carta 1 no topo e a carta n na base. A seguinte operação é ralizada enquanto tiver 2 ou mais cartas na pilha.
Jogue fora a carta do topo e mova a próxima carta (a que ficou no topo) para a base da pilha.
Sua tarefa é encontrar a sequência de cartas descartadas e a última carta remanescente.
Cada linha de entrada (com exceção da última) contém um número n ≤ 50. A última linha contém 0 e não deve ser processada. Cada número de entrada produz duas linhas de saída. A primeira linha apresenta a sequência de cartas descartadas e a segunda linha apresenta a carta remanescente.
Entrada
A entrada consiste em um número indeterminado de linhas contendo cada uma um valor de 1 até 50. A última linha contém o valor 0.
Saída
Para cada caso de teste, imprima duas linhas. A primeira linha apresenta a sequência de cartas descartadas, cada uma delas separadas por uma vírgula e um espaço. A segunda linha apresenta o número da carta que restou. Nenhuma linha tem espaços extras no início ou no final. Veja exemplo para conferir o formato esperado.
Exemplo de Entrada | Exemplo de Saída |
7 19 10 6 0 | Discarded cards: 1, 3, 5, 7, 4, 2 Remaining card: 6 Discarded cards: 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 4, 8, 12, 16, 2, 10, 18, 14 Remaining card: 6 Discarded cards: 1, 3, 5, 7, 9, 2, 6, 10, 8 Remaining card: 4 Discarded cards: 1, 3, 5, 2, 6 Remaining card: 4 |
#include <stdio.h>
#include <stdlib.h>
typedef struct lista{
int info;
struct lista *prox;
}TLista;
typedef struct pilha{
struct lista *prim;
}TPilha;
TPilha *inicializa(void){
TPilha *p = (TPilha *)malloc(sizeof(TPilha));
p->prim = NULL;
return p;
}
int vazia(TPilha *p){
return (p->prim == NULL);
}
void push(TPilha *p,int elem){
TLista *novo = (TLista *)malloc(sizeof(TLista));
novo->info = elem;
novo->prox = p->prim;
p->prim = novo;
}
void insere_fim(TPilha *l, int info)
{
TLista *p = l->prim;
TLista *novo = (TLista *)malloc(sizeof(TLista));
novo->info = info;
novo->prox = NULL;
if(!vazia(p)) O ERRO VEM DESSA LINHA NÃO ESTOU CONSEGUINDO ACHAR UMA SOLUÇÃO
{
l->prim = novo;
}
else
{
while(p->prox)
{
p = p->prox;
}
p->prox = novo;
}
}
int pop(TPilha *p){
if (!vazia(p)){
TLista *aux = p->prim;
int x = aux->info;
p->prim = aux->prox;
free(aux);
return x;
}
else{ // pilha vazia
exit(1);
}
}
void libera(TPilha *p){
if (p) {
TLista *q = p->prim,*r ;
while(q){
r = q;
q=q->prox;
free(r);
}
free(p);
}
}
int tamanho(TPilha *l)
{
TLista *p = l->prim;
int contador = 0;
while(p)
{
contador++;
p = p->prox;
}
free(p);
return contador;
}
void imprime_desc(TPilha *p){
TPilha *aux = inicializa();
while (!vazia(p)){
push(aux,pop(p));
}
while(!vazia(aux)){
int x = pop(aux);
printf("%d ",x);
push(p,x);
}
libera(aux);
}
void imprime_pilha(TPilha *l)
{
TLista *p = l->prim;
while(p)
{
printf("%d ", p->info);
p = p->prox;
}
free(p);
}
int main()
{
int numero;
do
{
TPilha *p = inicializa();
TPilha *descartados = inicializa();
scanf("%d", &numero);
//if(numero != 0)
// push(p, numero);
int i;
for(i = 1; i<= numero; i++)
{
insere_fim(p, i);
printf("%d # ", i);
}
int troca = 1;
while(tamanho(p)>= 2)
{
if(troca)
{
push(descartados, pop(p));
}
else
{
insere_fim(p, pop(p));
}
troca = !troca;
}
printf("Discarded cards: ");
imprime_desc(descartados);
printf("\nRemaining card: ");
imprime_pilha(p);
printf("\n");
} while (numero != 0);
return 0;
}