RiseOJ는 solved.ac와 제휴 관계가 없습니다. 티어 아이콘 © solved.ac. solved.ac
포럼
ICPC00023

A. Self-Assembly

Unrated 레이팅 미적용
난이도
3s
시간 제한
1024MB
메모리 제한
0
맞았습니다!!
0
제출 수
0.0%
정답률
레이팅

의견: 0

설명

Automatic Chemical Manufacturing is experimenting with a process called se\(lf-as\)sembly. In this p\(ro- ce\)ss, molecules with natural affinity for each other are mixed together in a solution and allowed to sp\(on- ta\)neously assemble themselves into larger structures. But there is one problem: sometimes molecules assemble themselves into a structure of unbounded size, which gums up the machinery. You must write a program to decide whether a given collection of molecules can be assembled into a structure of unbounded size. You should make two simplifying assumptions: 1) the problem is restricted to two dimensions, and 2) each molecule in the collection is represented as a square. The four edges of the square represent the surfaces on which the molecule can connect to other compatible molecules. In each test case, you will be given a set of molecule descriptions. Each type of molecule is described by four t\(wo-ch\)aracter connector labels that indicate how its edges can connect to the edges of other molecules. There are two types of connector labels:

  • An uppercase letter (A, . . . , Z) followed \(by + or\) −. Two edges are compatible if their labels have the same letter but different signs. For example, \(A+ is\) compatible with \(A - bu\)t is not compatible with \(A+ or\) \(B\)−.

  • Two zero digits 00. An edge with this label is not compatible with any edge (not even with another edge labeled 00). Assume there is an unlimited supply of molecules of each type, which may be rotated and reflected. As the molecules assemble themselves into larger structures, the edges of two molecules may be adjacent to each other only if they are compatible. It is permitted for an edge, regardless of its connector label, to be connected to nothing (no adjacent molecule on that edge). Figure A.1 shows an example of three molecule types and a structure of bounded size that can be ass\(em- bl\)ed from them (other bounded structures are also possible with this set of molecules). Figure A.1: Illustration of Sample Input 1.

제약
입력 형식

The input consists of a single test case. A test case consists of two lines. The first contains an integer \(n\) (\(1 \le n \le 40\,000\)) indicating the number of molecule types. The second line contains \(n\) eig\(ht-ch\)aracter strings, each describing a single type of molecule, separated by single spaces. Each string consists of four t\(wo-ch\)aracter connector labels representing the four edges of the molecule in clockwise order.

출력 형식

Display the word unbounded if the set of molecule types can generate a structure of unbounded size. Otherwise, display the word bounded.

예제 1
입력
3
A+00A+A+ 00B+D+A- B-C+00C+
출력
bounded
예제 2
입력
1
K+K-Q+Q-
출력
unbounded
문제 정보

생성자가 기록되지 않았습니다.

출처 ICPC World Finals 2013

평가 및 의견

A. Self-Assembly

개요
출제자 난이도 Unrated 레이팅 미적용 의견 0 / 50 공개 집계 (커뮤니티 난이도, 주요 주제, 품질)는 의견이 충분히 모이면 공개됩니다.

Log in to rate problems.

개별 의견

아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.

풀이 제출

A. Self-Assembly

게스트로 둘러보고 있습니다. 로그인하면 풀이를 제출하고 진행 상황을 확인할 수 있습니다. 로그인하고 제출하기
공개
C++20 Tab 들여쓰기 · Ctrl+/ 주석 토글 · Enter 자동 들여쓰기
1 1 1 0 공백: 4 · UTF-8