JOIN
Get Time

   Problem Statement  

 Problem Statement for FlattenOut

Problem Statement

    Circular Island is a small undeveloped island with a circular shape. The circle is divided into N sectors. The sectors are numbered 0 through N-1 in clockwise order. Each sector has some constant altitude.

The inhabitants of the island have some desired altitude. This altitude will be given in the input as 0. Negative altitudes are lower, positive ones are higher.

The people on the island decided to spend T days on flattening their island to the desired altitude. Each day looked as follows: The people formed N teams, one on each segment. If the altitude of the segment was negative, the team did nothing that day. If the altitude was positive, the team took shovels and removed enough dirt to decrease the altitude by 1. Also, that dirt was then moved into the next sector clockwise. In other words, if the altitude of sector i was positive, the team on sector i decreased the altitude of sector i by 1, and increased the altitude of sector ((i+1) modulo N) by 1. Note that all teams always worked at the same time, so it is possible that the altitude of some sectors was decreased and increased on the same day.

You are given a long[] height containing N elements. The i-th element of height represents the altitude of sector i at the beginning. You are also given a long T specifying the number of days of flattening. Return a long[] containing exactly N elements. The i-th element of the return value should be the height of sector i after the entire flattening is done.
 

Definition

    
Class:FlattenOut
Method:simulateIt
Parameters:long[], long
Returns:long[]
Method signature:long[] simulateIt(long[] height, long T)
(be sure your method is public)
    
 

Constraints

-height will contain between 2 and 50 elements, inclusive.
-Each element of height will be between -10^16 and 10^16, inclusive.
-T will be between 1 and 10^16, inclusive.
 

Examples

0)
    
{1, 3, -4, -4, 2, 0}
1
Returns: {0, 3, -3, -4, 1, 1 }
In this case there is only one day of flattening. The teams on sectors 2, 3, and 5 do nothing. The teams on sectors 0, 1, and 4 shovel dirt to the next sector (i.e., sectors 1, 2, and 5). The resulting sector altitudes are shown in the output above.
1)
    
{1, 3, -4, -4, 2, 0}
2
Returns: {1, 2, -2, -4, 0, 1 }
The initial altitudes are the same as in Example 0, but this time there are two days. We already know that the altitudes after the first day will be {0, 3, -3, -4, 1, 1}. On the second day, teams on sectors 1, 4, and 5 will be the ones working.
2)
    
{9999999999999999, -9999999999999999, 9999999999999999, -9999999999999999}
9999999999999999
Returns: {0, 0, 0, 0 }
Watch out for overflow, the input values may be huge.
3)
    
{0, 0, 0}
4
Returns: {0, 0, 0 }

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       2012 TCO Algorithm Round 2C - Division I, Level Three
       2012 TCO Algorithm Parallel Round 2C - Division I, Level Three