eolymp
bolt
Try our new interface for solving problems
Məsələlər

Klingon Battle Bagel

Klingon Battle Bagel

\includegraphics{https://static.e-olymp.com/content/22/224a790e04c227f88d079f28a27c52748832260a.jpg} Two opponents play a game on a checkered field of size \textbf{N}×\textbf{M}. The first player places several shapes of "Klingon battle bagel" spaceship in the field. The shape of the ship is a solid \textbf{3}×\textbf{3 }square having a hole in the center (see Fig.). Ships can touch the edges of the field and each other but cannot intersect. The second player tries to find all the ships, firing at the cells of the field. The second player has made \textbf{K} shots at different cells hitting the ships, and \textbf{F} shots at other cells that missed. Write program to calculate the minimum and the maximum number of ships that can be located in the field. \InputFile The number of rows \textbf{N} and the number of columns \textbf{M} (\textbf{1} ≤ \textbf{N}, \textbf{M} ≤ \textbf{100000}) of the playing field are given in the first line of the input file, separated with a space character. The second line contains the number of hits \textbf{H} and the number of misses \textbf{F} (\textbf{0} ≤ \textbf{H}, \textbf{F }≤ \textbf{N}×\textbf{M}, \textbf{0} ≤ \textbf{H+F} ≤ \textbf{N}×\textbf{M}). \OutputFile Space-delimited values of the minimum and the maximum number of ships possibly located on the field. Output "\textbf{BAZINGA!}" (without quotation marks) if no solution exists for the input data.
Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB
Giriş verilənləri #1
7 7
1 1
Çıxış verilənləri #1
1 4
Mənbə 2013-2014 ACM Central Region of Russia Quarterfinal, Rybinsk 2013/10/17