Задача 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 |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
#include <iostream> using namespace std; int main() { int n, k; double waterPerTree = 0; cin >> n; int days = 0; while(waterPerTree <= 0.5) { waterPerTree += (double) 1 / (n - days++); } k = n - days +1; cout << k; return 0; } |
Для запроса на выполнение нажать здесь.
Решение
Пускай в переменной [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].