Madhouse (Hard version)

题意翻译

本题和简单版的唯一区别是子串总长度的限制。 这是一道交互题。 有一个长度为 $n$ 的由小写字母组成的字符串，你需要通过两种操作得到整个字符串： - `? l r` ——列出 $s[l\dots r]$ 的所有子串。子串返回的顺序会被随机打乱，并且在每一个子串中，字母的顺序也会被随机打乱。 - `! s` ——表示你已经得到了 $s$。这个操作只能进行一次，进行完后游戏立即结束。 你可以进行最多三次询问，同时所有询问中所有子串个数的总数 $\lceil0.777(n+1)^2\rceil$。 注意测试点中的字符串是预先给定的，而不会根据你的询问而发生改变。

题目描述

This problem is different with easy version only by constraints on total answers length It is an interactive problem Venya joined a tour to the madhouse, in which orderlies play with patients the following game. Orderlies pick a string $ s $ of length $ n $ , consisting only of lowercase English letters. The player can ask two types of queries: - ? l r – ask to list all substrings of $ s[l..r] $ . Substrings will be returned in random order, and in every substring, all characters will be randomly shuffled. - ! s – guess the string picked by the orderlies. This query can be asked exactly once, after that the game will finish. If the string is guessed correctly, the player wins, otherwise he loses. The player can ask no more than $ 3 $ queries of the first type. To make it easier for the orderlies, there is an additional limitation: the total number of returned substrings in all queries of the first type must not exceed $ \left\lceil 0.777(n+1)^2 \right\rceil $ ( $ \lceil x \rceil $ is $ x $ rounded up). Venya asked you to write a program, which will guess the string by interacting with the orderlies' program and acting by the game's rules. Your program should immediately terminate after guessing the string using a query of the second type. In case your program guessed the string incorrectly, or it violated the game rules, it will receive verdict Wrong answer. Note that in every test case the string is fixed beforehand and will not change during the game, which means that the interactor is not adaptive.

输入输出格式

输入格式

First line contains number $ n $ ( $ 1 \le n \le 100 $ ) — the length of the picked string.

输出格式

You start the interaction by reading the number $ n $ . To ask a query about a substring from $ l $ to $ r $ inclusively ( $ 1 \le l \le r \le n $ ), you should output ? l r on a separate line. After this, all substrings of $ s[l..r] $ will be returned in random order, each substring exactly once. In every returned substring all characters will be randomly shuffled. In the case, if you ask an incorrect query, ask more than $ 3 $ queries of the first type or there will be more than $ \left\lceil 0.777(n+1)^2 \right\rceil $ substrings returned in total, you will receive verdict Wrong answer. To guess the string $ s $ , you should output ! s on a separate line. After printing each query, do not forget to flush the output. Otherwise, you will get Idleness limit exceeded. To flush the output, you can use: - fflush(stdout) or cout.flush() in C++; - System.out.flush() in Java; - flush(output) in Pascal; - stdout.flush() in Python; - see documentation for other languages. If you received - (dash) as an answer to any query, you need to terminate your program with exit code 0 (for example, by calling exit(0)). This means that there was an error in the interaction protocol. If you don't terminate with exit code 0, you can receive any unsuccessful verdict. Hack format To hack a solution, use the following format: The first line should contain one integer $ n $ ( $ 1 \le n \le 100 $ ) — the length of the string, and the following line should contain the string $ s $ .

输入输出样例

输入样例 #1

4

a
aa
a

cb
b
c

c

输出样例 #1

? 1 2

? 3 4

? 4 4

! aabc

题意翻译

本题和简单版的唯一区别是子串总长度的限制。 这是一道交互题。 有一个长度为 $n$ 的由小写字母组成的字符串，你需要通过两种操作得到整个字符串： - `? l r` ——列出 $s[l\dots r]$ 的所有子串。子串返回的顺序会被随机打乱，并且在每一个子串中，字母的顺序也会被随机打乱。 - `! s` ——表示你已经得到了 $s$。这个操作只能进行一次，进行完后游戏立即结束。 你可以进行最多三次询问，同时所有询问中所有子串个数的总数 $\lceil0.777(n+1)^2\rceil$。 注意测试点中的字符串是预先给定的，而不会根据你的询问而发生改变。