Algorithm


Problem link- https://www.spoj.com/problems/RRSCHED/

RRSCHED - Round-Robin Scheduling

 

A computer processor is given N tasks to perform (1 ≤ N ≤ 50,000). The i-th task requires Ti seconds of processing time (1 ≤ Ti ≤ 1,000,000,000). The processor runs the tasks as follows: each task is run in order, from 1 to N, for 1 second, and then the processor repeats this again starting from task 1. Once a task has been completed, it will not be run in later iterations. Determine, for each task, the total running time elapsed once the task has been completed.

Input

The first line of the input contains the integer N, and the next N lines contain the integers T1 through TN.

Output

Output N lines, the i-th of which contains an integer representing the time elapsed when task i has been processed.

Example

Input:
5
8
1
3
3
8

Output:
22
2
11
12
23

The second task is completed during the first iteration, finishing 2 seconds in. On the third iteration, the third and fourth tasks complete at 11 seconds and 12 seconds, respectively. Finally, on the eighth iteration, the first and last tasks complete at 22 seconds and 23 seconds, respectively.

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h7gt;
using namespace std;
typedef long long ll;
 
#define MOD                 1000000007LL
#define EPS                 1e-9
#define io                  ios_base::sync_with_stdio(false);cin.tie(NULL);
#define M_PI                3.14159265358979323846

template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}

const int MAXN = 5e4+5;

ll n;
pair<int, int> table[MAXN];
ll res[MAXN];
ll BIT[MAXN];

void update(int idx, ll val){
	while(idx <= 50000){
		BIT[idx] += val;
		idx += idx & -idx;
	}
}

ll query(int idx){
	ll sum = 0;
	while(idx > 0){
		sum += BIT[idx];
		idx -= idx & -idx;
	}
	return sum;
}

int main(){
	io;
	cin >> n;
	for(int i = 1;i <= n; i++){
		int x;
		cin >> x;
		table[i] = {x, i};
	}
	sort(table+1, table+n+1);
	for(int i = 1;i <= n; i++)
		update(i, 1);
	ll delta, tot = 0;
	for(int i = 1;i <= n; i++){
		delta = table[i].first - ((i > 1) ? table[i-1].first : 0);
		tot += (n-(i-1))*delta;
		res[table[i].second] = tot - (n-(i-1)) + query(table[i].second);
		update(table[i].second, -1);
	}
	for(int i = 1; i <= n; i++)
		cout << res[i] << endl;
	return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
5
8
1
3
3
8

Output

x
+
cmd
22
2
11
12
23
Advertisements

Demonstration


SPOJ Solution-Round-Robin Scheduling-Solution in C, C++, Java, Python

Previous
SPOJ Solution - Test Life, the Universe, and Everything - Solution in C, C++, Java, Python