e-olymp 1452. Кролики

14/10/2018 by Владимир Дроздин

Задача взята с сайта e-olymp.

Задача

Как-то наконец земляне нашли обитаемую планету, назвали ее ТТВ, и отправили вместе с кораблем туда одного кролика. Кролику понравился климат новой планеты и через месяц он произвел на свет еще одного кролика. Известно, что каждый месяц каждый кролик, присутствующий на планете, производил на свет еще одного кролика. На планете откуда-то взялся монстр, который в начале месяца съедал [latex] k [/latex] кроликов, если только их становилось строго больше [latex] k [/latex]. В задаче необходимо определить количество кроликов, которое будет на планете через [latex] n [/latex]месяцев после прибытия туда космического корабля с первым кроликом.

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

Первая строка содержит количество месяцев [latex] n [/latex] [latex] (0 ≤ n ≤ 100) [/latex], вторая — число кроликов [latex] k [/latex] [latex] (0 ≤ k ≤ 10000) [/latex], которое съедал монстр.

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

Определить количество кроликов, которое будет находиться на планете ТТВ через [latex] n [/latex] месяцев после поселения туда первого кролика. Известно, что результат для любого теста всегда не больше [latex] 2 \cdot 10^9 [/latex].

Тесты

#	Входные данные	Выходные данные
1	0 10	1
2	1 10	2
3	10 7	128
4	7 128	12
5	30 0	1073741824
6	29 29	2
7	20 20	16
8	90 90	64

Cпособ 1 (с циклом)

Код

#include <iostream>
using namespace std;
 
int main() {
    long int r = 1, n, k;
    cin >> n >> k;
    for (int i = n; i > 0; i--){
        if (r > k) r -= k;
        r *= 2;
    }
    cout << r;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long int r = 1, n, k;

cin >> n >> k;

for (int i = n; i > 0; i--){

if (r > k) r -= k;

r *= 2;

}

cout << r;

return 0;

}

Решение

Известно, что изначально на планете был один кролик. Создадим цикл, который будет высчитывать популяцию кроликов на планете через [latex] n [/latex] месяцев после прибытия. Цикл будет работать до тех пор, пока количество месяцев будет больше нуля. В нем будем высчитывать популяцию кроликов по простой формуле [latex] r = r \cdot 2 [/latex], где [latex] r [/latex] — количество кроликов. Если же количество кроликов, съедаемых монстром в начале месяца строго больше того количества, которое уже есть на планете, то от этой популяции отнимем [latex] k [/latex]кроликов : [latex] r = r[/latex] $-$ [latex] k [/latex]. Внутри цикла также не забываем от данного количества [latex] n [/latex] месяцев отнимать по одному каждый раз.

Способ 2 (без цикла)

Код

#include <iostream>
using namespace std;

int f2(long int r, long int n, long int k){
    if (n == 0) return r;
    if (r <= k) return f2(r * 2, n - 1, k);
    return f2(2 * (r-k), n - 1, k);
}   

int main() {
    long int n, k, r = 1;
    cin >> n >> k;
    cout << f2(r, n, k);
    return 0;
}

#include <iostream>

using namespace std;

int f2(long int r, long int n, long int k){

if (n == 0) return r;

if (r <= k) return f2(r * 2, n - 1, k);

return f2(2 * (r-k), n - 1, k);

}

int main() {

long int n, k, r = 1;

cin >> n >> k;

cout << f2(r, n, k);

return 0;

}

Решение

Сам алгоритм похож на 1 способ, однако здесь мы будем использовать рекурсивную функцию, а не цикл. Функция int f2(); будет вызывать сама себя до тех пор, пока количество месяцев [latex] n [/latex] не станет равным нулю.

Ссылки

Засчитанное решение на e-olymp.

1 Код в ideone.

2 Код в ideone.

Related Images:

e-olymp 7367. Спортсмен

21/12/2017 by Иван Мясоедов

Задача

