{"id":231,"date":"2017-04-03T15:40:03","date_gmt":"2017-04-03T18:40:03","guid":{"rendered":"http:\/\/www.galirows.com.br\/meublog\/competir\/?p=231"},"modified":"2021-10-14T17:40:11","modified_gmt":"2021-10-14T20:40:11","slug":"mergulho-maratona2013","status":"publish","type":"post","link":"http:\/\/www.galirows.com.br\/meublog\/competir\/mergulho-maratona2013\/","title":{"rendered":"Mergulho [Maratona 2013]"},"content":{"rendered":"
\n
\n

O recente terremoto em Nlog\u00f4nia n\u00e3o chegou a afetar muito as edifica\u00e7\u00f5es da capital, principal epicentro do abalo. Mas os cientistas detectaram que o principal dique de conten\u00e7\u00e3o teve um dano significativo na sua parte subterr\u00e2nea que, se n\u00e3o for consertado rapidamente, pode causar o seu desmoronamento, com a consequente inunda\u00e7\u00e3o de toda a capital.<\/p>\n

O conserto deve ser feito por mergulhadores, a uma grande profundidade, em condi\u00e7\u00f5es extremamente dif\u00edceis e perigosas. Mas como \u00e9 a sobreviv\u00eancia da pr\u00f3pria cidade que est\u00e1 em jogo, seus moradores acudiram em grande n\u00famero como volunt\u00e1rios para essa perigosa miss\u00e3o.<\/p>\n

Como \u00e9 tradicional em miss\u00f5es perigosas, cada mergulhador recebeu no in\u00edcio do mergulho uma pequena placa com um n\u00famero de identifica\u00e7\u00e3o. Ao terminar o mergulho, os volunt\u00e1rios devolviam a placa de identifica\u00e7\u00e3o, colocando-a em um reposit\u00f3rio.<\/p>\n

O dique voltou a ser seguro, mas aparentemente alguns volunt\u00e1rios n\u00e3o voltaram do mergulho. Voc\u00ea foi contratado para a penosa tarefa de, dadas as placas colocadas no reposit\u00f3rio, determinar quais volunt\u00e1rios perderam a vida salvando a cidade.<\/p>\n<\/div>\n


\nEntrada<\/strong><\/p>\n

\n

A entrada cont\u00e9m v\u00e1rios casos de teste e termina com EOF. Cada caso de teste \u00e9 composto de duas linhas. A primeira linha cont\u00e9m dois inteiros N<\/strong> e R <\/strong>( 1 \u2264 R<\/strong> \u2264 N<\/strong> \u2264 104<\/sup>), indicando respectivamente o n\u00famero de volunt\u00e1rios que mergulhou e o n\u00famero de volunt\u00e1rios que retornou do mergulho. Os volunt\u00e1rios s\u00e3o identificados por n\u00fameros de 1 a N. A segunda linha da entrada cont\u00e9m R inteiros, indicando os volunt\u00e1rios que retornaram do mergulho (ao menos um volunt\u00e1rio retorna do mergulho).<\/p>\n<\/div>\n

Sa\u00edda<\/strong><\/p>\n

\n

Seu programa deve produzir uma \u00fanica linha para cada caso de teste, contendo os identificadores dos volunt\u00e1rios que n\u00e3o retornaram do mergulho, na ordem crescente de suas identifica\u00e7\u00f5es. Deixe um espa\u00e7o em branco ap\u00f3s cada identificador (note que isto significa que deve haver um espa\u00e7o em branco tamb\u00e9m ap\u00f3s o \u00faltimo identificador). Se todos os volunt\u00e1rios retornaram do mergulho, imprima apenas o caractere \u2018*\u2019 (asterisco).<\/p>\n<\/div>\n

\u00a0Exemplo<\/strong><\/div>\n\n\n\n\n\n
Entrada<\/td>\nSa\u00edda<\/td>\n<\/tr>\n<\/thead>\n
5 3
\n3 1 5
\n6 6
\n6 1 3 2 5 4<\/td>\n		2 4
\n*<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

Solu\u00e7\u00e3o em C<\/strong><\/p>\n

A solu\u00e7\u00e3o apresentada definiu um vetor de 10001 posi\u00e7\u00f5es. Isso porque o enunciado disse que a entrada teria um valor de N<\/strong> \u2264 104<\/sup>.\u00a0 Veja que 104<\/sup> = 1000 e entre 0 e 1000 existem 10001 n\u00fameros inteiros.<\/p>\n

#include<stdio.h>\n\nint main(){\n    int n, r, i, idVoluntario, v[10001]; \/\/10001 = 10^4+1 (porque \u00e9 menor igual)\n\n    while(scanf(\"%i %i\",&n, &r) != EOF) {\n    \t\/\/zera o vetor (somente a parte que interessa)\n    \tfor(i=0; i<=n; i++) {\n    \t\tv[i] = 0;\n    \t}\n    \t\n    \t\/\/l\u00ea os identificadores dos volunt\u00e1rios\n        for(i=0; i<r; i++) {\n            scanf(\"%i\",&idVoluntario);\n            v[idVoluntario] = 1;\n        }\n        \n        \/\/resolve o enunciado\n        if(n==r) { \/\/mergulharam o mesmo n\u00famero de volunt\u00e1rios que voltaram\n            printf(\"*\\n\");\n        } else{\n            for(i=1; i<=n ; i++){\n                if(v[i]==0) {\n                    printf(\"%i \", i);\n                }\n                else{\n                    v[i]=0;\n                }\n            }\n            printf(\"\\n\");\n        }\n    }\n\treturn 0;\n}<\/pre>\n
Teste o c\u00f3digo:<\/strong> http:\/\/ideone.com\/X4PMIF<\/a><\/p>\n
Dica de melhoria
\n<\/strong><\/p>\n
A solu\u00e7\u00e3o envolve encontrar os n\u00fameros inteiros de 1 a <\/span><\/span>N<\/span> que n\u00e3o\u00a0 <\/span>aparecem na entrada. O problema foi resolvido utilizando um <\/span>vetor <\/span>com <\/span><\/span>N<\/span> posi\u00e7\u00f5es <\/span>par<\/span>a <\/span>identificar <\/span>os <\/span>n\u00fameros <\/span>que <\/span>apareceram na <\/span>entrada. Quando o valor <\/span><\/span>i<\/span><\/span><\/em> \u00e9 informado, foi alterado o valor do vetor nesse \u00edndice para 1. Com isso, a complexidade de tempo desse algoritmo <\/span><\/span>\u00e9 O(N)<\/em>. Em linguagem C++, \u00e9 poss\u00edvel utilizar o std::set<\/a> que faz inser\u00e7\u00f5es e busca em complexidade de tempo O(log N)<\/em>. Com isso, \u00e9 poss\u00edvel obter uma solu\u00e7\u00e3o com complexidade de O(N.log N)<\/em>.
<\/span><\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
O recente terremoto em Nlog\u00f4nia n\u00e3o chegou a afetar muito as edifica\u00e7\u00f5es da capital, principal epicentro do abalo. Mas os cientistas detectaram que o principal dique de conten\u00e7\u00e3o teve um dano significativo na sua parte subterr\u00e2nea que, se n\u00e3o for consertado rapidamente, pode causar o seu desmoronamento, com a consequente inunda\u00e7\u00e3o de toda a capital. […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[8,7],"tags":[],"class_list":["post-231","post","type-post","status-publish","format-standard","hentry","category-cc","category-maratona-de-programacao"],"aioseo_notices":[],"amp_enabled":true,"_links":{"self":[{"href":"http:\/\/www.galirows.com.br\/meublog\/competir\/wp-json\/wp\/v2\/posts\/231","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.galirows.com.br\/meublog\/competir\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.galirows.com.br\/meublog\/competir\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.galirows.com.br\/meublog\/competir\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.galirows.com.br\/meublog\/competir\/wp-json\/wp\/v2\/comments?post=231"}],"version-history":[{"count":6,"href":"http:\/\/www.galirows.com.br\/meublog\/competir\/wp-json\/wp\/v2\/posts\/231\/revisions"}],"predecessor-version":[{"id":452,"href":"http:\/\/www.galirows.com.br\/meublog\/competir\/wp-json\/wp\/v2\/posts\/231\/revisions\/452"}],"wp:attachment":[{"href":"http:\/\/www.galirows.com.br\/meublog\/competir\/wp-json\/wp\/v2\/media?parent=231"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.galirows.com.br\/meublog\/competir\/wp-json\/wp\/v2\/categories?post=231"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.galirows.com.br\/meublog\/competir\/wp-json\/wp\/v2\/tags?post=231"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}