D2630. Сходимость ряда

13/12/2017 by Курьянов Павел

Задача
Исследовать сходимость ряда [latex]\sum_{n=1}^{\infty}\frac{ln(n!)}{n^{a}}[/latex] и вычислить его сумму при заданной точности.

Входные данные
Натуральное число [latex]a[/latex]

Выходные данные
Сумма ряда если она существует.

Тесты

входящие данные	выходящие данные
2	-nan
3	0.578615
6	0.0146958
12	0.000172786
22	1.65259e-07

#include <cmath>
#include <iostream>
using namespace std;
int poww(int a,int n) {
  return (!n)?1:a*poww(a,n-1);
}
int main() {
    int a;
    cin>>a; //ряд будет сходящимся только при a>2
    double s=0;
    long double f=1;
    double e=10;
    for(int n=2;e>0.000001;n++){
    f*=n;
    s+=log(f)/poww(n,a);
    e=log(f)/poww(n,a);
    }
    cout<<s;
    return 0;
    
}

#include <cmath>

#include <iostream>

using namespace std;

int poww(int a,int n) {

return (!n)?1:a*poww(a,n-1);

}

int main() {

int a;

cin>>a; //ряд будет сходящимся только при a>2

double s=0;

long double f=1;

double e=10;

for(int n=2;e>0.000001;n++){

f*=n;

s+=log(f)/poww(n,a);

e=log(f)/poww(n,a);

}

cout<<s;

return 0;

}

Решение задачи
Исследуем ряд на сходимость при различных значениях переменных [latex]a[/latex]. При [latex]a\leq 1[/latex] случай тривиальный — ряд будет расходиться.
Рассчитаем его при [latex]a\geq 2[/latex]. Как видно при [latex]a=2[/latex] ряд продолжает расходиться, а при [latex]a>2[/latex] он начинает сходиться и становиться возможным вычислить его сумму.

Ссылки
Условие задачи (стр. 257)
Код на ideone

Related Images:

D2550. Сумма ряда

10/12/2017 by Сытников Дан

Условие задачи:
Найти сумму сходящегося ряда:
[latex]\frac{1}{1 \cdot 4} + \frac{1}{4 \cdot 7} + … + \frac{1}{(3n — 2)(3n + 1)} + …[/latex]

Входные данные:
Целое число [latex]k[/latex] — номер искомой частичной суммы.

Выходные данные:
Искомая частичная сумма.

Тесты

№	Входные данные	Выходные данные
1	1	0.25
2	234	0.3328591749644379
3	10000	0.33332222259257893

Код на языке C++:

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

int main() {
    int k;
    long double val = 0;
    cin >> k;
    for (int n = 1; n <= k; n++){
        val += 1.0/((3*n - 2)*(3*n + 1)); 
    }
    cout << setprecision(15) <<val;
    return 0;
}

#include <iostream>

#include <iomanip>

using namespace std;

int main() {

int k;

long double val = 0;

cin >> k;

for (int n = 1; n <= k; n++){

val += 1.0/((3*n - 2)*(3*n + 1));

}

cout << setprecision(15) <<val;

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);
        int k;
        double val = 0;
        k = in.nextInt();
        for (int n = 1; n <= k; n++){
            val += 1.0/((3*n - 2)*(3*n + 1)); 
        }
        System.out.println(val);
    }
}

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);

int k;

double val = 0;

k = in.nextInt();

for (int n = 1; n <= k; n++){

val += 1.0/((3*n - 2)*(3*n + 1));

}

System.out.println(val);

}

Решение задачи:
Используем цикл for от 1 до заданного пользователем [latex]k[/latex] номера частичной суммы, в котором будем суммировать слагаемые ряда вида: [latex]\frac{1}{(3n — 2)(3n + 1)},[/latex] где [latex]n = \overline{1,k}[/latex].

Условие задачи (стр.248)
Код задачи на C++: Ideone
Код задачи на Java: Ideone

Related Images:

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

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] иначе.

Ссылки

Related Images:

MS9. Шифрование символов

29/08/2017 by Курьянов Павел

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

Входные данные
Последовательность символов.

Выходные данные
Зашифрованная последовательность символов, напечатанная через пробел.

Тесты

входные данные	выходные данные
pack my box with five dozen liquor jugs	p 11 2 8 4b 4d 14 59 42 d 17 58 57 1e 1d 1c 48 46 f 1f 13 45 44 b 15 1f b 4e 4c 5 18 4 1a 1d 52 4a 1f 12 14

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

#include <iostream>
using namespace std;

int main() {
    unsigned char a, b; 
    scanf("%c", &b); 
    cout<<b<<" ";
    while (scanf("%c", &a)) {
        if (a == '\n')  break;
        printf("%x ", a^b);
        b=a;
}
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned char a, b;

scanf("%c", &b);

cout<<b<<" ";

while (scanf("%c", &a)) {

if (a == '\n') break;

printf("%x ", a^b);

b=a;

}

return 0;

}

Решение задачи
Объявляем 2 символьные переменные. Считываем первый символ и выводим его. Остальные символы будут считываться в цикле, пока не произойдет переход на следующую строку.По мере ввода запоминаем старый символ во 2 переменной и складываем их по модулю 2 и выводим результат в шестнадцатеричной системе.

Ссылки

Подзадача — дешефратор
Написать программу, которая сможешь преобразовать полученный код обратно в текст.

Входные данный
Код полученный из выполнения основной задачи.

Выходные данные
Изначальный текст.

Тесты

входные данные	выходные данные
p 11 2 8 4b 4d 14 59 42 d 17 58 57 1e 1d 1c 48 46 f 1f 13 45 44 b 15 1f b 4e 4c 5 18 4 1a 1d 52 4a 1f 12 14	pack my box with five dozen liquor jugs

Код задачи

#include <iostream>
using namespace std;

