2595. Wall
Vasily Pupkin decided to
stick the wallpaper on the wall of size n
meters in height and m meters in
width. As you know, the sold wallpaper rolls have 1 meter in width and k meters in length. They are glued on
the wall vertically – from floor to ceiling. Vasily wants to glue the wallpaper
without horizontal joints, with solid strips only (one solid piece is glued
from the ceiling to the floor). From a roll you can cut a piece the size you
want. Of course, if you leave a piece of a smaller size, it will go to waste.
What is the smallest number of rolls you should buy and how many meters of
Vasyl's wallpaper will go to waste?
Input. Three integers n, m
and k (1 ≤ n ≤ 100, 1 ≤ m
≤ 100, n ≤ k ≤ 100).
Output. Print two numbers – the minimum number of rolls to buy and
the total length of loose wallpaper.
|
Sample
input |
Sample
output |
|
6 7 20 |
3 18 |
SOLUTION
mathematics
Algorithm analysis
The length of one roll is k meters, the height of the wall is n meters. Thus one roll is enough for lines = 
strips. To glue the
wall of width m meters it is enough rolls = 
rolls.
From one roll we have
waste of k % n meters. From rolls rolls
that is necessary for gluing all the wall, rolls
– 1 rolls will be used in fully, and the last roll, possibly, will be used not
all. So from rolls – 1 rolls we have (k % n)
* (rolls – 1) meters in waste.
With the last roll we can
cover p = m – lines * (rolls – 1) full bars. So out of it k – p
* n meters will go to waste.
Algorithm realization
Read the input data.
scanf("%d %d %d",&n,&m,&k);
Calculate how many strips can be covered with one roll.
lines = k / n;
Calculate the number of used rolls: 
= (m + lines
– 1) / lines.
rolls = (m + lines - 1)
/ lines;
Find the loose wallpaper from one roll if it is used fully.
waste = k % n;
Find the waste from fully used rolls – 1 rolls.
waste *= (rolls - 1);
Last roll can be used as fully or not. Calculate the
number of vertical strips, covered with the last roll.
p = m - lines * (rolls
- 1);
Add the loose wallpaper from the last roll.
waste += k - p * n;
Print the answer.
printf("%d %d\n",rolls,waste);