JavaScript Solution to “Theater Square” Problem

Problem 1A as presented on CodeForces:

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.

What 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.

PSEUDOCODE

  1. Define the variables in the problem:
    • Given (Input):
      1. n = length of one side of the “Theater Square”
      2. m = length of the adjacent side of “Theater Square”
      3. a = length of sides of the flagstone.
    • Placeholder Variables
      1. L = length of a row of flagstones = a*x
        • where x is the number of flagstones in that row
        • L must be grater than or equal to m
      2. W = width of one column of flagstones = a*y
        • where y is the number of flagstones in that column
        • W must be greater than or equal to n
      3. Z (Output) = the total number of flagstones = x*y
  2. Set X and Y = to 1,1.
  3. Determine if L is greater than or equal to m. If not, add 1 to current X value and recalculate L (a*X)
  4. Determine if W is greater than or equal to n. If not, add 1 to current Y value and recalculate W (a*Y).
  5. Find Z by multiplying X*Y – This will provide the total (minimum) number of block required to pave the theater square!

JavaScript Code

/* Solution to http://codeforces.com/problemset/problem/1/A
 With Visual Representation */

var n; var m; var a; var x=1; var y=1; var z; var l=a*x; var w=a*y;
n=7; m=3; a=1.5;

while(l<m) {x=x+1; l=a*x;}
while(w<n) {y=y+1; w=a*y;}

z=x*y;

fill(0, 0, 0); text("Min # Blocks = " + z,275,15); text("Theater Square",40,65);
text("Paved Area",270,65); text("Single Paver",120,15);
fill(255, 0, 0);
rect(5,80,n*10,m*10); fill(155, 200, 2000); rect(200,5,a*10,a*10);

for(var j=0; j<y; j++) {
for(var i=0; i<x; i++) {
rect(205+j*a*10,80+i*a*10,a*10,a*10);
}}

A Visual Representation using Processing JS


Leave a Reply