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

Задача

Тесты

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

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

Ссылки

e-olymp 112. Торт

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

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

C ветвлением:

Без ветвления:

Решение с ветвлением

Решение без ветвления

Ссылки

e-olymp 3604. Крейсерская скорость

e-olymp 7460. Поездка на экскурсию

e-olimp 57. Бабочка-санитар

Задача

Универсальное дерево отрезков

Задача 1: единичная модификация

Код класса

Описание класса

Инструкция по применению

Пример использования

Задача 2

Код класса

Описание дополнительных объектов класса

Ссылки

KM210. Классы эквивалентности некоторой последовательности

ML37. Самолёт и ветер

ML 36. Движение катера

ML25. Расстояние между двумя точками

Ml 34. Угол лодки относительно течения

ML 31. Площадь параллелепипеда

e-olymp 57. Бабочка-санитар

Условие

Тесты:

Код:

Ход решения:

Ссылки:

А26

Ю1.6

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

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

Задача

Тесты

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

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

Ссылки

Задача

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

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

Некоторые теоретические сведения

Задача

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

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

Тесты

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

Решение

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

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

Related Images:

Related Images:

Related Images:

Related Images:

Related Images:

Решение задачи №4082 на www.e-olymp.com

Фрагмент кода

Related Images:

Related Images:

Ссылки

Related Images:

Related Images:

Related Images:

Related Images:

Код на C++

Код на Java

Алгоритм

Related Images:

Related Images:

Related Images:

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

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

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

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

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

Ссылки:

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

Работающая версия программы на языке C++.

Работающая версия программы на языке Java.

Геометрические свойства векторного произведения.

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

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

Два натуральных числа [latex]n[/latex] и [latex]a[/latex].

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

Входные данные	Выходные данные
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);

}

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

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

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

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

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

26/11/2017 by Илья Черноморец

В честь дня рождения наследника Тутти королевский повар приготовил огромный праздничный торт, который был подан на стол Трем Толстякам. Первый толстяк сам мог бы целиком его съесть за $t_1$ часов, второй — за $t_2$ часов, а третий — за $t_3$ часов.

Сколько времени потребуется толстякам, чтобы съесть весь праздничный торт вместе?

Единственная строка содержит три целых неотрицетельных числа $t_1$, $t_2$ и $t_3$, каждое из которых не превосходит $10000$.

Вывести время в часах, за которое толстяки вместе могут съесть торт. Результат округлить до двух десятичных знаков.

TESTS

$t_1$	$t_2$	$t_3$	$t$
3	3	3	1.00
4	67	50	3.51
228.22	8	2.28	1.76
1577	157.7	15.77	14.21

#include<iostream>
#include<iomanip>

using namespace std;
int main(){
    double t1,t2,t3;
    cin >> t1 >> t2 >> t3;
    double t;
    t = (t1*t2*t3) / (t1*t2 + t1*t3 + t2*t3);
    if(t1*t2*t3 == 0) cout<<0;
        else cout<<fixed<<setprecision(2)<<t;
    return 0;
}

#include<iostream>

#include<iomanip>

using namespace std;

int main(){

double t1,t2,t3;

cin >> t1 >> t2 >> t3;

double t;

t = (t1*t2*t3) / (t1*t2 + t1*t3 + t2*t3);

if(t1*t2*t3 == 0) cout<<0;

else cout<<fixed<<setprecision(2)<<t;

return 0;

}

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
    double t1, t2, t3;
    cin >> t1 >> t2 >> t3;
    double t = 1 / (1 / t1 + 1 / t2 + 1 / t3) ;
    cout << setprecision(2) << fixed << t;
    return 0;
}

#include <iostream>

#include <iomanip>

using namespace std;

int main() {

double t1, t2, t3;

cin >> t1 >> t2 >> t3;

double t = 1 / (1 / t1 + 1 / t2 + 1 / t3) ;

cout << setprecision(2) << fixed << t;

return 0;

}

Первый толстяк ест со скоростью один торт за $t_1$ часов. Аналогично и с остальными толстяками. Тогда из торта следует вычесть те части, которые съест каждый, чтобы торта не осталось. Получается уравнение
$1-\frac{t}{t_1}-\frac{t}{t_2}-\frac{t}{t_3}=0;$
$\frac{t}{t_1}+\frac{t}{t_2}+\frac{t}{t_3}=1;$
$\frac{tt_2t_3+tt_1t_3+tt_1t_2}{t_1t_2t_3}=1;$
$t\left(t_1t_2+t_2t_3+t_1t_3\right)=t_1t_2t_3;$
$t = \frac{t_1t_2t_3}{t_1t_2+t_2t_3+t_1t_3};$
Рассматриваем случай, при котором одна из переменных равна нулю, тогда выводим ноль. В противном случае выводим значение $t$ с округлением до сотых.

Так как по условию задачи первый толстяк съедает весь торт за $t_1$ часа, второй — за $t_2$ часа и третий — за $t_3$ часа, то их скорость поедания торта составит $\frac{1}{t_1}$, $\frac{1}{t_2}$ и $\frac{1}{t_3}$ торта в час соответсвенно. Если толстяки будут есть торт одновременно, то в час они будут съедать $\left(\frac{1}{t_1}+\frac{1}{t_2}+\frac{1}{t_3}\right)$ часть торта. Тогда весь торт будет съеден за $\frac{1}{\frac{1}{t_1}+\frac{1}{t_2}+\frac{1}{t_3}}$ часов.
Затем нужно вывести результат, округлённый до двух десятичных знаков. Для этого воспользуемся функцией setprecision() и её аргументом fixed

cout << setprecision(2) << fixed << t;

1	cout << setprecision(2) << fixed << t;

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

19/11/2017 by Александр Волынец

Выдающийся ямайский спринтер Усейн Болд выиграл на Олимпиаде-2012 две золотые медали на дистанциях 100 и 200 метров.

Эти обе дистанции нам интересны тем, что могут при определённом научном подходе, предоставлять тренеру информацию в определении оптимального состава сборной команды страны для эстафеты 4×100 метров.

Так как обе дистанции очень коротки, то тактика бега здесь довольно проста: сначала спортсмен за какое-то стартовое время (время разгона) разгоняется до своей максимально возможной на данный момент скорости, а оставшуюся часть дистанции бежит с этой постоянной скоростью, которую назовём крейсерской скоростью. Естественно, что при формировании команды в эстафету нужно на старт ставить спортсмена, который на этой дистанции показывает наилучшее время, а на 3 оставшихся этапа отбирать из числа оставшихся спортсменов трёх с наилучшей крейсерской скоростью.

Тренер легкоатлетической сборной вашей страны поручил вам, как одному из лучших программистов, помочь ему с формированием состава сборной на эстафету. Для оказания оперативной помощи тренеру вам необходимо быстро решить следующую задачу: зная результаты спортсмена на дистанциях 100 и 200 метров, определить его крейсерскую скорость. Вам также известно, что крейсерская скорость и время разгона каждого из спортсменов на протяжении ваших исследований не изменялись.

В единственной строке задано 2 вещественных числа, разделённых единичным пробелом, соответственно результат спортсмена на дистанциях 100 и 200 метров.

В единственной строке выведите крейсерскую скорость спортсмена с точностью не менее 6-ти знаков после запятой.

Входные данные	Выходные данные
9.63 19.32	10.319917
12.49 21.30	11.350737
7.46 13.58	16.339869

#include <iostream>
using namespace std;
int main() {
    double a, b, s=100;
    cin>>a>>b;
    cout << fixed;
    cout << s/(b-a) << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

double a, b, s=100;

cin>>a>>b;

cout << fixed;

cout << s/(b-a) << endl;

return 0;

}

Для решения этой задачи мы воспользуемся формулами скорости при равноускоренном движении. Нам было дано время прохождения двух дистанций в 100 метров и 200 метров. Так как спортсмен разгоняется на дистанции 100 метров, то оставшиеся 100 метров из 200 он бежит с постоянной скоростью. Чтобы узнать время за которое он пробегает вторые 100 метров, мы вычитаем из второго значения времени первое. Дальше мы пользуемся формулой нахождения скорости по расстоянию и времени [latex]\frac{s}{t}[/latex]. Полученая скорость и будет крейсерской скоростью.

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

14/11/2017 by Андрей Святозар Чернецкий

Ученики 10-Б класса на осенние каникулы решили поехать на экскурсию в столицу. Зная количество мальчиков [latex]n[/latex] и девочек [latex]m[/latex], определить, сколько необходимо заказать комнат в отеле, в котором имеются комнаты на [latex]k[/latex] мест каждая, при условии что мальчиков и девочек поселять вместе запрещено.

В одной строке записаны три числа [latex]n[/latex], [latex]m[/latex], [latex]k[/latex] ([latex]n, m, k ≤ 100[/latex]).

Вывести одно число — количество комнат, которое необходимо забронировать в отеле.
Continue reading →

05/11/2017 by Бондаренко Кирилл

e-olimp 57. Бабочка-санитар

