CDX1603 - Editorial

PROBLEM LINK:

Practice
Contest

Author: Puneet Gupta
Editorialist: Puneet Gupta

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Math

PROBLEM:

Given the size NxM of a rectangular shape and the size AxA of each flagstone, we have to find the least number of flagstones required to cover the shape given constraints that it is allowed to cover the surface larger than the shape, not allowed to break the flagstones and the sides of flagstones should be parallel to the sides of the Square

EXPLANATION:

The constraint that the edges of each flagstone much be parralel to edges of the square allows you to analyze X and Y axes separately, i.e. how many segments of length ‘A’ are needed to cover segment of length ‘M’ and ‘N’ separately and you can obtain the final answer by taking the product of these two quantities.

Answer = ceil(M/A) * ceil(N/A), where ceil(x) is the least integer which is above or equal to x.

Using integers only, it is usually written as ((M+A-1)/A) x ((N+A-1)/A).

Note that answer may be as large as 10^18, which does not fit in 32-bit integer.

Most difficulties, if any, contestants had with data types and operator priority, which are highly dependant on language used, so they are not covered here.

AUTHOR’S SOLUTION:

Author’s solution can be found here.

Theatre Square in the capital city of Berland has a rectangular shape with the size n × m
meters. On the occasion of the city’s anniversary, a decision was taken to pave the Square
with square granite flagstones. Each flagstone is of the size a  × a.
W hat is the least number of flagstones needed to pave the Square? It’s allowed to cover
the surface larger than the Theatre Square, but the Square has to be covered. It’s not
allowed to break the flagstones. The sides of flagstones should be parallel to the sides of
the Square.
Input Format
The input contains three positive integer numbers in the first line: n,  m and a.
Constraints
(1 ≤  n, m, a ≤ 109)
Output Format
W rite the needed number of flagstones.

Theatre Square in the capital city of Berland has a rectangular shape with the size n × m
meters. On the occasion of the city’s anniversary, a decision was taken to pave the Square
with square granite flagstones. Each flagstone is of the size a  × a.
W hat is the least number of flagstones needed to pave the Square? It’s allowed to cover
the surface larger than the Theatre Square, but the Square has to be covered. It’s not
allowed to break the flagstones. The sides of flagstones should be parallel to the sides of
the Square.
Input Format
The input contains three positive integer numbers in the first line: n,  m and a.
Constraints
(1 ≤  n, m, a ≤ 109)
Output Format
W rite the needed number of flagstones.

Theatre Square in the capital city of Berland has a rectangular shape with the size n × m
meters. On the occasion of the city’s anniversary, a decision was taken to pave the Square
with square granite flagstones. Each flagstone is of the size a  × a.
W hat is the least number of flagstones needed to pave the Square? It’s allowed to cover
the surface larger than the Theatre Square, but the Square has to be covered. It’s not
allowed to break the flagstones. The sides of flagstones should be parallel to the sides of
the Square.
Input Format
The input contains three positive integer numbers in the first line: n,  m and a.
Constraints
(1 ≤  n, m, a ≤ 109)
Output Format
W rite the needed number of flagstones.

Theatre Square in the capital city of Berland has a rectangular shape with the size n × m
meters. On the occasion of the city’s anniversary, a decision was taken to pave the Square
with square granite flagstones. Each flagstone is of the size a  × a.
W hat is the least number of flagstones needed to pave the Square? It’s allowed to cover
the surface larger than the Theatre Square, but the Square has to be covered. It’s not
allowed to break the flagstones. The sides of flagstones should be parallel to the sides of
the Square.
Input Format
The input contains three positive integer numbers in the first line: n,  m and a.
Constraints
(1 ≤  n, m, a ≤ 109)
Output Format
W rite the needed number of flagstones.

Theatre Square in the capital city of Berland has a rectangular shape with the size n × m
meters. On the occasion of the city’s anniversary, a decision was taken to pave the Square
with square granite flagstones. Each flagstone is of the size a  × a.
W hat is the least number of flagstones needed to pave the Square? It’s allowed to cover
the surface larger than the Theatre Square, but the Square has to be covered. It’s not
allowed to break the flagstones. The sides of flagstones should be parallel to the sides of
the Square.
Input Format
The input contains three positive integer numbers in the first line: n,  m and a.
Constraints
(1 ≤  n, m, a ≤ 109)
Output Format
W rite the needed number of flagstones.