Connection Status:
Competition Arena > FlattenOut

FlattenOut

TCO12 Parallel Round 2C · 2012-03-27 · by rng_58

TCO12 Parallel Round 2C · 2012-03-27 · by rng_58 · Simulation
Class Name: FlattenOut
Return Type: long[]
Method Name: simulateIt
Arg Types: (vector<long long>, long long)
Problem Statement

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.

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)
{1, 3, -4, -4, 2, 0}
6
Returns: {0, 0, 1, -3, 0, 0 }

Again, the initial heights are the same with example #0. After six steps of the procedure, the island becomes more flat.

3)
{9999999999999999, -9999999999999999, 9999999999999999, -9999999999999999}
9999999999999999
Returns: {0, 0, 0, 0 }

Watch out for overflow, the input values may be huge.

4)
{0, 0, 0}
4
Returns: {0, 0, 0 }

Submissions are judged against all 156 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class FlattenOut with a public method vector<long long> simulateIt(vector<long long> height, long long T) · 156 test cases · 2 s / 256 MB per case

Submitting as anonymous