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:

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 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:

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

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:

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.

Links

Related Images:

There is no Spoon — Episode 1

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

Task

The Goal

The game is played on a rectangular grid with a given size. Some cells contain power nodes. The rest of the cells are empty.

The goal is to find, when they exist, the horizontal and vertical neighbors of each node.

Rules

To do this, you must find each [latex]\left( x1, y1 \right)[/latex] coordinates containing a node, and display the [latex]\left(x2, y2\right)[/latex] coordinates of the next node to the right, and the [latex]\left(x3, y3\right)[/latex] coordinates of the next node to the bottom within the grid.

If neighbor does not exist, you must output the coordinates [latex]\left(-1, -1\right)[/latex] instead of [latex]\left(x2, y2\right)[/latex] and/or [latex]\left(x3, y3\right)[/latex].

You lose if:

You give an incorrect neighbor for a node.
You give the neighbors for an empty cell.
You compute the same node twice.
You forget to compute the neighbors of a node.

Game input

The program must first read the initialization data from standard input. Then, provide to the standard output one line per instruction.

Initialization input

Line 1: one integer width for the number of cells along the x axis.

Line 2: one integer height for the number of cells along the y axis.

Next height lines: A string line containing width characters. A dot . represents an empty cell. A zero 0 represents a cell containing a node.

[latex]0 <[/latex] width[latex]\le 30[/latex]
[latex]0 <[/latex] height[latex]\le 30[/latex]

Output for one game turn

One line per node. Six integers on each line: x1 y1 x2 y2 x3 y3 Where:

( x1, y1) the coordinates of a node.
( x2, y2) the coordinates the closest neighbor on the right of the node.
( x3, y3) the coordinates the closest bottom neighbor.

[latex]0 \le[/latex] x1[latex]<[/latex] width
[latex]0 \le[/latex] y2[latex]<[/latex] height
[latex]-1 \le[/latex] x2, x3[latex]<[/latex] width
[latex]-1 \le[/latex] y2, y3[latex]<[/latex] height
Alloted response time to first output line [latex]\le 1[/latex]s.
Response time between two output lines [latex]\le 100[/latex]ms.

Tests

Input	Output
2 2 00 0.	0 0 1 0 0 1 1 0 -1 -1 -1 -1 0 1 -1 -1 -1 -1
4 4 .0.. .000 000. ..0.	1 0 -1 -1 1 1 1 1 2 1 1 2 2 1 3 1 2 2 3 1 -1 -1 -1 -1 0 2 1 2 -1 -1 1 2 2 2 -1 -1 2 2 -1 -1 2 3 2 3 -1 -1 -1 -1

The code of the program

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

int main()
{
    short width; // the number of cells on the X axis
    cin >> width; cin.ignore();
    short height; // the number of cells on the Y axis
    cin >> height; cin.ignore();
    string *node = new string[height];
    short x, y;
    for (y = 0; y < height; ++y)
    {
        getline(cin, node[y]);
    }
    for (y = 0; y < height; ++y)
    {
        for (x = 0; x < width; ++x)
        {
            if (node[y][x] == '0')
            {
                cout << x << ' ' << y << ' ';
                short x2, y2, ansX = -1, ansY = -1;
                for (x2 = x+1; x2 < width; ++x2)
                {
                    if (node[y][x2] == '0')
                    {
                        ansX = x2;
                        ansY = y;
                        break;
                    }
                }
                cout << ansX << ' ' << ansY << ' ';
                ansX = -1; ansY = -1;
                for (y2 = y+1; y2 < height; ++y2)
                {
                    if (node[y2][x] == '0')
                    {
                        ansX = x;
                        ansY = y2;
                        break;
                    }
                }
                cout << ansX << ' ' << ansY << '\n';
                x = x2-1;
            }
        }
    }
}

#include <iostream>

#include <string>

using namespace std;

int main()

