{"id":71,"date":"2015-09-15T11:09:25","date_gmt":"2015-09-15T14:09:25","guid":{"rendered":"http:\/\/www.galirows.com.br\/meublog\/competir\/?p=71"},"modified":"2015-10-14T15:06:14","modified_gmt":"2015-10-14T18:06:14","slug":"maratona-2011-botas-perdidas","status":"publish","type":"post","link":"http:\/\/www.galirows.com.br\/meublog\/competir\/maratona-2011-botas-perdidas\/","title":{"rendered":"Maratona [2011] &#8211; botas perdidas"},"content":{"rendered":"<p>A divis\u00e3o de Suprimentos de Botas e Cal\u00e7ados do Ex\u00e9rcito comprou um grande n\u00famero de pares de botas de v\u00e1rios tamanhos para seus soldados. No entanto, por uma falha de empacotamento da f\u00e1brica contratada, nem todas as caixas entregues continham um par de botas correto, com duas botas do mesmo tamanho, uma para cada p\u00e9. O sargento mandou que os recrutas retirassem todas as botas de todas as caixas para reembal\u00e1-las, desta vez corretamente.<\/p>\n<p>Quando o sargento descobriu que voc\u00ea sabia programar, ele solicitou com a gentileza habitual que voc\u00ea escrevesse um programa que, dada a lista contendo a descri\u00e7\u00e3o de cada bota entregue, determina quantos pares corretos de botas poder\u00e3o ser formados no total.<\/p>\n<p><!--more--><\/p>\n<p><strong>Entrada<\/strong><\/p>\n<p>A primeira linha de um caso de teste cont\u00e9m um inteiro N indicando o n\u00famero de botas individuais entregues. Cada uma das N linhas seguintes descreve uma bota, contendo um n\u00famero inteiro M e uma letra L, separados por um espa\u00e7o em branco. M indica o n\u00famero do tamanho da bota e L indica o p\u00e9 da bota: L = \u2018D\u2019 indica que a bota \u00e9 para o p\u00e9 direito, L = \u2018E\u2019 indica que a bota \u00e9 para o p\u00e9 esquerdo.<\/p>\n<p><strong>Sa\u00edda<\/strong><\/p>\n<p>Para cada caso de teste imprima uma linha contendo um \u00fanico n\u00famero inteiro indicando o n\u00famero total de pares corretos de botas que podem ser formados.<\/p>\n<p><strong>Restri\u00e7\u00f5es<\/strong><\/p>\n<p>\u20222 \u2264 N \u2264 10^4<br \/>\n\u2022N \u00e9 par<br \/>\n\u202230 \u2264 M \u2264 60<br \/>\n\u2022L \u2208{D,E}<\/p>\n<p><strong>Exemplo<\/strong><\/p>\n<table style=\"width: 370px; height: 121px;\" border=\"1\" cellspacing=\"2\" cellpadding=\"5\">\n<tbody>\n<tr>\n<td style=\"text-align: center;\"><strong>Entrada<\/strong><\/td>\n<td style=\"text-align: center;\"><strong>Sa\u00edda<\/strong><\/td>\n<\/tr>\n<tr>\n<td>4<br \/>\n40 D<br \/>\n41 E<br \/>\n41 D<br \/>\n40 E<br \/>\n6<br \/>\n38 E<br \/>\n39 E<br \/>\n40 D<br \/>\n38 D<br \/>\n40 D<br \/>\n37 E<\/td>\n<td>2<br \/>\n1<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p><strong>Solu\u00e7\u00e3o em C\/C++<\/strong><\/p>\n<pre class=\"lang:c decode:true\">#include&lt;stdio.h&gt;\r\n\r\nint main(){\r\n\tint D[61], E[61];\r\n\tint i,N,M,r;\r\n\tchar L;\r\n\r\n        \/\/enquanto existem valores sendo fornecidos\r\n\twhile(scanf(\"%d\", &amp;N)&gt;=0){\r\n\t\tr=0;\r\n\t\t\/\/preenche os dois vetores com zeros\r\n\t\tfor(i=0; i&lt;61; i++){\r\n\t\t\tD[i] = 0;\r\n\t\t\tE[i] = 0;\r\n\t\t}\r\n\t\t\/\/enquanto tiver botas (N &gt; 0) fa\u00e7a\r\n\t\twhile(N--){\r\n\t\t\tscanf(\"%d %c\", &amp;M, &amp;L);\r\n\t\t\tif(L=='E') {\r\n                            E[M]++;\r\n                        } else {\r\n                    \t    D[M]++;\r\n                        }\r\n\t\t\tif(E[M] &amp;&amp; D[M]){\r\n\t\t\t    E[M]--;\r\n\t\t\t    D[M]--;\r\n\t\t\t    r++;\r\n\t\t\t}\r\n\t\t}\r\n\t\tprintf(\"%d\\n\", r);\r\n\t}\r\n\r\n\treturn 0;\r\n}<\/pre>\n<p>Veja essa execu\u00e7\u00e3o online: <a href=\"http:\/\/ideone.com\/66GW5g\" target=\"_blank\">http:\/\/ideone.com\/66GW5g<\/a><\/p>\n<p>Solu\u00e7\u00e3o em Python<\/p>\n<pre class=\"lang:python decode:true \">D = [0]*61\r\nE = [0]*61\r\n\r\nN = int(input())\r\nwhile N &gt;= 0:\r\n    r=0\r\n    #preenche os dois vetores com zeros\r\n    for i in range(61):\r\n        D[i] = 0;\r\n        E[i] = 0;\r\n\r\n    #enquanto tiver botas (N &gt; 0) fa\u00e7a\r\n    while N:\r\n        N = N - 1\r\n        M = int(input())\r\n        L = raw_input()\r\n        \r\n        if L=='E':\r\n            E[M] = E[M] + 1\r\n        else:\r\n            D[M] = D[M] + 1\r\n\r\n        if E[M] and D[M]:\r\n            E[M] = E[M] - 1\r\n            D[M] = D[M] - 1\r\n            r = r + 1\r\n\r\n    print r\r\n    N = int(input())<\/pre>\n<p>Veja essa execu\u00e7\u00e3o online: <a href=\"http:\/\/www.codeskulptor.org\/#user40_Zxz2BgEPa0_0.py\" target=\"_blank\">http:\/\/www.codeskulptor.org\/#user40_Zxz2BgEPa0_0.py<\/a><\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>A divis\u00e3o de Suprimentos de Botas e Cal\u00e7ados do Ex\u00e9rcito comprou um grande n\u00famero de pares de botas de v\u00e1rios tamanhos para seus soldados. No entanto, por uma falha de empacotamento da f\u00e1brica contratada, nem todas as caixas entregues continham um par de botas correto, com duas botas do mesmo tamanho, uma para cada p\u00e9. [&hellip;]<\/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,5],"tags":[],"class_list":["post-71","post","type-post","status-publish","format-standard","hentry","category-cc","category-maratona-de-programacao","category-python"],"aioseo_notices":[],"amp_enabled":true,"_links":{"self":[{"href":"http:\/\/www.galirows.com.br\/meublog\/competir\/wp-json\/wp\/v2\/posts\/71","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=71"}],"version-history":[{"count":6,"href":"http:\/\/www.galirows.com.br\/meublog\/competir\/wp-json\/wp\/v2\/posts\/71\/revisions"}],"predecessor-version":[{"id":77,"href":"http:\/\/www.galirows.com.br\/meublog\/competir\/wp-json\/wp\/v2\/posts\/71\/revisions\/77"}],"wp:attachment":[{"href":"http:\/\/www.galirows.com.br\/meublog\/competir\/wp-json\/wp\/v2\/media?parent=71"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.galirows.com.br\/meublog\/competir\/wp-json\/wp\/v2\/categories?post=71"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.galirows.com.br\/meublog\/competir\/wp-json\/wp\/v2\/tags?post=71"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}