Спортсмен в первый день пробежал 10 км. Каждого следующего дня он увеличивал норму на 10% от нормы предыдущего дня. Опредилить через какое найменьшее количество дней спортсмен пробежит сусмарный путь не меньший чем [latex]N[/latex] км.

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

Целое число [latex]N (0 < N≤ 1000)[/latex].

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

Единственное число – количество дней.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	9	1
2	45	4
3	324	16
4	1234	28
5	213213123	153

Код программы №1 (с использованием цикла):

#include <iostream>
#include <cmath>
using namespace std;
 
int main() 
{
   double k = 1, T = 10, N, S = 10;
   cin >> N;
   while (N > T) {
       S = S * 1.1;
       T = S + T;
       k++;
   }
   cout << k;
   return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

double k = 1, T = 10, N, S = 10;

cin >> N;

while (N > T) {

S = S * 1.1;

T = S + T;

k++;

}

cout << k;

return 0;

}

Решение задачи:

Сначала вводим 4 переменные: [latex] k=1 [/latex] ( количество дней ), [latex] T=10 [/latex] ( количество километров которое спортсмен пробежал ), [latex] N [/latex] ( количество километров которое спортсмен должен пробежать ) и [latex] S [/latex] ( количество километров которое спортсмен пробегает в день ). Цикл каждый раз будет прибавлять к расстоянию которое пробежал спортсмен, количество километров которое спортсмен должен пробежать в течение следующего дня, с учетом того, что каждый день он будет пробегать на [latex] 10 [/latex] процентов больше, чем в прошлый день, параллельно увеличивая количество дней, пока [latex] N [/latex] будет больше [latex] T [/latex]. Если же [latex] N [/latex] при вводе изначально будет меньше [latex] T [/latex], то программа выведет, что спортсмену достаточно одного дня.

Время срабатывания программы при [latex]N = 1000[/latex] : [latex]65[/latex] [latex]ms[/latex]

Ссылки

Задача на сайте e-olymp
Код решения в Ideone

Код программы №2(с использованием линейных вычислений):

#include <iostream>
#include <cmath>

using namespace std;

int main() 
{
   double s;
   cin >> s;
   cout << ceil (log(s / 100 + 1) / log(1.1));
   return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

double s;

cin >> s;

cout << ceil (log(s / 100 + 1) / log(1.1));

return 0;

}

Решение задачи:

Также данную задачу можно решить с помощью формулы геометрической прогрессии [latex]S=\frac{b_1(q^n-1)}{q-1}[/latex] из которой нам нужно будет выразить степень [latex] n [/latex] через логарифм при условии того, что по условию задачи мы знаем, что [latex] q=1.1 [/latex] и [latex] b_1=1 [/latex]. И мы получаем, что [latex] \left(n=\log_{1.1}\left(\frac{s}{100}+1\right)\right) [/latex]. При записи логарифма по основанию в С++ мы пользуемся основным свойством логарифмов: [latex] \log_{a}\left(b\right)=\frac{\log_{c}\left(b\right)}{\log_{c}\left(a\right)} [/latex]. Также используем функцию сeil, которая округлит выходное число вверх, до ближайшего целого. ( [latex] S [/latex] — количество километров, которое должен пробежать спортсмен ).

Время срабатывания программы при [latex]N = 1000[/latex] : [latex]76[/latex] [latex]ms[/latex]

Ссылки

Задача на сайте e-olymp
Код решения в Ideone №2

Related Images:

e-olimp 146. Квадраты — 2

04/11/2017 by Антон Джашимов

Задача

В белом квадрате [latex]N[/latex] раз выполнили одну и ту же операцию: один из наименьших белых квадратов разбили на 4 одинаковых квадрата и 2 из них закрасили черным цветом. Для данного [latex]N[/latex] вычислить, сколько процентов занимает площадь черной фигуры.

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

Во входном файле одно число [latex]N[/latex]. [latex]1 ≤ N ≤ 100[/latex].

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

В выходной файл нужно записать ответ, вычисленный с точностью 5 знаков после запятой по правилам математических округлений.

