e-olymp 398. Торт для Серёжи

30/01/2020 by Дмитрий Воротов

Задача

Мама испекла Серёже на день рождения большой и вкусный круглый торт и поручила ему самому его разрезать. У него в распоряжении есть достаточно длинный нож, позволяющий делать разрез по всему торту, однако так как общение с режущими инструментами всегда таит в себе определенные опасности, Серёжа хочет сделать минимальное количество разрезов так, чтобы всем гостям досталось хотя бы по одному кусочку. Естественно, при этом он должен не забыть, что и ему должен за праздничным столом достаться хотя бы один кусочек маминого торта, но при этом Серёжу абсолютно не интересует, какого размера и формы будут куски торта – для него главное, чтобы они все имели такую же толщину, как и испеченный мамой торт.

Учтите, что гостей к Серёже может придти достаточно много.

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

Одно число – количество гостей $n$ $(n < 210000001)$ .

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

Искомое количество разрезов $k$ .

Тесты

№	Входные данные	Выходные данные
1	3	2
2	0	0
3	120	15
4	210000000	20494

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

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    cout << round(sqrt(2 * n));
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n;

cin >> n;

cout << round(sqrt(2 * n));

return 0;

}

Решение

Максимального количества кусков можно достичь в том случае, когда каждый новый разрез будет пересекать все предыдущие. Таким образом новым $k$ -ым сечением мы разрежем $k$ кусков торта на две части, а к общему количеству кусочков прибавится ровно $k$ новых. Заметим, что имениннику всегда достанется кусок, который не считается новым. Множество всех новых кусков составит арифметическую прогрессию: $0,1, 2, 3 … k-1, k$ значит общее количество кусочков для гостей вычисляется как сумма арифметической прогрессии $\mathbf{n = \frac{i^{2}+k}{2}}$ . Тогда $\mathbf{k =\left \lceil \frac{-1+\sqrt{1+8n}}{2} \right \rceil }$ .

Эту формулу немного можно упростить, в результате получим $\mathbf{k =\left [ \sqrt{2n}\right ]}$

Ссылки

Условие задачи e-olymp

Код решения ideone

Related Images:

e-olymp 8649. Емблема (Emblem)

20/06/2019 by Blyshchyk

Умова

До проведення $N$ -ї ярмарки «Мікротехнології у макропрограмуванні» дизайнери розробили емблему, у якій на квадрат розміром $N \times N$ дм «ставився зверху» квадрат розміром $\left(N-1\right) \times \left(N-1\right)$ дм і так далі. Зверху був квадрат $1 \times 1.$ В цілому організаторам емблема сподобалася, але вони забажали «прикрасити» її золотистою стрічкою, яка йшла б від лівого нижнього кута до правого верхнього, потім по верхньому краю і спускалася до правого нижнього кута (див. малюнок). У найближчому магазині можна було купити стрічку за ціною $Р$ грн. за дм, але відпускалися стрічки тільки з цілою кількістю дм. У той же час магазин пропонував знижку $10\%$ , якщо покупка коштувала не менше $100$ грн. і $15\%$ при покупці від $1000$ грн. Скільки щонайменше доведеться заплатити за цю «прикрасу»? Нагадаємо, що на декартовій площині довжина відрізку між точками $\left(x_{1};y_{1}\right)$ та $\left(x_{2};y_{2}\right)$ обчислюється за формулою: $d=\sqrt{\left(\left(x_{2}-x_{1}\right)^{2}+\left(y_{2}-y_{1}\right)^{2} \right)}.$

Вхідні дані:

Програма вводить два натуральних числа $N$ – номер ярмарки та $P$ -ціна стрічки у гривнях за дм $\left(1 \leqslant N \leqslant 100\right).$

Вихідні дані:

Ціна стрічки у копійках (щоб не працювати з дробовими числами).

Тести:

Вхідні дані	Вихідні дані
2 13	9360
5 10	28800
100 1	858670
1 5	2000
12 3	42660

Рішення:

#include 
#include 
using namespace std;

int main() {
    long long N, P;
    cin >> N >> P;
    double h, l, d, lenta, price;
    h = (1+N)*N*0.5;
    l = 0.5 + N*0.5;
    d = sqrt(h*h + l*l);
    lenta = ceil(d + d + 1);
    price = lenta * P;
    if (price >= 1000) {
        price *= 85;
    }
    else if (price >= 100) {
        price *= 90;
    }
    else {
        price *= 100;
    }
    if (ceil(100./P) > lenta and price > 90*ceil(100./P)*P){
        price = 90*ceil(100./P)*P;
    }
    else if (ceil(1000./P) > lenta and price > 85*ceil(1000./P)*P) {
        price = 85*ceil(1000./P)*P;
    }
    cout << price;
}

