Home > Back-end >  Minimum number of squares
Minimum number of squares

Time:11-10

There is a problem that states:

John has a piece of paper with NxM dimensions, he wants to cut it into 1x1 squares, with the rules:he can cut the piece of paper only once at a certain time, every cut has to go all the way around the paper

This is the code for it:

int n , m;
cin >> n >> m;
cout << (n - 1)   1LL * n * (m - 1);

Can somebody explain why do you solve it like this?

CodePudding user response:

This is my understanding of the question based on the answer:

  • You cut the paper into N equal length pieces. Each has a length of 1 and width of M. This requires (N-1) cuts.
  • For each of these N sheets, you cut them into M equal pieces which have 1 width and 1 length. This requires (M-1) for each sheet so, N * (M-1) in total.

Therefore the result is (N-1) N * (M-1)

CodePudding user response:

I have not figure out the question until I saw the answer by @mkemaltas.

Now, you can simplify that formula (N-1) N * (M-1) to N * M - 1.

A comment about 1LL *... in the question: if M * N is greater that maximum int value - you will get an integer overflow. By adding that long long int into the expression, you are converting everything to long long, avoiding that possible overflow.

  •  Tags:  
  • c
  • Related