Школьники, идя из дому в школу или наоборот — со школы домой, любят кушать конфеты. Но, как всегда, это приятное дело иногда имеет неприятные последствия – детки часто выбрасывают обертки на школьном дворе.
Мурзик всегда следил за чистотой школьного двора и ему в этом с радостью помогали бабочки, благодарные за прекрасные фотографии, сделанные им. Бабочки могли использовать собственные крылышки как линзы, причем они могли изменять их фокусное расстояние. Заметив обертку от конфетки, лежавшую на школьном дворе в точке с координатами [latex]X_1[/latex], [latex]Y_1[/latex], бабочка перелетала в точку с координатами [latex]X_2[/latex], [latex]Y_2[/latex], [latex]Z_2[/latex], расположенную на пути солнечных лучей к обертке и, изменяя фокусное расстояние своих крылышек-линз, сжигали обертку от конфеты.
Какую оптическую силу [latex]D[/latex] имели крылышки-линзы бабочки в этот момент? Continue reading →

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

Обобщённое условие задач на дерево отрезков, как правило, выглядит так:
«Пусть дан моноид [latex]\left(\mathbb{G}, \circ\right)[/latex], где [latex]\mathbb{G}[/latex] — некоторое непустое множество, [latex]\circ[/latex] — ассоциативная бинарная алгебраическая операция на этом множестве, имеющая нейтральный элемент, [latex]A[/latex] — последовательность (массив) элементов из [latex]\mathbb{G}[/latex], содержащая [latex]n[/latex] элементов ([latex]n \in \mathbb{N}[/latex]; с математической точки зрения [latex]A[/latex] — вектор, построенный из элементов [latex]\mathbb{G}[/latex], или [latex]А = \left( x_{0}, x_{1}, \ldots, x_{n-1} \right) \in \mathbb{G}^{n}[/latex]).
Даётся [latex]m[/latex] ([latex]m \in \mathbb{N}[/latex]) запросов двух типов:
1) вычислить значение выражения [latex]x_{i} \circ x_{i+1} \circ \ldots \circ x_{j-1} \circ x_{j}[/latex] с заданными [latex]i[/latex], [latex]j[/latex] ([latex]0 \le i \le j \le n-1[/latex], [latex]i, j \in \mathbb{N} \cup \{ 0 \}[/latex]) и вывести его;
2) заменить значение элемента с индексом [latex]k[/latex] на [latex]y[/latex] ([latex]k \in \mathbb{N} \cup \{ 0 \}[/latex], [latex]k \le n-1[/latex], [latex]y \in \mathbb{G}[/latex]).»

Как правило, человек, впервые увидевший задачу подобного рода, решает её следующим образом: для запросов первого типа (далее — запросы значения на отрезке [latex]\left[i, j\right][/latex]) создаётся вспомогательная переменная, изначально равная нейтральному элементу моноида (к примеру, если [latex]\left( \mathbb{G}, \circ \right) = \left( \mathbb{Z}, + \right)[/latex] то нейтральным элементом относительно [latex]+[/latex] является [latex]0[/latex]), и запускается цикл на заданном отрезке, который «прибавляет» к ней новые «слагаемые», а обработка запросов из пункта 2 реализуется через простое присваивание элементу массива с заданным индексом [latex]i[/latex] значения [latex]y[/latex]. Таким образом вычислительная сложность запросов замены составляет [latex]O\left(1\right)[/latex], а запросов поиска значения на отрезке [latex]\left[i, j\right][/latex] в лучшем случае составляет [latex]O\left(1\right)[/latex], когда [latex]i = j[/latex], а в худшем [latex]O\left(n\right)[/latex], когда [latex]i = 0[/latex], [latex]j = n-1[/latex].

Дерево отрезков — структура данных, которая позволяет сбалансировать операции замены и вычисления значения на заданном отрезке до вычислительной сложности [latex]O\left(\log_{2}{n}\right)[/latex] и значительно улучшить общую сложность программы с [latex]O\left(n+n\cdot m\right) = O\left(n\cdot m\right)[/latex] до [latex]O\left(n+m\cdot\log_{2}{n}\right)[/latex].

Определение: массив/последовательность элементов/вектор, над которым построено дерево отрезков, называется базой дерева или просто базой, а число её элементов — её размерностью.

Написать класс «дерево отрезков», применимый к любой задаче на моноиде, в которой присутствуют запросы замены элемента и результата операции на отрезке,
и таблицу его базовых функций и параметров.

#include <iostream>
using namespace std;

template <class TYPE> class segments_tree
{
    TYPE *SegmentTree;
    size_t base_capacity = 0;
    TYPE (*g)(TYPE, TYPE);
    TYPE neutral;

    /*
    TYPE:
        Type of elements in the tree.

    SegmentTree: (pointer)
        Array-based tree of elements.

    base_capacity: (unsigned integer value)
        Parental array size, rounded to the closest upper power of 2.

    g: (pointer)
        Pointer to the funtion (associative binary operation), applied on the given array of elements.
        WARNING: The given function must be associative. The monoidal structure of the tree will be ruined otherwise.

    neutral: (array element)
        The value of element, which is neutral relatively to "g" function.

    ################################
    #### INNER HELPER FUNCTIONS ####
    ################################
    result_on_segment_in:
        returns value on segment [l, r];
    */
    TYPE result_on_segment_in
    (
        size_t v, size_t tl,
        size_t tr, size_t l,
        size_t r
    )
    {
        if (l > r) return neutral;
        else if (l == tl && r == tr) return SegmentTree[v];
        else
        {
            size_t tm = (tl + tr) / 2;
            return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)),
            result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r));
        }
    }

    /*
    make_monoid_and_fill_rest:
        - fills the unused space of array (which appears due to rounding of size of parental array)
        with neutral elements.
        - assigns the necessary values to the upper "vertexes" of the tree.
    */
    void make_monoid_and_fill_rest(TYPE *NewTree, const size_t &n, TYPE f(TYPE, TYPE), const TYPE &neutr)
    {
        g = f;
        neutral = neutr;
        for(size_t i = base_capacity+n; i < 2*base_capacity; ++i)
        {
            NewTree[i] = neutral;
        }
        for(size_t i = base_capacity-1; i > 0; --i)
        {
            NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]);
        }
        SegmentTree = NewTree;
    }

    /*
    fix_capacity:
        Rounds base_capacity of the base array to closest upper power of 2.
    */
    void fix_capacity(const size_t &base_array_size)
    {
        for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1);
    }

    public:
    /*
    ##########################
    #### PUBLIC FUNCTIONS ####
    ##########################
    Definitions:
        n - amount of elements in the parental array;
        lb - binary logarithm.
        Lowest level of the tree - parental array (segment of elements, which is a base of the tree)
        and (if exists) unused space, filled with neutral elements.
    
    
    construct:
        Constructs the tree by copying elements of [begin; end) memory block into the segment tree,
        and by building tree's structure using the given binary operation "f" and its neutral element "neutr".
        Complexity: O(n).
    */
    void construct(const TYPE *begin, const TYPE *end, TYPE f(TYPE, TYPE), const TYPE neutr)
    {
        size_t base_size = end - begin;
        fix_capacity(base_size);
        TYPE *NewTree = new TYPE[base_capacity*2];
        for(size_t i = 0; i < base_size; ++i)
        {
            NewTree[base_capacity+i] = begin[i];
        }
        make_monoid_and_fill_rest(NewTree, base_size, f, neutr);
    }

    /*
    read_and_construct:
        Constructs the tree by filling with it with elements, created by "preprocessing_function",
        and by building tree's structure using the given binary operation "f" and its neutral element "neutr".
        This method is useful for creating tree by giving preprocessing_function an ability to read
        the data from the incoming stream, if the separate memorisation of the base array is not needed.
        Complexity: O(n).
    */
    void read_and_construct(const size_t amount_of_elements, TYPE preprocessing_function(), TYPE f(TYPE, TYPE), const TYPE neutr)
    {
        fix_capacity(amount_of_elements);
        TYPE *NewTree = new TYPE[base_capacity*2];
        for(size_t i = 0; i < amount_of_elements; ++i)
        {
            NewTree[base_capacity+i] = preprocessing_function();
        }
        make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr);
    }

    /*
    assign:
        Assigns new value to the element of base array with given index.
        Complexity: O(lb(n))
    */
    void assign(const size_t index, const TYPE new_value)
    {
        SegmentTree[base_capacity+index] = new_value;
        for (size_t i = (base_capacity+index)/2; i > 0; i /= 2)
        {
            SegmentTree[i] = g(SegmentTree[2*i], SegmentTree[2*i+1]);
        }
    }

    /*
    result_on_segment:
        Returns value of operation on the given segment of parental array.
        Complexity: O(lb(n)).
    */
    TYPE result_on_segment (size_t l, size_t r)
    {
        return result_on_segment_in(1, 0, base_capacity-1, l, r);
    }
};

int sum(int a, int b)
{
    return a+b;
}

int main()
{
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

#include <iostream>

using namespace std;

template <class TYPE> class segments_tree

{

TYPE *SegmentTree;

size_t base_capacity = 0;

TYPE (*g)(TYPE, TYPE);

TYPE neutral;

TYPE:

Type of elements in the tree.

SegmentTree: (pointer)

Array-based tree of elements.

base_capacity: (unsigned integer value)

Parental array size, rounded to the closest upper power of 2.

g: (pointer)

Pointer to the funtion (associative binary operation), applied on the given array of elements.

WARNING: The given function must be associative. The monoidal structure of the tree will be ruined otherwise.

neutral: (array element)

The value of element, which is neutral relatively to "g" function.

################################

#### INNER HELPER FUNCTIONS ####

################################

result_on_segment_in:

returns value on segment [l, r];

TYPE result_on_segment_in

(

size_t v, size_t tl,

size_t tr, size_t l,

size_t r

)

{

if (l > r) return neutral;

else if (l == tl && r == tr) return SegmentTree[v];

else

{

size_t tm = (tl + tr) / 2;

return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)),

result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r));

}