#include

using namespace std;

int main() {

long long N, P;

cin >> N >> P;

double h, l, d, lenta, price;

h = (1+N)*N*0.5;

l = 0.5 + N*0.5;

d = sqrt(h*h + l*l);

lenta = ceil(d + d + 1);

price = lenta * P;

if (price >= 1000) {

price *= 85;

}

else if (price >= 100) {

price *= 90;

}

else {

price *= 100;

}

if (ceil(100./P) > lenta and price > 90*ceil(100./P)*P){

price = 90*ceil(100./P)*P;

}

else if (ceil(1000./P) > lenta and price > 85*ceil(1000./P)*P) {

price = 85*ceil(1000./P)*P;

}

cout << price;

}

Пояснення: Спочатку необхідно знайти довжину діагоналі, для цього, умовно ми можемо продовжити саму верхню пряму в праву і ліву сторону до того моменту поки її довжина не стане не менш ніж $N$ дм, а потім починаючи з лівого нижнього кута куба $N \times N$ провести перпендикуляр до цієї прямої. Так у нас вийде прямокутний трикутник, в якому (знаходимо за формулою $n$ -перших членів арифметичної прогресії $S_{n} = \frac{a_{1}+a_{n}}{2} \cdot n$ ) та l — катети, тоді за теоремою Піфагора можемо знайти діагональ d. Далі знаходимо довжину стрічки і її ціну з огляду на знижки. Також необхідно зробити перевірку, чи буде вигідніше придбати стрічку на таку кількість грошей, яке буде відповідати умовам знижки.

Related Images:

e-olymp 2860. Сумма чисел на промежутке

05/12/2017 by Александр Дьяченко

Задача

Найти сумму целых чисел на промежутке от $a$ до $b$ .

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

Два целых числа $a$ и $b$ , по модулю не превышающих $10^9$ .

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

Сумма целых чисел на промежутке от $a$ до $b$ .

Тесты

Входные данные	Выходные данные
2 5	14
249 318	19845
23 69	2162
124 200	12474
478 653	99528

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

#include <iostream>
using namespace std;

int main() {
    long a, b, n, S;
    cin >> a >> b;
    n = b - a + 1;
    S = (a + b) * n / 2;
    cout << S;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long a, b, n, S;

cin >> a >> b;

n = b - a + 1;

S = (a + b) * n / 2;

cout << S;

return 0;

}

Решение

Для того, что бы найти ответ, нам необходимо знание формул прогрессии, так как решением данной задачи является сумма $n$ первых членов арифметической прогрессии. Вычислить её можно по формуле $\displaystyle S_n = \frac{a_1 + a_n}{2} \cdot n$ , где $a_1$ — это из входного потока, а $a_n$ — это . Тем не менее, мы все ещё не можем применить вышеприведенную формулу, так как нам неизвестно $n$ . Выведем же его из формулы $n$ -ого члена арифметической прогрессии: $a_n = a_1 + d \cdot (n-1)$ , где $d$ — это разность арифметической прогрессии, которая по условию (хоть и негласно) равна единице. Зная это, из последней формулы выведем, что $n = a_n-a_1 + 1$ . Теперь же, когда мы знаем все необходимые значения, остается только подсчитать сумму арифметической прогрессии по ранее данной формуле и подать результат на выход.

Ссылки

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

Related Images:

e-olymp 1210. Очень просто!!!

04/12/2017 by Вадим Гордийчук

Задача

По заданным числам $n$ и $a$ вычислить значение суммы: $\sum\limits_{i=1}^{n} {i \cdot a^i}$

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

Два натуральных числа $n$ и $a$ .

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

Значение суммы. Известно, что оно не больше $10^{18}$ .

Тесты

Входные данные	Выходные данные
3 3	102
4 4	1252
9 3	250959
7 14	785923166
1009 1	509545

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

#include <iostream>
using namespace std;

int main()
{
    unsigned long long int n, a, answer;
    cin >> n >> a;
    if (a > 1)
    {
        answer = n*a;
        for(unsigned long long int i = n-1; i > 0; --i)
            answer = (answer+i)*a;
    }
    else
        answer = n*(n+1)/2;
    cout << answer;
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

unsigned long long int n, a, answer;

cin >> n >> a;

if (a > 1)

{

answer = n*a;

for(unsigned long long int i = n-1; i > 0; --i)

answer = (answer+i)*a;

}

else

answer = n*(n+1)/2;

cout << answer;

return 0;

}

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

public class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        long n = in.nextInt(), a = in.nextInt(), ans;
        if (a > 1)
        {
            ans = n*a;
            for(long i = n-1; i > 0; --i)
                ans = (ans+i)*a;
        }
        else
            ans = n*(n+1)/2;
        System.out.println(ans);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