int main()
{
    unsigned short a;
    unsigned char b;
    cin>>b;
    cout<<b;
    while (cin >> hex >> a)
    {
        b = a^b;
        cout << b;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

unsigned short a;

unsigned char b;

cin>>b;

cout<<b;

while (cin >> hex >> a)

{

b = a^b;

cout << b;

}

return 0;

}

Решение задачи
Так как сложение по модулю 2 обратно само себе, то нам нужно считать символы в том же порядке и применить тот же алгоритм при шифровании.

Related Images:

A 325. Простые делители числа

28/08/2017 by Курьянов Павел

Задача
Дано натуральное число [latex]n[/latex]. Получить все простые делители этого числа.

Входные данные
Натуральное число [latex]n[/latex]

Выходные данные
Все его простые делители напечатанные через пробел

Тесты

входные данные	выходные данные
2	2
7	7
50	2 5 5
169	13 13
583	11 53
2368	2 2 2 2 2 2 37
73890	2 3 3 5 821
885066	2 3 7 13 1621
6943960340	2 2 5 97 1787 2003

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

#include <iostream>
#include <cmath>
using namespace std;
 
int main()
{
    unsigned long long n;
  cin>>n;
    
    for (unsigned long long i = 2; i < sqrt(n)+0.00001; )    {
        if ( n % i == 0 ){
            std::cout << i << ' ';
            n /= i;
        }
        else{
            ++i;
        }
    }
    if ( n > 1 )
        std::cout << n;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

unsigned long long n;

cin>>n;

for (unsigned long long i = 2; i < sqrt(n)+0.00001; ) {

if ( n % i == 0 ){

std::cout << i << ' ';

n /= i;

}

else{

++i;

}

if ( n > 1 )

std::cout << n;

return 0;

}

Решение задачи
Для решения задачи мы проверяем все числа от 2 до [latex]\sqrt{n}[/latex]. Если число является делителем [latex]n[/latex], то мы его выводим и делим [latex]n[/latex] на это число. Повторная проверка на простоту не требуется так как мы ведем поиск снизу, а значит число полученное после проверки уже не может делиться на составное. В конце, если остается простой делитель больше, то он выводиться так же.

Ссылки

Условие задачи(страница 135)
Код на ideone

Related Images:

A328

21/06/2017 by Алла Марокко

Задача:
Найти [latex]100[/latex] первых простых чисел.
Тесты:
Обобщим задачу и для тестов используем разное количество первых простых чисел.

№	Вход	Выход
1	25	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
2	50	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229
3	100	2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541

Код:

#include <iostream>
using namespace std;

int main() { 
    printf("2"); 
    int n;
    cin>>n;
    for (int i=3; n; i+=2) { 
        for (int j = 3; j*j<=i ; ++j){
            if (i%j==0) goto next;
        }
        printf(", %d",i);
        --n; 
        next:;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

printf("2");

int n;

cin>>n;

for (int i=3; n; i+=2) {

for (int j = 3; j*j<=i ; ++j){

if (i%j==0) goto next;

}

printf(", %d",i);

--n;

next:;

}

return 0;

}

Решение:
Первое простое число печатаем сразу, остальные [latex]n-1[/latex] будем проверять циклами: проверим нечетные числа на нечетные делители(пройдём цикл по делителям). Число простое, если нет делителей. Если не простое, то переходим к следующему. Каждое простое число печатаем до [latex]n[/latex] включительно.
Ссылки:

Условие задачи.
Онлайн компилятор ideone.

Related Images:

e-olymp 5062. Максимальный подпалиндром

10/06/2017 by Тимур Фирсов

Задача

Из данной строки удалите наименьшее количество символов так, чтобы получился палиндром (строка, одинаково читающаяся как справа налево, так и слева направо).

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

Непустая строка длиной не более [latex]100[/latex] символов. Строка состоит только из заглавных латинских букв.

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

Вывести строку-палиндром максимальной длины, которую можно получить из исходной вычёркиванием нескольких букв. При наличии нескольких решений необходимо вывести одно (любое) из них.

Тесты

№	Входные данные	Выходные данные
1	QWEERTYY	YY
2	QWEERT	EE
3	BAOBAB	BAOAB
4	ABCDCBA	ABCDCBA

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

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

string **dp;
int main() {
    string s1,s2;
    long long i,j;
    cin>>s1;
    s2=s1;
    long long m=s1.size()+1;
    reverse(s2.begin(),s2.end());
    dp=new string* [m];
    for(i=0;i<m;i++)dp[i]=new string [m];
    for(i=1;i<m;i++){
        for(j=1;j<m;j++){
            if(s1[i-1]==s2[j-1])dp[i][j]=dp[i-1][j-1]+s2[j-1];
            else{
                if(dp[i-1][j].size()>dp[i][j-1].size())dp[i][j]=dp[i-1][j];
                else dp[i][j]=dp[i][j-1];
            }
        }
    }
    cout<<dp[m-1][m-1];
    return 0;
}

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

string **dp;

int main() {

string s1,s2;

long long i,j;

cin>>s1;

s2=s1;

long long m=s1.size()+1;

reverse(s2.begin(),s2.end());

dp=new string* [m];

for(i=0;i<m;i++)dp[i]=new string [m];

for(i=1;i<m;i++){

for(j=1;j<m;j++){

if(s1[i-1]==s2[j-1])dp[i][j]=dp[i-1][j-1]+s2[j-1];

else{

if(dp[i-1][j].size()>dp[i][j-1].size())dp[i][j]=dp[i-1][j];

else dp[i][j]=dp[i][j-1];

}

cout<<dp[m-1][m-1];

return 0;

}

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

Решение

Так как палиндром читается одинаково как справа налево, так и слева направо, то максимальным подпалиндромом будет наибольшая общая подстрока двух строк: исходной строки [latex]s_1[/latex] и этой же строки, но записанной в обратном порядке [latex]s_2[/latex] (как, если бы мы её читали справа налево). Для нахождения их наибольшей общей подстроки следует заполнить таблицу [latex]D[/latex] размером [latex] (n+1)\times(n+1) [/latex], где [latex]n[/latex]-длина строки. Заполнять таблицу будем методом аналогичным поиску длины наибольшей общей подстроки, но в каждой ячейке [latex]D_{i j}[/latex] таблицы будем хранить наибольшую подстроку строки, содержащей только первые [latex]i[/latex] символов [latex]s_1[/latex], и строки, содержащей только [latex]j[/latex] первых символов [latex]s_2[/latex]. В ячейках [latex]D_{0 j}[/latex] и [latex]D_{i 0}[/latex] будем хранить пустые строки. Если [latex]i[/latex]-й символ строки [latex]s_1[/latex] равен [latex]j[/latex]-ому символу строки [latex]s_2[/latex], то в ячейку [latex]D_{i j}[/latex] запишем конкатенацию строки из ячейки [latex]D_{i-1 j-1}[/latex] и данного символа. Иначе в ячейке [latex]D_{i j}[/latex] будем хранить наибольшую из строк [latex]D_{i-1 j}[/latex] и [latex]D_{i j-1}[/latex]. Таким образом в ячейке [latex]D_{n n}[/latex] будет хранится наибольший подпалиндром исходной строки.

Ссылки

Related Images:

e-olymp 1285. Деление Гольдбаха

10/06/2017 by Тимур Фирсов

Задача

Широко известна проблема Гольдбаха! Вот одна из её версий:

Любое нечетное число больше [latex]17[/latex] можно записать в виде суммы трёх нечётных простых чисел;
Любое чётное число больше [latex]6[/latex] можно записать в виде суммы двух нечётных простых чисел.

Если число чётное, то мы раскладываем его на суммы двух простых разных нечётных, а если нечётное — то на суммы трёх простых разных нечётных. Такой способ разложения для заданного [latex]N[/latex] назовём делением Гольдбаха и обозначим как [latex]G\left( N \right)[/latex].
Зная заданное число [latex]N[/latex], найти [latex]\left| G\left( N \right) \right| [/latex], т.е. количество различных [latex]G(N)[/latex].

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

Входные данные содержат несколько тестовых случаев.
Каждый тест в отдельной строке содержит одно единственное число [latex]N \left( 1\le N\le 20000 \right) [/latex].
Ввод продолжается до конца входного файла.

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

Для каждого тестового случая вывести в отдельной строке одно число — найденное значение [latex]\left| G\left( N \right) \right| [/latex].

Тесты

№	Входные данные	Выходные данные
1	5 8 18 19 20	0 1 2 1 2
2	13 22 78 4 150	0 2 7 0 12
3	2000	37
4	6 8 17 19 337	0 1 0 1 195

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

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

bool prime (int x){ //функция для проверки простоты нечётного числа
    bool pr=true;
    for(int i=2; i<=sqrt(x);i++)if(!(x%i))pr=false;
    return pr;
}
int main() {
    vector <int> v,prime_v;
    unordered_map <int,bool> prime_m;
    int u,i,j,maxx=0;
    while(cin>>u){
        v.push_back(u);
        maxx=max(maxx,u);//максимальное значение во входном потоке
    }
    for(i=3;i<=maxx;i+=2){
        if(prime(i)){
            prime_m[i]=true;
            prime_v.push_back(i); 
        }
    }
    int *dp,k;
    dp = new int [maxx+1];
    for(i=0;i<=maxx;i++)dp[i]=0;
    for(i=8;i<=maxx;i++){//заполняем массив значениями |G(i)|
        if(i%2){
            for(j=0;(j<prime_v.size())&&(prime_v[j]<i);j++){
                k=i-prime_v[j];
                if(dp[k]){
                    dp[i]+=dp[k];
                    if((prime_m[k-prime_v[j]])&&((k-prime_v[j])!=prime_v[j]))--dp[i];
                }
            }
        }
        else{
            for(j=0;(j<prime_v.size())&&(prime_v[j]<(i/2));j++){
                k=i-prime_v[j];
                if(prime_m[k])dp[i]++;
            }
        }
        if(i%2)dp[i]/=3;
    }
    for(i=0;i<v.size();i++)cout<<dp[v[i]]<<'\n';
    return 0;
}

#include <iostream>

#include <vector>

#include <unordered_map>

#include <cmath>

using namespace std;

bool prime (int x){ //функция для проверки простоты нечётного числа

bool pr=true;

for(int i=2; i<=sqrt(x);i++)if(!(x%i))pr=false;

return pr;

}

int main() {

vector <int> v,prime_v;

unordered_map <int,bool> prime_m;

int u,i,j,maxx=0;

while(cin>>u){

v.push_back(u);

maxx=max(maxx,u);//максимальное значение во входном потоке

}

for(i=3;i<=maxx;i+=2){

if(prime(i)){

prime_m[i]=true;

prime_v.push_back(i);

}

int *dp,k;

dp = new int [maxx+1];

for(i=0;i<=maxx;i++)dp[i]=0;

for(i=8;i<=maxx;i++){//заполняем массив значениями |G(i)|

if(i%2){

for(j=0;(j<prime_v.size())&&(prime_v[j]<i);j++){

k=i-prime_v[j];

if(dp[k]){

dp[i]+=dp[k];

if((prime_m[k-prime_v[j]])&&((k-prime_v[j])!=prime_v[j]))--dp[i];

}

else{

for(j=0;(j<prime_v.size())&&(prime_v[j]<(i/2));j++){

k=i-prime_v[j];

if(prime_m[k])dp[i]++;

}

if(i%2)dp[i]/=3;

}

for(i=0;i<v.size();i++)cout<<dp[v[i]]<<'\n';

return 0;

}

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

Решение

Поместим все тестовые случаи в вектор и найдём максимальное из данных чисел — [latex]max[/latex]. Затем найдём все нечётные простые числа меньшие [latex]max[/latex] (единственное чётное простое число — [latex]2[/latex]). Заведём массив размером [latex]max+1[/latex], [latex]i[/latex]-м элементом которого будет [latex]\left| G\left( i \right) \right| [/latex]. Тогда, если [latex]i[/latex]- чётное, то одно из слагаемых суммы [latex]a_{i}+b_{i}[/latex] двух простых разных нечётных чисел будем подбирать из найденных ранее простых нечётных чисел, но строго меньших [latex]\frac { i }{ 2 } [/latex], чтобы разбиения, отличающиеся только порядком следования частей считать равными, и выполнялось неравенство [latex]a_{i}\neq b_{i}[/latex]. Если разность [latex]i[/latex] и подобранного таким образом числа — нечётное простое число, то это деление Гольдбаха, тогда увеличиваем на единицу [latex]\left| G\left( i \right) \right| [/latex]. Если [latex]i[/latex] — нечётное, то [latex]a_{i}[/latex]из суммы [latex]a_{i}+b_{i}+c_{i}[/latex] трёх простых разных нечётных чисел будем подбирать из всех простых нечётных чисел строго меньших [latex]i[/latex]. Разностью [latex]i[/latex] и подобранного числа [latex]a_{i}[/latex] (разность двух нечётных) будет чётное число [latex]j[/latex], [latex]\left| G\left( j \right) \right| [/latex] мы уже нашли ранее. Тогда можем представить [latex]\left| G\left( j \right) \right| [/latex] различных разложений [latex]G\left( i \right)[/latex] в виде [latex]a_{i}+G\left( j \right)_{k}[/latex] или [latex]a_{i}+{a_j}_{k}+{b_j}_{k}[/latex], где [latex]k=\overline { 1,\left| G\left( j \right) \right| } [/latex], a [latex]G\left( j \right)_{k}[/latex] — [latex]k[/latex]-е разбиение числа [latex]j[/latex]. Значит все полученные [latex]\left| G\left( j \right) \right| [/latex] будем прибавлять к [latex]\left| G\left( i \right) \right| [/latex], а чтоб избежать ситуаций [latex]a_i={a_j}_k[/latex] и [latex]a_i={b_j}_k[/latex], если [latex]i-2a_{i}[/latex] — простое число не равное [latex]a_{i}[/latex] (то есть при некотором значении [latex]k[/latex] одно из чисел [latex] G\left( j \right)_{k} [/latex] равно [latex]a_{i}[/latex] и не равно второму числу, так как [latex]{a_{j}}_k\neq {b_{j}}_k[/latex] мы учли ранее), то будем отнимать единицу от [latex]\left| G\left( i \right) \right| [/latex]. В разбиениях [latex]j[/latex] мы не учитываем порядок следования частей. Чтобы не учитывать его в и разбиениях числа [latex]i[/latex], разделим полученный результат [latex]\left| G\left( i \right) \right| [/latex] на [latex]3[/latex].

Ссылки

Related Images:

e-olymp 1078. Степень строки

11/05/2017 by Вадим Гордийчук

Задача

Обозначим через [latex]a \cdot b[/latex] конкатенацию строк [latex]a[/latex] и [latex]b[/latex].

Например, если [latex]a =[/latex]«abc» и [latex]b =[/latex]«def» то [latex]a \cdot b =[/latex]«abcdef».

Если считать конкатенацию строк умножением, то можно определить операцию возведения в степень следующим образом:
[latex]a^{0} =[/latex]«» (пустая строка)
[latex]a^{n+1} = a \cdot a^{n}[/latex]

По заданной строке [latex]s[/latex] необходимо найти наибольшее значение [latex]n[/latex], для которого [latex]s = a^{n}[/latex] для некоторой строки [latex]a[/latex].

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

Каждый тест состоит из одной строки [latex]s[/latex], содержащей печатные (отображаемые) символы. Строка [latex]s[/latex] содержит не менее одного и не более миллиона символов.

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

Для каждой входной строки [latex]s[/latex] вывести в отдельной строке наибольшее значение [latex]n[/latex], для которого [latex]s[/latex] = [latex]a^{n}[/latex] для некоторой строки [latex]a[/latex].

Тесты

Входные данные	Выходные данные
abcabc gcdgcd gcgcgc gggggg hhhh	2 2 3 6 4
BbbbBbbbBbbb dogdogdog aaaaaaaa cstring	3 3 8 1

Код программы (c-string)

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

unsigned int cstringpow(const char *s)
{
    unsigned int answer = 1;
    const unsigned int size = strlen(s);
    for (unsigned int i = 1; i < size/2+1; ++i)
    {
        /*
        Ищем предполагаемую степень для ответа, которая
        обязательно является делителем длины строки.
        */
        if (size % i == 0)
        {
            bool not_broken = 1; //предполагаем, что выбранная степень строки максимальна
            for (int j = 0; j < size-i; j += i)
            {
                //сравниваем блоки строки
                if (strncmp(s+j, s+j+i, i) != 0)
                {
                    not_broken = 0;
                    break;
                }
            }
            if (not_broken)
            {
                //Если предполагаемая степень строки оказалась верной, возвращаем её.
                answer = size/i;
                break;
            }
        }
    }
    return answer;
}

int main()
{
    char s[1000010]; //Выделяем память для строк
    while (cin >> s)
        cout << cstringpow(s) << endl;
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

unsigned int cstringpow(const char *s)

{

unsigned int answer = 1;

const unsigned int size = strlen(s);

for (unsigned int i = 1; i < size/2+1; ++i)

{

Ищем предполагаемую степень для ответа, которая

обязательно является делителем длины строки.

if (size % i == 0)

{

bool not_broken = 1; //предполагаем, что выбранная степень строки максимальна

for (int j = 0; j < size-i; j += i)

{

//сравниваем блоки строки

if (strncmp(s+j, s+j+i, i) != 0)

{

not_broken = 0;

break;

}

if (not_broken)

{

//Если предполагаемая степень строки оказалась верной, возвращаем её.

answer = size/i;

break;

}

return answer;

}

int main()

{

char s[1000010]; //Выделяем память для строк

while (cin >> s)

cout << cstringpow(s) << endl;

return 0;

}

Решение задачи (c-string)

Из условия следует, что степень строки определяется максимальным числом одинаковых подстрок. В таком случае степень строки является одним из делителей длины этой строки, и очевидно, что максимальная степень строки будет обратно пропорциональна максимальной длине подстроки.

Для решения поставленной задачи используем функцию cstringpow, которая в качестве аргумента принимает строку, и возвращает её степень. Реализуем эту функцию следующим образом: вначале ищем делители значения переменной size (с использованием счётчика i в цикле), в которую было предварительно была сохранена длина строки, полученная функцией strlen. Числа, которые будут получатся из выражения size/i, будут предполагаемой максимальной степенью строки. Естественно, они будут находится в порядке убывания.
Найденные счётчиком делители будут представлять из себя длины подстрок, на которые можно полностью разбить данную строку. Затем, используя функцию strncmp, сравниваем каждую подстроку. В случае, если какие-то из подстрок не совпали, то предположенная максимальная степень строки не является верной, и необходимо искать следующую. Иначе (если несовпадающих подстрок не найдено, то) значение выражения size/i будет ответом на поставленную задачу. В крайнем случае, необходимое разбиение строки не будет найдено, и тогда совокупностью одинаковых подстрок будет сама строка, а следовательно её степень равна [latex]1[/latex].

Код программы (string)

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

unsigned int stringpow(const string &s)
{
    unsigned int answer = 1;
    const unsigned int size = s.size();
    for (unsigned int i = 1; i < size/2+1; ++i)
    {
        /*
        Ищем предполагаемую степень для ответа, которая
        обязательно является делителем длины строки.
        */
        if (size % i == 0)
        {
            bool not_broken = 1; //предполагаем, что выбранная степень строки максимальна
            for (int j = 0; j < size-i; j += i)
            {
                //сравниваем блоки строки
                if (s.compare(j, i, s, j+i, i) != 0)
                {
                    not_broken = 0;
                    break;
                }
            }
            
            if (not_broken)
            {
                //Если предполагаемая степень строки оказалась верной, возвращаем её.
                answer = size/i;
                break;
            }
        }
    }
    return answer;
}

int main()
{
    string s; //Выделяем переменную класса "строка"
    while (cin >> s)
        cout << stringpow(s) << endl;
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

unsigned int stringpow(const string &s)

{

unsigned int answer = 1;

const unsigned int size = s.size();

for (unsigned int i = 1; i < size/2+1; ++i)

{

Ищем предполагаемую степень для ответа, которая

обязательно является делителем длины строки.

if (size % i == 0)

{

bool not_broken = 1; //предполагаем, что выбранная степень строки максимальна

for (int j = 0; j < size-i; j += i)

{

//сравниваем блоки строки

if (s.compare(j, i, s, j+i, i) != 0)

{

not_broken = 0;

break;

}

if (not_broken)

{

//Если предполагаемая степень строки оказалась верной, возвращаем её.

answer = size/i;

break;

}

return answer;

}

int main()

{

string s; //Выделяем переменную класса "строка"

while (cin >> s)

cout << stringpow(s) << endl;

return 0;

}

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

public class Main
{
    public static int stringpow(String s)
    {
        int answer = 1;
        int size = s.length();
        for(int i = 1; i < size/2+1; ++i)
        {
            /*
            Ищем предполагаемую степень для ответа, которая
            обязательно является делителем длины строки.
            */
            if (size % i == 0)
            {
                boolean not_broken = true; //предполагаем, что выбранная степень строки максимальна
                String current = s.substring(0, i);
                for(int j = 0; j < size-i; j += i)
                {
                    //сравниваем блоки строки
                    if (!(current.equals(s.substring(j+i, j+2*i))))
                    {
                        not_broken = false;
                        break;
                    }
                }
            
                if (not_broken)
                {
                    answer = size/i;
                    break;
                }
            }
        }
        return answer;
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        String S; //Выделяем переменную класса "строка"
        while(in.hasNextLine())
        {
            S = in.nextLine();
            out.println(stringpow(S));
        }

        out.flush();
    }
}

import java.util.*;

import java.io.*;

public class Main

{

public static int stringpow(String s)

{

int answer = 1;

int size = s.length();

for(int i = 1; i < size/2+1; ++i)

{

Ищем предполагаемую степень для ответа, которая

обязательно является делителем длины строки.

if (size % i == 0)

{

boolean not_broken = true; //предполагаем, что выбранная степень строки максимальна

String current = s.substring(0, i);

for(int j = 0; j < size-i; j += i)

{

//сравниваем блоки строки

if (!(current.equals(s.substring(j+i, j+2*i))))

{

not_broken = false;

break;

}

if (not_broken)

{

answer = size/i;

break;

}

return answer;

}

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

{

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

String S; //Выделяем переменную класса "строка"

while(in.hasNextLine())

{

S = in.nextLine();

out.println(stringpow(S));

}

out.flush();

}

Решение задачи (string)

Решение задачи с использованием класса string аналогично. Единственное отличие — замена функций strlen и strncmp, предназначенных для работы с c-string, на эквивалентные им методы класса string size и compare.

Ссылки

Related Images:

e-olymp 4496. Приключение Незнайки и его друзей

09/05/2017 by Эммануил Прокопов

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

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

Все мы помним историю о том, как Незнайка со своими друзьями летали на воздушном шаре путешествовать. Но не все знают, что не все человечки влезли в шар, так как у него была ограниченная грузоподъемность.

В этой задаче Вам необходимо узнать, сколько же человечков улетело путешествовать. Известно, что посадка в шар не является оптимальной, а именно: человечки садятся в шар в той очереди, в которой они стоят, как только кому-то из них не хватает места, он и все оставшиеся в очереди разворачиваются и уходят домой.

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

В первой строке содержится количество человечков [latex]n (1 ≤ n ≤ { 10 }^{ 6 })[/latex] в цветочном городе. Во второй строке заданы веса каждого из человечков в том порядке, в котором они будут садиться в шар. Все веса натуральные числа и не превышают [latex]{ 10 }^{ 9 }[/latex]. Далее следует количество запросов [latex]m (1 ≤ m ≤ { 10 }^{ 5 })[/latex]. Каждый запрос представляет собой одну строку. Если первое число в строке равно единице, то далее следует еще одно число [latex]v (1 ≤ v ≤ { 10 }^{ 9 })[/latex] – грузоподъемность воздушного шара. Если же оно равно двум, то далее следует два числа [latex]x (1 ≤ x ≤ n)[/latex] и [latex]y (1 ≤ y ≤ { 10 }^{ 9 })[/latex] — это значит, что вес человечка, стоящего на позиции [latex]x[/latex], теперь равен [latex]y[/latex].

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

Для каждого запроса с номером один выведите в отдельной строке количество человечков, поместившихся в шар.

Тесты

№	Входные данные	Выходные данные
1	5 1 2 3 4 5 5 1 7 1 3 2 1 5 1 7 1 3	3 2 2 0
2	2 1 2 3 1 4 2 1 10 1 4	2 0
3	2 999999999 1000000000 4 1 999999999 2 1 1000000000 1 999999999 1 1000000000	1 0 1

Код на C++

#include <iostream>
using namespace std;

//Дерево отрезков.
struct segment_tree{
    long *tree;
    
    //Конструктор.
    segment_tree(int length){
        tree = new long[4*length+1];
    }
    
    //Построение дерева отрезков по массиву a.
    void build(int *a, int v, int tree_l, int tree_r){
        if(tree_l == tree_r) tree[v] = a[tree_l];
        else{
            int tree_m = (tree_l + tree_r)/2;
            build(a, v*2, tree_l, tree_m);
            build(a, v*2+1, tree_m+1, tree_r);
            tree[v] = tree[v*2] + tree[v*2+1];
        }
    }
    
    //Присваивание человечку на позиции pos веса new_val.
    void update(int v, int tree_l, int tree_r, int pos, int new_val){
        if(tree_l == tree_r) tree[v] = new_val;
        else{
            int tree_m = (tree_l + tree_r)/2;
            if(pos <= tree_m){
                update(v*2, tree_l, tree_m, pos, new_val);
            }
            else{
                update(v*2+1, tree_m+1, tree_r, pos, new_val);
            }
            tree[v] = tree[v*2] + tree[v*2+1];
        }
    }
    
    //Нахождение количества поместившихся человечков.
    int find_numb_of_p(int v, int tree_l, int tree_r, int max_w){
        if(tree_l == tree_r) return tree[v] <= max_w;
        int tree_m = (tree_l + tree_r)/2;
        if(tree[v*2] > max_w)
            return find_numb_of_p(v*2, tree_l, tree_m, max_w);
        else
            return tree_m - tree_l + 1 + find_numb_of_p(v*2+1, tree_m+1, tree_r, max_w-tree[v*2]);
    }
};
 
int main() {
    int n, m, *weights;
    cin >> n;
    //Заполнение массива весов человечков.
    weights = new int[n+1];
    for(int i = 1; i <= n; ++i){
        cin >> weights[i];
    }
    //Построение дерева отрезков.
    segment_tree tr(n);
    tr.build(weights, 1, 1, n);
    //Обработка запросов.
    cin >> m;
    int type, x, y, v;
    for(int i = 0; i < m; ++i){
        cin >> type;
        if(type == 2){
            cin >> x >> y;
            tr.update(1, 1, n, x, y);
        }
        else{
            cin >> v;
            cout << tr.find_numb_of_p(1, 1, n, v) << '\n';
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

//Дерево отрезков.

struct segment_tree{

long *tree;

//Конструктор.

segment_tree(int length){

tree = new long[4*length+1];

}

//Построение дерева отрезков по массиву a.

void build(int *a, int v, int tree_l, int tree_r){

if(tree_l == tree_r) tree[v] = a[tree_l];

else{

int tree_m = (tree_l + tree_r)/2;

build(a, v*2, tree_l, tree_m);

build(a, v*2+1, tree_m+1, tree_r);

tree[v] = tree[v*2] + tree[v*2+1];

}

//Присваивание человечку на позиции pos веса new_val.

void update(int v, int tree_l, int tree_r, int pos, int new_val){

if(tree_l == tree_r) tree[v] = new_val;

else{

int tree_m = (tree_l + tree_r)/2;

if(pos <= tree_m){

update(v*2, tree_l, tree_m, pos, new_val);

}

else{

update(v*2+1, tree_m+1, tree_r, pos, new_val);

}

tree[v] = tree[v*2] + tree[v*2+1];

}

//Нахождение количества поместившихся человечков.

int find_numb_of_p(int v, int tree_l, int tree_r, int max_w){

if(tree_l == tree_r) return tree[v] <= max_w;

int tree_m = (tree_l + tree_r)/2;

if(tree[v*2] > max_w)

return find_numb_of_p(v*2, tree_l, tree_m, max_w);

else

return tree_m - tree_l + 1 + find_numb_of_p(v*2+1, tree_m+1, tree_r, max_w-tree[v*2]);

}

};

int main() {

int n, m, *weights;

cin >> n;

//Заполнение массива весов человечков.

weights = new int[n+1];

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

cin >> weights[i];

}

//Построение дерева отрезков.

segment_tree tr(n);

tr.build(weights, 1, 1, n);

//Обработка запросов.

cin >> m;

int type, x, y, v;

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

cin >> type;

if(type == 2){

cin >> x >> y;

tr.update(1, 1, n, x, y);

}

else{

cin >> v;

cout << tr.find_numb_of_p(1, 1, n, v) << '\n';

}

return 0;

}

Код на Java

import java.util.*;
import java.io.*;
//Для решения задачи требуется читать целые числа быстрее, чем это можно делать при помощи Scanner.
class FastIntReader extends BufferedReader
{
    int cur, res;
    
    FastIntReader(InputStream s){super(new InputStreamReader(s));}
    
    int getNextInt() throws IOException
    {
        cur = read();
        res = 0;
        while(cur!=32 && cur!=-1 && cur != '\n'){
            res*=10;
            res += (int)(cur-'0');
            cur = read();
        }
        return res;
    }
}
//Дерево отрезков.
class SegmentTree
{
    static long []tree;
    //Конструктор.
    SegmentTree(int length){tree = new long[4*length+1];}
    
    void build(int v, int treeL, int treeR, FastIntReader in) throws IOException
    {
        
        if(treeL == treeR) tree[v] = in.getNextInt();
        else{
            int treeM = (treeL + treeR)/2;
            build(v*2, treeL, treeM, in);
            build(v*2+1, treeM+1, treeR, in);
            tree[v] = tree[v*2] + tree[v*2+1];
        }
    }
    
    //Присваивание человечку на позиции pos веса newVal.
    void update(int v, int treeL, int treeR, int pos, int newVal)
    {
        if(treeL == treeR) tree[v] = newVal;
        else{
            int treeM = (treeL + treeR)/2;
            if(pos <= treeM){
                update(v*2, treeL, treeM, pos, newVal);
            }
            else{
                update(v*2+1, treeM+1, treeR, pos, newVal);
            }
            tree[v] = tree[v*2] + tree[v*2+1];
        }
    }
    
    //Нахождение количества поместившихся человечков.
    int findNumberOfPeople(int v, int treeL, int treeR, long max_w)
    {
        if(treeL == treeR){
            if(tree[v] <= max_w) return 1;
            else return 0;
        }
        int treeM = (treeL + treeR)/2;
        if(tree[v*2] > max_w)
            return findNumberOfPeople(v*2, treeL, treeM, max_w);
        else
            return treeM - treeL + 1 + findNumberOfPeople(v*2+1, treeM+1, treeR, max_w-tree[v*2]);
    }
}

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        FastIntReader in = new FastIntReader(System.in);
        PrintWriter out = new PrintWriter(System.out);
        //Построение дерева отрезков.
        int n, m;
        n = in.getNextInt();
        SegmentTree tr = new SegmentTree(n);
        tr.build(1, 1, n, in);
        //Обработка запросов.
        m = in.getNextInt();
        int type, x, y, v;
        for(int i = 0; i < m; ++i){
            type = in.getNextInt();
            if(type == 2){
                x = in.getNextInt();
                y = in.getNextInt();
                tr.update(1, 1, n, x, y);
            }
            else{
                v = in.getNextInt();
                out.print(tr.findNumberOfPeople(1, 1, n, v));
                out.print('\n');
            }
        }
        out.flush();
    }
}

100

101

import java.util.*;

import java.io.*;

//Для решения задачи требуется читать целые числа быстрее, чем это можно делать при помощи Scanner.

class FastIntReader extends BufferedReader

{

int cur, res;

FastIntReader(InputStream s){super(new InputStreamReader(s));}

int getNextInt() throws IOException

{

cur = read();

res = 0;

while(cur!=32 && cur!=-1 && cur != '\n'){

res*=10;

res += (int)(cur-'0');

cur = read();

}

return res;

}

//Дерево отрезков.

class SegmentTree

{

static long []tree;

//Конструктор.

SegmentTree(int length){tree = new long[4*length+1];}

void build(int v, int treeL, int treeR, FastIntReader in) throws IOException

{

if(treeL == treeR) tree[v] = in.getNextInt();

else{

int treeM = (treeL + treeR)/2;

build(v*2, treeL, treeM, in);

build(v*2+1, treeM+1, treeR, in);

tree[v] = tree[v*2] + tree[v*2+1];

}

//Присваивание человечку на позиции pos веса newVal.

void update(int v, int treeL, int treeR, int pos, int newVal)

{

if(treeL == treeR) tree[v] = newVal;

else{

int treeM = (treeL + treeR)/2;

if(pos <= treeM){

update(v*2, treeL, treeM, pos, newVal);

}

else{

update(v*2+1, treeM+1, treeR, pos, newVal);

}

tree[v] = tree[v*2] + tree[v*2+1];

}

//Нахождение количества поместившихся человечков.

int findNumberOfPeople(int v, int treeL, int treeR, long max_w)

{

if(treeL == treeR){

if(tree[v] <= max_w) return 1;

else return 0;

}

int treeM = (treeL + treeR)/2;

if(tree[v*2] > max_w)

return findNumberOfPeople(v*2, treeL, treeM, max_w);

else

return treeM - treeL + 1 + findNumberOfPeople(v*2+1, treeM+1, treeR, max_w-tree[v*2]);

}

class Main

{

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

{

FastIntReader in = new FastIntReader(System.in);

PrintWriter out = new PrintWriter(System.out);

//Построение дерева отрезков.

int n, m;

n = in.getNextInt();

SegmentTree tr = new SegmentTree(n);

tr.build(1, 1, n, in);

//Обработка запросов.

m = in.getNextInt();

int type, x, y, v;

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

type = in.getNextInt();

if(type == 2){

x = in.getNextInt();

y = in.getNextInt();

tr.update(1, 1, n, x, y);

}

else{

v = in.getNextInt();

out.print(tr.findNumberOfPeople(1, 1, n, v));

out.print('\n');

}

out.flush();

}

Описание

В данной задаче требуется эффективно выполнять две операции: изменять значение одного из элементов массива и находить, сколько человечков поместится в шар при заданной грузоподъёмности. Это было реализовано при помощи структуры segment_tree. В функции main сначала вводится значение n и заполняется массив весов человечков weights, после чего по нему выполняется построение дерева отрезков tr. В его вершинах хранятся частичные суммы элементов массива. Да и в целом функции для построения и выполнения запроса модификации у него такие же, как и у обычного дерева отрезков для нахождения суммы на отрезке. Для удобства в массиве weights и в самом дереве используются элементы с первого по [latex]n[/latex]-й, а не с нулевого по [latex]\left( n-1 \right) [/latex]-й. Далее в ходе работы функции main в цикле выполняется обработка запросов. Сначала вводится тип запроса type. Если запрос второго типа, вводятся позиция человечка x, его новый вес y и вызывается метод update, пересчитывающий значения суммы в вершинах, на которые влияет это изменение. Иначе вводится грузоподъемность воздушного шара v и вызывается метод find_numb_of_p, который находит количество человечков, поместившихся в шар. Работает он следующим образом: если выполняется условие tree_l == tree_r, значит, рассматриваемый отрезок состоит из одного элемента, и функция возвращает [latex]1[/latex], если человечек может поместиться в шар, и [latex]0[/latex], если он слишком тяжёлый. Если отрезок больше, вычисляется индекс элемента, находящегося посередине tree_m. Далее, если сумма весов человечков в левом поддереве tree[v*2] больше, чем грузоподъёмность шара, то никто из правого поддерева уже не поместится, и искать следует только в левом поддереве. Иначе в шар следует посадить всех человечков из левого поддерева (их количество равно tree_m - tree_l + 1) и посмотреть, сколько поместится человечков из правого поддерева. При этом необходимо от максимально допустимого веса отнять вес человечков из левого поддерева, уже сидящих в шаре ( max_w-tree[v*2]).

Код на ideone.com. (C++)
Засчитанное решение на e-olymp.com. (C++)
Код на ideone.com. (Java)
Засчитанное решение на e-olymp.com. (Java)
При решении задачи был использован материал с сайта e-maxx.ru.

Related Images:

A302. Количество различных цифр числа в его десятичной записи

09/05/2017 by Андреев Даниил

Задача

Дано натуральное число [latex]N[/latex]. Сколько различных цифр встречается в его десятичной записи?

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

Натуральное число [latex]N[/latex].

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

Количество различных цифр [latex]sum[/latex].

Тесты

Входные данные	Выходные данные
[latex]N[/latex]	[latex]sum[/latex]
12345678900987654321	sum:10
302	sum:3

Код программы с использованием deque

#include <iostream>
#include <deque>
using namespace std;
 
int main(){
    deque<int> folder;
    unsigned long long N;
    
    cin >> N;
    folder.push_back(N%10);
    N/=10;
    while (N!=0){
        for (int i=0; i<folder.size(); i++){
            if (folder.at(i) == N%10)
                i+=folder.size();   
            if (i == folder.size() -1)
                folder.push_back(N%10);
        }
        N/=10;
    }
    cout << "sum:" << folder.size();
 
    return 0;
}

#include <iostream>

#include <deque>

using namespace std;

int main(){

deque<int> folder;

unsigned long long N;

cin >> N;

folder.push_back(N%10);

N/=10;

while (N!=0){

for (int i=0; i<folder.size(); i++){

if (folder.at(i) == N%10)

i+=folder.size();

if (i == folder.size() -1)

folder.push_back(N%10);

}

N/=10;

}

cout << "sum:" << folder.size();

return 0;

}

Решение

Создадим дэк [latex]folder[/latex] в котором будем хранить различные цифры десятичной записи. Добавляем первую цифру числа [latex]N[/latex] в дэк и делим [latex]N[/latex] на [latex]10[/latex]. Следующие цифры мы будем добавлять после проверки на отсутствие таких же в [latex]folder[/latex], если цифры совпадают заканчиваем цикл. В конце выводим размер [latex]folder[/latex] который и является [latex]sum[/latex].

Код программы с использованием массива

#include <iostream>
using namespace std;
 
int main(){
    int folder[10]={0}, sum=0;
    long long N;
 
    cin >> N;
    while (N!=0){
        folder[N%10]++;
        N/=10;
    }
    for (int j=0; j<10; j++)
        if(folder[j]!=0)    sum++;
    cout << "sum:" << sum;
 
    return 0;
}

#include <iostream>

using namespace std;

int main(){

int folder[10]={0}, sum=0;

long long N;

cin >> N;

while (N!=0){

folder[N%10]++;

N/=10;

}

for (int j=0; j<10; j++)

if(folder[j]!=0) sum++;

cout << "sum:" << sum;

return 0;

}

Решение

Создадим массив [latex]folder[/latex] в котором будем хранить кол-во встреч для различных цифр десятичной записи в соответствующих позициях массива. Увеличиваем на один значения соответствующей позиции массива и делим [latex]N[/latex] на [latex]10[/latex]. Для определения [latex]sum[/latex] делаем цикл и проверяем ненулевые значения массива [latex]folder[/latex].

Ссылки

Ideone через deque;
Ideone через массив;
Условие задачи (стр. 126).

Related Images:

A272. Количество осадков

07/05/2017 by Тимур Фирсов

Задача

Даны действительные числа [latex]a_{1}, a_{2}, …, a_{n}[/latex] – количество осадков (в миллиметрах), выпавших в Москве в течение [latex]n[/latex] лет. Вычислить среднее количество осадков [latex]average[/latex] и отклонение от среднего для каждого года [latex]d_{1}, d_{2}, …, d_{n}[/latex].

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

Последовательность действительных чисел.

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

Среднее количество осадков [latex]average[/latex].
Последовательность действительных чисел [latex]d_{1}, d_{2}, …, d_{n}[/latex] — отклонение от среднего.

Тесты

№	Входные данные	Выходные данные
1	0 0 0 0 0 0 1 0 0 0	0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.9 0.1 0.1 0.1
2	1.23 2.34 3.45 4.56 5.67	3.45 2.22 1.11 0 1.11 2.22
3	234.109 4655.15 43.629 14.109	1236.75 1002.64 3418.4 1193.12 1222.64
4	5 5 5 5 5 5	5 0 0 0 0 0 0

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

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

int main() {
    vector <long double> v;
    long double a, average=0;
    while(cin>>a){
        average+=a;
        v.push_back(a);
    }
    average/=v.size();
    cout<<average<<'\n';
    for(int i=0; i<v.size(); i++)cout<<abs(v[i]-average)<<' ';
    return 0;
}

#include <iostream>

#include <vector>

#include <cmath>

using namespace std;

int main() {

vector <long double> v;

long double a, average=0;

while(cin>>a){

average+=a;

v.push_back(a);

}

average/=v.size();

cout<<average<<'\n';

for(int i=0; i<v.size(); i++)cout<<abs(v[i]-average)<<' ';

return 0;

}

Решение

В цикле считываем числа из входного потока и прибавляем их к переменной [latex]average[/latex] (изначально [latex]average=0[/latex]), а также помещаем их в вектор [latex]v[/latex]. Далее делим [latex]average[/latex] на количество элементов в векторе, таким образом получим среднее количество осадков. Затем при помощи цикла поочередно будем выводить отклонение от среднего количества осадков для каждого года. Отклонением от среднего будет абсолютная величина разности соответствующего элемента вектора [latex]v[/latex] и среднего значения [latex]average[/latex].

Ссылки

Код программы
Условие задачи (страница 117).

Related Images:

e-olymp 1521. Оптимальное умножение матриц

07/05/2017 by Тимур Фирсов

Задача

Имея два двумерных массива [latex]A[/latex] и [latex]B[/latex], мы можем вычислить [latex]C = AB[/latex] используя стандартные правила умножения матриц. Число колонок в массиве [latex]A[/latex] должно совпадать с числом строк массива [latex]B[/latex]. Обозначим через [latex]rows(A)[/latex] и [latex]columns(A)[/latex] соответственно количество строк и колонок в массиве [latex]A[/latex]. Количество умножений, необходимых для вычисления матрицы [latex]C[/latex] (ее количество строк совпадает с [latex]A[/latex], а количество столбцов с [latex]B[/latex]) равно [latex]rows(A) columns(B) columns(A)[/latex]. По заданной последовательности перемножаемых матриц следует найти оптимальный порядок их умножения. Оптимальным называется такой порядок умножения матриц, при котором количество элементарных умножений минимально.

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

Каждый тест состоит из количества [latex]n (n ≤ 10)[/latex] перемножаемых матриц, за которым следуют [latex]n[/latex] пар целых чисел, описывающих размеры матриц (количество строк и столбцов). Размеры матриц задаются в порядке их перемножения. Последний тест содержит [latex]n = 0[/latex] и не обрабатывается.

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

Пусть матрицы пронумерованы [latex]A_{1}[/latex], [latex]A_{2}[/latex],…, [latex]A_{n}[/latex]. Для каждого теста в отдельной строке следует вывести его номер и скобочное выражение, содержащее оптимальный порядок умножения матриц. Тесты нумеруются начиная с [latex]1[/latex]. Вывод должен строго соответствовать формату, приведенному в примере. Если существует несколько оптимальных порядков перемножения матриц, выведите любой из них.

Тесты

№	Входные данные	Выходные данные
1	3 1 5 5 20 20 1 3 5 10 10 20 20 35 6 30 35 35 15 15 5 5 10 10 20 20 25 0	Case 1: (A1 x (A2 x A3)) Case 2: ((A1 x A2) x A3) Case 3: ((A1 x (A2 x A3)) x ((A4 x A5) x A6))
2	10 653 273 273 692 692 851 851 691 691 532 532 770 770 690 690 582 582 519 519 633 0	Case 1: (A1 x ((((((((A2 x A3) x A4) x A5) x A6) x A7) x A8) x A9) x A10))
3	2 11 12 12 33 7 1 5 5 28 28 19 19 2 2 10 10 1 1 12 4 10 29 29 133 133 8 8 15 0	Case 1: (A1 x A2) Case 2: (((((A1 x A2) x A3) x A4) x (A5 x A6)) x A7) Case 3: ((A1 x (A2 x A3)) x A4)

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

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int n;
vector <int> v;
void f(long long **a, long long i, long long j ){
    if(a[j][i]>0){
        v.push_back(a[j][i]);
        if((a[j][i]<=n)&&(i<=n)&&(j<=n)){
            f(a,i,a[j][i]);
            f(a,a[j][i],j);
        }
    }
}
string answer(long long x, long long si, long long sj, long long el){
     long long z1=el,z2=el;
     if(sj!=si){
        if(si!=x){
            while((v[v.size()-z1]<si)||(v[v.size()-z1]>=x))z1++;
        }
        if(sj!=(x+1)){
            while((v[v.size()-z2]<(x+1))||(v[v.size()-z2]>=sj))z2++; 
        }
     }
    return si==sj? "A"+to_string(si):"("+answer(v[v.size()-z1],si,x,z1+1)+" x "+answer(v[v.size()-z2],x+1,sj,z2+1)+")";
}
int main() {
    long long i,j,useless,number=1,**dp;
    cin>>n;
    while(n){
        n++;
        dp = new long long* [n];
        for(i=0;i<n;i++)dp[i]=new long long [n];
        for(i=0;i<n;i++){
            for(j=0;j<n;j++){
                dp[i][j]=0;
            }
        }
        cin>>dp[0][0];
        for(i=1;i<n;i++){
            cin>>dp[i][i];
            if(i<(n-1))cin>>useless;//лишние для нас значения
        }
        i=2;
        for(i=2;i<n;i++){        
            for(j=0;j<=(i-2);j++){
                dp[i][j]=2e10;
            }
        }
        long long t;
        for(i=2;i<n;i++){
            for(j=0;j<(n-i);j++){
                long long k=j+i;
                for(t=1;(j+t)<(n-1);t++){
                    if(dp[k][j]>(dp[k][j+t]+dp[j+t][j]+dp[k][k]*dp[j][j]*dp[j+t][j+t])){
                        dp[k][j]=dp[k][j+t]+dp[j+t][j]+dp[k][k]*dp[j][j]*dp[j+t][j+t];
                        dp[j][k]=j+t;//запоминаем последнее умножение
                    }
                }
            }
        }
        f(dp,n-1,0);//восстанавливаем порядок умножений (от последнего к первому)
        reverse(v.begin(),v.end());
        cout<<"Case "<<number<<": "<<answer(v[v.size()-1],1,n-1,1)<<'\n';
        number++;
        delete [] dp;//очищаем память для следующего теста
        v.clear();
        cin>>n;
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

using namespace std;

int n;

vector <int> v;

void f(long long **a, long long i, long long j ){

if(a[j][i]>0){

v.push_back(a[j][i]);

if((a[j][i]<=n)&&(i<=n)&&(j<=n)){

f(a,i,a[j][i]);

f(a,a[j][i],j);

}

string answer(long long x, long long si, long long sj, long long el){

long long z1=el,z2=el;

if(sj!=si){

if(si!=x){

while((v[v.size()-z1]<si)||(v[v.size()-z1]>=x))z1++;

}

if(sj!=(x+1)){

while((v[v.size()-z2]<(x+1))||(v[v.size()-z2]>=sj))z2++;

}

return si==sj? "A"+to_string(si):"("+answer(v[v.size()-z1],si,x,z1+1)+" x "+answer(v[v.size()-z2],x+1,sj,z2+1)+")";

}

int main() {

long long i,j,useless,number=1,**dp;

cin>>n;

while(n){

n++;

dp = new long long* [n];

for(i=0;i<n;i++)dp[i]=new long long [n];

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

for(j=0;j<n;j++){

dp[i][j]=0;

}

cin>>dp[0][0];

for(i=1;i<n;i++){

cin>>dp[i][i];

if(i<(n-1))cin>>useless;//лишние для нас значения

}

i=2;

for(i=2;i<n;i++){

for(j=0;j<=(i-2);j++){

dp[i][j]=2e10;

}

long long t;

for(i=2;i<n;i++){

for(j=0;j<(n-i);j++){

long long k=j+i;

for(t=1;(j+t)<(n-1);t++){

if(dp[k][j]>(dp[k][j+t]+dp[j+t][j]+dp[k][k]*dp[j][j]*dp[j+t][j+t])){

dp[k][j]=dp[k][j+t]+dp[j+t][j]+dp[k][k]*dp[j][j]*dp[j+t][j+t];

dp[j][k]=j+t;//запоминаем последнее умножение

}

f(dp,n-1,0);//восстанавливаем порядок умножений (от последнего к первому)

reverse(v.begin(),v.end());

cout<<"Case "<<number<<": "<<answer(v[v.size()-1],1,n-1,1)<<'\n';

number++;

delete [] dp;//очищаем память для следующего теста

v.clear();

cin>>n;

}

return 0;

}

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

Решение

Пусть [latex]A[/latex]- любая не последняя матрица заданной последовательности, [latex]B[/latex] — матрица, что следует за [latex]A[/latex] в данной последовательности перемножаемых матриц. Заведём двумерный массив [latex]dp[/latex] размером [latex] {(n+1)}\times {(n+1)}[/latex]. По главной диагонали массива запишем размеры матриц, причём [latex]rows(B)[/latex] не будем записывать, так как [latex]rows(B)=columns(A)[/latex]. В dp[k][j] [latex]\left( j<k \right) [/latex] будем хранить минимальное количество операций необходимое для получения матрицы [latex]C_{kj}[/latex] такой, что [latex]columns(C_{kj})[/latex] равно элементу dp[k][k], а [latex]rows(C_{kj})[/latex] соответственно dp[j][j]. Для получения матрицы [latex]C_{kj}[/latex] нужно умножить матрицу [latex]C_{k(j+t)}[/latex] на [latex]C_{(j+t)j}[/latex] [latex](\left( k-j \right) >t>0)[/latex], для этого нам понадобиться [latex]rows(C_{k(j+t)}) columns(C_{(j+t)j}) columns(C_{k(j+t)}) [/latex], что равно dp[k][k]*dp[j][j]*dp[j+t][j+t], операций непосредственно на перемножение этих матриц, а также dp[k][j+t] и dp[j+t][j] операций для получения матриц [latex]C_{k(j+t)}[/latex] и [latex]C_{(j+t)j}[/latex] соответственно.
Тогда dp[k][j]=dp[k][j+t]+dp[j+t][j]+dp[k][k]*dp[j][j]*dp[j+t][j+t]. При помощи цикла подберём [latex] t [/latex], при котором значение dp[k][j] выходит минимальным. Для получения матриц, которые даны изначально, не требуется ни одной операции, поэтому диагональ массива прилегающую к главной диагонали оставим заполненной нулями. Далее, при помощи вложенных циклов на каждом шаге внешнего цикла будем заполнять диагональ массива, что расположена ниже предыдущей. Параллельно будем запоминать номер последнего умножения, который будет равен [latex]j+t[/latex], в элемент массива, который расположен симметрично dp[k][j] относительно главной диагонали (то есть в dp[j][k]). Таким образом от умножения двух исходных матриц поэтапно перейдём к оптимальному произведению [latex]n[/latex] матриц. Затем, рекурсивно восстановим оптимальный порядок умножения матриц. Для вывода ответа в соответствующем формате также воспользуемся рекурсией.

Ссылки

Related Images:

e-olymp 3358. Чёрный ящик

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

Задача

В черный ящик кладутся листки с написанными на них числами. На каждом листке — ровно одно целое число. Иногда некоторые листки исчезают из ящика. После каждого события (когда в ящик положили листок, или когда из ящика исчез листок), нужно вывести число, которое встречается чаще всего на листках, находящихся в данный момент в ящике. Если таких чисел несколько, выведите наименьшее.

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

Первая строка содержит количество событий [latex]n[/latex] [latex]\left(1 \le n \le 2 \times 10^{5} \right)[/latex]. Каждая из следующих n строк содержит описание одного события:

[latex]+ x[/latex] — положен листок с числом [latex]x[/latex] [latex]\left(1 \le x \le 10^{6} \right)[/latex];
[latex]- x[/latex] — исчез листок с числом [latex]x[/latex] (гарантируется, что в ящике был хотя бы один листок с числом [latex]x[/latex]).

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

Вывести в точности [latex]n[/latex] строк — по одной для каждого события. Каждая строка должна содержать одно число — ответ к задаче. Если после какого-то события ящик оказался пуст, следует вывести [latex]0[/latex].

Тесты

Входные данные	Выходные данные
3 + 1 — 1 + 2	1 0 2
6 + 1 + 1000000 — 1 + 4 + 4 — 1000000	1 1 1000000 4 4 4
8 + 71 + 91 + 99 + 71 — 71 — 91 — 71 — 99	71 71 71 71 71 71 99 0

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

#include <iostream>
using namespace std;

template <class POINTER_TYPE, class TYPE> class segment_tree
{
    TYPE *SegmentTree;
    POINTER_TYPE base_capacity = 0;
    TYPE (*g)(TYPE, TYPE);
    TYPE neutral;
 
    TYPE result_on_segment_in
    (
        POINTER_TYPE v, POINTER_TYPE tl,
        POINTER_TYPE tr, POINTER_TYPE l,
        POINTER_TYPE r
    )
    {
        if (l > r) return neutral;
        else if (l == tl && r == tr) return SegmentTree[v];
        else
        {
            POINTER_TYPE 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));
        }
    }
 
    void make_monoid_and_fill_rest(TYPE *NewTree, const POINTER_TYPE &n, TYPE f(TYPE, TYPE), const TYPE &neutr)
    {
        g = f;
        neutral = neutr;
        for(POINTER_TYPE i = base_capacity+n; i < 2*base_capacity; ++i)
        {
            NewTree[i] = neutral;
        }
        for(POINTER_TYPE i = base_capacity-1; i > 0; --i)
        {
            NewTree[i] = g(NewTree[2*i], NewTree[2*i+1]);
        }
        SegmentTree = NewTree;
    }
 
    void fix_capacity(const POINTER_TYPE &base_array_size)
    {
        for (base_capacity = 1; base_capacity < base_array_size; base_capacity <<= 1);
    }
 
    public:
    void read_and_construct(const POINTER_TYPE amount_of_elements, TYPE preprocessing_function(const POINTER_TYPE&), TYPE f(TYPE, TYPE), const TYPE neutr)
    {
        fix_capacity(amount_of_elements);
        TYPE *NewTree = new TYPE[base_capacity*2];
        for(POINTER_TYPE i = 0; i < amount_of_elements; ++i)
        {
            NewTree[base_capacity+i] = preprocessing_function(i);
        }
        make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr);
    }
 
    void assign(const POINTER_TYPE index, const TYPE new_value)
    {
        SegmentTree[base_capacity+index] = new_value;
        for (POINTER_TYPE i = (base_capacity+index)/2; i > 0; i /= 2)
        {
            SegmentTree[i] = g(SegmentTree[2*i], SegmentTree[2*i+1]);
        }
    }
 
    TYPE result_on_segment (POINTER_TYPE l, POINTER_TYPE r)
    {
        return result_on_segment_in(1, 0, base_capacity-1, l, r);
    }
};

struct leaf
{
    unsigned int number, amount;
    leaf()
    {
        number = 2000000;
        amount = 0;
    }

    leaf(unsigned int a)
    {
        number = a, amount = 0;
    }
};

leaf max_leafs(leaf a, leaf b)
{
    return
    (a.amount == b.amount) ?
        (a.number < b.number) ? a : b
    :
        (a.amount > b.amount) ? a : b;
}

leaf constructor(const unsigned int &i)
{
    return leaf(i);
}

int main()
{
    segment_tree <unsigned int, leaf> box;
    box.read_and_construct(1000001, constructor, max_leafs, leaf());

    unsigned int n, index;
    char operation;
    leaf tmp;

    scanf("%u\n", &n); ++n;
    while (--n)
    {
        scanf("%c %u\n", &operation, &index);
        tmp = box.result_on_segment(index, index);
        if (operation == '+') ++tmp.amount;
        else --tmp.amount;
        box.assign(index, tmp);
        printf("%u\n", (box.result_on_segment(0, 1000000)).number);
    }
    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

#include <iostream>

using namespace std;

template <class POINTER_TYPE, class TYPE> class segment_tree

{

TYPE *SegmentTree;

POINTER_TYPE base_capacity = 0;

TYPE (*g)(TYPE, TYPE);

TYPE neutral;

TYPE result_on_segment_in

(

POINTER_TYPE v, POINTER_TYPE tl,

POINTER_TYPE tr, POINTER_TYPE l,

POINTER_TYPE r

)

{

if (l > r) return neutral;

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

else

{

POINTER_TYPE 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));

}

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

{

g = f;

neutral = neutr;

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

{

NewTree[i] = neutral;

}

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

{

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

}

SegmentTree = NewTree;

}

void fix_capacity(const POINTER_TYPE &base_array_size)

{

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

}

public:

void read_and_construct(const POINTER_TYPE amount_of_elements, TYPE preprocessing_function(const POINTER_TYPE&), TYPE f(TYPE, TYPE), const TYPE neutr)

{

fix_capacity(amount_of_elements);

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

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

{

NewTree[base_capacity+i] = preprocessing_function(i);

}

make_monoid_and_fill_rest(NewTree, amount_of_elements, f, neutr);

}

void assign(const POINTER_TYPE index, const TYPE new_value)

{

SegmentTree[base_capacity+index] = new_value;

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

{

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

}

TYPE result_on_segment (POINTER_TYPE l, POINTER_TYPE r)

{

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

}

};

struct leaf

{

unsigned int number, amount;

leaf()

{

number = 2000000;

amount = 0;

}

leaf(unsigned int a)

{

number = a, amount = 0;

}

};

leaf max_leafs(leaf a, leaf b)

{

return

(a.amount == b.amount) ?

(a.number < b.number) ? a : b

(a.amount > b.amount) ? a : b;

}

leaf constructor(const unsigned int &i)

{

return leaf(i);

}

int main()

{

segment_tree <unsigned int, leaf> box;

box.read_and_construct(1000001, constructor, max_leafs, leaf());

unsigned int n, index;

char operation;

leaf tmp;

scanf("%u\n", &n); ++n;

while (--n)

{

scanf("%c %u\n", &operation, &index);

tmp = box.result_on_segment(index, index);

if (operation == '+') ++tmp.amount;

else --tmp.amount;

box.assign(index, tmp);

printf("%u\n", (box.result_on_segment(0, 1000000)).number);

}

return 0;

}

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

Проанализируем задачу: так как требуется вывести число, которое встречается чаще всего на листках, находящихся в ящике после запроса удаления/добавления, а если таких чисел несколько, то вывести наименьшее, то задачу можно переформулировать следующим образом:

«Даётся последовательность (массив) объектов leaf [latex]x_{1}[/latex], [latex]x_{2}[/latex], [latex]x_{3}[/latex], [latex]\ldots[/latex], [latex]x_{999999}[/latex], [latex]x_{1000000}[/latex], представляющих из себя пару (number, amount)[latex]=x_{i}=\left(i, a_{i}\right) \in {\mathbb{N}_{0}}^{2}[/latex], где первые элементы пар [latex]i[/latex] представляет из себя число/номер листка, а вторые элементы [latex]a_{i}[/latex] — число листков с этим номером. Изначально все элементы пар [latex]a_{i}[/latex] равны нулю (так как изначально ящик пуст). Для запросов первого типа [latex]+ x[/latex] необходимо увеличивать на единицу число [latex]a_{i}[/latex] объекта, у которого номер [latex]i[/latex] равен [latex]x[/latex], а для запросов второго типа — уменьшать. Для каждого запроса необходимо вывести число [latex]j[/latex], удовлетворяющее условию [latex]j = \min\limits_{i \in \mathbb{K}}{i}[/latex], где [latex]\mathbb{K} = \{i \mid a_{i} = \max\limits_{k \in \{1, 2, \ldots, 1000000\}}{a_{k}} \}[/latex]».

Иными словами, число [latex]i[/latex] соответствует некоторому элементу [latex]x_{i} = \left(i, a_{i}\right)[/latex], который в свою очередь определяется операцией такой, что [latex]i[/latex] и [latex]a_{i}[/latex] удовлетворяют приведённым выше условиям. Очевидно, что данная операция является ассоциативной (как объединение минимума и максимума на заданных множествах), а потому для решения задачи воспользуемся универсальным деревом отрезков.

Создадим дерево отрезков box методом read_and_construct из объектов leaf. Так как нумерация листков начинается с единицы, а их число не превышает [latex]10^{6}[/latex], зададим размер базы дерева отрезков [latex]10^{6}+1[/latex], добавив неё элемент с индексом [latex]0[/latex]. Модифицируем метод read_and_construct таким образом, чтобы в функцию-препроцессор передавался номер элемента [latex]i[/latex], дабы была возможность задавать элементам [latex]x_{i}[/latex] их первоначальные значения [latex]\left(i, 0\right)[/latex]. Вышеупомянутую операцию назовём max_leafs и определим таким образом, чтобы она принимала два аргумента [latex]x_{i} = \left(i, a_{i}\right)[/latex] и [latex]x_{j} = \left(j, a_{j}\right)[/latex] и возвращала тот из них, у которого значение [latex]a[/latex] является большим, а в случае равенства этих значений — аргумент с меньшим индексом. Нейтральным элементом относительно данной операции будет, очевидно, пара [latex]\left(+\infty, 0\right)[/latex], но в силу того, что номера элементов не превышают [latex]10^6[/latex], вместо неё мы будем пользоваться парой [latex]\left(2 \times 10^{6}, 0\right)[/latex].

Далее при запросах вида [latex]+ x[/latex] будем увеличивать соответствующее значение [latex]a_{x}[/latex] пары [latex]\left(x, a_{x}\right)[/latex] на единицу, а при запросах вида [latex]- x[/latex] — уменьшать. Для обоих запросов будем выводить номер заданного листка, который удовлетворяет приведённым в задаче условиям, с использованием метода result_on_segment на всём отрезке [latex]\left[0, 10^{6}\right][/latex]. Ответом для каждого запроса будет значение number пары, которую вернёт метод.

Примечание: ситуация когда ящик становится пустым нигде не обрабатывается, но в силу того, что мы определили массив на отрезке [latex]\left[0, 10^{6}\right][/latex] вместо [latex]\left[1, 10^{6}\right][/latex] в нём всегда есть пара [latex]\left(0, 0\right)[/latex] (листки с номером [latex]0[/latex], число (значение [latex]b[/latex]) которых всегда равно [latex]0[/latex] в силу того, что листки с номером [latex]0[/latex] в ящик не добавляются). Так как определённая нами операция всегда возвращает минимальный номер листка, число которого максимально, то в случае, когда ящик пуст (т.е. значения всех [latex]a_{i} = 0, i = 0, 1, \ldots, 10^{6}[/latex]) будет выводится номер листка [latex]0[/latex]. Этот побочный эффект данного нами определения массива решает эту ситуацию и завершает решение задачи.

Ссылки

Related Images:

А282(а)

03/05/2017 by Антон Куперман

Задача

Даны действительные числа [latex]a_1,a_2, …,a_{2n}[/latex]. Получить:

[latex]a_1,a_{n+1},a_2,a_{n+2}, …,a_n,a_{2n}[/latex]

Тесты

Ввод	Вывод
1 2 3 4 5 6 7 8 9 10	1 6 2 7 3 8 4 9 5 10
8 25 3 7	8 3 25 7
5.5 6.025 2.387 1.0986 7.762 3.5958	5.5 1.0986 6.025 7.762 2.387 3.5958

Хороший код

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

int main() {
    vector <double> s;
    vector <double> l;
    double a,n;
    while(cin>>a)
    {
        s.push_back(a);
    }
    n=s.size()/2;
    for(int i=0;i<n;i++)
    {
        l.push_back(s.at(i));
        l.push_back(s.at(i+n));
    }
    for(int i=0;i<l.size();i++)
    {
        cout<<l.at(i)<<" ";
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

vector <double> s;

vector <double> l;

double a,n;

while(cin>>a)

{

s.push_back(a);

}

n=s.size()/2;

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

{

l.push_back(s.at(i));

l.push_back(s.at(i+n));

}

for(int i=0;i<l.size();i++)

{

cout<<l.at(i)<<" ";

}

return 0;

}

Решение

Считываем действительные числа в первый вектор и узнаем [latex]n[/latex]. Затем поочередно вписываем элементы и элементы с измененным индексом в другой вектор, пока счетчик не будет равен [latex]n[/latex] и выводим полученный вектор, он и будет ответом.

Лучший код на C++

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
        vector <double> s;
        double a,n;
        int b=0;
        while(cin>>a)
        {
                s.push_back(a);
        }
        n=s.size()/2;
        for(int i=0;i<n;i++)
        {
                s.insert(s.begin()+2*i+1,s.at(n+b+i));
                b++;
        }
        s.resize(2*n);
        for(int i=0;i<s.size();i++)
        {
                cout<<s.at(i)<<" ";
        }
        return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

vector <double> s;

double a,n;

int b=0;

while(cin>>a)

{

s.push_back(a);

}

n=s.size()/2;

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

{

s.insert(s.begin()+2*i+1,s.at(n+b+i));

b++;

}

s.resize(2*n);

for(int i=0;i<s.size();i++)

{

cout<<s.at(i)<<" ";

}

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);
        Vector a = new Vector();
        while(in.hasNextDouble()){ 
            a.add(in.nextDouble()); 
        }
        int n=a.size()/2;
        int b=0;
        for(int i=0;i<n;i++){
            a.add(2*i+1,a.get(n+b+i));
            b++;
        }
        a.setSize(2*n);
        Double[] s = new Double[a.size()];
        a.toArray(s);
        for(int i=0;i<s.length;i++){
            System.out.print(s[i]+" "); 
        }
    }
}

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);

Vector a = new Vector();

while(in.hasNextDouble()){

a.add(in.nextDouble());

}

int n=a.size()/2;

int b=0;

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

a.add(2*i+1,a.get(n+b+i));

b++;

}

a.setSize(2*n);

Double[] s = new Double[a.size()];

a.toArray(s);

for(int i=0;i<s.length;i++){

System.out.print(s[i]+" ");

}

Решение

В первом способе мы задавали два вектора, чем естественно увеличивали занимаемую память. C помощью функции insert() мы можем вставлять элементы в вектор, не используя дополнительных средств. Однако мы сталкиваемся с тем, что функция по определению вставляет в вектор константу из-за чего наш цикл не будет правильно работать. Чтобы изменять параметр вводимого элемента, заводим отдельный счетчик. Теперь каждый [latex]2*i+1[/latex]-ый шаг мы вставляем [latex]n+b+i[/latex]-ый элемент вектора. Проведем resize() вектора чтобы убрать лишние элементы и получим готовый результат.

Ссылки

Related Images:

e-olymp 595. Новый Лабиринт Амбера

02/05/2017 by Эммануил Прокопов

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

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

Как-то Корвину – принцу Амбера, по каким-то важным делам срочно понадобилось попасть в самую далекую тень, которую он только знал. Как всем известно, самый быстрый способ путешествия для принцев Амбера – это Лабиринт Амбера. Но у Корвина были настолько важные дела, что он не хотел тратить время на спуск в подземелье (именно там находится Амберский Лабиринт). Поэтому он решил воспользоваться Новым Лабиринтом, который нарисовал Дворкин. Но этот Лабиринт не так прост, как кажется…

Новый Лабиринт имеет вид последовательных ячеек, идущих друг за другом, пронумерованных от [latex]1[/latex] до [latex]N[/latex]. Из ячейки под номером [latex]i[/latex] можно попасть в ячейки под номерами [latex]i+2[/latex] (если [latex]i+2 ≤ N[/latex]) и [latex]i+3[/latex] (если [latex]i+3 ≤ N[/latex]). На каждой ячейке лежит какое-то количество золотых монет [latex]{ k }_{ i }[/latex]. Для того чтобы пройти лабиринт нужно, начиная ходить из-за границ лабиринта (с нулевой ячейки) продвигаться по выше описанным правилам, при этом подбирая все монетки на ячейках, на которых вы делаете промежуточные остановки. Конечная цель путешествия – попасть на ячейку с номером [latex]N[/latex]. Дальнейшее путешествие (в любое место Вселенной) возможно лишь тогда, когда достигнув ячейки с номером [latex]N[/latex], вы соберете максимально количество монеток. Напишите программу, которая поможет Корвину узнать, какое максимальное количество монеток можно собрать, проходя Новый Лабиринт Амбера.

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

В первой строке входного файла содержится натуральное число [latex]N (2 ≤ N ≤ 100000)[/latex], а во второй [latex]N[/latex] целых чисел, разделенных одним пробелом, [latex]{ k }_{ i }[/latex] – количество монеток, лежащих в ячейке с номером [latex]i[/latex] [latex](0 ≤ i ≤ 1000)[/latex].

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

В выходной файл вывести одно целое число – максимальное количество монеток, которое можно собрать, проходя лабиринт.

Тесты

№	Входные данные	Выходные данные
1	5 1000 2 3 1 3	6
2	2 1 2	2
3	4 1 3 100 0	3

Решение с использованием цикла

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

#include <iostream>
using namespace std;

int main() {
    int n, i;
    cin >> n;
    int *dp;
    dp = new int [n+1];
    for(i = 1; i<=n; ++i){
        cin >> dp[i];
    }
    dp[0] = 0;
    dp[1] = 0;
    for(int i = 2; i<=n; ++i){
        if(i - 3 >= 0) dp[i] = dp[i] + max(dp[i-2], dp[i-3]);
    }
    cout << dp[n];
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, i;

cin >> n;

int *dp;

dp = new int [n+1];

for(i = 1; i<=n; ++i){

cin >> dp[i];

}

dp[0] = 0;

dp[1] = 0;

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

if(i - 3 >= 0) dp[i] = dp[i] + max(dp[i-2], dp[i-3]);

}

cout << dp[n];

return 0;

}

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

Описание

Для хранения количества монет в каждой ячейке лабиринта используем массив [latex]dp[/latex] длиной [latex]n+1[/latex] элементов. При этом каждой ячейке лабиринта соответствует ячейка массива с тем же индексом, а нулевой элемент массива понимаем как точку перед входом в лабиринт. В цикле считываем количество монет в каждой ячейке, после чего обнуляем значение нулевого элемента массива, поскольку ячейка, соответствующая ему, находится вне лабиринта, и первого, поскольку в ячейку, соответствующую ему, невозможно попасть никаким образом. Далее в цикле для каждой ячейки лабиринта находим, какое максимальное количество монет может быть у Корвина после её посещения. В ячейку с номером [latex]i[/latex] он может попасть или из ячейки с номером [latex]i-2[/latex], или из ячейки с номером [latex]i-3[/latex]. При этом он несёт с собой все собранные ранее монеты, и добавляет к ним те, что находятся в данной ячейке. Таким образом, формула для нахождения максимального количества монет после посещения [latex]i[/latex]-й ячейки имеет вид [latex]dp[i] = dp[i] + max(dp[i-2], dp[i-3])[/latex], и ответ к задаче хранится в [latex]n[/latex]-й ячейке массива. Дополнительно требуется проводить проверку на выход за границы массива.

Код на ideone.com.

Решение с использованием рекурсивной функции

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

#include <iostream>
using namespace std;

int *dp;
int *used;

int f(int i){
    if(i < 2) return 0;
    else{
        if(used[i] == 0){
            dp[i] = dp[i] + max(f(i-2), f(i-3));
            used[i] = 1;
        }
        return dp[i];
    }
}

int main() {
    int n, i;
    cin >> n;
    dp = new int [n+1];
    used = new int [n+1];
    for(i = 1; i<=n; ++i){
        cin >> dp[i];
        used[i] = 0;
    }
    f(n);
    cout << dp[n];
    return 0;
}

#include <iostream>

using namespace std;

int *dp;

int *used;

int f(int i){

if(i < 2) return 0;

else{

if(used[i] == 0){

dp[i] = dp[i] + max(f(i-2), f(i-3));

used[i] = 1;

}

return dp[i];

}

int main() {

int n, i;

cin >> n;

dp = new int [n+1];

used = new int [n+1];

for(i = 1; i<=n; ++i){

cin >> dp[i];

used[i] = 0;

}

f(n);

cout << dp[n];

return 0;

}

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

Описание

В данном случае используется функция [latex]f[/latex], принимающая номер ячейки массива и возвращающая максимальное количество монет после посещения ячейки с этим номером. Сначала объявляются два глобальных массива:
[latex]dp[/latex], в [latex]i[/latex]-й ячейке которого изначально хранится количество монет в [latex]i[/latex]-й ячейке лабиринта, и [latex]used[/latex], элементы которого принимают значения [latex]0[/latex] или [latex]1[/latex] (значение [latex]0[/latex] в [latex]i[/latex]-й ячейке означает, что максимальное количество монет после посещения
ячейки лабиринта с тем же номером рассчитано ещё не было). Далее всё происходит как в решении с использованием цикла, но одновременно с чтением входных данных обнуляются элементы [latex]used[/latex], а вместо второго цикла происходит вызов функции [latex]f[/latex]. Сама же функция [latex]f[/latex], если значение параметра меньше двух, возвращает [latex]0[/latex], а иначе, если этого не было сделано ранее, вычисляет максимальное количество монет после посещения ячейки с номером [latex]i[/latex] по формуле [latex]dp[i] = dp[i] + max(dp[i-2], dp[i-3])[/latex] и возвращает его.

Код на ideone.com.
Кроме того, об идее решения данной задачи можно почитать здесь.

Related Images:

A274. Среднее арифметическое всех членов последовательности, кроме одного

27/04/2017 by Эммануил Прокопов

Задача из сборника задач по программированию Абрамова С.А. 2000г.
Даны действительные числа [latex]a_{ 1 }[/latex],…,[latex]a_{ 20 }[/latex]. Получить числа [latex]b_{ 1 }[/latex],…,[latex]b_{ 20 }[/latex], где [latex]b_{ i }[/latex] – среднее арифметическое всех членов последовательности [latex]a_{ 1 }[/latex],…,[latex]a_{ 20 }[/latex], кроме [latex]a_{ i }[/latex] ([latex]i[/latex] = 1,2,…,20).

Обобщим задачу для последовательности длины [latex]n[/latex]
Даны действительные числа [latex]a_{ 1 }[/latex],…,[latex]a_{ n }[/latex]. Получить числа [latex]b_{ 1 }[/latex],…,[latex]b_{ n }[/latex], где [latex]b_{ i }[/latex] – среднее арифметическое всех членов последовательности [latex]a_{ 1 }[/latex],…,[latex]a_{ n }[/latex], кроме [latex]a_{ i }[/latex] ([latex]i[/latex] = 1,2,…,[latex]n[/latex]).

Входные данные:
Последовательность действительных чисел.

Выходные данные:
[latex]n[/latex] чисел, [latex]i[/latex]-ое из которых является средним арифметическим всех членов последовательности, кроме [latex]i[/latex]-го ([latex]i[/latex] = 1,2,…,[latex]n[/latex]).

Тесты

№	Входные данные	Выходные данные
1	4	The sequence must consist of at least two elements.
2	1 0 1	The arithmetic average of all elements of this series except the element №i is: for i = 1: 0.5 for i = 2: 1 for i = 3: 0.5
3	10.1 2.4 11.3 0.8	The arithmetic average of all elements of this series except the element №i is: for i = 1: 4.8(3) for i = 2: 7.4 for i = 3: 4.4(3) for i = 4: 7.9(3)
4	2.5 -1.5 4 -9 1.22	The arithmetic average of all elements of this series except the element №i is: for i = 1: -1.32 for i = 2: -0.32 for i = 3: -1.695 for i = 4: 1.555 for i = 5: -1

Код на C++

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

int main() {
    vector <double> a, b;
    double cur, sum = 0;
    while(cin >> cur){
        a.push_back(cur);
        sum += cur;
    }
    //Если последовательность состоит мене чем из двух элементов.
    if(a.size() < 2){
        cout << "The sequence must consist of at least two elements.";
    }
    
    else{
        //Заполняем вектор b.
        for(int i=0; i < a.size(); ++i){
            b.push_back((sum - a[i])/(a.size() - 1));
        }
        
        //Выводим ответ.
        cout << "The arithmetic average of all elements of this series except the element №i is:\n";
        for(int i=0; i < b.size(); ++i){
            cout << "for i = " << i+1 << ": " << b[i] << '\n';
        }
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

vector <double> a, b;

double cur, sum = 0;

while(cin >> cur){

a.push_back(cur);

sum += cur;

}

//Если последовательность состоит мене чем из двух элементов.

if(a.size() < 2){

cout << "The sequence must consist of at least two elements.";

}

else{

//Заполняем вектор b.

for(int i=0; i < a.size(); ++i){

b.push_back((sum - a[i])/(a.size() - 1));

}

//Выводим ответ.

cout << "The arithmetic average of all elements of this series except the element №i is:\n";

for(int i=0; i < b.size(); ++i){

cout << "for i = " << i+1 << ": " << b[i] << '\n';

}

return 0;

}

Код на Java

import java.util.*;

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        Vector a,b;
        a = new Vector();
        b = new Vector();
        double cur, sum = 0;
        
        while(in.hasNext()){
            cur = in.nextDouble();
            a.add(cur);
            sum += cur;
        }
        //Если последовательность состоит только из одного числа.
        if(a.size() < 2){
            System.out.print("The sequence must consist of at least two elements.");
        }
        else{
            //Заполняем вектор b.
            for(int i=0; i < a.size(); ++i){
                b.add((sum - (double)(a.elementAt(i)))/(a.size() - 1));
            }
        
            //Выводим ответ.
            System.out.print("The arithmetic average of all elements of this series except the element №i is:\n");
            for(int i=0; i < b.size(); ++i){
                System.out.print("for i = " + (i+1) + ": " + b.elementAt(i) + '\n');
            }
        }
    }
}

import java.util.*;

class Main

{

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

{

Scanner in = new Scanner(System.in);

Vector a,b;

a = new Vector();

b = new Vector();

double cur, sum = 0;

while(in.hasNext()){

cur = in.nextDouble();

a.add(cur);

sum += cur;

}

//Если последовательность состоит только из одного числа.

if(a.size() < 2){

System.out.print("The sequence must consist of at least two elements.");

}

else{

//Заполняем вектор b.

for(int i=0; i < a.size(); ++i){

b.add((sum - (double)(a.elementAt(i)))/(a.size() - 1));

}

//Выводим ответ.

System.out.print("The arithmetic average of all elements of this series except the element №i is:\n");

for(int i=0; i < b.size(); ++i){

System.out.print("for i = " + (i+1) + ": " + b.elementAt(i) + '\n');

}

Решение
Для начала, в первом цикле мы читаем числа из входного потока, помещаем их в вектор a и прибавляем к переменной sum, предназначенной для хранения суммы всех чисел последовательности. Последовательность должна состоять как минимум из двух элементов. Чтобы получить среднее арифметическое всех её членов, кроме [latex]i[/latex]-го, достаточно отнять [latex]i[/latex]-й элемент вектора a от значения переменной sum и разделить результат на количество членов такой неполной последовательности, а оно будет на единицу меньше размера вектора a. Таким образом заполняется вектор b, в котором хранятся элементы последовательности [latex]b_{ 1 }[/latex],…,[latex]b_{ n }[/latex], после чего требуемая последовательность выводится.

Код на ideone.com (C++)
Код на ideone.com (Java)
Условие задачи (с.118)

Related Images:

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

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].

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

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

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

Код класса

#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 соответственно.

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

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

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

Так как в задаче необходимо выводить знак или произведения на заданных отрезках (либо нуль), то очевидно, что сами числа не интересуют нас. Тогда каждое из них можно представить в виде пары (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;

}

Задача 2

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

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

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

Код класса

#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 (то есть очень большую 🙂 ) благодарность её автору.

Related Images:

MS2. Сумма чисел во входном потоке

23/04/2017 by Роман Саркисян

Условие

Сосчитайте сумму чисел во входном потоке.

Тесты

Ввод	Вывод
1 2 3 4 5 6	21
12 13 14	39
1-100	5050

#include <iostream>
using namespace std;

int main() {
    double x, S=0;
    while( cin>>x){
        S+=x;
    }
    cout<<S;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

double x, S=0;

while( cin>>x){

S+=x;

}

cout<<S;

return 0;

}

import java.util.*;
import java.util.*;
import java.lang.*;
import java.io.*;
import java.util.Scanner;
class Ideone
{
    public static void main (String[] args) throws java.lang.Exception {
        Scanner scan = new Scanner(System.in);
        double sum = 0;
        double number = 0;
        while(scan.hasNext()){
            number=scan.nextInt();
            sum+=number;
        }
        System.out.println(sum);
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

import java.util.Scanner;

class Ideone

{

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

Scanner scan = new Scanner(System.in);

double sum = 0;

double number = 0;

while(scan.hasNext()){

number=scan.nextInt();

sum+=number;

}

System.out.println(sum);

}

Решение

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

Код на ideone C++
Код на ideone Java

Related Images:

ASCII ART

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

Task

In stations and airports you often see this type of screen:

Have you ever asked yourself how it might be possible to simulate this display on a good old terminal? We have: with ASCII art!

Your mission is to write a program that can display a line of text in ASCII art in a style you are given as input.

Input

Line 1: the width L of a letter represented in ASCII art. All letters are the same width.
Line 2: the height H of a letter represented in ASCII art. All letters are the same height.
Line 3: the line of text T, composed of N ASCII characters.
Following H lines: the string of characters ABCDEFGHIJKLMNOPQRSTUVWXYZ? Represented in ASCII art.

[latex]0 < [/latex] L[latex] < 30[/latex] [latex]0 < [/latex] H[latex] < 30[/latex] [latex]0 < [/latex] N[latex] < 200[/latex]

Output

The text T in ASCII art.
The characters a to z are shown in ASCII art by their equivalent in upper case.
The characters that are not in the intervals [a-z] or [A-Z] will be shown as a question mark in ASCII art.

Tests

Input	Output
1 1 Encoding using ASCII? Hah! ?ZYXWVUTSRQPONMLKJIHGFEDCBA	WNYMXSNUAGISNUA?IYSSAAT?TA

Codes of the program

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main()
{
    short Lwidth, Lheight;
    cin >> Lwidth >> Lheight; cin.ignore();
    string Text;
    char **alphabet = new char*[256];
    
    //initializing alphabet
    for (char ltr = 'a'; ltr < 'z'+1; ++ltr)
    {
        alphabet[ltr] = new char[Lwidth];
    }
    for (char ltr = 'A'; ltr < 'Z'+1; ++ltr)
    {
        alphabet[ltr] = new char[Lwidth];
    }
    alphabet['?'] = new char[Lwidth];
    
    getline(cin, Text);
    for (short h = 0; h < Lheight; ++h)
    {
        char ltr;
        for (ltr = 'a'; ltr < 'z'+1; ++ltr) //reading letters
        {
            for (short w = 0; w < Lwidth; ++w)
            {
                scanf("%c", &alphabet[ltr][w]);
                alphabet[ltr-('a'-'A')][w] = alphabet[ltr][w];
            }
        }
        
        for (short w = 0; w < Lwidth; ++w) //reading ?
        {
            scanf("%c", &alphabet['?'][w]);
        }
        
        scanf("%c", &ltr); //reading endl
        if (ltr != '\n') cerr << "ERROR: INVALID TESTS PROVIDED\n";
        
        //Putting result out.
        for (short i = 0; i < Text.size(); ++i)
        {
            if //it is a letter
            (
                (('a'-1 < Text[i]) && (Text[i] < 'z'+1)) ||
                (('A'-1 < Text[i]) && (Text[i] < 'Z'+1))
            ) //then print it
                cout << alphabet[Text[i]];
            else //it is definitely something weird
                cout << alphabet['?'];
        }
        cout << '\n';
    }
}

#include <iostream>

#include <string>

#include <algorithm>

using namespace std;

int main()

{

short Lwidth, Lheight;

cin >> Lwidth >> Lheight; cin.ignore();

string Text;

char **alphabet = new char*[256];

//initializing alphabet

for (char ltr = 'a'; ltr < 'z'+1; ++ltr)

{

alphabet[ltr] = new char[Lwidth];

}

for (char ltr = 'A'; ltr < 'Z'+1; ++ltr)

{

alphabet[ltr] = new char[Lwidth];

}

alphabet['?'] = new char[Lwidth];

getline(cin, Text);

for (short h = 0; h < Lheight; ++h)

{

char ltr;

for (ltr = 'a'; ltr < 'z'+1; ++ltr) //reading letters

{

for (short w = 0; w < Lwidth; ++w)

{

scanf("%c", &alphabet[ltr][w]);

alphabet[ltr-('a'-'A')][w] = alphabet[ltr][w];

}

for (short w = 0; w < Lwidth; ++w) //reading ?

{

scanf("%c", &alphabet['?'][w]);

}

scanf("%c", &ltr); //reading endl

if (ltr != '\n') cerr << "ERROR: INVALID TESTS PROVIDED\n";

//Putting result out.

for (short i = 0; i < Text.size(); ++i)

{

if //it is a letter

(

(('a'-1 < Text[i]) && (Text[i] < 'z'+1)) ||

(('A'-1 < Text[i]) && (Text[i] < 'Z'+1))

) //then print it

cout << alphabet[Text[i]];

else //it is definitely something weird

cout << alphabet['?'];

}

cout << '\n';

}

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

class Solution
{
    public static void main(String args[])
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        short Lwidth = in.nextShort(), Lheight = in.nextShort();
        Map alphabet = new HashMap();
        
        if (in.hasNextLine())
        {
            in.nextLine();
        }
        
        String Text = in.nextLine();

        for (short h = 0; h < Lheight; ++h)
        {
            String alphabet_line = in.nextLine();
            short i = 0;
            
            for(char sym = 'a', Sym = 'A'; sym <= 'z'; ++sym, ++Sym, ++i)
            {
                String letter = alphabet_line.substring(i*Lwidth, (i+1)*Lwidth);
                alphabet.put(sym, letter);
                alphabet.put(Sym, letter);
            }
            alphabet.put('?', alphabet_line.substring(i*Lwidth, (i+1)*Lwidth));
            
            for(i = 0; i < Text.length(); ++i)
            {
                if //it is a letter
                (
                    (('a' <= Text.charAt(i)) && (Text.charAt(i) <= 'z')) ||
                    (('A' <= Text.charAt(i)) && (Text.charAt(i) <= 'Z'))
                )
                    out.print(alphabet.get(Text.charAt(i)));
                else //it is definitely something weird
                    out.print(alphabet.get('?'));
            }
            out.print('\n');
        }

        out.flush();
    }
}

import java.util.*;

import java.io.*;

class Solution

{

public static void main(String args[])

{

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

short Lwidth = in.nextShort(), Lheight = in.nextShort();

Map alphabet = new HashMap();

if (in.hasNextLine())

{

in.nextLine();

}

String Text = in.nextLine();

for (short h = 0; h < Lheight; ++h)

{

String alphabet_line = in.nextLine();

short i = 0;

for(char sym = 'a', Sym = 'A'; sym <= 'z'; ++sym, ++Sym, ++i)

{

String letter = alphabet_line.substring(i*Lwidth, (i+1)*Lwidth);

alphabet.put(sym, letter);

alphabet.put(Sym, letter);

}

alphabet.put('?', alphabet_line.substring(i*Lwidth, (i+1)*Lwidth));

for(i = 0; i < Text.length(); ++i)

{

if //it is a letter

(

(('a' <= Text.charAt(i)) && (Text.charAt(i) <= 'z')) ||

(('A' <= Text.charAt(i)) && (Text.charAt(i) <= 'Z'))

)

out.print(alphabet.get(Text.charAt(i)));

else //it is definitely something weird

out.print(alphabet.get('?'));

}

out.print('\n');

}

out.flush();

}

<?php
fscanf(STDIN, "%d", $Lwidth);
fscanf(STDIN, "%d", $Lheight);

$alphabet = array();

$Text = stream_get_line(STDIN, 1024, "\n");

for ($h = 0; $h < $Lheight; ++$h)
{   
    $ltr = 'a';
    $ltr2 = 'A';
    while(true) //reading letters
    {
        $alphabet[$ltr] = stream_get_line(STDIN, $Lwidth);
        $alphabet[$ltr2] = $alphabet[$ltr];
        if ($ltr == 'z') break;
        ++$ltr;
        ++$ltr2;
    }
    
    //reading '?'
    $alphabet['?'] = stream_get_line(STDIN, $Lwidth);

    //reading endl   
    fscanf(STDIN, "%c", $useless);
    
    for ($i = 0; $i < strlen($Text); ++$i)
    {
        if //it is a letter
        (
            (('a' <= $Text[$i]) and ($Text[$i] <= 'z')) or
            (('A' <= $Text[$i]) and ($Text[$i] <= 'Z'))
        ) //then print it
            echo $alphabet[$Text[$i]];
        else //it is definitely something weird
            echo $alphabet['?'];
    }
    echo "\n";
}
?>

<?php

fscanf(STDIN, "%d", $Lwidth);

fscanf(STDIN, "%d", $Lheight);

$alphabet = array();

$Text = stream_get_line(STDIN, 1024, "\n");

for ($h = 0; $h < $Lheight; ++$h)

{

$ltr = 'a';

$ltr2 = 'A';

while(true) //reading letters

{

$alphabet[$ltr] = stream_get_line(STDIN, $Lwidth);

$alphabet[$ltr2] = $alphabet[$ltr];

if ($ltr == 'z') break;

++$ltr;

++$ltr2;

}

//reading '?'

$alphabet['?'] = stream_get_line(STDIN, $Lwidth);

//reading endl

fscanf(STDIN, "%c", $useless);

for ($i = 0; $i < strlen($Text); ++$i)

{

if //it is a letter

(

(('a' <= $Text[$i]) and ($Text[$i] <= 'z')) or

(('A' <= $Text[$i]) and ($Text[$i] <= 'Z'))

) //then print it

echo $alphabet[$Text[$i]];

else //it is definitely something weird

echo $alphabet['?'];

}

echo "\n";

}

Solution of the task

After saving the string, we can convert the task to «semi-stream processing». After we read and save the first line of ASCII characters into alphabet array, we start to print the tops of the ASCII letters. Then the same procedure is repeated on the following lines, and new parts of ASCII letters are read over the old ones into alphabet.