Gina Santos

Sim seria isso mesmo. Mexi no #include<stdio.h> #include<stdlib.h> void merge(int *arr, int beg, int mid, int end){ int i=beg, j=mid+1, index=beg, *temp = malloc((end+1) *sizeof(int)), k; while((i<=mid) && (j<=end)){ if(arr[i] < arr[j]){ temp[index] = arr[i]; i++; } else{ temp[index] = arr[j]; j++; } index++; } if(i>mid){ while(j<=end){ temp[index] = arr[j]; j++; index++; } } else{ while(i<=mid){ temp[index] = arr[i]; i++; index++; } } for(k=beg; k<index; k++) arr[k] = temp[k]; } void merge_sort(int *arr, int beg, int end){ int mid; if(beg<end){ mid = (beg+end)/2; merge_sort(arr, beg, mid); merge_sort(arr, mid+1, end); merge(arr, beg, mid, end); } } int main(){ int c=0; while (scanf("%d",&c)!=EOF){ int *cartas1, *cartas2; cartas1 = malloc(c * sizeof(int)); cartas2 = malloc(c * sizeof(int)); int i, j, temp=0, jogos_ganhos=0; for(i=0; i<c; i++) scanf("%d", &cartas1[i]); for(i=0; i<c; i++) scanf("%d", &cartas2[i]); merge_sort(cartas1, 0, c-1); merge_sort(cartas2, 0, c-1); j=c-1; for(i=c-1; i>=0; i--){ if(cartas2[j]>cartas1[i]){ jogos_ganhos=jogos_ganhos+1; j=j-1; } } printf("%d\n", jogos_ganhos); free(certas1); free(certas2); } return 0; } só que esta dando erro tempo limite excedido no spoj. Como corrigir esse erro? No codeblocks roda normalmente.