public class Main

{

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

{

Scanner in = new Scanner(System.in);

long n = in.nextInt(), a = in.nextInt(), ans;

if (a > 1)

{

ans = n*a;

for(long i = n-1; i > 0; --i)

ans = (ans+i)*a;

}

else

ans = n*(n+1)/2;

System.out.println(ans);

}

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

Данную задачу можно решить прямым линейным вычислением значений элементов заданного ряда, то есть получать значение элемента ряда с индексом $i$ умножением $a$ (которое необходимо возвести в степень $i$ ) на индекс $i$ и накапливать сумму этих значений в выделенной переменной.
Но безусловно такое решение не является качественным (даже если будет использован алгоритм бинарного возведения в степень).

Для получения качественного решения распишем ряд подробно:
$A$ $=$ $\sum\limits_{i=1}^{n} {i \cdot a^i}$ $=$ $a+2a^2+3a^3+\ldots+\left( n-1 \right) a^{n-1}+na^{n}$ $=$ $na^{n}$ $+$ $\left( n-1 \right)a^{n-1}$ $+$ $\ldots$ $+$ $3a^{3}$ $+$ $2a^2$ $+$ $a$ .
Очевидно, что из полученного выражения можно вынести $a$ за скобки. Применим данную операцию:
$A$ $=$ $\left( na^{n-1}+\left( n-1 \right)a^{n-2}+\ldots+3a^{2}+2a+1\right) \cdot a$ Из полученной формулы видно, что аналогичное действие можно применить вновь, для внутреннего выражения $na^{n-1}$ $+$ $\left( n-1 \right)a^{n-2}$ $+$ $\ldots$ $+$ $3a^{2}$ $+$ $2a$ . Получим:
$A$ $=$ $\left( \left( na^{n-2}+\left( n-1 \right)a^{n-3}+\ldots+3a+2 \right) \cdot a +1 \right) \cdot a$ .
После конечного количества вынесений за скобки, получим:
$A$ $=$ $\left( \left( \ldots \left( \left(na+\left(n-1\right)\right) \cdot a + \left(n-2\right) \right) \ldots+2\right) \cdot a +1\right) \cdot a$ .

Таким образом, решение данной задачи сводится к вычислению суммы «изнутри» скобок.

Но из-за того, что в условии подано ограничение только на сумму, программа с реализованным вычислением суммы изнутри и асимптотикой $O \left( n \right)$ не пройдёт все тесты системы www.e-olymp.com в силу частного случая $a = 1$ , так как значение $n$ может быть для него достаточно большим, ибо числа $a$ и $n$ компенсируют друг-друга по отношению к максимальному значению суммы. Но в случае $a = 1$ сумма данного ряда является суммой арифметической прогрессии, а именно — натурального ряда. Для вычисления этой суммы существует формула $\sum\limits_{i=1}^{n} {i} = \frac{n \left( n+1 \right)}{2}$ . Этот частный случай легко отсеять.

Асимптотика программы: $const$ при $a = 1$ , и $O \left( n \right)$ иначе.

Ссылки

Related Images:

e-olymp 248. Юный садовод

01/10/2015 by Кондратюк Настя

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

Условие задачи

Мама попросила Васю полить все молодые деревца в саду. Вася знает, что пока деревья маленькие, их надо очень хорошо поливать. А вот сколько поливать — неизвестно. Но Вася — очень умный мальчик. Он внимательно прочитал весь учебник ботаники для средней школы и выяснил, что полив прямо пропорционален количеству листьев на дереве. Для хорошего роста деревьев достаточно выливать под дерево ежедневно по одному литру воды на каждый лист.

К счастью Васи оказалось, что листья на деревьях растут ярусами, причем на верхнем ярусе два листа, на втором — четыре, на следующем — шесть, и так далее, на каждом последующем ярусе на два листа больше по сравнению с предыдущим. А на самой верхушке растет еще один листик. Хитрый Вася послал младшую сестренку Машеньку подсчитать количество ярусов на каждом дереве, а Вас просит написать программу, которая для каждого дерева вычислит количество литров воды для его полива.

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

Количество ярусов $n (0 \leq n \leq 1000)$ на дереве.

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

Вывести количество литров воды для полива этого дерева.

Тесты