make_monoid_and_fill_rest:

- fills the unused space of array (which appears due to rounding of size of parental array)

with neutral elements.

- assigns the necessary values to the upper "vertexes" of the tree.

void make_monoid_and_fill_rest(TYPE *NewTree, const size_t &n, TYPE f(TYPE, TYPE), const TYPE &neutr)

{

g = f;

neutral = neutr;

for(size_t i = base_capacity+n; i < 2*base_capacity; ++i)

{

NewTree[i] = neutral;

}

for(size_t i = base_capacity-1; i > 0; --i)

{

NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]);

}

SegmentTree = NewTree;

}

fix_capacity:

Rounds base_capacity of the base array to closest upper power of 2.

void fix_capacity(const size_t &base_array_size)

{

for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1);

}

public:

##########################

#### PUBLIC FUNCTIONS ####

##########################

Definitions:

n - amount of elements in the parental array;

lb - binary logarithm.

Lowest level of the tree - parental array (segment of elements, which is a base of the tree)

and (if exists) unused space, filled with neutral elements.

construct:

Constructs the tree by copying elements of [begin; end) memory block into the segment tree,

and by building tree's structure using the given binary operation "f" and its neutral element "neutr".

Complexity: O(n).

void construct(const TYPE *begin, const TYPE *end, TYPE f(TYPE, TYPE), const TYPE neutr)

{

size_t base_size = end - begin;

fix_capacity(base_size);

TYPE *NewTree = new TYPE[base_capacity*2];

for(size_t i = 0; i < base_size; ++i)

{

NewTree[base_capacity+i] = begin[i];

}

make_monoid_and_fill_rest(NewTree, base_size, f, neutr);

}

read_and_construct:

Constructs the tree by filling with it with elements, created by "preprocessing_function",

and by building tree's structure using the given binary operation "f" and its neutral element "neutr".

This method is useful for creating tree by giving preprocessing_function an ability to read

the data from the incoming stream, if the separate memorisation of the base array is not needed.

Complexity: O(n).

void read_and_construct(const size_t amount_of_elements, TYPE preprocessing_function(), TYPE f(TYPE, TYPE), const TYPE neutr)

{

fix_capacity(amount_of_elements);

TYPE *NewTree = new TYPE[base_capacity*2];

for(size_t i = 0; i < amount_of_elements; ++i)

{

NewTree[base_capacity+i] = preprocessing_function();

}

make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr);

}

assign:

Assigns new value to the element of base array with given index.

Complexity: O(lb(n))

void assign(const size_t index, const TYPE new_value)

{

SegmentTree[base_capacity+index] = new_value;

for (size_t i = (base_capacity+index)/2; i > 0; i /= 2)

{

SegmentTree[i] = g(SegmentTree[2*i], SegmentTree[2*i+1]);

}

result_on_segment:

Returns value of operation on the given segment of parental array.

Complexity: O(lb(n)).

TYPE result_on_segment (size_t l, size_t r)

{

return result_on_segment_in(1, 0, base_capacity-1, l, r);

}

};

int sum(int a, int b)

{

return a+b;

}

int main()

{

return 0;

}

Далее [latex]n[/latex] — размерность базы дерева.

Название объекта	Описание
Параметр
TYPE	Тип объектов дерева, над которыми будут проводится вычисления.
Внутренние объекты
SegmentTree	Массив, хранящий в себе дерево отрезков.
base_capacity	Переменная, хранящая округлённую к ближайшей большей степени двойки размерность базы дерева отрезков.
g	Указатель на функцию, которая представляет из себя ассоциативную бинарную операцию. Формально определяется как функция/операция.
neutral	Нейтральный элемент относительно бинарной операции g.
Методы класса
construct	Аргументы: Адрес начала полуинтервала [latex]a[/latex]; Адрес конца полуинтервала [latex]b[/latex]; Ассоциативная бинарная операция f; Нейтральный элемент относительно f. Генерирует базу на основе полуинтервала [latex]\left[a; b\right)[/latex], копируя его элементы внутрь дерева, и строит на основе этой базы дерево отрезков. Вычислительная сложность: [latex]O\left(n\right)[/latex].
read_and_construct	Аргументы: Размер базы дерева; Функция-препроцессор; Ассоциативная бинарная операция f; Нейтральный элемент относительно f. Генерирует базу на основе элементов, возвращаемых функцией-препроцессором, и строит на их основе дерево отрезков. Вычислительная сложность: [latex]O\left(n\right)[/latex].
assign	Аргументы: Индекс элемента; Новое значение элемента. Заменяет значение элемента с заданным индексом на новое. Вычислительная сложность: [latex]O\left(\log_{2}{n}\right)[/latex].
result_on_segment	Аргументы: Индекс левого конца отрезка; Индекс правого конца отрезка. Возвращает результат функции на заданном отрезке. Вычислительная сложность: [latex]O\left(\log_{2}{n}\right)[/latex].

Прежде всего, код универсального дерева отрезков необходимо скопировать в исходную программу.

Построение:

Создать тип объектов (структуру данных), который будет использоваться в дереве для вычислений; (в зависимости от задачи. Вполне может быть, что необходимый для решения задачи класс уже создан. Например — int или double.)
Инициализировать дерево отрезков, передав классу segments_tree в качестве параметра тип объектов, над которыми будут проводиться вычисления, и задав дереву имя. (инициализация класса segments_tree происходит аналогично инициализации класса vector)
Построить дерево отрезков на основе заданных элементов при помощи метода construct или read_and_construct, передав методу соответствующие параметры (упомянутые в таблице выше);

Далее для вычисления результатов на отрезках и модификаций элементов с заданным индексом использовать методы result_on_segment и assign соответственно.

Примечание: условие и альтернативное решение приведённой ниже задачи находится по этой ссылке.

Так как в задаче необходимо выводить знак или произведения на заданных отрезках (либо нуль), то очевидно, что сами числа не интересуют нас. Тогда каждое из них можно представить в виде пары (zero, plus)[latex]= \left(a, b\right) \in \mathbb{B}^{2}[/latex] (где [latex]\mathbb{B}[/latex] — булево множество), где первый элемент пар [latex]a[/latex] будет характеризовать равенство числа нулю, а [latex]b[/latex] — его положительность. Назовём структуру данных пар такого типа number_sign. Функция make_number_sign будет преобразовывать числа типа short в number_sign. Затем определим для этой структуры функцию умножения prod формулой prod(number_sign a, number_sign b)[latex]=[/latex] (a.zero|b.zero, !(a.plus^b.plus));. В первой части формулы используется дизъюнкция, так как произведение нуля и произвольного числа всегда должно возвращать нуль, а во второй части — эквиваленция, так как результат произведения является отрицательным, если оба аргумента различны по знаку.

Затем, предварительно считав размер базы, конструируем дерево отрезков методом read_and_construct, передавая ему число элементов базы, анонимную функцию-препроцессор, которая считывает элементы базы из входного потока и которая преобразует их в тип данных number_sign, функцию произведения prod и её нейтральный элемент number_sign(), являющийся парой [latex]\left(0, 1\right)[/latex], который по сути представляет из себя число [latex]+1[/latex] (нейтральный элемент умножения).

Остальная часть решения требует только замены старых элементов новыми и вычислений результатов на отрезках, для чего есть готовые методы класса.

#include <iostream>
using namespace std;

// . . . . . . . . . . . . . . . . . . . .
// . . . . segments_tree class . . . . . .
// . . . . . . . . . . . . . . . . . . . .

struct number_sign
{
    bool zero, plus;
    number_sign()
    {
        zero = 0;
        plus = 1;
    }
    number_sign(bool a, bool b)
    {
        zero = a;
        plus = b;
    }
};

number_sign make_number_sign(const short &X)
{
    return number_sign(X == 0, X > 0);
}

number_sign prod(number_sign a, number_sign b)
{
    return number_sign(a.zero|b.zero, !(a.plus^b.plus));
}

char sign(const number_sign d)
{
    if (d.zero) return '0';
    else if (d.plus) return '+';
    else return '-';
}

int main()
{
    unsigned int i, j, m;
    char q;
    short X;
    
    segments_tree <number_sign> A;
    number_sign *B, neutr;
    while (cin >> i)
    {
        scanf("%u", &m);
        A.read_and_construct(i, [] () {short X; scanf("%hd", &X); return make_number_sign(X);}, prod, number_sign());
        scanf("\n");
        ++m;
        while (--m)
        {
            scanf("%c%u", &q, &i);
            if (q == 'P')
            {
                scanf("%u", &j);
                printf("%c", sign(A.result_on_segment(i-1, j-1)));
            }
            else
            {
                scanf("%hd", &X);
                A.assign(i-1, make_number_sign(X));
            }
            scanf("\n");
        }
        printf("\n");
    }
    return 0;
}

#include <iostream>

using namespace std;

// . . . . . . . . . . . . . . . . . . . .

// . . . . segments_tree class . . . . . .

// . . . . . . . . . . . . . . . . . . . .

struct number_sign

{

bool zero, plus;

number_sign()

{

zero = 0;

plus = 1;

}

number_sign(bool a, bool b)

{

zero = a;

plus = b;

}

};

number_sign make_number_sign(const short &X)

{

return number_sign(X == 0, X > 0);

}

number_sign prod(number_sign a, number_sign b)

{

return number_sign(a.zero|b.zero, !(a.plus^b.plus));

}

char sign(const number_sign d)