#include<stdio.h> #include<stdlib.h> struct Node{ int data; struct Node *next; }; struct Node* SortedMerge(struct Node* a, struct Node* b); void FrontBackSplit(struct Node* source,struct Node** frontRef, struct Node** backRef); void printContador(struct Node *a, struct Node *a2); void MergeSort(struct Node** headRef){ struct Node* head = *headRef; struct Node* a; struct Node* b; if ((head == NULL) || (head->next == NULL)) { return; } FrontBackSplit(head, &a, &b); MergeSort(&a); MergeSort(&b); *headRef = SortedMerge(a, b); } struct Node* SortedMerge(struct Node* a, struct Node* b){ struct Node* result = NULL; if (a == NULL) return (b); else if (b == NULL) return (a); if (a->data >= b->data) { result = a; result->next = SortedMerge(a->next, b); } else { result = b; result->next = SortedMerge(a, b->next); } return (result); } void FrontBackSplit(struct Node* source,struct Node** frontRef, struct Node** backRef){ struct Node* fast; struct Node* slow; slow = source; fast = source->next; while (fast != NULL) { fast = fast->next; if (fast != NULL) { slow = slow->next; fast = fast->next; } } *frontRef = source; *backRef = slow->next; slow->next = NULL; } void push(struct Node** head_ref, int new_data){ struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } int main(){ int n=0; while (scanf("%i",&n)!=EOF){ int *arr; int *arr2; arr=calloc(n, sizeof(int)); arr2=calloc(n, sizeof(int)); int j=0; while (j<n){ scanf("%i",&arr[j]); j++; } int i=0; struct Node *a = NULL; while(i< n){ push(&a, arr[i]); i++; MergeSort(&a); } for(int g=0; g<n; g++){ scanf("%i",&arr2[g]); } int s; struct Node *a2 = NULL; for (s = 0; s< n; s++) push(&a2, arr2[s]); MergeSort(&a2); printContador(a,a2); getchar(); free(arr); free(arr2); free(a); free(a2); } return 0; } void printContador(struct Node *a,struct Node *a2){ int contador=0; struct Node *temp = a; struct Node *temp2= a2; while( temp2 != NULL){ while ( temp != NULL){ if (temp2->data > temp->data){ contador++; temp = temp->next; break; free(temp); free(temp2); } temp = temp->next; } temp2 = temp2->next; } printf("%i\n",contador); free(temp); free(temp2); } Jogo Você e seu amigo estão se divertindo, jogando um jogo de tabuleiro. Nele, cada jogador tem um baralho de cartas e ambos têm a mesma quantidade de cartas. Estas cartas representam personagens que se enfrentam em diversas lutas. Então ocorrerá sucessivas lutas, onde um personagem de um dado jogador vai enfrentar um personagem do oponente. Como regra, cada personagem irá participar de uma única luta. Ao final do jogo, ganha o jogador que mais vezes derrotar seu oponente. Cada baralho é formado por diversos personagens, e cada um tem certa pontuação de luta. Em cada luta de personagens, vence aquele com maior pontuação de luta. Se ambos têm a mesma pontuação de luta, declara-se empate e ninguém vence. Sua tarefa é: conhecendo a pontuação de luta das suas cartas e das cartas do seu oponente, calcule o número máximo de lutas que você pode ganhar se os seus personagens forem confrontados em uma ordem apropriada. Input Em cada entrada há vários casos de teste. Cada um seguindo a forma: primeira linha contém um número que representa a quantidade de cartas de cada jogador (1 ≤ C ≤ 105). A segunda linha contém C números, que representam as pontuações de luta dos personagens do seu oponente (1 ≤ Ci ≤ 109). A terceira linha contém outros C números, que representam as pontuações de luta dos seus próprios personagens. Output Para cada caso de teste, imprima uma linha contendo o número máximo de lutas que você pode vencer. Restrições da Solução C Seu código não pode usar rotinas de biblioteca para manipular/alterar os dados. Apenas as rotinas de biblioteca p/ interação com o teclado/tela (ex., printf, scanf, gets, ...) e as rotinas relacionadas à alocação de memória (ex. malloc, calloc, ...) são permitidas. Seu código não deve usar variáveis globais. Seu programa deve usar alocação dinâmica de memória Seu código deve ser formado por funções e/ou procedimentos criados por você. Deve haver no mínimo 1 funções/procedimentos. Exemplo Input: 7 3 87 59 42 11 17 68 20 55 9 71 4 7 81 8 99 85 95 38 42 20 20 92 73 33 52 24 83 49 40 38 Output: 5 4 Exemplo Input: 8 63 10 28 3 17 77 99 41 83 28 73 35 18 88 19 57 9 86 27 43 9 87 89 51 17 72 28 42 21 69 83 49 32 83 12 Output: 7 6 O código abaixo funciona só que preciso transformá-lo para vetor como faço isso? Pelo que entendi só posso usar variável local e nesse código foi usado variável global. Preciso entregá-lo amanha cedo. É um trabalho de faculdade. #include<stdio.h> #include<stdlib.h> struct Node{ int data; struct Node *next; }; struct Node* SortedMerge(struct Node* a, struct Node* b); void FrontBackSplit(struct Node* source,struct Node** frontRef, struct Node** backRef); void printContador(struct Node *a, struct Node *a2); void MergeSort(struct Node** headRef){ struct Node* head = *headRef; struct Node* a; struct Node* b; if ((head == NULL) || (head->next == NULL)) { return; } FrontBackSplit(head, &a, &b); MergeSort(&a); MergeSort(&b); *headRef = SortedMerge(a, b); } struct Node* SortedMerge(struct Node* a, struct Node* b){ struct Node* result = NULL; if (a == NULL) return (b); else if (b == NULL) return (a); if (a->data >= b->data) { result = a; result->next = SortedMerge(a->next, b); } else { result = b; result->next = SortedMerge(a, b->next); } return (result); } void FrontBackSplit(struct Node* source,struct Node** frontRef, struct Node** backRef){ struct Node* fast; struct Node* slow; slow = source; fast = source->next; while (fast != NULL) { fast = fast->next; if (fast != NULL) { slow = slow->next; fast = fast->next; } } *frontRef = source; *backRef = slow->next; slow->next = NULL; } void push(struct Node** head_ref, int new_data){ struct Node* new_node = (struct Node*)malloc(sizeof(struct Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } int main(){ int n=0; while (scanf("%i",&n)!=EOF){ int *arr; int *arr2; arr=calloc(n, sizeof(int)); arr2=calloc(n, sizeof(int)); int j=0; while (j<n){ scanf("%i",&arr[j]); j++; } int i=0; struct Node *a = NULL; while(i< n){ push(&a, arr[i]); i++; MergeSort(&a); } for(int g=0; g<n; g++){ scanf("%i",&arr2[g]); } int s; struct Node *a2 = NULL; for (s = 0; s< n; s++) push(&a2, arr2[s]); MergeSort(&a2); printContador(a,a2); getchar(); free(arr); free(arr2); free(a); free(a2); } return 0; } void printContador(struct Node *a,struct Node *a2){ int contador=0; struct Node *temp = a; struct Node *temp2= a2; while( temp2 != NULL){ while ( temp != NULL){ if (temp2->data > temp->data){ contador++; temp = temp->next; break; free(temp); free(temp2); } temp = temp->next; } temp2 = temp2->next; } printf("%i\n",contador); free(temp); free(temp2); }

