Connection Status:
Competition Arena > RectangularSum

RectangularSum

SRM 547 · 2011-11-22 · by sdya

SRM 547 · 2011-11-22 · by sdya · Math, Simple Search, Iteration
Class Name: RectangularSum
Return Type: long
Method Name: minimalArea
Arg Types: (int, int, long long)
Problem Statement

Problem Statement

Consider the following table:

The table has height rows and width columns. Rows and columns are each numbered sequentially, starting from 0. For each i, j: the cell in row i, column j contains the number (i*width+j). For example, the table with height=2 and width=3 looks as follows: 

0 1 2
3 4 5
A subtable of this table is any table that can be obtained from the original table by selecting a rectangle of cells and erasing everything outside the rectangle.

You are given the ints height and width, and a long S. If there is no subtable in which the elements sum to S, return -1. Otherwise, return the smallest possible area of such a subtable.

Constraints

  • height will be between 1 and 1,000,000 (10^6), inclusive.
  • width will be between 1 and 1,000,000 (10^6), inclusive.
  • S will be between 1 and 1,000,000,000,000 (10^12), inclusive.
Examples
0)
2
3
8
Returns: 4

The following subtable (shown in bold italic) has a sum of 8: 0 1 2 3 4 5

1)
3
3
10
Returns: -1
2)
3
3
36
Returns: 9
3)
25
25
16000
Returns: 32
4)
1000000
1000000
1000000000000
Returns: 2

Submissions are judged against all 146 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class RectangularSum with a public method long long minimalArea(int height, int width, long long S) · 146 test cases · 2 s / 256 MB per case

Submitting as anonymous