Optimum Tiling Problem ------- ------ ------- This problem is a harder variant of the Tiling Problem (short name `tile'). You must read that problem before reading this problem. It is intended that you will code the `tile' problem before you code this problem, and use the `tile' code in the solution to this problem, but there is no requirement that you do this. By a placement of tiles we mean an order in which the algorithm of the `tile' problem tries to place the tiles. A placement can be labeled by giving the names of the tiles in the order of the placement. The `tile' problem only tries one placement, the placement ABC... in which the tiles are tried in order of their names. In this problem you are asked to find a placement that `works', in the sense that all tiles can actually be placed, and none are ignored. There may be more than one such placement. For example, if there are just two tiles and the placement AB works, then so will the placement BA. You are asked to find the unique working placement that is first in lexical (dictionary) order. Thus you would find AB and not BA. Input ----- Same as the `tile' problem. This is a search problem. The input is chosen so the search will always succeed, and never fail, within the contest problem time limit, provided you do some very simple search tree pruning. If your program does not handle the sample input below very fast, you have not pruned properly. Output ------ For each case, a line containing nothing but the placement order you found for the case. Sample Input ------ ----- 10 3 3 2 4 4 6 2 0 10 4 3 4 6 3 0 26 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 24 0 Sample Output ------ ------ ABCGDFE ABEDC ABCDEFGHIJKLMNZOPQRSTUVWXY File: opttile.txt Author: Bob Walton Date: Thu Oct 21 06:10:04 EDT 2004 The authors have placed this file in the public domain; they make no warranty and accept no liability for this file. RCS Info (may not be true date or author): $Author: walton $ $Date: 2004/10/21 10:21:08 $ $RCSfile: opttile.txt,v $ $Revision: 1.4 $