{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n div.illustration {\n float: right;\n padding-left: 20px;\n }\n div.illustration .illustration {\n width: 100%;\n border-radius: 4px;\n }\n pre {\n display: block;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n color: #333;\n word-break: break-all;\n word-wrap: break-word;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eVocê está matriculado no curso de Organização e Arquitetura de Computadores em sua universidade. Você decide escrever um programa para ajudar a verificar seu trabalho calculando o valor de saída de um circuito digital combinacional, dado seus inputs.\u003c/p\u003e\n \u003cdiv id\u003d\"circuitmath:1\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/ecdefacde026d12b5944a1028fb06c69?v\u003d1713479429\" alt\u003d\"\\includegraphics[width\u003d0.4\\textwidth ]{example_circuit}\" style\u003d\"width:40.00%\"\u003e\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigura 1\u003c/b\u003e: Um exemplo de um circuito digital combinacional. Veja o texto para uma explicação.\n \u003c/div\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n \u003cp\u003eConsidere o circuito mostrado na Figura\u0026nbsp;1, que usamos para ilustração. Este circuito tem quatro inputs (letras A a D à esquerda), cada um dos quais é verdadeiro ou falso. Existem quatro \u0027gates\u0027, cada um dos quais é um dos três tipos: AND, OR ou NOT. Cada gate produz um valor verdadeiro ou falso, dependendo de seus inputs. O último gate (o OR à direita) produz a saída de todo o circuito. Podemos escrever esses três tipos de gates em texto por seus equivalentes \u003cem\u003eoperadores lógicos\u003c/em\u003e: \u003ctt\u003e*\u003c/tt\u003e para AND, \u003ctt\u003e+\u003c/tt\u003e para OR e \u003ctt\u003e-\u003c/tt\u003e para NOT. A seguir, usaremos os operadores em vez de gates para descrever circuitos.\u003c/p\u003e\n \u003cp\u003eAqui está como esses operadores funcionam. Dada uma atribuição de verdadeiro (\u003ctt\u003eT\u003c/tt\u003e) ou falso (\u003ctt\u003eF\u003c/tt\u003e) para cada input, os operadores produzem o valor de verdade indicado nas tabelas a seguir:\u003c/p\u003e\n \u003ccenter\u003e\n \u003ctable cellspacing\u003d\"0\" class\u003d\"tabular\"\u003e\n \u003ctbody\u003e\u003ctr\u003e\n \u003ctd style\u003d\"border-top-style:solid; border-left:1px solid black; border-right:1px solid black; border-top-color:black; border-top-width:1px; text-align:center\"\u003e\n \u003cp\u003e\u003ctt\u003eA\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-top-style:solid; text-align:center; border-top-color:black; border-top-width:1px; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eB\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-top-style:solid; text-align:center; border-top-color:black; border-top-width:1px; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eA B *\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-top-style:solid; text-align:center; border-top-color:black; border-top-width:1px; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eA B +\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"border-top-style:solid; border-left:1px solid black; border-right:1px solid black; border-top-color:black; border-top-width:1px; text-align:center\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-top-style:solid; text-align:center; border-top-color:black; border-top-width:1px; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-top-style:solid; text-align:center; border-top-color:black; border-top-width:1px; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-top-style:solid; text-align:center; border-top-color:black; border-top-width:1px; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"text-align:center; border-right:1px solid black; border-left:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:center; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:center; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:center; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"text-align:center; border-right:1px solid black; border-left:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:center; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:center; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"text-align:center; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"border-bottom-style:solid; border-bottom-width:1px; border-left:1px solid black; border-right:1px solid black; text-align:center; border-bottom-color:black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-bottom-color:black; border-bottom-width:1px; text-align:center; border-bottom-style:solid; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-bottom-color:black; border-bottom-width:1px; text-align:center; border-bottom-style:solid; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-bottom-color:black; border-bottom-width:1px; text-align:center; border-bottom-style:solid; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\u003c/table\u003e \n \u003ctable cellspacing\u003d\"0\" class\u003d\"tabular\"\u003e\n \u003ctbody\u003e\u003ctr\u003e\n \u003ctd style\u003d\"border-top-style:solid; border-left:1px solid black; border-right:1px solid black; border-top-color:black; border-top-width:1px; text-align:center\"\u003e\n \u003cp\u003e\u003ctt\u003eA\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-top-style:solid; text-align:center; border-top-color:black; border-top-width:1px; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eA -\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"border-top-style:solid; border-left:1px solid black; border-right:1px solid black; border-top-color:black; border-top-width:1px; text-align:center\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-top-style:solid; text-align:center; border-top-color:black; border-top-width:1px; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003ctr\u003e\n \u003ctd style\u003d\"border-bottom-style:solid; border-bottom-width:1px; border-left:1px solid black; border-right:1px solid black; text-align:center; border-bottom-color:black\"\u003e\n \u003cp\u003e\u003ctt\u003eF\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003ctd style\u003d\"border-bottom-color:black; border-bottom-width:1px; text-align:center; border-bottom-style:solid; border-right:1px solid black\"\u003e\n \u003cp\u003e\u003ctt\u003eT\u003c/tt\u003e\u003c/p\u003e\n \u003c/td\u003e\n \u003c/tr\u003e\n \u003c/tbody\u003e\u003c/table\u003e\n \u003c/center\u003e\n \u003cp\u003eObserve que AND e OR têm dois inputs, enquanto NOT opera apenas com um input. Além disso, usamos a \u003cem\u003enotação postfix\u003c/em\u003e para escrever expressões envolvendo operadores (como \u003cspan class\u003d\"tex2jax_process\"\u003e$\\verb|A B *|$\u003c/span\u003e), onde o operador vem \u003cem\u003edepois\u003c/em\u003e de seu(s) input(s) (assim como em Figura\u0026nbsp;1, cada gate no diagrama do circuito vem depois de seus inputs).\u003c/p\u003e\n \u003cp\u003eQuando descrevemos um circuito válido em notação postfix, usamos a seguinte sintaxe.\u003c/p\u003e\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eUma letra maiúscula (\u003ctt\u003eA\u003c/tt\u003e a \u003ctt\u003eZ\u003c/tt\u003e) é um circuito válido. Em outras palavras, um input sozinho (sem nenhum gate) é um circuito válido (que produz como saída seu próprio valor de input).\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eSe \u003ctt\u003e\u0026lt;C1\u0026gt;\u003c/tt\u003e e \u003ctt\u003e\u0026lt;C2\u0026gt;\u003c/tt\u003e são circuitos válidos, então ‘\u003ctt\u003e\u0026lt;C1\u0026gt; \u0026lt;C2\u0026gt; *\u003c/tt\u003e’ é um circuito válido que produz o AND das saídas dos dois subcircuitos.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eSe \u003ctt\u003e\u0026lt;C1\u0026gt;\u003c/tt\u003e e \u003ctt\u003e\u0026lt;C2\u0026gt;\u003c/tt\u003e são circuitos válidos, então ‘\u003ctt\u003e\u0026lt;C1\u0026gt; \u0026lt;C2\u0026gt; +\u003c/tt\u003e’ é um circuito válido que produz o OR das saídas dos dois subcircuitos.\u003c/p\u003e\n \u003c/li\u003e\n \u003cli\u003e\n \u003cp\u003eSe \u003ctt\u003e\u0026lt;C1\u0026gt;\u003c/tt\u003e é um circuito válido, então ‘\u003ctt\u003e\u0026lt;C1\u0026gt; -\u003c/tt\u003e’ é um circuito válido que produz o NOT da saída de \u003ctt\u003e\u0026lt;C1\u0026gt;\u003c/tt\u003e.\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n \u003cp\u003eNenhuma outra descrição é um circuito válido.\u003c/p\u003e\n \u003cp\u003eAssim, uma das maneiras como o circuito na Figura 1 poderia ser descrito usando notação postfix é como a string:\u003c/p\u003e\n \u003ccenter\u003e\n \u003ctt\u003eA B * C D + - +\u003c/tt\u003e\n \u003c/center\u003e\n \u003cp\u003eDado um valor de verdade (\u003ctt\u003eT\u003c/tt\u003e ou \u003ctt\u003eF\u003c/tt\u003e) para cada um dos inputs (\u003ctt\u003eA\u003c/tt\u003e, \u003ctt\u003eB\u003c/tt\u003e, \u003ctt\u003eC\u003c/tt\u003e e \u003ctt\u003eD\u003c/tt\u003e neste exemplo), seus valores se propagam pelos gates do circuito, e o valor de verdade produzido pelo último gate é a saída do circuito. Por exemplo, quando o circuito acima recebe os inputs \u003ctt\u003eA\u003dT\u003c/tt\u003e, \u003ctt\u003eB\u003dF\u003c/tt\u003e, \u003ctt\u003eC\u003dT\u003c/tt\u003e, \u003ctt\u003eD\u003dF\u003c/tt\u003e, a saída do circuito é \u003ctt\u003eF\u003c/tt\u003e.\u003c/p\u003e\n \u003cp\u003eDada uma atribuição de variáveis e uma descrição do circuito, seu software deve imprimir a saída do circuito.\u003c/p\u003e\n \u003ch2\u003eEntrada\u003c/h2\u003e\n \u003cp\u003eA primeira linha da entrada consiste em um único inteiro \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e, satisfazendo\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq n \\leq 26$\u003c/span\u003e,\n denotando o número de variáveis de input. Em seguida, segue uma linha com \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e caracteres separados por espaço. Cada caractere é ou \u003cspan class\u003d\"tex2jax_process\"\u003e$\\verb|T|$\u003c/span\u003e ou \u003cspan class\u003d\"tex2jax_process\"\u003e$\\verb|F|$\u003c/span\u003e, com o \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e-ésimo caractere indicando o valor de verdade do input que é rotulado com a \u003cspan class\u003d\"tex2jax_process\"\u003e$i$\u003c/span\u003e-ésima letra do alfabeto.\u003c/p\u003e\n \u003cp\u003eA última linha da entrada contém uma descrição do circuito, que segue a sintaxe descrita acima. Cada circuito é válido, usa apenas as primeiras \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e letras\n do alfabeto como rótulos de input e contém no mínimo\n \u003cspan class\u003d\"tex2jax_process\"\u003e$1$\u003c/span\u003e e no máximo\n \u003cspan class\u003d\"tex2jax_process\"\u003e$250$\u003c/span\u003e caracteres totais, excluindo espaços.\u003c/p\u003e\n \u003cp\u003eObserve que enquanto cada variável é fornecida apenas um valor de verdade, uma variável pode aparecer várias vezes na descrição do circuito e servir como input para mais de um gate.\u003c/p\u003e\n \u003ch2\u003eSaída\u003c/h2\u003e\n \u003cp\u003eImprima um único caractere, a saída do circuito (seja \u003ctt\u003eT\u003c/tt\u003e ou \u003ctt\u003eF\u003c/tt\u003e), quando avaliado usando os valores de input fornecidos.\u003c/p\u003e\n \u003ch2\u003eExemplo 1\u003c/h2\u003e\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\nT F T F\nA B * C D + - +\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eF\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}