22 August 2014

Quiz 17: Find average number of balls in each jar

There are N empty candy jars, numbered from 1 to N, with infinite capacity. M operations are performed. Each operation is described by 3 integers a, b and k. Here, a and b are index of the jars, and k is the number of candies to be added inside each jar whose index lies between a and b (both inclusive). Can you tell the average number of candies after M operations?

Input format
The first line contains two integers N and M separated by a single space.
M lines follow. Each of the M lines contain three integers a, b and k separated by single space.

Output Format
A single line containing the average number of candies across N jars, rounded down to the nearest integer.

Rounded down means finding the greatest integer which is less than or equal to given number. Eg, 13.65 and 13.23 is rounded down to 13, while 12.98 is rounded down to 12.

3 <= N <= 10000000
1 <= M <= 100000
1 <= a <= b <= N

0 <= k <= 1000000

Sample Input
4 2
1 4 100
2 3 50

Sample Output:

balls initially in 4 jars 0,0,0,0
1st operation -> 100,100,100,100
2nd operation->100,150,150,100
average = 500/4=125


chomp($line1 =<STDIN>);
@line = split(" ",$line1);
$n = $line[0];
$m = $line[1];
if($n<3 or $n>10000000 or $m<1 or $m>100000)
$output = 0;
chomp($line2 = <STDIN>);
        @op = split(" ",$line2);
if($op[0]<1 or $op[0]>$op[1] or $op[1]<1 or $op[1]>$n or $op[2]<0 or 

$output = $output/$n;
$output = int $output;
print "$output";

Use int $string to round off to nearest interger, note 6.67 will return 6 and not 7.

No comments:

Post a Comment