{

if (d.zero) return '0';

else if (d.plus) return '+';

else return '-';

}

int main()

{

unsigned int i, j, m;

char q;

short X;

segments_tree <number_sign> A;

number_sign *B, neutr;

while (cin >> i)

{

scanf("%u", &m);

A.read_and_construct(i, [] () {short X; scanf("%hd", &X); return make_number_sign(X);}, prod, number_sign());

scanf("\n");

++m;

while (--m)

{

scanf("%c%u", &q, &i);

if (q == 'P')

{

scanf("%u", &j);

printf("%c", sign(A.result_on_segment(i-1, j-1)));

}

else

{

scanf("%hd", &X);

A.assign(i-1, make_number_sign(X));

}

scanf("\n");

}

printf("\n");

}

return 0;

}

Дополнить класс «дерево отрезков» из первой задачи таким образом, чтобы для базы дерева были реализованы:

параметры «вместимость» и «размер»;
функции добавления нового элемента в базу;
функции, возвращающие размер базы и вместимость дерева;
функция изменения размера базы.

Написать таблицу новых функций и параметров.

#include <iostream>
using namespace std;

template <class TYPE> class segments_tree
{
    TYPE *SegmentTree;
    size_t base_capacity = 0;
    TYPE (*g)(TYPE, TYPE);
    TYPE neutral;

    /*
    TYPE:
        Type of elements in the tree.

    SegmentTree: (pointer)
        Array-based tree of elements.

    base_capacity: (unsigned integer value)
        Parental array size, rounded to the closest upper power of 2.

    g: (pointer)
        Pointer to the funtion (associative binary operation), applied on the given array of elements.
        WARNING: The given function must be associative. The monoidal structure of the tree will be ruined otherwise.

    neutral: (array element)
        The value of element, which is neutral relatively to "g" function.

    ################################
    #### INNER HELPER FUNCTIONS ####
    ################################
    result_on_segment_in:
        returns value on segment [l, r];
    */
    TYPE result_on_segment_in
    (
        size_t v, size_t tl,
        size_t tr, size_t l,
        size_t r
    )
    {
        if (l > r) return neutral;
        else if (l == tl && r == tr) return SegmentTree[v];
        else
        {
            size_t tm = (tl + tr) / 2;
            return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)),
            result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r));
        }
    }

    /*
    make_monoid_and_fill_rest:
        - fills the unused space of array (which appears due to rounding of size of parental array)
        with neutral elements.
        - assigns the necessary values to the upper "vertexes" of the tree.
    */
    void make_monoid_and_fill_rest(TYPE *NewTree, const size_t &n, TYPE f(TYPE, TYPE), const TYPE &neutr)
    {
        g = f;
        neutral = neutr;
        for(size_t i = base_capacity+n; i < 2*base_capacity; ++i)
        {
            NewTree[i] = neutral;
        }
        for(size_t i = base_capacity-1; i > 0; --i)
        {
            NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]);
        }
        SegmentTree = NewTree;
    }

    /*
    fix_capacity:
        Rounds base_capacity of the base array to closest upper power of 2.
    */
    void fix_capacity(const size_t &base_array_size)
    {
        for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1);
    }

    public:
    /*
    ##########################
    #### PUBLIC FUNCTIONS ####
    ##########################
    Definitions:
        n - amount of elements in the parental array;
        lb - binary logarithm.
        Lowest level of the tree - parental array (segment of elements, which is a base of the tree)
        and (if exists) unused space, filled with neutral elements.
    
    
    construct:
        Constructs the tree by copying elements of [begin; end) memory block into the segment tree,
        and by building tree's structure using the given binary operation "f" and its neutral element "neutr".
        Complexity: O(n).
    */
    void construct(const TYPE *begin, const TYPE *end, TYPE f(TYPE, TYPE), const TYPE neutr)
    {
        size_t base_size = end - begin;
        fix_capacity(base_size);
        TYPE *NewTree = new TYPE[base_capacity*2];
        for(size_t i = 0; i < base_size; ++i)
        {
            NewTree[base_capacity+i] = begin[i];
        }
        make_monoid_and_fill_rest(NewTree, base_size, f, neutr);
    }

    /*
    read_and_construct:
        Constructs the tree by filling with it with elements, created by "preprocessing_function",
        and by building tree's structure using the given binary operation "f" and its neutral element "neutr".
        This method is useful for creating tree by giving preprocessing_function an ability to read
        the data from the incoming stream, if the separate memorisation of the base array is not needed.
        Complexity: O(n).
    */
    void read_and_construct(const size_t amount_of_elements, TYPE preprocessing_function(), TYPE f(TYPE, TYPE), const TYPE neutr)
    {
        fix_capacity(amount_of_elements);
        TYPE *NewTree = new TYPE[base_capacity*2];
        for(size_t i = 0; i < amount_of_elements; ++i)
        {
            NewTree[base_capacity+i] = preprocessing_function();
        }
        make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr);
    }

    /*
    assign:
        Assigns new value to the element of base array with given index.
        Complexity: O(lb(n))
    */
    void assign(const size_t index, const TYPE new_value)
    {
        SegmentTree[base_capacity+index] = new_value;
        for (size_t i = (base_capacity+index)/2; i > 0; i /= 2)
        {
            SegmentTree[i] = g(SegmentTree[2*i], SegmentTree[2*i+1]);
        }
    }

    /*
    result_on_segment:
        Returns value of operation on the given segment of parental array.
        Complexity: O(lb(n)).
    */
    TYPE result_on_segment (size_t l, size_t r)
    {
        return result_on_segment_in(1, 0, base_capacity-1, l, r);
    }
};

int main()
{
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

#include <iostream>

using namespace std;

template <class TYPE> class segments_tree

{

TYPE *SegmentTree;

size_t base_capacity = 0;

TYPE (*g)(TYPE, TYPE);

TYPE neutral;

TYPE:

Type of elements in the tree.

SegmentTree: (pointer)

Array-based tree of elements.

base_capacity: (unsigned integer value)

Parental array size, rounded to the closest upper power of 2.

g: (pointer)

Pointer to the funtion (associative binary operation), applied on the given array of elements.

WARNING: The given function must be associative. The monoidal structure of the tree will be ruined otherwise.

neutral: (array element)

The value of element, which is neutral relatively to "g" function.

################################

#### INNER HELPER FUNCTIONS ####

################################

result_on_segment_in:

returns value on segment [l, r];

TYPE result_on_segment_in

(

size_t v, size_t tl,

size_t tr, size_t l,

size_t r

)

{

if (l > r) return neutral;

else if (l == tl && r == tr) return SegmentTree[v];

else

{

size_t tm = (tl + tr) / 2;

return g(result_on_segment_in(v*2, tl, tm, l, min(r,tm)),

result_on_segment_in(v*2+1, tm+1, tr, max(l,tm+1), r));

}

make_monoid_and_fill_rest:

- fills the unused space of array (which appears due to rounding of size of parental array)

with neutral elements.

- assigns the necessary values to the upper "vertexes" of the tree.

void make_monoid_and_fill_rest(TYPE *NewTree, const size_t &n, TYPE f(TYPE, TYPE), const TYPE &neutr)

{

g = f;

neutral = neutr;

for(size_t i = base_capacity+n; i < 2*base_capacity; ++i)

{

NewTree[i] = neutral;

}

for(size_t i = base_capacity-1; i > 0; --i)

{

NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]);

}

SegmentTree = NewTree;

}

fix_capacity:

Rounds base_capacity of the base array to closest upper power of 2.

void fix_capacity(const size_t &base_array_size)

{

for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1);

}

public:

##########################

#### PUBLIC FUNCTIONS ####

##########################

Definitions:

n - amount of elements in the parental array;

lb - binary logarithm.

Lowest level of the tree - parental array (segment of elements, which is a base of the tree)

and (if exists) unused space, filled with neutral elements.

construct:

Constructs the tree by copying elements of [begin; end) memory block into the segment tree,

and by building tree's structure using the given binary operation "f" and its neutral element "neutr".

Complexity: O(n).

void construct(const TYPE *begin, const TYPE *end, TYPE f(TYPE, TYPE), const TYPE neutr)

{

size_t base_size = end - begin;

fix_capacity(base_size);

TYPE *NewTree = new TYPE[base_capacity*2];

for(size_t i = 0; i < base_size; ++i)

{

NewTree[base_capacity+i] = begin[i];

}

make_monoid_and_fill_rest(NewTree, base_size, f, neutr);

}

read_and_construct:

Constructs the tree by filling with it with elements, created by "preprocessing_function",

and by building tree's structure using the given binary operation "f" and its neutral element "neutr".

This method is useful for creating tree by giving preprocessing_function an ability to read

the data from the incoming stream, if the separate memorisation of the base array is not needed.

Complexity: O(n).

void read_and_construct(const size_t amount_of_elements, TYPE preprocessing_function(), TYPE f(TYPE, TYPE), const TYPE neutr)

{

fix_capacity(amount_of_elements);

TYPE *NewTree = new TYPE[base_capacity*2];

for(size_t i = 0; i < amount_of_elements; ++i)

{

NewTree[base_capacity+i] = preprocessing_function();

}

make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr);

}

assign:

Assigns new value to the element of base array with given index.

Complexity: O(lb(n))

void assign(const size_t index, const TYPE new_value)

