Предъ­явим стра­те­гию, поз­во­ля­ю­щую узнать пло­щадь боль­шо­го пря­мо­уголь­ни­ка за 199 во­про­сов.

Узна­ем за 199 во­про­сов пло­ща­ди всех пря­мо­уголь­ни­ков в ниж­ней стро­ке и в левом столб­це. До­ка­жем, что те­перь можно од­но­знач­но вос­ста­но­вить пло­щадь лю­бо­го ма­лень­ко­го пря­мо­уголь­ни­ка на кар­тин­ке.

Вы­бе­рем про­из­воль­ный пря­мо­уголь­ник раз­би­е­ния. Рас­смот­рим че­ты­ре пря­мо­уголь­ни­ка, ле­жа­щих в пе­ре­се­че­нии пер­вых рядов и рядов, со­дер­жа­щих вы­бран­ный пря­мо­уголь­ник. Обо­зна­чим их пло­ща­ди и длины сто­рон как на ри­сун­ке. Тогда от­ку­да не­из­вест­ная пло­щадь вы­ра­жа­ет­ся через из­вест­ные пло­ща­ди фор­му­лой

Сум­ми­руя пло­ща­ди всех ма­лень­ких пря­мо­уголь­ни­ков, на­хо­дим пло­щадь боль­шо­го.

Те­перь до­ка­жем от про­тив­но­го, что мень­ше чем за 199 во­про­сов пло­щадь узнать не по­лу­чит­ся. Рас­смот­рим дву­доль­ный граф, у ко­то­ро­го вер­ши­ны одной доли со­от­вет­ству­ют стро­кам, вер­ши­ны дру­гой доли со­от­вет­ству­ют столб­цам, а рёбра со­от­вет­ству­ют пря­мо­уголь­ни­кам на пе­ре­се­че­нии строк и столб­цов, про пло­ща­ди ко­то­рых спро­си­ли у Пети. Так как в графе 200 вер­шин и мень­ше 199 рёбер, он не­связ­ный. Зна­чит, граф можно раз­бить на не­сколь­ко ком­по­нент связ­но­сти. Вы­бе­рем одну ком­по­нен­ту.

Рас­смот­рим все стро­ки и все столб­цы, со­от­вет­ству­ю­щие вер­ши­нам вы­бран­ной ком­по­нен­ты. По­про­бу­ем уве­ли­чить вы­со­ты всех рас­смат­ри­ва­е­мых строк в раз, од­но­вре­мен­но умень­шив длины всех рас­смат­ри­ва­е­мых столб­цов в x раз. За­ме­тим, что от этого пло­ща­ди всех ма­лень­ких пря­мо­уголь­ни­ков, про ко­то­рые спро­си­ли у Пети, не из­ме­нят­ся, так как мы ра­бо­та­ем с от­дель­ной ком­по­нен­той связ­но­сти.

Введём обо­зна­че­ния: a  — сумма высот рас­смат­ри­ва­е­мых строк, b  — сумма высот осталь­ных строк, c  — сумма длин рас­смат­ри­ва­е­мых столб­цов, d  — сумма длин осталь­ных столб­цов.

Из­на­чаль­но пло­щадь боль­шо­го пря­мо­уголь­ни­ка была равна а после из­ме­не­ния стала Урав­не­ние можно при­ве­сти к виду

Если вы­брать то пло­ща­ди до и после из­ме­не­ния будут раз­ны­ми, а со­от­вет­ствен­ные от­ве­ты Пети в этих двух слу­ча­ях  — оди­на­ко­вы­ми. Зна­чит, узнать пло­щадь за мень­ше чем 199 во­про­сов на­вер­ня­ка не по­лу­чит­ся.

Ответ: 199.