Vasya və toplar#4538

Vasya və toplar (Həll təhlili)

Əgər $n$ üçbucağın tərəfinin uzunluğudursa, onun tam yerləşdirilməsi üçün

1 + 2 + ... + n = n \cdot (n + 1) /2

1 + 2 + ... + n = n \cdot (n + 1) / 2

şar tələb olunur.

Tutaq ki, $k$ sayda şar mövcuddur. Maksimal mümkün $n$ tapmaq üçün aşağıdakı tənliyi həll edək

n \cdot (n + 1) /2 = k

n \cdot (n + 1) / 2 = k

və mənfi olmayan kökü aşağıya doğru ən yaxın tam ədədə yuvarlaqlaşdırırıq.

Kvadrat tənliyi həll edək:

n^{2} + n - 2 k = 0, d = 1 + 8 k, n = (- 1 + 1 + 8 k) /2

n^2 + n - 2k = 0, \\ d = 1 + 8k, n = (-1 + \sqrt{1 + 8k}) / 2

Cavab $⌊(- 1 + 1 + 8 k) /2 ⌋$ \lfloor(-1 + \sqrt{1 + 8k}) / 2 \rfloor olacaq.

Alqoritmin realizasiyası

Girdi dəyəri $k$ oxunur.

scanf("%d",&k);

Cavabı hesablayır və çıxışa veririk.

n = int((-1 + sqrt(1.0 + 8*k)) / 2.0);
printf("%d\n",n);