{

SegmentTree[base_capacity+index] = new_value;

for (size_t i = (base_capacity+index)/2; i > 0; i /= 2)

{

SegmentTree[i] = g(SegmentTree[2*i], SegmentTree[2*i+1]);

}

result_on_segment:

Returns value of operation on the given segment of parental array.

Complexity: O(lb(n)).

TYPE result_on_segment (size_t l, size_t r)

{

return result_on_segment_in(1, 0, base_capacity-1, l, r);

}

};

int main()

{

return 0;

}

Название объекта	Описание
Новый внутренний объект
base_size	Переменная, хранящая размерность базы дерева отрезков.
Новые методы класса
begin	Аргументы: отсутствуют. Возвращает адрес начала базы. Вычислительная сложность: константа.
end	Аргументы: отсутствуют. Возвращает адрес конца базы. Вычислительная сложность: константа.
push_back	Аргумент: значение нового элемента базы. Добавляет новый элемент в конец базы. Вычислительная сложность: если база заполнена, то [latex]O\left(n\right)[/latex], иначе — [latex]O\left(\log_{2}{n}\right)[/latex].
pop_back	Аргументы: отсутствуют. Удаляет элемент в конце базы. Вычислительная сложность: [latex]O\left(\log_{2}{n}\right)[/latex].
insert	Аргументы: Индекс нового элемента; Значение нового элемента. Добавляет на заданную позицию базы новый элемент с заданным значением. Вычислительная сложность: [latex]O\left(n\right)[/latex].
erase	Аргумент: индекс удаляемого элемента. Удаляет из базы элемент с заданным индексом. Вычислительная сложность: [latex]O\left(n\right)[/latex].
size	Аргументы: отсутствуют. Возвращает размерность базы дерева. Вычислительная сложность: константа.
capacity	Аргументы: отсутствуют. Возвращает размерность базы дерева, округлённую к ближайшей большей степени двойки. Позволяет оценить число неиспользованных ячеек, на которые уже выделена память. Вычислительная сложность: константа.
resize	Аргумент: новый размер базы. Изменяет размер базы дерева, и преобразовывает незадействованные элементы в нейтральные Вычислительная сложность: [latex]O\left(n\right)[/latex], если новый размер базы превысил вместимость дерева или является меньше, чем старый, и константа в противном случае.

Код универсального дерева отрезков;
Код универсального дерева отрезков (дополнение функциями вектора);
Код универсального дерева отрезков (множественная модификация);
Статья о дереве отрезков на e-maxx.ru, за которую выражаю unsigned long long int (то есть очень большую 🙂 ) благодарность её автору.

14/10/2016 by Иванна Ялымова

Задача
Задача из журнала «Квант» №3, 1974 год (Задача составлена на основе задачи Гуревича)

Рассмотрим последовательности, состоящие из [latex]n[/latex] цифр 1 и 2. В такой последовательности разрешено поменять местами любые две соседние тройки цифр. Две последовательности называем эквивалентными, если одну из них можно перевести в другую несколькими такими перестановками. Сколько существует классов эквивалентности?

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

[latex]n[/latex] — целове число, [latex]k[/latex] — целое число ([latex]k \neq 0[/latex], [latex]k \leq n[/latex]).

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

[latex]m[/latex] — целое число, неполное частное от деления, [latex]q[/latex] — целое число, остаток от деления, [latex]N[/latex] — классы эквивалентности.

Тесты

[latex]n[/latex]	[latex]k[/latex]	[latex]m[/latex]	[latex]q[/latex]	[latex]N[/latex]
4	3	1	1	12
8	4	2	0	81

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

Код программы на С++

#include <iostream>
using namespace std;
long pow (long x, int n) {
    return (n == 0) ? 1 :
    (n % 2 == 0) ? pow(x*x, n/2) :
    pow(x, n-1)*x;
}
int main() {
    int n, m, k, q, N;
    cin >> n >> k;
    m=n/k;
    q=n%k;
    N=pow((m+1),k-q)*pow((m+2),q);
    cout << m << " " << q << " " << N << endl;
    return 0;
}

#include <iostream>

using namespace std;

long pow (long x, int n) {

return (n == 0) ? 1 :

(n % 2 == 0) ? pow(x*x, n/2) :

pow(x, n-1)*x;

}

int main() {

int n, m, k, q, N;

cin >> n >> k;

m=n/k;

q=n%k;

N=pow((m+1),k-q)*pow((m+2),q);

cout << m << " " << q << " " << N << endl;

return 0;

}

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

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

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        int n, k, q, m;
        double N;
        Scanner in = new Scanner(System.in);
            
        n = in.nextInt();
        k = in.nextInt();
        
        m = n/k;
        q = n%k;
        N = Math.pow((m+1),k-q) * Math.pow((m+2),q);
        
        System.out.println(q + " " + m + " " + N);
    }
    public static long pow(long x, int n) {
        return (n == 0) ? 1 :
        (n % 2 == 0) ? pow(x*x, n/2) :
        pow(x, n-1)*x;
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

int n, k, q, m;

double N;

Scanner in = new Scanner(System.in);

n = in.nextInt();

k = in.nextInt();

m = n/k;

q = n%k;

N = Math.pow((m+1),k-q) * Math.pow((m+2),q);

System.out.println(q + " " + m + " " + N);

}

public static long pow(long x, int n) {

return (n == 0) ? 1 :

(n % 2 == 0) ? pow(x*x, n/2) :

pow(x, n-1)*x;

}

Решение

