cho.sh연구초미니
문제 설명
시간 제한
메모리 제한
cho.sh시간 제한
메모리 제한
시간 제한
1초
메모리 제한
128 MB
컴퓨터 하드웨어를 다루는 입문 강의에서는 집적 회로(“칩”), 이진 논리, 불 대수 등의 기본 원리를 설명한다. 논리 회로의 가장 기본적인 단위를 게이트라고 부른다. 게이트는 하나의 간단한 논리 연산을 수행하는 소자이며, 선을 통해 다른 게이트와 연결될 수 있다.
논리 회로는 게이트를 직사각형으로 그린 그림으로 나타낼 수 있으며, 입력은 왼쪽에, 출력은 오른쪽에 둔다. 각 직사각형 내부에는 게이트의 종류를 나타내는 기호가 하나 있다.
1 은 OR 게이트를 뜻한다. 값이 1 인 입력이 하나도 없을 때에만 출력이 0 이다.& 은 AND 게이트를 뜻한다. 값이 0 인 입력이 하나도 없을 때에만 출력이 1 이다.= 은 XOR 게이트를 뜻한다. 값이 1 인 입력의 개수가 홀수일 때에만 출력이 1 이다.이 그림을 읽어 이름이 붙은 모든 회로 출력의 값을 계산하는 것이 목표다. 선은 갈라졌다가 다시 합쳐질 수 있지만, 모든 값 소비자(게이트의 입력 포트 또는 이름이 붙은 출력)는 정확히 하나의 값 공급원(게이트의 출력 포트 또는 입력 값)에 연결되어 있다고 가정할 수 있다. 되먹임(피드백) 회로는 없다. 즉, 같은 게이트를 두 번 지나는 사이클은 존재하지 않는다.
입력에는 여러 개의 그림이 있다. 각 그림은 1개 이상 200개 이하의 행으로 이루어지며, 각 행은 다음 문자들로 구성된다.
). 빈 공간이다. 문자의 정확한 위치가 중요하기 때문에, 공백은 다른 문자를 알맞은 위치로 들여쓰기 하는 데 쓰인다. 행 끝의 공백은 있을 수도 있고 생략될 수도 있다.-). 수평선이다. 왼쪽과 오른쪽 문자를 연결하며, 그 문자들은 항상 존재하고 연결을 받아들인다.|). 수직선이다. 바로 위와 아래 문자를 연결한다.+). 선의 연결점 또는 꺾임이다. 연결을 받아들일 수 있는 네 방향의 문자를 모두 연결한다(연결되는 문자는 항상 둘 이상이다). 해당 방향으로 연결을 받아들이지 않는, 비어 있지 않은 이웃 문자는 연결되지 않는다. 예를 들어 + 바로 아래에 있는 - 는 + 와 연결되지 않는다.x. 두 선이 연결 없이 교차하는 지점이다. 네 이웃이 모두 연결을 받아들이는데, 위 문자는 아래 문자와, 왼쪽 문자는 오른쪽 문자와 연결되지만 두 쌍 사이에는 서로 연결이 없다.=). 입력 또는 출력 포트다. 왼쪽과 오른쪽 문자를 연결하며, 그중 하나가 포트 자신이다. = 의 왼쪽에 있는 포트는 값 공급원만 될 수 있고, 오른쪽에 있는 포트는 값 소비자만 될 수 있다.o. 부정(NOT)이다. 왼쪽에는 항상 게이트가, 오른쪽에는 항상 포트(=)가 있으며, 그 게이트의 출력을 반전시킨다.#). 게이트다. 게이트는 항상 두 개의 수직 변과 두 개의 수평 변을 가진 직사각형 모양이다. 왼쪽 변에는 입력 포트가, 오른쪽 변에는 (경우에 따라 반전된) 출력 포트가 붙을 수 있다. 두 게이트는 서로의 변에 맞닿지 않으므로, 수직 또는 수평으로 인접한 두 # 는 항상 같은 게이트의 일부다. 게이트는 가로·세로 모두 최소 3칸이므로 내부 칸이 적어도 하나 있다. 내부 칸은 정확히 하나를 제외하고 모두 공백이며, 그 하나가 게이트의 종류를 나타낸다(게이트 내부에서는 바깥과 의미가 다름에 유의하라). 그 문자는 1, &, = 중 하나다. 입력·출력 포트는 게이트 왼쪽·오른쪽 변의 내부 칸에만 붙으며, 게이트의 모서리 칸은 결코 포트가 아니다.0, 1). 회로의 입력 값이다. 오른쪽 문자와 연결되며, 그 문자는 항상 등호다.A~Z). 회로의 이름이 붙은 출력이다. 왼쪽 문자로부터 연결을 받아들이며, 그 문자는 항상 등호다. 각 글자는 최대 한 번만 나타나므로, 이름이 붙은 출력의 개수는 0개 이상 26개 이하다.각 그림은 오직 별표(*, 하나 이상)로만 이루어진 행으로 끝난다. 마지막 그림 뒤에는 그러한 행이 두 개 온다. 입력의 어떤 행도 200자를 넘지 않는다.
각 그림에 대해, 이름이 붙은 모든 출력의 값을 알파벳 순으로 정렬하여 출력한다. 각 출력은 한 줄에 세 문자로 적는다. 출력 이름(대문자 한 글자), 등호, 그리고 이진 값(0 또는 1)이다. 연속한 두 그림의 결과 사이에는 빈 줄 하나를 넣어 구분한다(마지막 그림 뒤에는 빈 줄을 출력하지 않는다).