@arfneto Eu fiz as alterações realmente a estrutura fica mais fácil de entender só que na hora em que fui fazer a troca me confundi toda, eu confundo um pouco pode dar uma olha no que fiz e me ajudar a corrigir? Vou tentar aqui fazer como me explicou. Modifique Insere() para inserir os valores já por ordem de Chave. E ignore as duplicatas, como eu expliquei antes. Assim ao terminar de inserir só precisa mostrar os primeiros N valores. É muito mais simples e poderá usar sempre se escrever direito.

@Midori No int main caso eu siga a sua lógica ao invés de já aparecer na tela eu poderia tipo inseri-los? trocaria o codigo seu do int main por: int main(){ int contador= 0; int id; char entrada[10]; Lista *lista = NULL; while(scanf("%s",entrada)!= -1){ if(strcmp(entrada,"Entrada")==0){ lista = imprime(lista); contador=contador+1; } if (strcmp(entrada, "Saida")==0){ if(lista != NULL){ contador=contador-1; printf("%d/n",lista->numero,contador); } lista = ordena(lista); imprime(resultado(lista)); } } }

Seria ótimo! Realmente, bem mais prático, mas não posso usar vetor. Mesmo assim, muito obrigada,

Restrição de Complexidade Assintótica na Solução: NÃO Tempo máximo: 60 segundos Você projetou um robô que percorre os cômodos de sua residência e, neste processo, ele faz uma limpeza do piso. Este robô se move para frente e pode rotacionar em ângulos de 90°, portanto, se move em 4 direções (p/ cima, p/ baixo, p/ esquerda, p/ direita). Além disso, ele se move apenas entre os cômodos onde a porta de acesso está aberta. Inicialmente, uma porta fechada não é um problema, pois sua casa é inteligente e periodicamente ela envia o mapa atualizado da casa ao robô, ou seja, um mapa marcando os cômodos abertos e fechados. Deste modo seu robô é capaz de identificar se ele consegue ou não entrar no cômodo para limpar. Hoje faz 30 dias que seu robô está ajudando na limpeza da casa. Então você resolveu perguntar aos seus familiares se o robô está funcionando corretamente. Sua mãe lhe respondeu: “Ele ajuda bastante. Entretanto, ele poderia automaticamente identificar que vai ficar sem bateria e, neste instante, poderia voltar ao ponto de carga. Isso evita que as pessoas pisem nele”. Você pensou que isso é possível pois, com um sensor, seu robô consegue saber que a bateria está fraca. Então ele pode solicitar a casa o mapa atualizado e, com isso, ele pode identificar uma rota que o leva a base de carga. Então agora temos que atualizar o sistema do robô. Para isso projete um algoritmo que recebe como entra: 1) o mapa atualizado da casa; 2) o atual ponto onde o robô se encontra; 3) o ponto onde se encontra a base de carga; e gera como saída se ele consegue ou não chegar no ponto de carga. Entrada Cada entrada é formada por um único caso de teste. Na primeira linha de cada caso há dois números, representando as dimensões do mapa atualizado: 1) iLinhas – quantidade de linhas existentes no mapa; 2) jColunas – quantidade de colunas no mapa. As próximas iLinhas descrevem o mapa, que é formado por quatro caracteres diferentes: 1) espaço – representando uma área livre ou uma porta aberta; 2) # (hashtag) – representando um obstáculo intransponível, seja uma parede, seja uma porta fechada; 3) S (letra em uppercase) – representando o atual local do robô; 4) D (letra em uppercase) – representando o ponto de carga do robô. O mapa tem dimensão mínima de 3 linhas por 4 colunas, formando um quadrado ou um retângulo. Além disso, a primeira linha, a última linha, a primeira coluna e a última coluna, são paredes ou portas fechadas. Considere que há apenas um robô e um ponto de carga. Saída Para cada caso de teste, seu programa deve imprimir: “fica no mesmo lugar” (sem aspas) caso o robô não consiga voltar ao ponto de carga, ou “vai ao ponto de carga” (sem aspas) caso tenhaum caminho livre e possível para voltar ao ponto de carga. Restrições da Implementação C Seu código não pode usar rotinas de biblioteca para manipular/alterar os dados. Apenas as rotinas de biblioteca p/ interação com o teclado/tela (ex., printf, scanf, gets, ...) e as rotinas relacionadas à alocação de memória (ex. malloc, calloc, ...) são permitidas. Seu programa deve usar alguma implementação de árvore e/ou grafo (use apenas as que estudamos). Não utilize Vetores/matrizes como estrutura de dados, no lugar, utilize alguma implementação de lista encadeada. Seu programa DEVE usar o algoritmo BFS ou DFS. Seu programa NÃO deve utilizar variáveis globais. GARANTA que não haverá desperdício de memória, seja por alocação extra, seja por não liberar a memória. Seu programa deve utilizar no mínimo três funções e/ou procedimentos, criados por você. Seu programa deve usar APENAS algoritmos que estudamos e foram apresentados em aula. Eu fiz mas, não sei se esta certo e outra coisa esta dando erro de compilação e não consigo encontrar os erros. #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 100 /* Estrutura do banco de dados do Robo*/ struct FL { char from[20]; char to[20]; char skip; }; struct FL robo[MAX]; int f_pos=0; /*número de comodos na casa*/ int find_pos=0; /*indice do banco dados de busca*/ int tos=0;/*topo da pilha*/ struct stack bt_stack[MAX];/*pilha de retorno*/ void setup(void), route(void); void assert_robo(char *from, char *to); void push(char *from, char *to); void pop (char *from, char *to); void isrobo(char *from, char *to); int find(char *from, char *anywhere); int match(char *from, char *to); void main (void) { seyo(); isrobo("front_door", "robo"); route(); } void setudp (void) { assert_robo("front_door", lr); assert_robo("lr", "banheiro"); assert_robo("lr", hall); assert_robo("hall", bd1); assert_robo("hall", bd2); assert_robo("hall","mb"); assert_robo("lr", "cozinha"); assert_robo("cozinha", "robo"); } void assert_robo(char *from, char *to) { if(f_pos<MAX){ strcpy(robo[f_pos].from, from); strcpy(robo[f_pos].to, to); robo[f_pos].skip = 0; f_pos++; } else printf ( fica no mesmo lugar.\n); } /* Mostra a rota do robo*/ void rout(void){ int t; t=0; while (t<tos){ printf("%s", bt_stack[t].from); t++; if(t<tos) printf("para"); } printf("\n"); } /* Verifica se há uma coincidência.*/ natch(char *from, char *to){ register int t; for(t=f_pos-1; t>-1; t--); if(!strcmp(robo[t].from, from) && !strcmp(robo[t].to, to)) return 1; return 0; /*não encontrou*/ } /*Dado from, pare em qualquer lugar.*/ find_pos = 0; while (find_pos<f_pos){ if(!strcmp(robo[find_pos].from, from)&& !robo[find_pos].skip{ strcpy(anywhere, robo[find_pos].to); robo[find_pos].skip = 1; return 1; } find_pos++; } return 0; } /*Determina se há uma rota entre from e to.*/ void isrobo(char *from, char *to) { char anywhere[20]; if(match(from, to)){ push(from, to);/*distância*/ return; } if(find(from, anywhere)){ push(from, to); isrobo(anywhere, to); } else if (tos>0){ pop(from, to); isrobo(from, to); } } /*Rotinas de pilha*/ void push(char *from, char *to); { if (tos<MAX){ strcpy(bt_stack[tos].from, from); strcpy(bt_stack[tos].to, to); tos++; } else printf("Piha cheia. \n"); } void pop(char *from, char *to) { if(tos>0){ tos--; strcpy(from, bt_stack[tos].from); strcpy(to, bt_stack[tos].to); } else printf("Pilha vazia.\n"); }