Решим задачу для последовательностей из [latex]3n[/latex] цифр. Чтобы не возникло путаницы, греческими буквами будем обозначать последовательности, а латинскими – элементы последовательностей. Пусть последовательность [latex]\alpha[/latex] состоит из [latex]3n[/latex] цифр [latex]{\alpha_1, \alpha_2,\ldots,\alpha_{3n}}[/latex]. Разобъем [latex]\alpha[/latex] на три подпоследовательности:
[latex]\alpha_1={\alpha_1,\alpha_4,\alpha_7,\ldots, \alpha_{3k+1},\ldots,\alpha_{3(n-1)+1}}[/latex],
[latex]\alpha_2={\alpha_2, \alpha_5, \alpha_8,\ldots, \alpha_{3k+2},\ldots,\alpha_{3(n-1)+2}}[/latex],
[latex]\alpha_3={\alpha_3, \alpha_6, \alpha_9,\ldots, \alpha_{3k},\ldots,\alpha_{3n}}[/latex].
Такое разбиение будем называть стандартным. Каждая из последовательностей [latex]\alpha_1[/latex], [latex]\alpha_2[/latex], [latex]\alpha_3[/latex] стандартного разбиения состоит из [latex]n[/latex] цифр. Пусть [latex]\beta[/latex] – произвольная последовательностей. Через [latex]|\beta|[/latex] обозначим число единиц в последовательности [latex]\beta[/latex]. Подсчет числа неэквивалентных последовательностей основывается на следующей теореме:
Теорема. Пусть [latex]\alpha[/latex] и [latex]\beta[/latex] – последовательности длины [latex]3n[/latex], ([latex]\alpha_1,\alpha_2,\alpha_3[/latex]) и ([latex]\beta_1,\beta_2,\beta_3[/latex]) – их стандартные разбиения. Для того чтобы последовательности [latex]\alpha[/latex] и [latex]\beta[/latex] были эквивалентны, необходимо и достаточно, чтобы подпоследовательности [latex]\alpha_1[/latex] и [latex]\beta_1[/latex], [latex]\alpha_2[/latex] и [latex]\beta_2[/latex], [latex]\alpha_3[/latex] и [latex]\beta_3[/latex] содержали одинаковое число единиц соответственно, то есть чтобы выполнялось условие
[latex]|\alpha_1|=|\beta_1|[/latex], [latex]|\alpha_2|=|\beta_2|[/latex], [latex]|\alpha_3|=|\beta_3|[/latex].
Покажем сначала, как на основе этой теоремы подсчитывается число неэквивалентных последовательностей, а затем докажем теорему. В силу теоремы каждый класс эквивалентных последовательностей однозначно определяются упорядоченной тройкой чисел ([latex]|\alpha_1|, |\alpha_2|, |\alpha_3|[/latex]). Эти числа смогут принимать любые значения от 0 до [latex]n[/latex]. Следовательно, число неэквивалентных последовательностей длины [latex]3n[/latex] равно числу различных упорядоченных троек целых чисел от 0 до [latex]n[/latex]. Нетрудно видеть, что число таких троек равно [latex] \left(n+1\right)^{3} [/latex].
Доказательство теоремы. Необходимость. Пусть мы переставили в последовательности [latex]\alpha={\alpha_1, \alpha_2,\ldots,\alpha_{3n}}[/latex] две соседние тройки цифр: [latex]a_k, a_{k+1}, a_{k+2}[/latex] и [latex]a_{k+3}, a_{k+4}, a_{k+5}[/latex]. Эту перестановку можно представить следующим образом: сначала поменяли местами цифры [latex]a_k[/latex] и [latex]a_{k+3}[/latex], затем поменяли местами цифры [latex]a_{k+1}[/latex] и [latex]a_{k+4}[/latex] и, наконец, поменяли местами цифры [latex]a_{k+2}[/latex] и [latex]a_{k+5}[/latex]. Число [latex]a_k[/latex] и [latex]a_{k+3}[/latex] – соседние цифры одной и той же подпоследовательности стандартного разбиения [latex]\alpha[/latex]; числа [latex]a_{k+1}[/latex] и [latex]a_{k+4}[/latex] – другой, а числа [latex]a_{k+2}[/latex] и [latex]a_{k+5}[/latex] – третьей. Таким образом, в каждой из подпоследоваетльностей [latex]\alpha_1, \alpha_2, \alpha_3[/latex] стандартного разбиения [latex]\alpha[/latex] мы пeреставили два соседних члена. Значит, если последовательность [latex]\beta[/latex] получена из последовательности [latex]\alpha[/latex] конечным числом перестановок, то есть, если последовательности [latex]\alpha[/latex] и [latex]\beta[/latex] эквивалентны, то подпоследовательности [latex]\beta_1, \beta_2, \beta_3[/latex] стандартного разбиения [latex]\beta[/latex] суть некоторые перестановки подпоследовательностей [latex]\alpha_1, \alpha_2, \alpha_3[/latex] соответственно. Отсюда вытекают равенства (1).
Достаточность. Нам надо доказать, что если последовательности [latex]\alpha[/latex] и [latex]\beta[/latex] длины [latex]3n[/latex] удовлетворяют условию (1), то эти последовательности эквиваленты. Удобнее доказывать более общее утверждение: если последовательности [latex]\alpha[/latex] и [latex]\beta[/latex] длины [latex]k[/latex] удовлетворяют условию (1), то эти последовательности эквивалентны. Доказательство будем вести индукцией по [latex]k[/latex].
1) При [latex]k=1[/latex] последовательности [latex]\alpha[/latex] и [latex]\beta[/latex] содержит по одной цифре. Из условия (1) следует, что эти цифры равны, то есть что последовательности [latex]\alpha[/latex] и [latex]\beta[/latex] просто совпадают.
2) Предположим, что в случае, когда [latex]k=p[/latex], утверждение уже доказано. Докажем его при [latex]k=p+1[/latex]. Итак, пусть [latex]\alpha[/latex] и [latex]\beta[/latex] – последовательности длины [latex]p+1[/latex] и пусть выполнено соотношение (1). Пусть далее, последовательность [latex]\alpha[/latex] состоит из цифр [latex]{\alpha_1, \alpha_2,\ldots,\alpha_{p+1}}[/latex], а последовательность [latex]\beta[/latex] — из цифр [latex]{\beta_1, \beta_2,\ldots,\beta_{p+1}}[/latex].
а) если [latex]\alpha_1 = \beta_1[/latex], то рассмотрим последовательности [latex]\alpha\prime={\alpha_2,\alpha_3,\ldots,\alpha_{p+1}}[/latex] и [latex]\beta\prime={\beta_2,\beta_3,\ldots,\beta_{p+1}}[/latex]. Ясно, что последовательности [latex]\alpha\prime[/latex] и [latex]\beta\prime[/latex] удовлетворяют условия (1). А так как длины этих последовательностей равны [latex]p[/latex], то можно воспользоваться индуктивным предположением. Таким образом, последовательности [latex]\alpha\prime[/latex] и [latex]\beta\prime[/latex] эквивалентны, то есть последовательность [latex]\alpha\prime[/latex] несколькими перестановками можно перевести в последовательность [latex]\beta\prime[/latex]. Эти же перестановки переводят [latex]\alpha[/latex] и [latex]\beta[/latex]. Значит, последовательности [latex]\alpha[/latex] и [latex]\beta[/latex] эквивалентны.
б) Пусть [latex]a_1\neq b_1[/latex], и пусть для определенности [latex]a_1=1[/latex], а [latex]b_1=2[/latex]. Так как [latex]a_1=1[/latex], то [latex]|\alpha|>0[/latex]. Тогда в силу (1) и [latex]|\beta|>0[/latex]. Следовательно, найдется число [latex]q[/latex] такое, что [latex]b_{3q+1} = 1[/latex]. В последовательности [latex]\beta[/latex] поменяем местами соседние тройки цифр [latex]b_{3(q-1)+1}, b_{3q+2}, b_{3q+3}[/latex] и [latex]b_{3(q-1)+1}, b_{3(q-1)+2}, b_{3(q-1)+3}[/latex]. В результате этой перестановки тройка [latex]b_{3(q-1)+1}, b_{3q+2}, b_{3q+3}[/latex] сдвигается на 3 цифры влево. Затем поменяем местами эту тройку с рядом стоящей тройкой цифр [latex]b_{3(q-2)+1}, b_{3(q-2)+2}, b_{3(q-2)+3}[/latex] и так далее; после [latex]q[/latex] перестановок получим последовательность [latex]\beta\prime\prime[/latex], первой цифрой которой будет [latex]b_{3q+1}[/latex], то есть 1. Последовательность [latex]\beta[/latex] и [latex]\beta\prime\prime[/latex] эквивалентны и поэтому, как было доказано выше, удовлетворяют условию (1). Значит, последовательности [latex]\alpha[/latex] и [latex]\beta\prime\prime[/latex] удовлетворяют условию (1). Но первые элементы этих последовательностей совпадают. Таким образом, случай б) свелся к уже разобранному случаю а). Теорема доказана.
Следовательно, если [latex]n=mk+q[/latex], где [latex]0<=q<k[/latex], то число классов эквивалентных последовательностей равно [latex] \left(m+1\right)^{k-q}\left(k+1\right)^{q} [/latex].

Ссылки

Условие задачи (стр.40-41)
Решение задачи на сайте Ideone.com (C++)
Решение задачи на сайте Ideone.com (Java)

30/09/2016 by Андреев Даниил

Самолёт летит из пункта в [latex]A[/latex] в пункт [latex]B[/latex] и обратно со скоростью [latex]V[/latex] км/час. Всё время дует ветер с постоянной скоростью [latex]U[/latex] км/час под углом [latex]\alpha[/latex] радиан к направлению движения (0 соответствует попутному ветру). Расстояние между пунктами составляет [latex]S[/latex] км. Для любых неотрицательных действительных значений угла, расстояния и скоростей вычислите время в пути.

[latex]V[/latex]-скорость самолета, [latex]U[/latex]-скорость ветра, [latex]S[/latex]-расстояние [latex]AB[/latex], [latex]\alpha[/latex]-угол направления ветра.

Время полета [latex]t[/latex] в часах.

Входные данные				Выходные данные
[latex]V[/latex]	[latex]U[/latex]	[latex]S[/latex]	[latex]\alpha[/latex]	[latex]t[/latex]
600	20	1200	1,5708	4.0013
600	20	1200	0	4.00445
600	20	1200	3,1415	4.00436
600	20	1200	1,0472	4.0013
600	20	1200	2,6179	4.00077
600	601	1200	0	inf
0	20	1200	0	inf

#include <iostream>
#include <cmath>
 
using namespace std;
 
int main()
{
    double V, U, S, a, t;
    
    cin >> V >> U >> S >> a;
    
    t=S/(V+cos(a)*U)+S/(V-cos(a)*U);//Сумма времени полета от A к B и обратно
    
    cout << (U>=V ? 1/tan(0) : t);

    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

double V, U, S, a, t;

cin >> V >> U >> S >> a;

t=S/(V+cos(a)*U)+S/(V-cos(a)*U);//Сумма времени полета от A к B и обратно

cout << (U>=V ? 1/tan(0) : t);

return 0;

}

Учитывая скорость ветра [latex]U[/latex] и угол [latex]\alpha[/latex] под которым ветер дует на самолет, на пути от [latex]A[/latex] к [latex]B[/latex] скорость самолета будет равна [latex]V+cos(\alpha)\cdot U[/latex] , а на обратном пути от [latex]B[/latex] к [latex]A[/latex] скорость самолета будет равна [latex]V-cos(\alpha)\cdot U[/latex].Общее время полета узнаем по формуле [latex]t =\frac{S}{V+cos(\alpha)\cdot U} +\frac{S}{V-cos(\alpha)\cdot U}[/latex].

Ideone

27/09/2016 by Валентина Андриеш

Задача. Катер движется по течению реки из пункта в A в пункт B и обратно с собственной скоростью [latex]v[/latex] км/час. Скорость течения постоянна — [latex]u[/latex] км/час. Расстояние между пунктами составляет [latex]s[/latex] км. Для любых неотрицательных действительных значений расстояния и скоростей вычислите время в пути.

Решение. Пусть катер движется со скоростью [latex]v[/latex] км/час, соответственно, учитывая скорость течения [latex]u[/latex] км/час, скорость катера движущегося по течению равна [latex]v+u[/latex] км/час и против течения — [latex]v-u[/latex] км/час. Используя физическую формулу [latex]t=\frac{s}{v}[/latex], где [latex]t[/latex]-время, [latex]s[/latex]-путь, [latex]v[/latex]-скорость, можем выразить время всего пути [latex]t=\frac{s}{v+u}+\frac{s}{v-u}[/latex]. Так как физическая величина [latex]t[/latex] всегда больше 0, и по математическому свойству делитель дроби не должен равняться нулю, имеем ограничение: [latex]v>u[/latex];

Решение на языке C++ имеет вид:

#include <iostream>
#include <limits> 
using namespace std; 
int main() 
{ 
    double u, v, s, t; 
    double inf = std::numeric_limits<double>::infinity(); 
    cin >> u >> v >> s;
    t = (v <= u) ? inf : s / ( v + u ) + s / ( v - u );
    cout << t; 
    return 0; 
}

#include <iostream>

#include <limits>

using namespace std;

int main()

{

double u, v, s, t;

double inf = std::numeric_limits<double>::infinity();

cin >> u >> v >> s;

t = (v <= u) ? inf : s / ( v + u ) + s / ( v - u );

cout << t;

return 0;

}

Тесты