Тесты

Входные данные	Выходные данные
1	50.00000
3	65.62500
10	66.66660
50	66.66667
100	66.66667

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

#include <iostream>
#include <cmath>
#include <iomanip>
//Подключаем этот модуль,чтобы установить точность ответа
using namespace std;

int main() {
    double n;
    cin >> n;
    cout << fixed << setprecision(5) << (50*(1-(pow(0.25,n))))/(0.75);
    return 0;
}

#include <iostream>

#include <cmath>

#include <iomanip>

//Подключаем этот модуль,чтобы установить точность ответа

using namespace std;

int main() {

double n;

cin >> n;

cout << fixed << setprecision(5) << (50*(1-(pow(0.25,n))))/(0.75);

return 0;

}

Решение задачи

При [latex]N=1[/latex] площадь черной фигуры составляет [latex]50\%[/latex]. При [latex]N=2[/latex] площадь фигуры равна [latex]50\%+50\%\cdot 1/4[/latex]. При [latex]N=3[/latex] площадь черной фигуры составляет [latex]50\%+50\%\cdot 1/4+50\%\cdot 1/16[/latex]. Очевидно, что перед нами геометрическая прогрессия. Процент, занимаемый площадью черной фигуры, будем искать через сумму геометрической прогресcии: [latex]S_n={{b_1(1-q^N)}\over{1-q}}[/latex], где [latex]q={{b_2}\over{b_1}}={{12.5}\over{50}}=0.25[/latex], [latex]N-[/latex]кол-во операций.

Ссылки

Условие задачи на e-olymp
Код решения

Related Images:

D2547. Cумма ряда

23/10/2016 by Антон Куперман

Задача

Доказать сходимость и найти сумму ряда [latex]\sum \limits_{n=1}^{\infty}\left(\frac{1}{2^n}+\frac{1}{3^n}\right)[/latex].

Код на C++

#include <iostream>
using namespace std;

int main() {
    double S,s1,s2;
    s1=(1.0/2.0)/(1.0-(1.0/2.0));
    s2=(1.0/3.0)/(1.0-(1.0/3.0));
    S=s1+s2;
    cout << S;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

double S,s1,s2;

s1=(1.0/2.0)/(1.0-(1.0/2.0));

s2=(1.0/3.0)/(1.0-(1.0/3.0));

S=s1+s2;

cout << S;

return 0;

}

Код на Java

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        double S,s1,s2;
        s1=(1.0/2.0)/(1.0-(1.0/2.0));
        s2=(1.0/3.0)/(1.0-(1.0/3.0));
        S=s1+s2;
        System.out.print(S);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

double S,s1,s2;

s1=(1.0/2.0)/(1.0-(1.0/2.0));

s2=(1.0/3.0)/(1.0-(1.0/3.0));

S=s1+s2;

System.out.print(S);

}

Решение

Разобьем ряд на два: [latex]\frac{1}{2^n}[/latex] и [latex]\frac{1}{3^n}[/latex]. Оба ряда являются бесконечно убывающими геометрическими прогрессиями, следовательно они сходятся и сумма этих рядов тоже будет сходиться. Знаменателем первой прогрессии([latex]s_1[/latex]) будет [latex]\frac{1}{2}[/latex], а знаменателем второй([latex]s_2[/latex]) — [latex]\frac{1}{3}[/latex]. Тогда по формуле суммы бесконечно убывающей прогрессии: [latex]s=\frac{b_1}{1-q}[/latex], где [latex]b_1[/latex] первый член прогрессии, а [latex]q[/latex] — ее знаменатель. Затем суммируем суммы прогрессий и получаем ответ.

Ответ

[latex]\sum \limits_{n=1}^{\infty}\left(\frac{1}{2^n}+\frac{1}{3^n}\right)=\frac{3}{2}=1.5[/latex].

Ссылки

1.Решение на C++

2.Решение на Java

3.Решение на WolframAlpha