Preciso criar um programa em c e estou tendo dificuldades na implementação dele. Ele pede o seguinte: Input Em cada entrada há vários casos de teste. Um caso de teste segue a forma: primeira linha contém dois números: 1) representa a quantidade de números do conjunto (1 ≤ C ≤ 10 7 ) e 2) quantidade dos N menores números duplicados a serem listados (0 ≤ N ≤ 10 7 ). A segunda linha contém C números, que representam os números do conjunto (1 ≤ Ci ≤ 10 9 ). Output Para cada caso de teste, imprima duas linhas: a primeira contendo a quantidade total de números duplicados e a segunda com uma lista ordenada dos N menores números duplicados, separados uns dos outros por um espaço (exceto no final – último número da lista). Caso N seja zero ou não tenham números duplicados, escreva “empty” (sem aspa). Se N for maior do que a quantidade de números duplicados, liste todos os duplicados. Se N for menor doque a quantidade total de números duplicados, liste apenas o Ns menores e em ordem crescente. Restrições da Solução C Seu código não pode usar rotinas de biblioteca para manipular/alterar os dados. Apenas as rotinas de biblioteca p/ interação com o teclado/tela (ex., printf, scanf, gets, ...) e as rotinas relacionadas à alocação de memória (ex. malloc, calloc, ...) são permitidas. Seu código não deve usar variáveis globais. Seu programa deve usar alocação dinâmica de memória. Não utilize Vetores/matrizes como estrutura de dados. Seu código deve ser formado por funções e/ou procedimentos criados por você. Deve haver no mínimo 1 funções/procedimentos. Example Input: 13 5 1 1 3 3 5 5 7 7 10 10 10 11 11 13 3 1 1 3 3 5 5 7 7 10 10 10 11 11 Output: 13 1 3 5 7 10 13 1 3 5 O meu código ficou assim, tem alguém que possa me auxiliar para que o programa possa somar a quantidade de digitos repetidos na entrada e na saída somar essa quantidade e ordenar a lista em ordem crescente? Output: 13 1 3 5 7 10 13 1 3 5 #include <stdlib.h> #include <stdio.h> #define MAX 10 typedef struct { int Chave; } TipoItem; typedef struct TipoCelula *TipoApontador; typedef struct TipoCelula { TipoItem Item; TipoApontador Prox; } TipoCelula; typedef struct { TipoApontador Primeiro, Ultimo; } TipoLista; void FLVazia(TipoLista *Lista) { Lista -> Primeiro = (TipoApontador) malloc(sizeof(TipoCelula)); Lista -> Ultimo = Lista -> Primeiro; Lista -> Primeiro -> Prox = NULL; } int Vazia(TipoLista Lista) { return (Lista.Primeiro == Lista.Ultimo); } void Insere(TipoItem x, TipoLista *Lista) { Lista -> Ultimo -> Prox = (TipoApontador) malloc(sizeof(TipoCelula)); Lista -> Ultimo = Lista -> Ultimo -> Prox; Lista -> Ultimo -> Item = x; Lista -> Ultimo -> Prox = NULL; } void Retira(TipoApontador p, TipoLista *Lista, TipoItem *Item) { /* --- Obs.: o item a ser retirado e o seguinte ao apontado por p --- */ TipoApontador q; if (Vazia(*Lista) || p == NULL || p -> Prox == NULL) { printf(" Erro: Lista vazia ou posicao não existe\n"); return; } q = p -> Prox; *Item = q -> Item; p -> Prox = q -> Prox; if (p -> Prox == NULL) Lista -> Ultimo = p; free(q); } void Imprime(TipoLista Lista) { TipoApontador Aux; Aux = Lista.Primeiro -> Prox; while (Aux != NULL) { printf("%d\n", Aux -> Item.Chave); Aux = Aux -> Prox; } } Me ajudem preciso incluir algumas funções e não estou dando conta.