Входные данные
Физические величины: v, u, s

Выходные данные
Физическая величина t

u	v	s	t
2	2	4	inf
1	2	6	8
5	4	8	inf

Решение на ideone.

26/09/2016 by Иванна Ялымова

Задача

Вычислить расстояние между двумя точками [latex]A\left(x_a,y_a,z_a\right)[/latex] и [latex]B\left(x_b,y_b,z_b\right)[/latex] по известным координатам.

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

Координаты: [latex]x_a, y_a, z_a, x_b, y_b, z_b[/latex].

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

[latex]|AB|[/latex] — расстояние между точками [latex]A[/latex] и [latex]B[/latex].

Тесты

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

Код программы на С++

#include <iostream>
#include <cmath>
using namespace std;

int main() {
    double xa, xb, ya, yb, za, zb;
    cin >> xa >> xb >> ya >> yb >> za >> zb;//вводим наши координаты
    double AB = sqrt((xb-xa)*(xb-xa)+(yb-ya)*(yb-ya)+(zb-za)*(zb-za));
    cout << AB;//выводим полученное расстояние
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double xa, xb, ya, yb, za, zb;

cin >> xa >> xb >> ya >> yb >> za >> zb;//вводим наши координаты

double AB = sqrt((xb-xa)*(xb-xa)+(yb-ya)*(yb-ya)+(zb-za)*(zb-za));

cout << AB;//выводим полученное расстояние

return 0;

}

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

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

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        double xa, ya, za, xb, yb, zb;
        Scanner in = new Scanner(System.in);
        
        xa = in.nextDouble();
        ya = in.nextDouble();
        za = in.nextDouble();
        xb = in.nextDouble();
        yb = in.nextDouble();
        zb = in.nextDouble();
        
        double AB = Math.sqrt((xb-xa)*(xb-xa)+(yb-ya)*(yb-ya)+(zb-za)*(zb-za));
        
        System.out.println(AB);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

double xa, ya, za, xb, yb, zb;

Scanner in = new Scanner(System.in);

xa = in.nextDouble();

ya = in.nextDouble();

za = in.nextDouble();

xb = in.nextDouble();

yb = in.nextDouble();

zb = in.nextDouble();

double AB = Math.sqrt((xb-xa)*(xb-xa)+(yb-ya)*(yb-ya)+(zb-za)*(zb-za));

System.out.println(AB);

}

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

Вычисляем [latex]|AB|[/latex] между точками [latex]A\left(x_a,y_a,z_a\right)[/latex] и [latex]B\left(x_b,y_b,z_b\right)[/latex] по такой формуле : [latex]|AB|=\sqrt{(x_b-x_a)^2+(y_b-y_a)^2+(z_b-z_a)^2}[/latex] и получаем результаты.

Ссылка: Условие задачи
Ссылка: Решение задачи на сайте Ideone.com (C++)
Ссылка: Решение задачи на сайте Ideone.com (Java)

22/09/2016 by Антон Куперман

21/09/2016 by Сытников Дан

Найти площадь полной поверхности параллелепипеда три стороны которого образованы векторами [latex] \overrightarrow{a}=(a_x,a_y,a_z), \overrightarrow{b}=(b_x,b_y,b_z) [/latex] и [latex]\overrightarrow{c}=(c_x,c_y,c_z)[/latex].

Координаты векторов [latex] \overrightarrow{a}, \overrightarrow{b}[/latex] и [latex] \overrightarrow{c} [/latex].

Площадь полной поверхности параллелепипеда.

Тесты

№	Входные данные	Выходные данные
1	-5.6 8.3 -7.1 2 11 -8 2.1 1 3.3	389.28894739406866
2	1 2 3 4 5 6 7 8 9	58.787753826796276
3	-9 2 4 -3 5 1 -6 7 8	305.5334243147188
4	1 1 1 1 1 1 1 1 1	0.0
5	0 0 1 0 1 0 1 0 0	6.0
6	0 0 0 1 0 0 0 0 1	2.0
7	1 0 0 0 0 1 0 0 1	2.0

#include <iostream>
#include <cmath>
#include <iomanip>
using namespace std;
double s1(double a1, double a2, double a3, double b1, double b2, double b3) //Создаем функцию для нахождения стороны параллелепипеда
{
    return sqrt((a2*b3 - a3*b2)*(a2*b3 - a3*b2) + (a3*b1 - a1*b3)*(a3*b1 - a1*b3) + (a1*b2 - a2*b1)*(a1*b2 - a2*b1)); //Модуль векторного произведения
}
int main() 
{
    double ax, ay, az, bx, by, bz, cx, cy, cz, sab, sac, sbc, s;
    cin >> ax >> ay >> az >> bx >> by >> bz >> cx >> cy >> cz;
    sab = s1(ax, ay, az, bx, by, bz); //Поочередно вызываем функцию для каждой стороны
    sac = s1(ax, ay, az, cx, cy, cz);
    sbc = s1(bx, by, bz, cx, cy, cz);
    if ((ax == bx && ay == by && az == bz) || (ax == cx && ay == cy && az==cz) || (bx == cx && by == cy && bz == cz))
        s = sab + sac + sbc; //Конечная формула площади полной поверхности параллелепипеда
    else
        s = (sab + sac + sbc)*2; 
    cout << setprecision(15) << s;
    return 0;
}

#include <iostream>

#include <cmath>

#include <iomanip>

using namespace std;

double s1(double a1, double a2, double a3, double b1, double b2, double b3) //Создаем функцию для нахождения стороны параллелепипеда

{

return sqrt((a2*b3 - a3*b2)*(a2*b3 - a3*b2) + (a3*b1 - a1*b3)*(a3*b1 - a1*b3) + (a1*b2 - a2*b1)*(a1*b2 - a2*b1)); //Модуль векторного произведения

}

int main()

{

double ax, ay, az, bx, by, bz, cx, cy, cz, sab, sac, sbc, s;

cin >> ax >> ay >> az >> bx >> by >> bz >> cx >> cy >> cz;

sab = s1(ax, ay, az, bx, by, bz); //Поочередно вызываем функцию для каждой стороны

sac = s1(ax, ay, az, cx, cy, cz);

sbc = s1(bx, by, bz, cx, cy, cz);

if ((ax == bx && ay == by && az == bz) || (ax == cx && ay == cy && az==cz) || (bx == cx && by == cy && bz == cz))

s = sab + sac + sbc; //Конечная формула площади полной поверхности параллелепипеда

else

s = (sab + sac + sbc)*2;

cout << setprecision(15) << s;

return 0;

}

import java.util.*;
import java.lang.*;
import java.io.*;
 
