[Solution] notepad.exe solution codeforces

notepad.exe solution codeforces – There are ๐‘›nย words in a text editor. Theย ๐‘–i-th word has lengthย ๐‘™๐‘–liย (1โ‰ค๐‘™๐‘–โ‰ค20001โ‰คliโ‰ค2000). The arrayย ๐‘™lย is hidden and only known by the grader.

[Solution] notepad.exe solution codeforces

The text editor displays words in lines, splitting each two words in a line with at least one space. Note that a line does not have to end with a space. Let the height of the text editor refer to the number of lines used. For the givenย width, the text editor will display words in such a way that the height is minimized.

More formally, suppose that the text editor hasย widthย ๐‘คw. Letย ๐‘Žaย be an array of lengthย ๐‘˜+1k+1ย whereย 1=๐‘Ž1<๐‘Ž2<โ€ฆ<๐‘Ž๐‘˜+1=๐‘›+11=a1<a2<โ€ฆ<ak+1=n+1.ย ๐‘Žaย is aย validย array if for allย 1โ‰ค๐‘–โ‰ค๐‘˜1โ‰คiโ‰คk,ย ๐‘™๐‘Ž๐‘–+1+๐‘™๐‘Ž๐‘–+1+1+โ€ฆ+1+๐‘™๐‘Ž๐‘–+1โˆ’1โ‰ค๐‘คlai+1+lai+1+1+โ€ฆ+1+lai+1โˆ’1โ‰คw. Then theย heightย of the text editor is the minimumย ๐‘˜kย over all valid arrays.

Note that ifย ๐‘ค<max(๐‘™๐‘–)w<max(li), the text editor cannot display all the words properly and will crash, and the height of the text editor will beย 00ย instead.

You can askย ๐‘›+30n+30ย queries. In one query, you provide a widthย ๐‘คw. Then, the grader will return the heightย โ„Ž๐‘คhwย of the text editor when its width isย ๐‘คw.

Find the minimum area of the text editor, which is the minimum value ofย ๐‘คโ‹…โ„Ž๐‘คwโ‹…hwย over allย ๐‘คwย for whichย โ„Ž๐‘คโ‰ 0hwโ‰ 0.

The lengths are fixed in advance. In other words,ย the interactor is not adaptive.

[Solution] notepad.exe solution codeforces

The first and only line of input contains a single integerย ๐‘›nย (1โ‰ค๐‘›โ‰ค20001โ‰คnโ‰ค2000) ย โ€” the number of words on the text editor.

It is guaranteed that the hidden lengthsย ๐‘™๐‘–liย satisfyย 1โ‰ค๐‘™๐‘–โ‰ค20001โ‰คliโ‰ค2000.


Begin the interaction by readingย ๐‘›n.

To make a query, print “?ย ๐‘คw” (without quotes,ย 1โ‰ค๐‘คโ‰ค1091โ‰คwโ‰ค109). Then you should read our response from standard input, that is,ย โ„Ž๐‘คhw.

If your program has made an invalid query or has run out of tries, the interactor will terminate immediately and your program will get a verdictย Wrong answer.

To give the final answer, print “!ย ๐‘Ž๐‘Ÿ๐‘’๐‘Žarea” (without the quotes). Note that giving this answer is not counted towards the limit ofย ๐‘›+30n+30ย queries.

After printing a query do not forget to output end of line and flush the output. Otherwise, you will getย Idleness limit exceeded. To do this, 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.

[Solution] notepad.exe solution codeforces

The first line of input must contain a single integerย ๐‘›nย (1โ‰ค๐‘›โ‰ค20001โ‰คnโ‰ค2000) โ€” the number of words in the text editor.

The second line of input must contain exactlyย ๐‘›nย space-separated integersย ๐‘™1,๐‘™2,โ€ฆ,๐‘™๐‘›l1,l2,โ€ฆ,lnย (1โ‰ค๐‘™๐‘–โ‰ค20001โ‰คliโ‰ค2000).


? 1

? 9

? 16

! 32




notepad.exe solution codeforces

In the first test case, the words areย {๐š๐š•๐š˜๐š›๐šข,๐š๐š˜,๐šž๐š”๐š›๐šŠ๐š’๐š—๐šŽ,๐šŠ๐š—๐š,๐šŠ๐š—๐š๐š˜๐š—,๐š๐š›๐šข๐š๐šž๐š‹}{glory,to,ukraine,and,anton,trygub}, soย ๐‘™={5,2,7,3,5,6}l={5,2,7,3,5,6}.

Ifย ๐‘ค=1w=1, then the text editor is not able to display all words properly and will crash. The height of the text editor isย โ„Ž1=0h1=0, so the grader will returnย 00.

Ifย ๐‘ค=9w=9, then a possible way that the words will be displayed on the text editor is:

  • ๐š๐š•๐š˜๐š›๐šข__๐š๐š˜glory__to
  • ๐šž๐š”๐š›๐šŠ๐š’๐š—๐šŽ__ukraine__
  • ๐šŠ๐š—๐š_๐šŠ๐š—๐š๐š˜๐š—and_anton
  • __๐š๐š›๐šข๐š๐šž๐š‹___trygub_

The height of the text editor isย โ„Ž9=4h9=4, so the grader will returnย 44.

Ifย ๐‘ค=16w=16, then a possible way that the words will be displayed on the text editor is:

  • ๐š๐š•๐š˜๐š›๐šข_๐š๐š˜_๐šž๐š”๐š›๐šŠ๐š’๐š—๐šŽglory_to_ukraine
  • ๐šŠ๐š—๐š_๐šŠ๐š—๐š๐š˜๐š—_๐š๐š›๐šข๐š๐šž๐š‹and_anton_trygub

The height of the text editor isย โ„Ž16=2h16=2, so the grader will returnย 22.

We have somehow figured out that the minimum area of the text editor isย 3232, so we answer it.

For Solution

Click here

Leave a Comment