fork download 
  1. /*
  2.  * Problema nu e chiar atat de simpla pe cat pare, totusi se poate obtine
  3.  * matematic o complexitate amortizata O(140).
  4.  * La prima vedere se observa ca sirul contine secvente de numere unde
  5.  * secventa[i] contine aceleasi numere ca si secventa[i-1] + X unde
  6.  * X reprezinta dimensiunea+1 a secventei i-1, practic la fiecare secventa
  7.  * se adauga in plus fata de penultima un numar mai mare cu 1 fata de ultimul adaugat.
  8.  *
  9.  * Lungimea unui sir format din subsecvente complete este suma lungimilor fiecarei
  10.  * subsecvente: 1 + 2 + 3 + ... + N respectiv N(N+1)/2.
  11.  * Sa zicem ca avem K=3 (lungimea sirului) si vrem sa aflam N (lungimea ultimei subsecvente).
  12.  * Atunci N(N+1)/2=K devine N^2/2+N/2=K mai exact avem ecuatia 0.5N^2+0.5N-K=0.
  13.  * Rezolvam ecuatia cu ajutorul subprogramului si vedem ca N=2 pentru K=3
  14.  * deci lungimea ultimei subsecvente este 2 adica avem sirul: (1)(12) iar N e ultimul termen.
  15.  * Stiind N stim si ultimul termen din subsecventa (care este egal cu N) astfel
  16.  * aflam si ce termen avem pe pozitia K (pozitie pentru care N este radacina intreaga)
  17.  * dar nu pentru orice K vom avea solutii intregi, asa ca tot aflam radacina pozitiva
  18.  * pana cand ea apartine lui [N]*, decrementand pe K. In momentul asta stim ca elementul
  19.  * de pe noul K este chiar radacina, dar de la vechiul K s-a ajuns la noul K
  20.  * decrementand de Z ori, deci Z este numarul cautat pentru ca se pleaca de la sfarsitul
  21.  * ultimei subsecvente complete de dimensiunea noului K.
  22.  */
  23.  
  24.  
  25. #include <stdio.h>
  26. #include <math.h>
  27.  
  28.  
  29. #define RET -32000
  30.  
  31.  
  32. float Ecuatie(float a, float b, float c)
  33. {
  34.     /// Calculeaza radacina maxima a unei ecuatii de gradul 2.
  35.     float del = b * b - 4 * a * c;
  36.     if (del < 0) return RET; // solutii complexe
  37.     float x1 = (sqrt(del) - b) / (2 * a);
  38.     float x2 = c / a / x1; // bunicu' Viete
  39.     //fprintf(stdout, "%f %f\n", x1, x2);
  40.     x1 = x1 > x2 ? x1 : x2;
  41.     if (x1 < 0) return RET; // ambele negative
  42.     return x1;
  43. }
  44.  
  45.  
  46. int main()
  47. {
  48.     /**
  49.      * Citim `k`.
  50.      * Il decrementam progresiv pana gasim solutie intreaga.
  51.      * Vedem de la ce numar am plecat.
  52.      * Il afisam, acesta apartinandu-i pozitiei `k`.
  53.      */
  54.     printf("Introdu `k`: ");
  55.     int k, cnt;
  56.     for (scanf("%d", &k), cnt = 0; 1; --k, ++cnt) {
  57.         float res = Ecuatie(0.5, 0.5, -k);
  58.         if (res == RET) continue; // invalid root
  59.         if (res - (int)res == 0.0) { // daca avem radacina intreaga
  60.             // `k` reprezinta indexul unui ultimul element dintr-o serie
  61.             if (!cnt) cnt = res; // daca avem serii complete atunci afisam dimensiunea ultimei serii
  62.             printf("Elementul `k`: %d\n", cnt);
  63.             break;
  64.         }
  65.     }
  66.     return 0;
  67. }
  68.  
Success #stdin #stdout 0.01s 1724KB
comments ()
stdin 
18
stdout 
Introdu `k`: Elementul `k`: 3
https://ideone.com/h2Gxg
language:
C (gcc 8.3)
created:
13 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!