{

short width; // the number of cells on the X axis

cin >> width; cin.ignore();

short height; // the number of cells on the Y axis

cin >> height; cin.ignore();

string *node = new string[height];

short x, y;

for (y = 0; y < height; ++y)

{

getline(cin, node[y]);

}

for (y = 0; y < height; ++y)

{

for (x = 0; x < width; ++x)

{

if (node[y][x] == '0')

{

cout << x << ' ' << y << ' ';

short x2, y2, ansX = -1, ansY = -1;

for (x2 = x+1; x2 < width; ++x2)

{

if (node[y][x2] == '0')

{

ansX = x2;

ansY = y;

break;

}

cout << ansX << ' ' << ansY << ' ';

ansX = -1; ansY = -1;

for (y2 = y+1; y2 < height; ++y2)

{

if (node[y2][x] == '0')

{

ansX = x;

ansY = y2;

break;

}

cout << ansX << ' ' << ansY << '\n';

x = x2-1;

}

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

class Player
{
    public static void main(String args[])
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);
        
        short width = in.nextShort(); // the number of cells on the X axis
        short height = in.nextShort(); // the number of cells on the Y axis
        
        if (in.hasNextLine()) {
            in.nextLine();
        }

        String node[] = new String[height];
        
        for(short y = 0; y < height; ++y)
        {
            node[y] = in.nextLine();
        }
        
        for(short y = 0; y < height; ++y)
        {
            for(short x = 0; x < width; ++x)
            {
                if (node[y].charAt(x) == '0')
                {
                    out.printf(String.valueOf(x)+" "+String.valueOf(y)+" ");
                    short x2, y2, ansX = -1, ansY = -1;
                    for (x2 = (short)(x+1); x2 < width; ++x2)
                    {
                        if (node[y].charAt(x2) == '0')
                        {
                            ansX = x2;
                            ansY = y;
                            break;
                        }
                    }
                    out.printf(String.valueOf(ansX)+" "+String.valueOf(ansY)+" ");
                    ansX = -1;
                    ansY = -1;
                    
                    for(y2 = (short)(y+1); y2 < height; ++y2)
                    {
                        if (node[y2].charAt(x) == '0')
                        {
                            ansX = x;
                            ansY = y2;
                            break;
                        }
                    }
                    out.printf(String.valueOf(ansX)+" "+String.valueOf(ansY)+"\n");
                    x = (short)(x2-1);
                }
            }
        }
        out.flush();
    }
}

import java.util.*;

import java.io.*;

import java.math.*;

class Player

{

public static void main(String args[])

{

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

short width = in.nextShort(); // the number of cells on the X axis

short height = in.nextShort(); // the number of cells on the Y axis

if (in.hasNextLine()) {

in.nextLine();

}

String node[] = new String[height];

for(short y = 0; y < height; ++y)

{

node[y] = in.nextLine();

}

for(short y = 0; y < height; ++y)

{

for(short x = 0; x < width; ++x)

{

if (node[y].charAt(x) == '0')

{

out.printf(String.valueOf(x)+" "+String.valueOf(y)+" ");

short x2, y2, ansX = -1, ansY = -1;

for (x2 = (short)(x+1); x2 < width; ++x2)

{

if (node[y].charAt(x2) == '0')

{

ansX = x2;

ansY = y;

break;

}

out.printf(String.valueOf(ansX)+" "+String.valueOf(ansY)+" ");

ansX = -1;

ansY = -1;

for(y2 = (short)(y+1); y2 < height; ++y2)

{

if (node[y2].charAt(x) == '0')

{

ansX = x;

ansY = y2;

break;

}

out.printf(String.valueOf(ansX)+" "+String.valueOf(ansY)+"\n");

x = (short)(x2-1);

}

out.flush();

}

Solution of the task

First of all, we must pay attention, that we have to find the closest neighbor. It doesn’t mean, that if there is no neighbor on adjacent cells, then the answer will be negative, because the neighbor may be further. This leads to the fact, that the task can not be completed without memorization of the whole list of cells.

After storing every string in array, the task becomes simple: we go using the cycle through every cell, and if the cell contains a node, then we launch two cycles from it in two directions (to the right and to the bottom), and assume there are no neighbors with assigning value -1 to both variables ansX and ansY. If there will be no nodes found, the value will remain the same, otherwise variables will take values of the node coordinates. In any case, the result will be correct.

This process is optimized by usage of the following: the [latex]x[/latex] coordinate of the closest right neighbor (or the value of width) is saved in a variable x2. Whether we find a neighbor or no, we can start the further horizontal search right from the coordinate x2, because empty cells must be skipped anyway.

Links

Related Images:

Код Хаффмана

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

Задача

Дана строка, после которой следует символ перехода на следующую строку (далее — endl. Вывести:

Код графа на языке DOT, иллюстрирующий кодирование символов строки;
Символы строки и соответствующие им коды Хаффмана;
Закодированную строку.

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

Некоторая последовательность символов и endl.

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

Код графа на языке DOT, иллюстрирующий кодирование символов строки;
Символы строки и соответствующие им коды Хаффмана;
Закодированная строка.

Тест

Входные данные	Выходные данные
MOLOKO KIPIT	digraph G { "'MLO KITP', 12, code: ''" -> "'MLO', 5, code: '0'" [ label = "0" ]; "'MLO KITP', 12, code: ''" -> "' KITP', 7, code: '1'" [ label = "1" ]; "'MLO', 5, code: '0'" -> "'ML', 2, code: '00'" [ label = "0" ]; "'MLO', 5, code: '0'" -> "'O', 3, code: '01'" [ label = "1" ]; "'ML', 2, code: '00'" -> "'M', 1, code: '000'" [ label = "0" ]; "'ML', 2, code: '00'" -> "'L', 1, code: '001'" [ label = "1" ]; "' KITP', 7, code: '1'" -> "' K', 3, code: '10'" [ label = "0" ]; "' KITP', 7, code: '1'" -> "'ITP', 4, code: '11'" [ label = "1" ]; "' K', 3, code: '10'" -> "' ', 1, code: '100'" [ label = "0" ]; "' K', 3, code: '10'" -> "'K', 2, code: '101'" [ label = "1" ]; "'ITP', 4, code: '11'" -> "'I', 2, code: '110'" [ label = "0" ]; "'ITP', 4, code: '11'" -> "'TP', 2, code: '111'" [ label = "1" ]; "'TP', 2, code: '111'" -> "'T', 1, code: '1110'" [ label = "0" ]; "'TP', 2, code: '111'" -> "'P', 1, code: '1111'" [ label = "1" ]; } Codes of letters: 'O'(01) 'K'(101) 'I'(110) 'T'(1110) 'P'(1111) 'M'(000) 'L'(001) ' '(100) Encoded string: 00001001011010110010111011111101110

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

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

MOLOKO KIPIT

digraph G {
"'MLO KITP', 12, code: ''" -> "'MLO', 5, code: '0'" [ label = "0" ];
"'MLO KITP', 12, code: ''" -> "' KITP', 7, code: '1'" [ label = "1" ];
"'MLO', 5, code: '0'" -> "'ML', 2, code: '00'" [ label = "0" ];
"'MLO', 5, code: '0'" -> "'O', 3, code: '01'" [ label = "1" ];
"'ML', 2, code: '00'" -> "'M', 1, code: '000'" [ label = "0" ];
"'ML', 2, code: '00'" -> "'L', 1, code: '001'" [ label = "1" ];
"' KITP', 7, code: '1'" -> "' K', 3, code: '10'" [ label = "0" ];
"' KITP', 7, code: '1'" -> "'ITP', 4, code: '11'" [ label = "1" ];
"' K', 3, code: '10'" -> "' ', 1, code: '100'" [ label = "0" ];
"' K', 3, code: '10'" -> "'K', 2, code: '101'" [ label = "1" ];
"'ITP', 4, code: '11'" -> "'I', 2, code: '110'" [ label = "0" ];
"'ITP', 4, code: '11'" -> "'TP', 2, code: '111'" [ label = "1" ];
"'TP', 2, code: '111'" -> "'T', 1, code: '1110'" [ label = "0" ];
"'TP', 2, code: '111'" -> "'P', 1, code: '1111'" [ label = "1" ];
}

Codes of letters:
'O'(01) 'K'(101) 'I'(110) 'T'(1110) 'P'(1111) 'M'(000) 'L'(001) ' '(100)

Encoded string:
00001001011010110010111011111101110

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

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

struct ltcode
{
    unsigned long long frequency;
    unsigned char letter;
    string code = "";
};

void zeroset(ltcode *c)
{
    for (unsigned int i = 0; i < 256; ++i)
    {
        c[i].frequency = 0;
        c[i].letter = i;
    }
}

bool f(ltcode x, ltcode y)
{
    if (x.frequency != y.frequency) return x.frequency > y.frequency;
    else return x.letter > y.letter;
}

struct B
{
    string list;
    int i;
    
    int left;
    int right;
    
    string code = "";
    
    B()
    {
        list = "";
        i = 0;
    }
};

void print_binary_tree(int num, vector <B> &tree)
{
    if (tree[num].list.size() > 1)
    {
        cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].left].list << "', " << tree[tree[num].left].i << ", code: \'" << tree[tree[num].left].code << "\'\" [ label = \"0\" ];\n";
        cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].right].list << "', " << tree[tree[num].right].i << ", code: \'" << tree[tree[num].right].code << "\'\" [ label = \"1\" ];\n";
        print_binary_tree(tree[num].left, tree);
        print_binary_tree(tree[num].right, tree);
    }
}

void print_tree_graph(vector <B> &tree)
{
    cout << "digraph G {\n";
    print_binary_tree(tree.size()-1, tree);
    cout << "}\n";
}

void huffman_encoding_in(int num, string code, vector <B> &tree, ltcode *letter_codes)
{
    tree[num].code = code;
    if (tree[num].list.size() > 1)
    {
        huffman_encoding_in(tree[num].left, code+"0", tree, letter_codes);
        huffman_encoding_in(tree[num].right, code+"1", tree, letter_codes);
    }
    else
    {
        for (int j = 0; ; ++j)
        {
            if (letter_codes[j].letter == tree[num].list[0])
            {
                letter_codes[j].code = code;
                break;
            }
        }
    }
}

void huffman_encoding(vector <B> &sorted_tree, ltcode *letter_codes)
{
    huffman_encoding_in(sorted_tree.size()-1, "", sorted_tree, letter_codes);
}

int main() {
    unsigned char c;
    string S;
    ltcode count[256], stringlinks[256];
    zeroset(count);

    while (scanf("%c", &c))
    {
        if (c == '\n') break;
        S += c;
        ++count[c].frequency;
    }
    sort(count, count+256, f);
    
    vector <B> tree;
    B tmp;
    tmp.list = "0";
    int j = 0, letter_amount;
    for (j = 0; (count[j].frequency); ++j)
    {
        tmp.i = count[j].frequency;
        tmp.list[0] = count[j].letter;
        tree.push_back(tmp);
    }
    int maxsize = j-1, size;
    
    sort(tree.begin(), tree.end(), [] (B a, B b)
    {
        if (a.i != b.i) return (a.i < b.i);
        else return (a.list.size() < b.list.size());
    });
    
    for (j = 0; size < maxsize;)
    {
        tmp.list = tree[j].list + tree[j+1].list;
        tmp.i = tree[j].i + tree[j+1].i;
        tmp.left = j;
        tmp.right = j+1;
        
        size = tmp.list.size();
        
        tree.push_back(tmp);
        j += 2;
        sort(tree.begin()+j, tree.end(), [] (B a, B b)
        {
            if (a.i != b.i) return (a.i < b.i);
            else return (a.list.size() < b.list.size());
        }
        );
    }
    huffman_encoding(tree, count);
    print_tree_graph(tree);
    cout << "\nCodes of letters:\n";
    for (j = 0; (count[j].frequency); ++j)
    {
        cout << '\'' << count[j].letter << "\'(" << count[j].code << ")  ";
        stringlinks[count[j].letter].code = count[j].code;
    }
    cout << "\n\nEncoded string:\n";
    for (unsigned int i = 0; i < S.size(); ++i)
    {
        cout << stringlinks[S[i]].code;
    }
    cout << '\n';
    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

#include <iostream>

#include <algorithm>

#include <vector>

#include <string>

using namespace std;

struct ltcode

{

unsigned long long frequency;

unsigned char letter;

string code = "";

};

void zeroset(ltcode *c)

{

for (unsigned int i = 0; i < 256; ++i)

{

c[i].frequency = 0;

c[i].letter = i;

}

bool f(ltcode x, ltcode y)

{

if (x.frequency != y.frequency) return x.frequency > y.frequency;

else return x.letter > y.letter;

}

struct B

{

string list;

int i;

int left;

int right;

string code = "";

B()

{

list = "";

i = 0;

}

};

void print_binary_tree(int num, vector &tree)

{

if (tree[num].list.size() > 1)

{

cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].left].list << "', " << tree[tree[num].left].i << ", code: \'" << tree[tree[num].left].code << "\'\" [ label = \"0\" ];\n";

cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].right].list << "', " << tree[tree[num].right].i << ", code: \'" << tree[tree[num].right].code << "\'\" [ label = \"1\" ];\n";

print_binary_tree(tree[num].left, tree);

print_binary_tree(tree[num].right, tree);

}

void print_tree_graph(vector &tree)

{

cout << "digraph G {\n";

print_binary_tree(tree.size()-1, tree);

cout << "}\n";

}

void huffman_encoding_in(int num, string code, vector &tree, ltcode *letter_codes)

{

tree[num].code = code;

if (tree[num].list.size() > 1)

{

huffman_encoding_in(tree[num].left, code+"0", tree, letter_codes);

huffman_encoding_in(tree[num].right, code+"1", tree, letter_codes);

}

else

{

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

{

if (letter_codes[j].letter == tree[num].list[0])

{

letter_codes[j].code = code;

break;

}

void huffman_encoding(vector &sorted_tree, ltcode *letter_codes)

{

huffman_encoding_in(sorted_tree.size()-1, "", sorted_tree, letter_codes);

}

int main() {

unsigned char c;

string S;

ltcode count[256], stringlinks[256];

zeroset(count);

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

{

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

S += c;

++count[c].frequency;

}

sort(count, count+256, f);

vector tree;

B tmp;

tmp.list = "0";

int j = 0, letter_amount;

for (j = 0; (count[j].frequency); ++j)

{

tmp.i = count[j].frequency;

tmp.list[0] = count[j].letter;

tree.push_back(tmp);

}

int maxsize = j-1, size;

sort(tree.begin(), tree.end(), [] (B a, B b)

{

if (a.i != b.i) return (a.i < b.i);

else return (a.list.size() < b.list.size());

});

for (j = 0; size < maxsize;)

{

tmp.list = tree[j].list + tree[j+1].list;

tmp.i = tree[j].i + tree[j+1].i;

tmp.left = j;

tmp.right = j+1;

size = tmp.list.size();

tree.push_back(tmp);

j += 2;

sort(tree.begin()+j, tree.end(), [] (B a, B b)

{

if (a.i != b.i) return (a.i < b.i);

else return (a.list.size() < b.list.size());

}

);

}

huffman_encoding(tree, count);

print_tree_graph(tree);

cout << "\nCodes of letters:\n";

for (j = 0; (count[j].frequency); ++j)

{

cout << '\'' << count[j].letter << "\'(" << count[j].code << ") ";

stringlinks[count[j].letter].code = count[j].code;

}

cout << "\n\nEncoded string:\n";

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

{

cout << stringlinks[S[i]].code;

}

cout << '\n';

return 0;

}

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

Для начала считываем посимвольно строку и запоминаем её, параллельно запоминая частоты появлений символов в ней в массиве count. Останавливаем считывание, когда встречается endl. После этого отсортировуем массив count в порядке убывания частот.

После этого элементы массива count, которые имеют ненулевую частоту, преобразовываем в элементы вектора tree (при этом символы конвертируются в строки), который после сортируется в порядке возрастания частот. Затем обрабатываем массив по алгортиму Хаффмана, объединяя элементы вектора с номерами [latex]j[/latex], [latex]j+1[/latex] в новый (который будет представлять собой структуру из конкатенации строк ранее упомянутых элементов и суммы их частот, а так же номеров его «предков»). После этого вектор вновь сортируется по частотам/суммам частот в порядке возрастания начиная с номера[latex]j+2[/latex], при этом элементы, которые имеют больший размер строк будут иметь меньший приоритет.

Такой алгоритм приводит к тому, что элементы с меньшей частотой/суммой частот не затрагиваются при добавлении новых, и система индексов (условных указателей на «предков») не нарушается.

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

Ссылки

Код программы на ideone.com.

Related Images:

Просто RSQ

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

Задача RSQ (Range Sum Query). Вам дан массив, необходимо отвечать на запросы получения суммы на отрезке и изменение одного элемента массива.

Ссылка на задачу на codeforces.com.

Имя входного файла: rsq.in
Имя выходного файла: rsq.out
Ограничение по памяти: 2 секунды
Ограничение по времени: 256 мегабайт

Формат входного файла

Входной файл в первой строке содержит два числа [latex]n[/latex] [latex]\left(1 \le n \le 10^{5} \right)[/latex] — размер массива и [latex]m[/latex] [latex]\left(1 \le m \le 10^{5} \right)[/latex] — количество запросов. Во второй строке задано начальное состояние массива [latex]a_{1}[/latex], [latex]a_{2}[/latex], [latex]\ldots[/latex], [latex]a_{n}[/latex] [latex]\left( -10^{5} \le a_{i} \le 10^{5} \right)[/latex].

Далее идёт [latex]m[/latex] строк с запросами вида [latex]t[/latex] [latex]x[/latex] [latex]y[/latex] [latex]\left( 0 \le t \le 1 \right)[/latex]. Если [latex]t = 0[/latex], тогда на запрос нужно вывести сумму элементов массива с индексами от [latex]x[/latex] до [latex]y[/latex] (в данном случае [latex]1 \le x \le y \le n[/latex]). Если [latex]t = 1[/latex], тогда надо присвоить элементу массива с индексом [latex]x[/latex] значение [latex]y[/latex] (в этом случае [latex]1 \le x \le n[/latex], [latex]-10^{5} \le y \le 10^{5}[/latex]).

Формат выходного файла

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

Примеры

rsq.in	rsq.out
5 3 1 2 3 4 5 0 1 5 1 1 -14 0 1 5	15 0
8 2 7 3 -10 4 1 2 5 6 0 2 4 0 5 7	-3 8

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

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

int main()
{
    ifstream cin("rsq.in");
    ofstream cout("rsq.out");
    ios::sync_with_stdio(false);
    unsigned int n, m, i;
    long long sum = 0, sum_k;
    int *a, x, y;
    bool t;
    cin >> n >> m; n++;
    a = new int[n];
    for (i = 1; i < n; i++)
    {
        cin >> a[i];
        sum += a[i];
    }
    const unsigned int ndiv2 = n/2;
    while (m--)
    {
        cin >> t >> x;
        if (t)
        {
            sum -= a[x];
            cin >> a[x];
            sum += a[x];
        }
        else
        {
            cin >> y;
            y++;
            if (y - x > ndiv2)
            {
                sum_k = sum;
                for (i = 1; i < x; i++)
                {
                    sum_k -= a[i];
                }
                for (i = y; i < n; i++)
                {
                    sum_k -= a[i];
                }
            }
            else
            {
                sum_k = 0;
                for (; x < y; x++)
                {
                    sum_k += a[x];
                }
            }
            cout << sum_k << endl;
        }
    }
    return 0;
}

#include <iostream>

#include <fstream>

using namespace std;

int main()

{

ifstream cin("rsq.in");

ofstream cout("rsq.out");

ios::sync_with_stdio(false);

unsigned int n, m, i;

long long sum = 0, sum_k;

int *a, x, y;

bool t;

cin >> n >> m; n++;

a = new int[n];

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

{

cin >> a[i];

sum += a[i];

}

const unsigned int ndiv2 = n/2;

while (m--)

{

cin >> t >> x;

if (t)

{

sum -= a[x];

cin >> a[x];

sum += a[x];

}

else

{

cin >> y;

y++;

if (y - x > ndiv2)

{

sum_k = sum;

for (i = 1; i < x; i++)

{

sum_k -= a[i];

}

for (i = y; i < n; i++)

{

sum_k -= a[i];

}

else

{

sum_k = 0;

for (; x < y; x++)

{

sum_k += a[x];

}

cout << sum_k << endl;

}

return 0;

}

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

Основная идея приведённого выше решения этой задачи заключается в оптимизации обработки запросов суммы построением дерева отрезков.
Сохраним сумму всех элементов массива в переменной sum. Теперь, если нам дан запрос суммы на отрезке [latex]\left[ x; y \right][/latex], то если [latex]y — x > \frac{n}{2}[/latex] (то есть если данный отрезок содержит больше элементов, чем половина всего отрезка) то считаем сумму элементов на отрезке [latex]\left[ 1; x-1 \right] \cup \left[ y+1; n \right] = \left[ 1; n \right] \setminus \left[ x; y \right][/latex] и отнимаем от суммы всех элементов, иначе (если [latex]y — x \le \frac{n}{2}[/latex], то) просто считаем сумму элементов на отрезке [latex]\left[ x; y \right][/latex]. Если же поступает запрос на замену значения элемента, то вычитаем из sum старое значение и прибавляем новое.

Таким образом, максимальная сложность запросов суммы (при простом подходе к задаче) уменьшается вдвое.

Ссылки

Related Images:

MS17. Самосинхронизирующийся скремблер

11/12/2016 by Вадим Гордийчук

Задача

Рассматривая входной поток как последовательность бит, зашифруйте его при помощи восьмибитового самосинхронизирующегося скремблера. Начальное значение и обратные связи скремблера должны быть заданы в программе значениями двух переменных типа unsigned char. Как расшифровать полученный код.

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

Подзадача 1

Рассматривая входной поток как последовательность бит, зашифруйте его при помощи восьмибитового самосинхронизирующегося скремблера.

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

Некая символьная последовательность.

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

Зашифрованная символьная последовательность.

Тесты

Входные данные	Выходные данные
Dogs eat meat.	ea 27 33 77 25 11 66 75 5 3b e0 89 6b fa
Scramble it!	fc 5a 80 ef 75 43 1e 92 9b 46 57 6
Base, base, it’s cheeseburger 1. Can you hear me?	ec 49 a0 c9 72 75 43 13 55 66 28 80 e7 ed d2 75 b7 bf 69 93 c7 df 4e d0 be 3f b1 de 5c f6 ea 6c 94 f5 8d 1f 86 80 aa 74 5e c7 9e 17 2 47 41 76 7c d4 a1

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

#include<iostream>
using namespace std;

class self_synchronizing_scrambler
{
    unsigned char key;
    unsigned char shift_register;

    bool pickbit(const unsigned char val, const short index)
    {
        return ((val >> index)%2);
    }

    public:
    self_synchronizing_scrambler() {}

    self_synchronizing_scrambler(unsigned char key, unsigned char shift_register)
    {
        this->key = key;
        this->shift_register = shift_register;
    }

    void assign_key(unsigned char key) {this->key = key;}
    void assign_register(unsigned char shift_register) {this->shift_register = shift_register;}

    unsigned char key_value() {return key;}
    unsigned char register_value() {return shift_register;}

    void scramble(unsigned char &letter)
    {
        unsigned char output = 0;
        for (unsigned char i = 0; i < 8; ++i)
        {
            bool newbit = pickbit(letter, 7-i);
            for (unsigned char j = 0; j < 8; ++j)
            {
                newbit ^= pickbit(this->key, 7-j) & pickbit(this->shift_register, 7-j);
            }
            output ^= (newbit << (7-i));

            key = (key >> 1) + (newbit << 7);
        }
        letter = output;
    }

    void descramble(unsigned char &letter)
    {
        unsigned char output = 0;
        for(unsigned char i = 0; i < 8; ++i)
        {
            bool oldbit = pickbit(letter, 7-i), scrambit = 0;
            for(unsigned char j = 0; j < 8; ++j)
            {
                scrambit ^= pickbit(this->key, 7-j) & pickbit(this->shift_register, 7-j);
            }
            output ^= ((scrambit^oldbit) << (7-i));

            key = (key >> 1) + (oldbit << 7);
        }
        letter = output;
    }
};

int main()
{
    self_synchronizing_scrambler A(5, 17);
    unsigned char input;

    while (scanf("%c", &input))
    {
        if (input == '\n') break;
        A.scramble(input);
        printf("%x ", input);
    }
    return 0;
}

#include<iostream>

using namespace std;

class self_synchronizing_scrambler

{

unsigned char key;

unsigned char shift_register;

bool pickbit(const unsigned char val, const short index)

{

return ((val >> index)%2);

}

public:

self_synchronizing_scrambler() {}

self_synchronizing_scrambler(unsigned char key, unsigned char shift_register)

{

this->key = key;

this->shift_register = shift_register;

}

void assign_key(unsigned char key) {this->key = key;}

void assign_register(unsigned char shift_register) {this->shift_register = shift_register;}

unsigned char key_value() {return key;}

unsigned char register_value() {return shift_register;}

void scramble(unsigned char &letter)

{

unsigned char output = 0;

for (unsigned char i = 0; i < 8; ++i)

{

bool newbit = pickbit(letter, 7-i);

for (unsigned char j = 0; j < 8; ++j)

{

newbit ^= pickbit(this->key, 7-j) & pickbit(this->shift_register, 7-j);

}

output ^= (newbit << (7-i));

key = (key >> 1) + (newbit << 7);

}

letter = output;

}

void descramble(unsigned char &letter)

{

unsigned char output = 0;

for(unsigned char i = 0; i < 8; ++i)

{

bool oldbit = pickbit(letter, 7-i), scrambit = 0;

for(unsigned char j = 0; j < 8; ++j)

{

scrambit ^= pickbit(this->key, 7-j) & pickbit(this->shift_register, 7-j);

}

output ^= ((scrambit^oldbit) << (7-i));

key = (key >> 1) + (oldbit << 7);

}

letter = output;

}

};

int main()

{

self_synchronizing_scrambler A(5, 17);

unsigned char input;

while (scanf("%c", &input))

{

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

A.scramble(input);

printf("%x ", input);

}

return 0;

}

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

class SelfSynchronizingScrambler
{
    private char key, shift_register;

    private static int pickbit(char val, int index)
    {
        return ((val >> index)%2);
    }

    public SelfSynchronizingScrambler() {}

    public SelfSynchronizingScrambler(char key, char shift_register)
    {
        this.key = key;
        this.shift_register = shift_register;
    }

    public void assignKey(char key) {this.key = key;}
    public void assignRegister(char shift_register) {this.shift_register = shift_register;}

    public char keyValue() {return key;}
    public char registerValue() {return shift_register;}

    public char scramble(char letter)
    {
        char output = 0;
        for (char i = 0; i < 8; ++i)
        {
            int newbit = pickbit(letter, 7-i);
            for (char j = 0; j < 8; ++j)
            {
                newbit ^= pickbit(this.key, 7-j) & pickbit(this.shift_register, 7-j);
            }
            output ^= (newbit << (7-i));

            key = (char)((key >> 1) + (newbit << 7));
        }
        return output;
    }

    public char descramble(char letter)
    {
        char output = 0;
        for(char i = 0; i < 8; ++i)
        {
            int oldbit = pickbit(letter, 7-i), scrambit = 0;
            for(char j = 0; j < 8; ++j)
            {
                scrambit ^= pickbit(this.key, 7-j) & pickbit(this.shift_register, 7-j);
            }
            output ^= ((scrambit^oldbit) << (7-i));

            key = (char)((key >> 1) + (oldbit << 7));
        }
        return output;
    }
};

public class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        SelfSynchronizingScrambler A = new SelfSynchronizingScrambler((char)5,(char)17);
        PrintWriter out = new PrintWriter(System.out);

        char letter = (char)System.in.read();
        while(letter != '\n')
        {
            out.print((int)(A.scramble(letter)));
            out.print(' ');
            letter = (char)System.in.read();
        }
        out.flush();
    }
}

import java.util.*;

import java.io.*;

class SelfSynchronizingScrambler

{

private char key, shift_register;

private static int pickbit(char val, int index)

{

return ((val >> index)%2);

}

public SelfSynchronizingScrambler() {}

public SelfSynchronizingScrambler(char key, char shift_register)

{

this.key = key;

this.shift_register = shift_register;

}

public void assignKey(char key) {this.key = key;}

public void assignRegister(char shift_register) {this.shift_register = shift_register;}

public char keyValue() {return key;}

public char registerValue() {return shift_register;}

public char scramble(char letter)

{

char output = 0;

for (char i = 0; i < 8; ++i)

{

int newbit = pickbit(letter, 7-i);

for (char j = 0; j < 8; ++j)

{

newbit ^= pickbit(this.key, 7-j) & pickbit(this.shift_register, 7-j);

}

output ^= (newbit << (7-i));

key = (char)((key >> 1) + (newbit << 7));

}

return output;

}

public char descramble(char letter)

{

char output = 0;

for(char i = 0; i < 8; ++i)

{

int oldbit = pickbit(letter, 7-i), scrambit = 0;

for(char j = 0; j < 8; ++j)

{

scrambit ^= pickbit(this.key, 7-j) & pickbit(this.shift_register, 7-j);

}

output ^= ((scrambit^oldbit) << (7-i));

key = (char)((key >> 1) + (oldbit << 7));

}

return output;

}

};

public class Main

{

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

{

SelfSynchronizingScrambler A = new SelfSynchronizingScrambler((char)5,(char)17);

PrintWriter out = new PrintWriter(System.out);

char letter = (char)System.in.read();

while(letter != '\n')

{

out.print((int)(A.scramble(letter)));

out.print(' ');

letter = (char)System.in.read();

}

out.flush();

}

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

Для зашифровки будем использовать стандартный алгоритм скремблирования. Скремблером будет переменная key, которая изначально равна [latex]5[/latex]. Выбирать из скремблера будем нулевой и четвёртый биты. Входные данные будут поступать в переменную input, после чего на них и на скремблере будет применяться функция scram.
Так как входные данные имеют формат unsigned char, считывание не прекратится никогда вплоть до принудительной остановки программы, ведь любые входные данные могут быть восприняты как символы. Для предотвращения этого, необходим символ, который будет служить «сигналом» для остановки программы. В нашем случае, это будет символ перехода на следующую строку.
Основная проблема задачи заключается в выводе зашифрованных данных, так как в результате скремблирования некоторые символы могут оказаться не отображаемыми. Дабы избежать подобной ситуации, зашифрованные данные будем выводить в шестнадцатеричном (для кода на Java — в десятичном) числовом формате.

Подзадача 2

Расшифровать входные данные из предыдущей подзадачи.

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

Некие зашифрованные данные, записанные в виде последовательности чисел шестнадцатеричного (для кода на Java — десятичного) формата.

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

Расшифрованные данные.

Тесты

Входные данные	Выходные данные
ea 27 33 77 25 11 66 75 5 3b e0 89 6b fa	Dogs eat meat.
fc 5a 80 ef 75 43 1e 92 9b 46 57 6	Scramble it!
ec 49 a0 c9 72 75 43 13 55 66 28 80 e7 ed d2 75 b7 bf 69 93 c7 df 4e d0 be 3f b1 de 5c f6 ea 6c 94 f5 8d 1f 86 80 aa 74 5e c7 9e 17 2 47 41 76 7c d4 a1	Base, base, it’s cheeseburger 1. Can you hear me?

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

#include <iostream>
using namespace std;

class self_synchronizing_scrambler
{
    unsigned char key;
    unsigned char shift_register;

    bool pickbit(const unsigned char val, const short index)
    {
        return ((val >> index)%2);
    }

    public:
    self_synchronizing_scrambler() {}

    self_synchronizing_scrambler(unsigned char key, unsigned char shift_register)
    {
        this->key = key;
        this->shift_register = shift_register;
    }

    void assign_key(unsigned char key) {this->key = key;}
    void assign_register(unsigned char shift_register) {this->shift_register = shift_register;}

    unsigned char key_value() {return key;}
    unsigned char register_value() {return shift_register;}

    void scramble(unsigned char &letter)
    {
        unsigned char output = 0;
        for (unsigned char i = 0; i < 8; ++i)
        {
            bool newbit = pickbit(letter, 7-i);
            for (unsigned char j = 0; j < 8; ++j)
            {
                newbit ^= pickbit(this->key, 7-j) & pickbit(this->shift_register, 7-j);
            }
            output ^= (newbit << (7-i));

            key = (key >> 1) + (newbit << 7);
        }
        letter = output;
    }

    void descramble(unsigned char &letter)
    {
        unsigned char output = 0;
        for(unsigned char i = 0; i < 8; ++i)
        {
            bool oldbit = pickbit(letter, 7-i), scrambit = 0;
            for(unsigned char j = 0; j < 8; ++j)
            {
                scrambit ^= pickbit(this->key, 7-j) & pickbit(this->shift_register, 7-j);
            }
            output ^= ((scrambit^oldbit) << (7-i));

            key = (key >> 1) + (oldbit << 7);
        }
        letter = output;
    }
};

int main()
{
    self_synchronizing_scrambler A(5,17);
    unsigned short scrambled;
    unsigned char output;

    while (cin >> hex >> scrambled)
    {
        output = scrambled;
        A.descramble(output);
        cout << output;
    }

    return 0;
}

#include <iostream>

using namespace std;

class self_synchronizing_scrambler

{

unsigned char key;

unsigned char shift_register;

bool pickbit(const unsigned char val, const short index)

{

return ((val >> index)%2);

}

public:

self_synchronizing_scrambler() {}

self_synchronizing_scrambler(unsigned char key, unsigned char shift_register)

{

this->key = key;

this->shift_register = shift_register;

}

void assign_key(unsigned char key) {this->key = key;}

void assign_register(unsigned char shift_register) {this->shift_register = shift_register;}

unsigned char key_value() {return key;}

unsigned char register_value() {return shift_register;}

void scramble(unsigned char &letter)

{

unsigned char output = 0;

for (unsigned char i = 0; i < 8; ++i)

{

bool newbit = pickbit(letter, 7-i);

for (unsigned char j = 0; j < 8; ++j)

{

newbit ^= pickbit(this->key, 7-j) & pickbit(this->shift_register, 7-j);

}

output ^= (newbit << (7-i));

key = (key >> 1) + (newbit << 7);

}

letter = output;

}

void descramble(unsigned char &letter)

{

unsigned char output = 0;

for(unsigned char i = 0; i < 8; ++i)

{

bool oldbit = pickbit(letter, 7-i), scrambit = 0;

for(unsigned char j = 0; j < 8; ++j)

{

scrambit ^= pickbit(this->key, 7-j) & pickbit(this->shift_register, 7-j);

}

output ^= ((scrambit^oldbit) << (7-i));

key = (key >> 1) + (oldbit << 7);

}

letter = output;

}

};

int main()

{

self_synchronizing_scrambler A(5,17);

unsigned short scrambled;

unsigned char output;

while (cin >> hex >> scrambled)

{

output = scrambled;

A.descramble(output);

cout << output;

}

return 0;

}

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

class SelfSynchronizingScrambler
{
    private char key, shift_register;

    private static int pickbit(char val, int index)
    {
        return ((val >> index)%2);
    }

    public SelfSynchronizingScrambler() {}

    public SelfSynchronizingScrambler(char key, char shift_register)
    {
        this.key = key;
        this.shift_register = shift_register;
    }

    public void assignKey(char key) {this.key = key;}
    public void assignRegister(char shift_register) {this.shift_register = shift_register;}

    public char keyValue() {return key;}
    public char registerValue() {return shift_register;}

    public char scramble(char letter)
    {
        char output = 0;
        for (char i = 0; i < 8; ++i)
        {
            int newbit = pickbit(letter, 7-i);
            for (char j = 0; j < 8; ++j)
            {
                newbit ^= pickbit(this.key, 7-j) & pickbit(this.shift_register, 7-j);
            }
            output ^= (newbit << (7-i));

            key = (char)((key >> 1) + (newbit << 7));
        }
        return output;
    }

    public char descramble(char letter)
    {
        char output = 0;
        for(char i = 0; i < 8; ++i)
        {
            int oldbit = pickbit(letter, 7-i), scrambit = 0;
            for(char j = 0; j < 8; ++j)
            {
                scrambit ^= pickbit(this.key, 7-j) & pickbit(this.shift_register, 7-j);
            }
            output ^= ((scrambit^oldbit) << (7-i));

            key = (char)((key >> 1) + (oldbit << 7));
        }
        return output;
    }
};

public class Main
{

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

        SelfSynchronizingScrambler A = new SelfSynchronizingScrambler((char)5,(char)17);
        char scrambled;

        while(in.hasNextInt())
        {
            scrambled = (char)in.nextInt();
            out.print(A.descramble(scrambled));
        }

        out.flush();
    }
}

import java.util.*;

import java.io.*;

class SelfSynchronizingScrambler

{

private char key, shift_register;

private static int pickbit(char val, int index)

{

return ((val >> index)%2);

}

public SelfSynchronizingScrambler() {}

public SelfSynchronizingScrambler(char key, char shift_register)

{

this.key = key;

this.shift_register = shift_register;

}

public void assignKey(char key) {this.key = key;}

public void assignRegister(char shift_register) {this.shift_register = shift_register;}

public char keyValue() {return key;}

public char registerValue() {return shift_register;}

public char scramble(char letter)

{

char output = 0;

for (char i = 0; i < 8; ++i)

{

int newbit = pickbit(letter, 7-i);

for (char j = 0; j < 8; ++j)

{

newbit ^= pickbit(this.key, 7-j) & pickbit(this.shift_register, 7-j);

}

output ^= (newbit << (7-i));

key = (char)((key >> 1) + (newbit << 7));

}

return output;

}

public char descramble(char letter)

{

char output = 0;

for(char i = 0; i < 8; ++i)

{

int oldbit = pickbit(letter, 7-i), scrambit = 0;

for(char j = 0; j < 8; ++j)

{

scrambit ^= pickbit(this.key, 7-j) & pickbit(this.shift_register, 7-j);

}

output ^= ((scrambit^oldbit) << (7-i));

key = (char)((key >> 1) + (oldbit << 7));

}

return output;

}

};

public class Main

{

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

{

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

SelfSynchronizingScrambler A = new SelfSynchronizingScrambler((char)5,(char)17);

char scrambled;

while(in.hasNextInt())

{

scrambled = (char)in.nextInt();

out.print(A.descramble(scrambled));

}

out.flush();

}

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

Для расшифровки будем применять обратный алгоритм к использованному в предыдущей задаче. Значение необходимого для расшифровки дескремблера нам известно из предыдущей задачи (а именно — [latex]5[/latex]), поэтому его мы и используем.
Входные данные будут считываться методом cin (для C++), где параметр hex будет указывать на то, что данные поданы в шестнадцатеричном формате. После считывания на входных данных будет применяться алгоритм дескремблирования, и итоговые данные будут выведены на экран.

Ссылки

Related Images:

A333. Наибольший общий делитель чисел последовательности

29/11/2016 by Вадим Гордийчук

Примечание: [latex]GCD[/latex] — Greatest common divisor (Наибольший общий делитель, НОД).

Задача

Даны натуральные числа [latex]m[/latex], [latex]n_1[/latex], [latex]\ldots[/latex], [latex]n_m[/latex] [latex]m \ge 2[/latex]. Вычислить [latex]GCD \left( n, \ldots, n_m \right)[/latex], воспользовавшись для этого соотношением [latex]GCD \left( n, \ldots, n_k \right) = GCD \left( GCD \left( n, \ldots, n_{k-1} \right), n_k \right)[/latex] [latex]\left( k = 3, \ldots, n \right)[/latex] и алгоритмом Евклида.

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

Количество чисел [latex]m[/latex]; числа [latex]n_1[/latex], [latex]\ldots[/latex], [latex]n_m[/latex].

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

[latex]GCD \left( n_1, \ldots, n_m \right)[/latex].

Тесты

Входные данные					Выходные данные
2	3	4			1
2	4	8			4
4	24	23	40	90	1
4	36	48	20	24	4
3	30	738	1926		6

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

#include <iostream>
using namespace std;

unsigned long long gcd(unsigned long long m, unsigned long long n)
{
    return (n != 0) ? gcd(n, m%n) : m;
}

int main()
{
    unsigned long long m, n, result;
    cin >> m >> result;
    for (unsigned long long i = 2; i <= m; i++)
    {
        cin >> n;
        result = gcd(result, n);
        if (result == 1) m = 1; //same as break
    }
    cout << result << endl;
    return 0;
}

#include <iostream>

using namespace std;

unsigned long long gcd(unsigned long long m, unsigned long long n)

{

return (n != 0) ? gcd(n, m%n) : m;

}

int main()

{

unsigned long long m, n, result;

cin >> m >> result;

for (unsigned long long i = 2; i <= m; i++)

{

cin >> n;

result = gcd(result, n);

if (result == 1) m = 1; //same as break

}

cout << result << endl;

return 0;

}

import java.util.*;

public class Main
{
    public static long gcd(long m, long n)
    {
        if (n != 0)
            return gcd(n, m%n);
        else
            return m;
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        long m = in.nextLong(), n, result = in.nextLong();
        
        for(long i = 2; i <= m; ++i)
        {
            n = in.nextLong();
            result = gcd(result, n);
            if (result == 1) m = 1; //same as break
        }
        System.out.println(result);
    }
}

import java.util.*;

public class Main

{

public static long gcd(long m, long n)

{

if (n != 0