Задача
Работник отдела технического контроля любил выбраковывать «доминошки», которые содержали одинаковые значения. Так как на предприятии, выпускающем [latex]K[/latex]-домино, этого не знали, к нему постоянно поступали претензии на сумму, равную стоимости [latex]K[/latex]-домино. Стоимость [latex]K[/latex]-домино составляла ровно столько гривен, сколько было в купленном покупателем наборе доминошек.Для того, чтобы его не уволили с работы, работник ОТК выбраковывал иногда не только все не любимые «доминошки», а несколько больше, но не более половины гарантированно выбраковыванных.Зная сумму претензии, пришедшей на предприятие, установите, какой из наборов [latex]K[/latex]-домино был куплен покупателем.
Входные данные
Единственное число [latex]S[/latex] – сумма претензии, пришедшей на предприятие, [latex]S ≤ 2000000000[/latex].
Выходные данные
Единственное число – индекс [latex]K[/latex] купленного покупателем [latex]K[/latex]-домино.
№ | Входные данные | Выходные данные |
---|---|---|
1 | 5 | 3 |
2 | 10 | 4 |
3 | 1000000 | 1414 |
4 | 555666777888 | 1054198 |
5 | 13 | 5 |
Код программы
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
#include <iostream> #include <cmath> using namespace std; int main() { //учтём ограничение для s (s ≤ 2000000000) long long s; //для k используем целочисленный тип, так как при присваивании ему дробного числа, это число автоматически округлится. long long k; cin>>s; k = sqrt(2 * s + 1); cout<<k; return 0; } |
Решение
[latex]K[/latex]-домино — набор домино с минимальным количеством точек на одной из половин доминошки.Количество дублей, то есть количество точно выбракованных доминошек — [latex]k[/latex]+1. Общее количество доминошек [latex]k[/latex]-домино:$$(k+1){{k+2}\over{2}}$$
Пусть работник дополнительно выбраковывал [latex]e[/latex] доминошек. [latex]s[/latex] — сумма претензии, тогда имеем: [latex]k+1+e+s= (k+1){{k+2}\over{2}}[/latex] [latex]k^2<=2s+1[/latex] [latex]k=[\sqrt{2s+1}][/latex]
Ссылки
Ссылка на e-olymp.
Ссылка на Ideone
One thought on “e-olymp 51. К-домино”