IATOYS-Editorial

editorial
, , , , ,
1

Problem Link : IATOYS
Author : aseet_dhale

DIFFICULTY :

Easy

PREREQUISITES :

High School Maths

PROBLEM :

In the problem you have to output the weight of all bags.

EXPLANATION :

As the problem states that ith toys starts to be filled from the ith location, i.e., 1st toy is filled starting from 1st position. So the Nth toy should start filling from the Nth position and the last bag which will be filled will be 2*N - 1 th bag. This gives us total of 2*N - 1 bags.

Now it can be observed that any ith bag which is not greater than N will contain all the toys from 1..to..i.
Hence the weight of the ith bag not greater than N will be \sum_{j = 1}^{i} j = (i*(i+1))/2

Now we can also see that the 1st toy will not be there in any other bag after all the N-1 clones and the original 1st toy is filled. That is the 1st toy will not be present after (N-1) + 1 = N bags.
Hence the ith bag greater than N will not contain the i-N th toy

Hence the weight all the bags greater than N will be \sum_{j = 1}^{N} j - \sum_{k = 1}^{i-N} k = (N*(N+1))/2 - ((i-N)*(i-N+1))/2.

SOLUTIONS:

Setter’s Solution:


#include <"bits/stdc++.h">
using namespace std;

#define ll long long
#define pb push_back
#define vb vector
#define vi vector
#define vll vector
#define pii pair
#define pll pair
#define MOD 1000000007
#define MAX_TIME 1e9
#define nl "\n"
#define sp " "
#define gcd __gcd
#define pf printf
#define sf scanf
#define se(a) a.begin(), a.end()
#define fill(a,n) for(int i = 0; i < n; i++) cin>>a[i];

int main()
{
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        for(ll i = 1; i <= 2*n-1; i++){
            if(i <= n)cout<<((i*(i+1))/2)<<sp;
            else{
                cout<<((n*(n+1))/2 - (((i-n)*(i-n+1))/2))<<sp;
            }
        }
        cout<<nl;
    }
}
2 Likes