e-olymp 10. Садовник

Задача e-olymp №10

Ссылка на засчитанное решение.

Условие

Садовник посадил за день [latex]n[/latex] деревьев и должен был вылить под каждое деревцо по ведру воды. Так как в день посадки шёл дождь, садовник начал поливку деревьев не в день посадки, а начиная с какого-то [latex]k[/latex]-го дня.

Сколько дней садовник не поливал деревья, если в последний день он под каждое из деревьев вылил [latex]\frac{1}{n}[/latex] часть воды из ведра, в предпоследний [latex]\frac{1}{n-1}[/latex]часть, и т.д., а всего под каждое из деревьев вылил не более, чем по половине ведра воды?

 

Входные данные

Количество деревьев [latex]n[/latex]. [latex]0 < n \le 1000000[/latex]

 

Тесты

Входные данные

(количество деревьев)

Выходные данные

(искомое количество дней)

3 2
1000000 606531

Код программы

Для запроса на выполнение нажать здесь.

Решение

Пускай в переменной [latex]days[/latex] будет храниться количество дней, в которые садовник поливал деревья, но так как отсчёт начинает с [latex]days = 0[/latex], ([latex]\frac{1}{n}[/latex]), то количество всех дней, когда садовник поливал деревья будет равно максимальному значению [latex]days[/latex] в цикле плюс 1; в переменной [latex]waterPerTree[/latex] — количество вёдер воды, вылитых на одно дерево. Количество вёдер воды, вылитых под одно дерево в определённый день: [latex]\frac{1}{n — days}[/latex]. Так как под каждое дерево садовник вылил не больше [latex]\frac{1}{2}[/latex] ведра воды, то будем выполнять цикл, пока [latex]waterPerTree[/latex] не будет равно этому значению.

Чтоб найти количество дней, на протяжении которых садовник поливал деревья, разделим количество воды, потраченное садовником за всё время поливки [latex]\frac{1}{2}[/latex] на количество вёдер воды, вылитых под одно дерево в определённый день [latex]\frac{1}{n — days}[/latex]. Тогда получим, что [latex]\frac{n — days}{2}[/latex].

По условию задачи, садовник должен был вылить по ведру воды под каждое деревцо, но вылил всего по половине из-за дождя. Из этого следует, что количество воды, выпавшей на каждое деревцо, пиблизительно равно [latex]\frac{1}{2}[/latex] ведра воды. Тогда если всего под каждым деревом по 1 ведру воды за [latex]x[/latex] дней, а садовник вылил по [latex]\frac{1}{2}[/latex] ведра воды за [latex]days + 1[/latex] дней, то [latex]x = 2n — 2days[/latex]. В итоге, [latex]k = \frac{1}{2}x = n — days[/latex]. Но, так как в последнем действии цикла вычисленное [latex]waterPerTree[/latex] будет больше [latex]\frac{1}{2}[/latex], то [latex]k = n — (days — 1)[/latex].

3 thoughts on “e-olymp 10. Садовник

  1. — В условии тоже должно быть [latex]n[/latex], а не n.
    — Добавьте ещё в ключевые слова «гармонический ряд», поскольку именно о нём идёт речь. Точнее о разности двух частичных сумм гармонического ряда.

    P.S. Поскольку Вы безусловно очень способная студентка, хочу попросить вас поразмышлять (и попрограммировать) на тему суммы гармонического ряда. Не получится, так не получится. Нестрашно. А если выйдет, то у нас будет ещё одно интересное решение.

  2. Зачтено.
    Когда я предлагал поиграть с частичными суммами гармонического ряда, то имел в виду приближенную формулу Эйлера. Поскольку решение нас интересует с точностью до целого числа дней, легко подобрать константу, чтобы решение проходило вообще без циклов:

    Можно попытаться апроксимировать логарифм и экспоненту многочленом так, чтобы и они не понадобились.
    Ну, это так, для любителей…

Добавить комментарий