Cod sursa(job #1822124)

Utilizator andrei_diaconu11Andrei C. Diaconu andrei_diaconu11 Data 4 decembrie 2016 12:42:48
Problema Farfurii Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <stdio.h>
#define LIM 1<<17
char BUF2[LIM];
FILE *fo;
int poz2=0;
inline long long sqrt(long long x){
  long long i;
  for(i=1;1LL*i*i<=x;i++);
  return i-1;
}

inline void putch(char ch){
  BUF2[poz2++]=ch;
  if(poz2==LIM){
    fwrite(BUF2,LIM,1,fo);
    poz2=0;
  }
}

inline void baga(int x){
  char s[15];
  int k=0;
  if(x<0){
    putch('0');
    return;
  }
  do{
    s[k++]=x%10+'0';
    x/=10;
  }while(x);
  while(k>0){
    k--;
    putch(s[k]);
  }
}

int main()
{
  long long n, k, nr, x, i;
  FILE *fi=fopen("farfurii.in", "r");
  fo=fopen("farfurii.out", "w");
  fscanf(fi, "%lld%lld", &n, &k);
  fclose(fi);
  //pentru ca config sa fie min lexicografica tre sa impingem farfuriile aflate descrescator cat de mult spre dreapta
  //astfel va aparea la final o secv descrescatoare de x elemente
  x=(sqrt(1+8*k)+1)/2;//functia de gradul 2
  //la final cel mai probabil nu E x natural a.i. x*(x-1)/2==k => tre sa alegem un nr sa stea in fata acestei secvente ca sa produca k in total
  x=n-x;
  for(i=1;i<x;i++){
    baga(i);
    putch(' ');
  }
  x=n-x;
  k=k-x*(x-1)/2;
  nr=k+n-x;
  if(nr!=0){
    baga(nr);
    putch(' ');
  }
  for(i=n;i>=n-x && i>0;i--)
    if(i!=nr){
      baga(i);
      putch(' ');
    }
  if(poz2>0)
    fwrite(BUF2,poz2,1,fo);
  fclose(fo);
  return 0;
}