	Входные данные	Выходные данные
1.	3	13
2.	0	1
3.	50	2551
4.	560	314161

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

#include <iostream>
using namespace std;

int main() {
    int n,a=0,sum=0;
    cin >> n;
    for(int i=0 ; i<n ; i++){
        a = a + 2;
        sum = sum + a;
    }
    cout << (sum+1) << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n,a=0,sum=0;

cin >> n;

for(int i=0 ; i<n ; i++){

a = a + 2;

sum = sum + a;

}

cout << (sum+1) << endl;

return 0;

}

ideone.com

Решение

Для решения этой задачи необходимо найти сумму арифметической прогрессии, где $N=n,$ $a_{1} = 2$ и $d = 2$ и добавить к ней единицу (лист с верхушки). Для этого можно воспользоваться формулой суммы арифметической прогрессии $Sn=\frac{2a_{1}+d\left(n-1 \right)}{2}n \rightarrow n^2+n$ , либо при помощи цикла $n$ раз прибавлять к $a$ двойку, получая при этом следующий член прогрессии и добавлять его к сумме.

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

Related Images:

ML21

29/09/2015 by Павел Загинайло

Задача. Найти сумму членов арифметической прогрессии $a, a+d, a+2d \dots, a+(n-1)d$ по данным значениям $a, d, n$ .

Тесты:

$a$	$d$	$n$	$Sn$
8	657	0	0
5	0	2	10
5	8	1	5
0	5565	88	21302776

Код:

#include <iostream>
using namespace std;

int main() {
	int a, d, n;
	cin >> a >> d >> n;
	cout << ((2*a + d*(n - 1))/2)*n;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, d, n;

cin >> a >> d >> n;

cout << ((2*a + d*(n - 1))/2)*n;

return 0;

}

Алгоритм.

В данной программе я воспользовался формулой суммы арифметической прогрессии. А именно $S_{n} = \frac{a_{1} + d(n — 1)}{2} * n$ , где $a_{1}$ — первый член арифметической прогрессии, $d$ -разница арифметической прогрессии и $n$ — номер последнего члена суммы. Программа же просто выводит результат данных вычислений на экран.

Related Images:

e-olymp 157. Зоопарк

14/09/2015 by Аня Шохина

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

Постановка задачи

В зоопарке $N$ клеток выстроены в ряд. В зоопарке, кроме прочих обитателей, живут две мартышки, Слава и Юра. Слава и Юра всегда были большими друзьями и сидели в соседних клетках, но теперь они поссорились и больше не хотят видеть друг друга. Смотритель уже собрался переселить их в соответствии с их желанием, однако возникла проблема. Слава и Юра — очень образованные мартышки (каждый из них закончил аж по восемь классов!), и они непременно хотят знать, сколько всего существует способов расселить их так, чтобы их клетки не были соседними, и уж конечно их клетки должны быть различными. Можно считать, что все $N$ клеток доступны, остальные обитатели зоопарка готовы переехать куда угодно.

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

В первой строке входных данных находится число $N$ $(2\leq N\leq 100)$ — количество клеток в зоопарке.

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

Выведите одно число — количество способов поселить Славу и Юру в разные клетки так, чтобы эти клетки не были соседними.

Тесты

4	6
15	182
30	812
48	2162
60	3422

Реализация

#include <iostream>
using namespace std;
 
int main() {
    int n; // количество клеток
    int c; //количество способов поселения 
    cin >> n;
    c = (n - 1) * (n - 2);
    cout << c;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n; // количество клеток

int c; //количество способов поселения

cin >> n;

c = (n - 1) * (n - 2);

cout << c;

return 0;

}

Здесь находится код в ideone.com

Решение

Рассмотрим возможные расположения клеток при условии, что одна из обезьян занимает первую клетку. Очевидно, что другая обезьяна не может занимать первую и вторую клетки, т к клетки должны быть разными и не соседними. Следовательно, существует $(n — 2)$ вариантов расположения второй обезьяны. Далее предположим, что первая обезьяна занимает вторую клетку. Тогда количество вариантов расположения второй обезьяны равно $(n-2-1) = (n-3)$ . И так далее, до тех пор пока не останется один вариант расположения второй обезьяны. Таким образом, ключ к решению задачи лежит в рассмотрении количества вариаций расположения клеток обезьян как арифметической прогрессии. Исходя из условия задачи, нам необходимо найти сумму первых $n$ членов прогрессии. Формула для вычислений: $S=\frac{(a_1 + a_k}{2}*k$ , где $a_1=n-2$ и $a_k=1$ , и $k=n-2$ . Применяя математические преобразования, получаем что $S=\frac{(n-1) * (n-2)}{2}$ . Однако, имеет значение не только, непосредственно, какие две клетки заняты, но и какая именно из обезьян занимает определенную клетку. То есть при $n=3$ мы имеем лишь пару клеток, которые можем использовать, но два способа поселения. Следовательно, полученное выражение необходимо умножить на два. Таким образом, мы вывели необходимую нам формулу.