{"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":"\n \u003cp\u003eAutomatic Chemical Manufacturing is experimenting with a\n process called self-assembly. In this process, molecules with\n natural affinity for each other are mixed together in a\n solution and allowed to spontaneously assemble themselves into\n larger structures. But there is one problem: sometimes\n molecules assemble themselves into a structure of unbounded\n size, which gums up the machinery.\u003c/p\u003e\n\n \u003cp\u003eYou must write a program to decide whether a given\n collection of molecules can be assembled into a structure of\n unbounded size. You should make two simplifying assumptions: 1)\n the problem is restricted to two dimensions, and 2) each\n molecule in the collection is represented as a square. The four\n edges of the square represent the surfaces on which the\n molecule can connect to other compatible molecules.\u003c/p\u003e\n\n \u003cp\u003eIn each test case, you will be given a set of molecule\n descriptions. Each type of molecule is described by four\n two-character \u003cem\u003econnector labels\u003c/em\u003e that indicate how its\n edges can connect to the edges of other molecules. There are\n two types of connector labels:\u003c/p\u003e\n\n \u003cul class\u003d\"itemize\"\u003e\n \u003cli\u003e\n \u003cp\u003eAn uppercase letter (\u003cspan class\u003d\"tex2jax_process\"\u003e$A,\n \\ldots , Z$\u003c/span\u003e) followed by \u003cspan class\u003d\"tex2jax_process\"\u003e$+$\u003c/span\u003e or \u003cspan class\u003d\"tex2jax_process\"\u003e$-$\u003c/span\u003e. Two edges are compatible if\n their labels have the same letter but different signs. For\n example, \u003cspan class\u003d\"tex2jax_process\"\u003e$A+$\u003c/span\u003e is\n compatible with \u003cspan class\u003d\"tex2jax_process\"\u003e$A-$\u003c/span\u003e\n but is not compatible with \u003cspan class\u003d\"tex2jax_process\"\u003e$A+$\u003c/span\u003e or \u003cspan class\u003d\"tex2jax_process\"\u003e$B-$\u003c/span\u003e.\u003c/p\u003e\n \u003c/li\u003e\n\n \u003cli\u003e\n \u003cp\u003eTwo zero digits \u003cspan class\u003d\"tex2jax_process\"\u003e$00$\u003c/span\u003e. An edge with this label is\n not compatible with any edge (not even with another edge\n labeled \u003cspan class\u003d\"tex2jax_process\"\u003e$00$\u003c/span\u003e).\u003c/p\u003e\n \u003c/li\u003e\n \u003c/ul\u003e\n\n \u003cp\u003eAssume there is an unlimited supply of molecules of each\n type, which may be rotated and reflected. As the molecules\n assemble themselves into larger structures, the edges of two\n molecules may be adjacent to each other only if they are\n compatible. It is permitted for an edge, regardless of its\n connector label, to be connected to nothing (no adjacent\n molecule on that edge).\u003c/p\u003e\n\n \u003cp\u003eFigure\u0026nbsp;1 shows an example of three molecule types and a\n structure of bounded size that can be assembled from them\n (other bounded structures are also possible with this set of\n molecules).\u003c/p\u003e\n\n \u003cdiv id\u003d\"fig:assembly\" class\u003d\"figure\"\u003e\n \u003ccenter\u003e\n \u003cimg src\u003d\"CDN_BASE_URL/34eabb880149db0824f90f2d959355ca?v\u003d1714830552\" alt\u003d\"\\includegraphics[scale\u003d0.5]{assembly1}\" style\u003d\"width:; height:\"\u003e \u003cimg src\u003d\"CDN_BASE_URL/52c1059a3a7618f6ecb2a90fe3a910ab?v\u003d1714830552\" alt\u003d\"\\includegraphics[scale\u003d0.5]{assembly2}\" style\u003d\"width:; height:\"\u003e\n\n \u003cdiv class\u003d\"caption\"\u003e\n \u003cb\u003eFigure 1\u003c/b\u003e: Illustration of Sample Input 1.\n \u003c/div\u003e\n \u003c/center\u003e\n \u003c/div\u003e\n\n \u003cp\u003e\u003cbr\u003e\u003c/p\u003e\n\n \u003ch2\u003eInput\u003c/h2\u003e\n\n \u003cp\u003eThe input consists of a single test case. A test case\n consists of two lines. The first contains an integer\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e (\u003cspan class\u003d\"tex2jax_process\"\u003e$1 \\leq n \\leq 40\\, 000$\u003c/span\u003e) indicating\n the number of molecule types. The second line contains\n \u003cspan class\u003d\"tex2jax_process\"\u003e$n$\u003c/span\u003e eight-character\n strings, each describing a single type of molecule, separated\n by single spaces. Each string consists of four two-character\n connector labels representing the four edges of the molecule in\n clockwise order.\u003c/p\u003e\n\n \u003ch2\u003eOutput\u003c/h2\u003e\n\n \u003cp\u003eDisplay the word \u003ctt class\u003d\"tt\"\u003eunbounded\u003c/tt\u003e if the set of\n molecule types can generate a structure of unbounded size.\n Otherwise, display the word \u003ctt class\u003d\"tt\"\u003ebounded\u003c/tt\u003e.\u003c/p\u003e\n\n \u003ch2\u003eSample 1\u003c/h2\u003e\u003cbody\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\u003e3\nA+00A+A+ 00B+D+A- B-C+00C+\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003ebounded\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n\n \u003ch2\u003eSample 2\u003c/h2\u003e\u003cbody\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\u003e1\nK+K-Q+Q-\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eunbounded\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003c/body\u003e\n "}}]}