Juliano Balcante Pereira

Percebi que a questão móbile era parecida com a questão família real, era sobre arborescência. O que muda é o processamento dos dados internos. Segue a questão móbile: MÓBILE Móbiles são objetos muito populares hoje em dia, sendo encontrados até em berços, para diversão de bebês, mas foram concebidos há muito tempo (em 1931) pelo então jovem artista americano Alexander Calder como esculturas em movimento. Um móbile é uma estrutura composta de peças unidas por fios. O móbile é preso por um fio a uma argola pela qual ele é suspenso, permitindo que a estrutura movimente-se livremente. A argola é presa a uma única peça, chamada de peça-raiz do móbile. A peça-raiz pode ter zero ou mais sub-móbiles pendurados nela, cada sub-móbile sendo composto por uma peça-raiz na qual por sua vez podem estar pendurados zero ou mais sub-móbiles, e assim sucessivamente. Abaixo podemos ver dois exemplos de móbiles: Victor é dono de uma fabrica de móbiles que emprega centenas de artesãos. Cada móbile produzido na fábrica é confeccionado por um artesão, que cria móbiles de acordo com o seu gosto pessoal, utilizando peças de formatos distintos. Entretanto, Victor tem notado que nem todos os seus artesãos possuem a mesma habilidade artística, de forma que às vezes o móbile produzido nem sempre é bem balanceado, segundo a sua concepção. Para Victor, um móbile é bem balanceado se, para cada peça, todos os sub-móbiles pendurados nela são compostos pelo mesmo número de peças. O número de peças de um sub-móbile é determinado contando-se o número de peças que o compõe, incluindo a sua peça-raiz. Note que cada peça do móbile, exceto a peça-raiz, é pendurada em exatamente uma outra peça. Por exemplo, o móbile da figura (a) acima é um móbile bem balanceado: a peça-raiz possui um único sub-móbile, que por sua vez possui três sub-móbiles, todos com o mesmo número de peças (uma única). Já o móbile da figura ( é um móbile mal balanceado: a peça-raiz possui dois sub-móbiles, um com o total de duas peças e outro com o total de uma peça. Tarefa Dada a descrição de um móbile, você deve escrever um programa para determinar se o móbile está bem balanceado ou não. Entrada A entrada contém um único conjunto de testes, que deve ser lido do dispositivo de entrada padrão (normalmente o teclado). A primeira linha da entrada contém um inteiro N que indica o número de peças utilizadas no móbile (1 ≤ N ≤ 10.000). As peças são identificadas por inteiros de 1 a N . Cada uma das N linhas seguintes contém dois números inteirosI e J , indicando que a peça de número I está pendurada na peça de número J (a peça raiz está pendurada na argola, que é identificada pelo o número 0). Saída Seu programa deve imprimir, na saída padrão, uma única linha, contendo a palavra bem se o móbile estiver bem balanceado ou mal caso esteja mal balanceado. A palavra deve ser escrita com todas as letras em minúsculas. Exemplos Entrada 31 02 13 2 Saída bem Entrada 51 02 14 23 25 2 Saída bem Entrada 72 01 23 14 35 46 47 5 Saída mal Agora a questão família real: FAMÍLIA REAL O rei de um reino muito muito distante deu uma grande festa para reunir todas as gerações dos seus descendentes: filhos e filhas, netos e netas, bisnetos e bisnetas, e assim por diante. Ele, que gosta muito de estatísticas, agora quer saber, para cada geração, qual a porcentagem de descendentes daquela geração que compareceu à festa. Você foi contratado para escrever um programa de computador que calcule as porcentagens de todas as gerações! O rei tem N descendentes, identificados com os números de 1 a N. O próprio rei será identificado com o número 0. Será dada apenas a informação, para cada descendente, de quem é o seu pai ou sua mãe, na linha de descendência que começa no rei. Além disso, claro, será dada a lista de todos que compareceram à festa. Entrada A primeira linha da entrada contém dois inteiros N e M, respectivamente, o número de descendentes e o número de participantes da festa. A segunda linha contém N números, representando os pais ou mães dos N descendentes, em ordem crescente: o primeiro número indica o pai ou a mãe do descendente de número 1, o segundo número indica o pai ou a mãe do descendente de número 2, e assim por diante. A terceira linha contém M números, identificando todos os descendentes que compareceram à festa. Saída Seu programa deve imprimir uma linha com uma lista de números reais, com precisaão de duas casas decimais, indicando a porcentagem, para cada geração, dos descendentes daquela geração que compareceram à festa. O primeiro número deve ser a porcentagem dos filhos e filhas, o segundo dos netos e netas, e assim por diante. Restrições 1 <= M <= N <=10000 Exemplos Entrada 9 57 3 0 9 0 3 5 6 73 2 8 1 9 Saída 50.00 33.33 100.00 0.00 Entrada 16 11 15 9 2 8 6 11 0 3 0 8 12 0 9 6 16 12 5 14 9 12 6 2 4 10 3 11 7 Saída 100.00 50.00 66.67 50.00 100.00 Então eu peguei uma solução disponível na internet e funcionou, acho que usaram recursão para melhorar a eficiência. Olha o código: #include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXN 10000int p[MAXN + 1];int n;int bem;int rec(int r);int main (){ int i,j,k; scanf("%d", &n); for (k = 0; k < n; k++){ scanf("%d%d", &i, &j); p[i] = j; } bem = 1; rec(0); if(bem==1){ printf("bem\n"); } else{ printf("mal\n"); } return 0;}int rec (int r){ int q, /* Quantidade de peças em cada sub-móbile de r. */ t, /* Quantidade de peças total no móbile r. */ s; int i; q = -1; t = 1; for (i = 1; i <= n; i++){ /* Procura pelos móbiles cujo pai é r. */ if (p[i] != r){ continue; } /* Calcula a quantidade de peças no sub-móbile i. */ s = rec(i); t += s;//quantida /* Primeiro sub-móbile de r. */ if (q == -1){ q = s; continue; } /* Verifica se o sub-móbile atual i tem a mesma quantidade de peças que o sub-móbile anterior. */ if (s != q){ bem = 0; } } return t;} Bem, tentei utilizar esse código como base e fazer algumas alterações: #include <stdio.h>#include <stdlib.h>#include <string.h>#define MAXN 10100int p[MAXN];//vetor de pais de vetor[i]int n,m;int bem;int rec(int r);int main(){ int i,j,k; int pre[MAXN]; scanf("%d%d",&n,&m); for(i=0;i<n;i++){ scanf("%d",&j); p[i]=j; } for(i=0;i<m;i++){ scanf("%d",&j); pre[i]=j; } rec(0); return 0;}int rec(int r){ int q; int t; int s; int i; q=-1; t=1; for(i=1;i<=n;i++){ if(p[i]!=r){ continue; } s=rec(i); t+=s; //....... ainda nao terminei } return t;} OBS.: Como não sei o termo correto e árvore genealógica parece um móbile, o que eu chamar de móbile no próximo parágrafo significa o "pai". Segundo o autor do 1º código, na parte dentro da função rec(int r) que chama ela mesma é para calcular a quantidade de peças do mobile r Eu posso até utilizar a quantidade de peças do mobile r no final para achar a porcentagem, mas como eu poderia armazenar os filhos do pai r para que eu possa comparar com o vetor de presentes e calcular a porcentagem? Eu pensei em utilizar um vetor para armazenar os "filhos" do pai e a quantidade de filhos do móbile r

Tentei colocar gets() dentro de um for(i=0;i<4;i++) e de um for(j=0;j<3;j++), porém quando está dentro do loop acaba finalizando o programa.

Entendi, mas o que while(1) ou como está lá, while(; faz? Fica no loop enquanto o quê? E acho que escolheram 0x3f ou ? apenas para preencher o array, funcionando apenas como um marcador inicial...

Estou estudando grafos para a prova da OBI e decidi estudar os códigos e a lógica através de códigos já pronto; O problema a ser resolvido está no seguinte endereço: http://olimpiada.ic.unicamp.br/pratique/programacao/nivel2/2009f1p2_pontes O código é esse (solução proposta pela própria OBI): /* Solucao para o problema "Caminho das Pontes" da OBI 2009 por: Igor Ribeiro de Assis */#include <stdio.h>#include <string.h> /* memset() */#define MAXN 1010/* matriz de adjacencias */int A[MAXN][MAXN], visitado[MAXN], dis[MAXN];int n, m;int dijkstra() { int i; memset(dis, 0x3f, sizeof(dis)); /* distancia inicial infinita */ memset(visitado, 0, sizeof(visitado)); dis[0] = 0; for (; { int no = -1; for (i = 0; i < n; i++) if (!visitado[i] && (no == -1 || dis[i] < dis[no])) no = i; if (no == -1) break; visitado[no] = 1; for (i = 0; i < n; i++) if (dis[no] + A[no][i] < dis[i]) dis[i] = dis[no] + A[no][i]; } return dis[n-1];}int main() { int i; int s, t, b; scanf("%d%d", &n, &m); n += 2; /* imagina os as bordas como pilares */ memset(A, 0x3f, sizeof(A)); /* numero de buracos infinito */ for (i = 0; i < m; i++) { scanf("%d%d%d", &s, &t, &; A[s][t] = A[t][s] = b; } printf("%d\n", dijkstra()); return 0;} O que entendi desse código foi: O grafo está sendo representado por matriz de adjacência; Como o grafo é ponderado, para identificar os arcos está sendo utilizado o próprio peso da aresta; Foi criado um vetor para a distância mínima; Foi criado um vetor para marcar as visitadas ( não sei como); A saída da função dijkstra() é a distância mínima percorrida, no caso a quantidade mínima de buracos; A função memset() preenche um array com determinado valor; Mas não entendi poruqe preenche o vetor dis[] com 0x3f. Tinha pesquisado e descobri que é 63 em número hexadecimal, mas por que 63 e por que em número hexadecimal? O que significa os ';;' em "for (; {"? Vocês poderiam me descrver como funciona a lógica dentro do for(;{}? Quando pesquisei sobre grafos não entendi como funciona aqueles visitados e não visitados...