Cod sursa(job #2089461)

Utilizator daniela12Sandu Daniela Teodora daniela12 Data 16 decembrie 2017 16:10:41
Problema Farfurii Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.96 kb
#include <iostream>
#include <cmath>
#include <fstream>
using namespace std;
int v[100050], n, k;
void sterge (int poz)
{
    int i;
    for(i=poz;i<n;++i)
        v[i]=v[i+1];
}
void adauga (int poz, int val)
{
    int i;
    for(i=n;i>=poz;--i)
        v[i]=v[i-1];
    v[poz]=val;
}
int main()
{   ifstream f("farfurii.in");
    ofstream g("farfurii.out");
    f>>n>>k;
    f.close();
    long long int i, l,cn=n, inv;
    l=(1+sqrt(1+8*k))/2;
    if(l%2==0 && l/2*(l-1)<k) l++;
    else  if((l-1)%2==0 && (l-1)/2*l<k) l++;
    for(i=1;i<=n;++i)
    {
        if(i<=n-l)
            v[i]=i;
        else
            v[i]=cn, cn--;
    }
    if(l%2==0)
        inv=l/2*(l-1);
    else
        inv=(l-1)/2*l;
    inv-=k;
    if(inv)
    {
        int nr=n-inv;
        if(k==(l-1)*(l-2)/2+1)  nr=n-1;
        int x=v[nr];
        sterge(nr);
        adauga(n-l+1, x);
    }
    for(i=1;i<=n;++i)
        g<<v[i]<<" ";
    g.close();
}