D - Long Blackboard Editorial /

Time Limit: 1 sec / Memory Limit: 256 MB

配点 : 150 点

問題文

京都大学のとある教室には縦に2行、横に N 列の黒板が設置されている。 あまりに長く連なっているため、どの黒板がすでに使用されていて、 どの黒板が未使用なのかを人間が全て把握するのは困難である。

そこで最近、黒板検索装置が導入された。 W を任意の整数として、 この装置に縦2行、横 W 列の黒板の使用状況を検索クエリとして入力すると、 そのような使用状況が部分黒板列として黒板の中に存在しているかが判定される。 ここで、使用状況に対して、ある i < j が存在して 黒板の i 列から j 列までが使用状況と一致するとき。 その使用状況は、その黒板の部分黒板列であるという。

この教室での発表を控えたあなたは滞りなく発表が進むよう、 この黒板検索装置を使って黒板全体の使用状況を特定するプログラムを書くことにした。 黒板検索装置の検索には多少時間がかかるので検索回数はなるべく少なくしたい。

黒板全体の使用状況は最初に決まっており、途中で変化することはない。

入出力

初めの入力は以下で与えられる。

N

N (1 \leq N \leq 100) は黒板の長さを表す整数である。

この入力の後に、解答プログラムは黒板検索装置への検索クエリを出力せよ。 検索クエリは次の形式で表される。 

s_1
s_2

ここで s_1 は部分黒板列の上の段、 s_2 は部分黒板列の下の段を表す文字列である。 ただし s_1,s_2 は、すでに使われている黒板を # 、未使用の黒板を . で表した文字列である。 文字列 s_1,s_2 の長さは任意だが一致していなければならない。 末尾には改行を出力せよ。

次に、黒板検索装置の検索結果を表す文字列が以下の形式で与えられる。 

r

r は T または F である。 意味は次の通りである。

  • T のとき、直前の検索クエリの部分黒板列が黒板に存在する。
  • F のとき、直前の検索クエリの部分黒板列が黒板に存在しない。

直前の検索クエリが黒板全体となっていた場合や 検索回数の上限を超えた場合は r の代わりに文字列 end が与えられる。 この文字列を受け取った場合，即座に解答プログラムを終了せよ。 検索回数の上限以内で，黒板全体を検索クエリとして出力した場合， Accepted と判定される． ただし，そのときの検索クエリも検索回数に含めて数える．

各出力の後には，出力をフラッシュする必要があることに注意せよ。例えば C/C++ では 検索クエリ s1, s2 を 

printf("%s\n%s\n", s1, s2); fflush(stdout);

と出力すればよい。 黒板検索装置から与えられる入力は最後まで受け取ること。受け取らなかった場合、Time Limit Exceeded の結果が得られることがあるため、注意すること。

検索回数の上限

検索回数の上限は 420 回である。 420 回以内に黒板全体となる検索クエリが与えられなかった場合は Query Limit Exceeded となる。

入出力例

以下では N=3 で黒板が

.#.
...

である場合を示している。実際には黒板の状態は解答プログラム側からは分からないことに注意せよ。


  

    解答プログラムの出力
    解答プログラムへの入力
    説明
  

  

    
    3
    黒板の長さが与えられる
  

  

    ..
##		
    
    検索クエリを出力
  

  

    
    F
    先ほどの部分黒板列は黒板の中に存在しない
  

  

    .
.		
    
    検索クエリを出力
  

  

    
    T
    先ほどの部分黒板列は黒板の中に存在する
  

  

    ..
..		
    
    検索クエリを出力
  

  

    
    F
    先ほどの部分黒板列は黒板の中に存在しない
  

  

    .#
..		
    
    検索クエリを出力
  

  

    
    T
    先ほどの部分黒板列は黒板の中に存在する
  

  

    .#.
...		
    
    検索クエリを出力
  

  

    
    end
    先ほどの部分黒板列は黒板全体となっていたので終了

Score : 150 points

Problem Statement

There is a long blackboard with 2 rows and N columns in a classroom of Kyoto University. This blackboard is so long that it is impossible to tell which cells are already used and which unused.

Recently, a blackboard retrieval device was installed at the classroom. To use this device, you type a search query that forms a rectangle with 2 rows and any length of columns, where each cell is used or unused. When you input a query, the decive answers whether the rectangle that corresponds to the query exists in the blackboard. Here, for a rectangle that corresponds to a search query, if two integer i, j ( i < j ) exist and the rectangle equals to the partial blackboard between column i and j , the rectangle is called a sub-blackboard of the blackboard.

You are currently preparing for a presentation at this classroom. To make the presentation go well, you decided to write a program to detect the status of the whole blackboard using the retrieval device. Since it takes time to use the device, you want to use it as few times as possible.

The status of the whole blackboard is already determined at the beginning and does not change while you are using the device.

Input

The first input is given in the following format:

N

N (1 \leq N \leq 100) is an integer that represents the length of the blackboard.

After this input value, your program must print search queries. A search query has the following format. 

s_1
s_2

Here, s_1 represents the upper part of the blackboard and s_2 represents the lower. # in s_1 and s_2 represents the cell is already used and . represents the cell is still unused. The lengths of s_1 and s_2 are arbitrary, but they must be the same. Make sure to insert a line break at the end of the lines.

Every time your program prints a search query, a string that represents the search result of the device is returned in the followin format. 

r

r is either T or F . The meaning of each character is as follows.

  • T represents that the sub-blackboard that corresponds to the search query exists in the blackboard.
  • F represents that the sub-blackboard that corresponds to the search query does not exist in the blackboard.

If the search query equals to the whole blackboard or the number of the search queries exceeds the limit, string end is given instead of r . Once you receive this string, exit your program immediately. If your program prints the whole blackboard as a search query before exceedin the limit, it is judged as Accepted. Note that the search query that represents the whole blackboard is also counted as the number of search queries.

Note that the output needs to be flushed every time the output is printed. For example, In C/C++, search query s1, s2 can be printed as follows. 

printf("%s\n%s\n", s1, s2); fflush(stdout);

Make sure your program receive all the input from the device. Otherwise, the result may be Time Limit Exceeded .

Query Limit

The maximun number of search queries is 420. If the number of queries exceeds the limit, the result will be Query Limit Exceeded .

Sample Input and Output

The following is an example where N=3 and the blackboard is as follows. 

.#.
...

Note that your program does not know the state of the blackboard. 


  

    Output of your program
    Input to your program
    Explanation
  

  

    
    3
    The length of the blackboard is given
  

  

    ..
##		
    
    Output a search query
  

  

    
    F
    The sub-blackboard does not exist
  

  

    .
.		
    
    Output a search query
  

  

    
    T
    The sub-blackboard exists
  

  

    ..
..		
    
    Output a search query
  

  

    
    F
    The sub-blackboard does not exist
  

  

    .#
..		
    
    Output a search query
  

  

    
    T
    The sub-blackboard exists
  

  

    .#.
...		
    
    Output a search query
  

  

    
    end
    Exit your program because the above sub-blackboard equals to the whole blackboard.

Source Name

KUPC2016