class Ideone
{
    static double s1(double a1, double a2, double a3, double b1, double b2, double b3) //Создаем функцию для нахождения стороны параллелепипеда
    { 
        return Math.sqrt((a2*b3 - a3*b2)*(a2*b3 - a3*b2) + (a3*b1 - a1*b3)*(a3*b1 - a1*b3) + (a1*b2 - a2*b1)*(a1*b2 - a2*b1)); //Модуль векторного произведения
    }
 
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        double ax, ay, az, bx, by, bz, cx, cy, cz, sab, sac, sbc, s;
        ax = in.nextDouble();
        ay = in.nextDouble();
        az = in.nextDouble();
        bx = in.nextDouble();
        by = in.nextDouble();
        bz = in.nextDouble();
        cx = in.nextDouble();
        cy = in.nextDouble();
        cz = in.nextDouble();
        sab = s1(ax, ay, az, bx, by, bz); //Поочередно вызываем функцию для каждой стороны
        sac = s1(ax, ay, az, cx, cy, cz);
        sbc = s1(bx, by, bz, cx, cy, cz);
        if ((ax == bx && ay == by && az == bz) || (ax == cx && ay == cy && az == cz) || (bx == cx && by == cy && bz == cz))
            s = sab + sac + sbc; //Конечная формула площади полной поверхности параллелепипеда
        else
            s = (sab + sac + sbc)*2; 
        System.out.println(s);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

static double s1(double a1, double a2, double a3, double b1, double b2, double b3) //Создаем функцию для нахождения стороны параллелепипеда

{

return Math.sqrt((a2*b3 - a3*b2)*(a2*b3 - a3*b2) + (a3*b1 - a1*b3)*(a3*b1 - a1*b3) + (a1*b2 - a2*b1)*(a1*b2 - a2*b1)); //Модуль векторного произведения

}

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

{

Scanner in = new Scanner(System.in);

double ax, ay, az, bx, by, bz, cx, cy, cz, sab, sac, sbc, s;

ax = in.nextDouble();

ay = in.nextDouble();

az = in.nextDouble();

bx = in.nextDouble();

by = in.nextDouble();

bz = in.nextDouble();

cx = in.nextDouble();

cy = in.nextDouble();

cz = in.nextDouble();

sab = s1(ax, ay, az, bx, by, bz); //Поочередно вызываем функцию для каждой стороны

sac = s1(ax, ay, az, cx, cy, cz);

sbc = s1(bx, by, bz, cx, cy, cz);

if ((ax == bx && ay == by && az == bz) || (ax == cx && ay == cy && az == cz) || (bx == cx && by == cy && bz == cz))

s = sab + sac + sbc; //Конечная формула площади полной поверхности параллелепипеда

else

s = (sab + sac + sbc)*2;

System.out.println(s);

}

По определению Параллелепипед — призма, основанием которой служит параллелограмм, или (равносильно) многогранник, у которого шесть граней и каждая из них — параллелограмм.

Для решения данной задачи нужно сперва найти площади трёх сторон (параллелограммов) данного параллелепипеда. Воспользуемся геометрическим смыслом векторного произведения:

Модуль векторного произведения [latex] [\overrightarrow{a},\overrightarrow{b}] [/latex] равняется площади S параллелограмма, построенного на приведённых к общему началу векторах [latex]\overrightarrow { a }[/latex] и [latex]\overrightarrow { b } [/latex]

Рассчитаем площадь каждого параллелограмма по формуле [latex] \left|\left[ \overrightarrow { a } , \overrightarrow { b } \right]\right| =
\left|(a_{ y }b_{ z }-a_{ z }b_{ y }, a_{ z }b_{ x }-a_{ x }b_{ z }, a_{ x }b_{ y }-a_{ y }b_{ x })\right|[/latex].

Найдя все три стороны, получим площадь полной поверхности параллелепипеда по формуле

[latex] S=2*(S_1+S_2+S_3) [/latex], где [latex] S_n [/latex] — площадь стороны параллелепипеда.

14/09/2015 by Сплошнов Кирилл

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

Мурзик всегда следил за чистотой школьного двора и ему в этом с радостью помогали бабочки, благодарные за прекрасные фотографии, сделанные им. Бабочки могли использовать собственные крылышки как линзы, причем они могли изменять их фокусное расстояние. Заметив обертку от конфетки, лежавшую на школьном дворе в точке с координатами [latex]X_1[/latex], [latex]Y_1[/latex], бабочка перелетала в точку с координатами [latex]X_2[/latex], [latex]Y_2[/latex], [latex]Z_2[/latex], расположенную на пути солнечных лучей к обертке и, изменяя фокусное расстояние своих крылышек-линз, сжигали обертку от конфеты.

Какую оптическую силу [latex]D[/latex] имели крылышки-линзы бабочки в этот момент?

В первой строке 2 числа: координаты [latex]X_1[/latex], [latex]Y_1[/latex], обертки от конфетки. Во второй – 3 числа: координаты [latex]X_2[/latex], [latex]Y_2[/latex], [latex]Z_2[/latex] бабочки в момент сжигания обертки.

Все входные данные целые числа, не превышающие по модулю 1000.

Единственное число – оптическая сила крылышек-линз [latex]D[/latex], вычисленная с точностью до 3-х знаков после запятой за правилами математических округлений.

[latex]X_1[/latex]	[latex]Y_1[/latex]	[latex]X_2[/latex]	[latex]Y_2[/latex]	[latex]Z_2[/latex]	[latex]D[/latex]
10	20	10	20	100	0.010
10	30	10	30	50	0.020
10	30	20	40	110	0.009

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;

int main() 
{
	int x1, y1;
	int x2, y2, z2;
	cin >> x1 >> y1;
	cin >> x2 >> y2 >> z2;
	double D = 1/sqrt((x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1) + z2*z2);
	cout << fixed << setprecision(3) << D << endl;
	return 0;
}

#include <iostream>

#include <iomanip>

#include <cmath>

using namespace std;

int main()

{

int x1, y1;

int x2, y2, z2;

cin >> x1 >> y1;

cin >> x2 >> y2 >> z2;

double D = 1/sqrt((x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1) + z2*z2);

cout << fixed << setprecision(3) << D << endl;

return 0;

}

Вычисляем оптическую силу линзы D по формуле [latex]D = \frac{1}{f}[/latex], где f — расстояние между бабочкой и обёрткой. вычисляем его по формуле: [latex]f[/latex] = [latex]\sqrt{(X_2-X_1)^2+(Y_2-Y_1)^2+Z_2^2}[/latex]. Вычисление в одну строку:

double D = 1/sqrt((x2 - x1)*(x2 - x1) + (y2 - y1)*(y2 - y1) + z2*z2);

13	double D = 1/sqrt((x2 - x1)(x2 - x1) + (y2 - y1)(y2 - y1) + z2*z2);

Далее округляем результат до требуемой точности и выводим на экран:

cout << fixed << setprecision(3) << D << endl;

14	cout << fixed << setprecision(3) << D << endl;

Зачитанный вариант на e-olimp.com: olymp.com

Рабочий код для тестирования на Ideaone.com: Ideaone.com

23/10/2014 by Гусак Дмитро Євгенович

Задача:

Найти площадь сектора, радиус которого равен 13.7, а дуга содержит заданное число радиан [latex] \varphi[/latex].

Тесты:

Ввод	Вывод	Результат
1	93.845	Площадь найдена
-1	Неверный ввод	Неправильные данные, подсчет невозможен
0.7	65.691	Площадь найдена
8.36	784.544	Площадь найдена
0	Неверный ввод	Неправильные данные, подсчет невозможен
3.14	294.673	Площадь найдена

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

#include <iostream>
using namespace std;

int main() {
	double r = 13.7; //заданный радиус
	double radian;  //угол, вводимый вручную
	double square;  //площадь, выводимая на экран
	printf("Введите число радиан дуги:");
	scanf("%lf", &radian);
	if(radian <= 0)
	            {
		         printf("Неверный ввод \n");
	            }
	else
	            {
	               square = radian/2 * (r*r);
	               printf("%5.3lf \n",square);
	            }
	return 0;
}

#include <iostream>

using namespace std;

int main() {

double r = 13.7; //заданный радиус

double radian; //угол, вводимый вручную

double square; //площадь, выводимая на экран

printf("Введите число радиан дуги:");

scanf("%lf", &radian);

if(radian <= 0)

{

printf("Неверный ввод \n");

}

else

{

square = radian/2 * (r*r);

printf("%5.3lf \n",square);

}

return 0;

}

Решение:
Площадь сектора находится по формуле [latex]S=\frac{\varphi}{2}r^2[/latex], после чего выводится на экран. В случае, если введённый угол меньше или равен нулю, программа выдает сообщение о неверном вводе.

Использованную формулу можно найти по этой ссылке, а здесь находится код в Ideone.

[latex]x_a[/latex]

[latex]y_a[/latex]

[latex]z_a[/latex]

[latex]x_b[/latex]

[latex]y_b[/latex]

[latex]z_b[/latex]

[latex]|AB|[/latex]

16/09/2014 by Іванов Вячеслав Володимирович

Задача: Коммерсант, имея стартовый капитал в [latex]k[/latex] рублей, занялся торговлей, которая ежемесячно увеличивает капитал на [latex]p%[/latex]. Через сколько лет он накопит сумму [latex]s[/latex], достаточную для покупки собственного магазина?

[latex]k[/latex]	[latex]p[/latex]	[latex]s[/latex]	[latex]years[/latex]	Комментарий:
0	10	0	0	Пройден
20	10	20	0	Пройден.
20	10	30	5	Пройден
0.6	30	21	14	Пройден
1.14	0.08	40.00	4450	Пройден
1.14	83.2	30	6	Пройден
1000	20	800	0	Пройден

#include <cstdio>
#include <cmath>

int main() {
    double k, p, s, years;
    scanf("%lf %lf %lf", &k, &p, &s);
     if( s<=k )
    {
        years=0;
        printf("%ld", years);
    }
     else
    {
        years = log( s/k )/log( 1 + (p/100) );
        //применяя функцию округления до ближайшего большего целого, рассчитать количество лет
        printf("%2.0lf", ceil(years) );
    }
    return 0;
}

#include <cstdio>

#include <cmath>

int main() {

double k, p, s, years;

scanf("%lf %lf %lf", &k, &p, &s);

if( s<=k )

{

years=0;

printf("%ld", years);

}

else

{

years = log( s/k )/log( 1 + (p/100) );

//применяя функцию округления до ближайшего большего целого, рассчитать количество лет

printf("%2.0lf", ceil(years) );

}

return 0;

}

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

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        double k = in.nextDouble();
        double p = in.nextDouble();
        double s = in.nextDouble();
        double years = 0;
        if(s > k)
            years = Math.ceil(Math.log(s/k)/Math.log(1+(p/100)));
        System.out.println(years);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.math.*;

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

double k = in.nextDouble();

double p = in.nextDouble();

double s = in.nextDouble();

double years = 0;

if(s > k)

years = Math.ceil(Math.log(s/k)/Math.log(1+(p/100)));

System.out.println(years);

}

Решение задачи основано на т.н. «формуле сложных процентов»: [latex]s=k(1+\frac {p}{100})^{years}[/latex].
По условию задачи, необходимо определить значение переменной years, с учётом следующих ограничений:
[latex]k \ge 0[/latex], [latex]p \ge 0[/latex], [latex]s \ge 0[/latex].
Если [latex]s \le k[/latex], то коммерсант уже может позволить себе покупку, следовательно, [latex]years = 0[/latex].
В противном случае, необходимо прологарифмировать левую и правую часть выражения.
Приведя его к удобному виду, получим:
[latex]\frac { s }{ k }=(1+\frac {p}{100})^{years}[/latex] [latex]\ln { (1 + \frac { p }{ 100 })^{ years } }= \ln{ (\frac { s }{ k }) }[/latex] В конечном итоге, получаем:
[latex]years=\frac { \ln { \frac {s}{k} } }{ \ln { (1+\frac { p }{ 100 }) } }[/latex]

В программе использован тип данных с плавающей точкой и двойной точностью.
Выбор продиктован требованиями функций заголовочного файла cmath.
Для выполнения программы и проверки тестов можно воспользоваться следующим объектом.
Реализация на Java: http://ideone.com/wbe8Ah