e-olymp 6975. Магический Множитель

19/06/2021 by Tychenko

Задача

Ельфійські раси Середзем’я вважали, що деякі числа є більш важливими, ніж інші. При використанні конкретного кількості $n$ металу для виплавки меча, вони вважають, що меч буде найбільш потужним, якщо його товщина $k$ обрана відповідно до наступного правила:

Визнач невід’ємне ціле число $n$. Знайти найменше $k$, для якого десяткове представлення чисел в послідовності

$n, 2n, 3n, 4n, 5n,\ldots, kn$

містить всі десять цифр (від $0$ до $9$) як мінімум один раз?

Лорд Елронд з Рівенделл доручив Вам розробити алгоритм, який знайде оптимальну товщину $k$ для будь-якого заданого кількості металу $n$.

Вхідні дані

Кожен рядок містить одне число $n$ $(1 \leqslant n \leqslant 200000000)$.

Вихідні дані

Для кожного тесту вивести в окремому рядку необхідне значення $k$ — таке що кожна цифра від $0$ до $9$ зустрічається хоча б один раз.

Тести

№	Вхідні дані	Вихідні дані
1	1 10 123456789 3141592	10 9 3 5
2	200000000	45

№

Вхідні дані

Вихідні дані

123456789

3141592

200000000

Код

#include <iostream>
using namespace std;
bool Cheking(bool arr[]) {
  bool q = true;
  for (int i = 0; i < 10; i++) if (arr[i] == false) q = false;
  if (q == false) return true;
  else return false;
}
void Filling(bool arr[], long a) {
  int b;
  while (a > 0) {
    b = a % 10;
    arr[b] = (bool)1;
    a = (a - b) / 10;
  }
}
int main() {
  long n, k;
  bool arr[10];
  while (cin >> n) {
    k = 0;
    for (int i = 0; i < 10; i++) arr[i] = 0;
    while (Cheking(arr)) {
      k++;
      Filling(arr, k * n);
    }
    cout << k << '\n';
  }
}

#include <iostream>

using namespace std;

bool Cheking(bool arr[]) {

bool q = true;

for (int i = 0; i < 10; i++) if (arr[i] == false) q = false;

if (q == false) return true;

else return false;

}

void Filling(bool arr[], long a) {

int b;

while (a > 0) {

b = a % 10;

arr[b] = (bool)1;

a = (a - b) / 10;

}

int main() {

long n, k;

bool arr[10];

while (cin >> n) {

k = 0;

for (int i = 0; i < 10; i++) arr[i] = 0;

while (Cheking(arr)) {

k++;

Filling(arr, k * n);

}

cout << k << '\n';

}

Рішення

Для знаходження числа $k$ треба всі отриманні цифри (від $0$ до $9$), які зустрічаються в числовій послідовності $n, 2n, 3n, 4n, 5n,\ldots, kn$, відзначати як знайдені. Для цього було використано масив з $10$ елементів, де поіндексово (відповідно до цифри) відзначалася знайденна цифра, яка зустрічалося в числовій послідовності хоча б один раз. Пошук числа $k$ здійнувався за допомогою циклу, де методом поступового збільшення $k$, здійснювалася перевірка числа. Перевірка рахувалося успішною і завершувала цикл, якщо в масиві було відзначено всі цифри. В разі неуспішної перевірки цикл продовжувався.

Посилання

Задача на e-olymp.
Код рішення на Replit.
Код рішення на Ideone.

Related Images:

e-olymp 8666. Коровий котильон

18/01/2020 by Нина Хоробрых

Задача

В коровьем котильоне — причудливом танце весны — участвуют коровы (обозначаются $ «\gt»$) и быки (обозначаются $ «\lt»$), они кланяются друг другу во время танца. Схематически обозначим пару кланяющихся животных следующим образом: $ «\gt \lt»$. Иногда вторая пара скота может находиться между кланяющейся парой: $ «\gt \gt \lt \lt»$.

Иногда и большее количество коров и быков встречается на танцевальной площадке: $ «\gt \gt \lt \lt \gt \lt»$ (имеется вторая пара кланяющихся коров справа). Сложные аранжировки могут быть совершенно легальными танцевальными образованиями:

Фермер Джон замечает, что бездомная корова иногда пробирается в группу и разбалансирует ее: $ «\gt \gt \lt \lt \lt \lt»$. Это строго запрещено; Фермер Джон хочет наказать нарушителей.

Фермер Джон скопировал данные о том, как $500$ коров участвуют в танцевальной линии, и задался вопросом, правильно ли уравновешена танцевальная линия (то есть весь скот может быть спарен как минимум одним способом чтобы правильно кланяться друг другу). Он скопировал только направление, в котором кланялась каждая корова, без каких-либо лишних пробелов, чтобы можно было определить, какая корова какому быку кланяется. Строки похожи на пример из предыдущего абзаца: «>><&lt». Фермер Джон хочет чтобы Вы написали программу, определяющую правильность танцевальной линии.

Фермер Джон имеет $n$ записей танца $P_{i}$ состоящих из символов $ «\gt»$ и $ «\lt»$;’ различной длины $K_{i} (1 \leqslant K_{i} \leqslant 200)$. Выведите «legal» для тех строк, которые содержат правильные пары кланяющихся коров и «illegal» иначе.

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

Первая строка содержит одно число $n$ $(1 \leqslant n \leqslant 1000)$. Каждая из следующих $n$ строк содержит число и строку из $K$ символов $ «\gt»$ и $ «\lt»$: $K_{i}$и $P_{i}$.

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

Выведите в каждой строке «legal» или «illegal» в зависимости от того, содержит ли соответствующая входная строка допустимую конфигурацию.

Тесты

№	Входные данные	Выходные данные
1	2 6 >><<>< 4 ><<>	legal illegal
2	3 8 <>><><>< 6 ><>><< 9 >><>><<><	illegal legal illegal
3	5 4 ><>< 10 >>><<>><<< 8 >><<<>>< 3 >>< 12 ><>><>>><<<<	legal legal illegal illegal legal

Код

#include <iostream>
using namespace std;

int main() {
  int n, q, count;
  char ungulate;
  bool b;
  cin >> n;
 
  for ( int i = 0; i < n; i++ ) {
    int count = 0;
    b = true;
    cin >> q;
   
    for ( int j = 0; j < q; j++ ) {
      cin >> ungulate;
      if ( ungulate == '>' ) {
        count++;
      }
      else {
        count--;
      }
      if ( count < 0 ) {
        b = false;
      }
    }
    
    if ( count != 0 ) {
        b = false;
    }
    
    if ( b ) {
        cout << "legal" << endl; 
      } 
    else {
        cout << "illegal" << endl;
      }
  }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, q, count;

char ungulate;

bool b;

cin >> n;

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

int count = 0;

b = true;

cin >> q;

for ( int j = 0; j < q; j++ ) {

cin >> ungulate;

if ( ungulate == '>' ) {

count++;

}

else {

count--;

}

if ( count < 0 ) {

b = false;

}

if ( count != 0 ) {

b = false;

}

if ( b ) {

cout << "legal" << endl;

}

else {

cout << "illegal" << endl;

}

return 0;

}

Решение

Пара начинается с коровы и каждой из них должен соответствовать один бык, стоящий после неё. Для того, чтобы проверить правильность танцевальной линии, будем фиксировать количество встречающихся коров, а при встрече быка это число уменьшать. Отрицательное значение показывает на наличие быка без пары. В таком случае баланса уже не будет и проверять дальше смысла нет. В случае конечного результата $0$, в линии соблюден баланс — у каждого есть своя пара.

Ссылки

Код на ideone
Задача на e-olymp
Засчитанное решение на e-olymp

Related Images:

e-olymp 8546. Найдите сумму

21/12/2019 by Никита Рудь

Задача

По заданному натуральному числу $n$ вычислите сумму

$\frac{1}{1\cdot2}+\frac{1}{2\cdot3}+ … +\frac{1}{n\cdot(n+1)}$

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

Одно натуральное число $n$ ($n$ $⩽$ $1000$).

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

Выведите сумму с $6$ десятичными знаками.

Тесты

№	Входные данные	Выходные данные
1	1	0.500000
2	5	0.833333
3	12	0.923077

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

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

int main() {
    int n;
    double sum = 0;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        sum += 1. / (i * (i + 1));
    }
    cout << fixed << setprecision(6) << sum;
}

#include <iostream>

#include <iomanip>

using namespace std;

int main() {

int n;

double sum = 0;

cin >> n;

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

sum += 1. / (i * (i + 1));

}

cout << fixed << setprecision(6) << sum;

}

Решение

Для вычисления данной суммы необходимо сложить $n$ слагаемых вида

$\frac{1}{i \cdot (i + 1)}$

начиная с $i = 1$ и с шагом в единицу до $i = n$.

Ссылки

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

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

Related Images:

e-olymp 7841. Нечетные элементы

21/12/2019 by Алексей Богач

Условие

Задана последовательность из $n$ целых чисел. Выведите все ее нечетные элементы.

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

Первая строка содержит число $n$. Следующая строка содержит $n$ ($n$ $⩽$ $100$) целых чисел, которые по модулю не превосходят $100$.

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

Вывести все нечетные элементы последовательности в том же порядке как они встречаются на входе.

Тесты

№	Входные данные	Выходные данные
1	7 14 17 16 3 7 19 9	17 3 7 19 9
2	5 2 4 3 11 5	3 11 5

Код

#include <iostream>
using namespace std;

int main() {
    int n, a;
    cin >> n;
    for (int i = 0; i < n; ++i) { 
        cin >> a;
        if (a % 2) cout << a << " ";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, a;

cin >> n;

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

cin >> a;

if (a % 2) cout << a << " ";

}

return 0;

}

Решение

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

Ссылки

Задача на e-olymp
Код программы на Ideone

Related Images:

e-olymp 8680. Чётные соседи

20/12/2019 by Алина Малыхина

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

Задана последовательность целых чисел. Подсчитать количество элементов, у которых чётные соседи.

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

В первой строке задано количество элементов последовательности $n$ $(n \leqslant 100)$. Во второй строке заданы сами элементы, значение каждого из которых по модулю не превышает $100$.

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

Вывести в одной строке количество элементов последовательности с чётными соседями.

Тесты

№	Входные данные	Выходные данные
1	6 1 2 3 4 5 6	2
2	9 3 6 3 5 2 9 1 2 5	0
3	3 2 1 2	1
4	6 13 24 54 66 44 77	2
5	4 100 224 666 222	2

Программный код

#include <iostream>
using namespace std;

int main(){
    int i=1, n, prev, pres, fut, count = 0;
    cin >> n;
    cin >> prev; //вводим предыдущий элемент
    cin >> pres; //вводим текущий элемент
    while ((cin >> fut) && (i<n)) {
        if (prev % 2 == 0 && fut % 2 == 0) 
            count++;
        prev = pres; //приравниваем предыдущий к текущему
        pres = fut; //приравниваем текущий к будущему
        i++;
    }
    cout << count;
    return 0;
}

#include <iostream>

using namespace std;

int main(){

int i=1, n, prev, pres, fut, count = 0;

cin >> n;

cin >> prev; //вводим предыдущий элемент

cin >> pres; //вводим текущий элемент

while ((cin >> fut) && (i<n)) {

if (prev % 2 == 0 && fut % 2 == 0)

count++;

prev = pres; //приравниваем предыдущий к текущему

pres = fut; //приравниваем текущий к будущему

i++;

}

cout << count;

return 0;

}

Решение

Идея решения задачи состоит в том, чтобы создать три переменные: $prev$ (предыдущий), $pres$ (настоящий, текущий) и $fut$ (будущий). Затем в цикле мы перезаписываем эти переменные т.е.: настоящий становится прошлым, будущий настоящим, а новый будущий мы читаем из cin. Так же, в ходе решения задачи обнаружилась проблема с чтением количества элементов. Допустим, если мы записали, что $n=6$, а дальше ввели $10$ элементов, то количество элементов с чётными соседями будет считаться для $10$ элементов. Чтобы избежать этого мы ограничиваем количество читаемых элементов с помощью счётчика i++ и цикла while.

Ссылки

Задача на e-olymp
Код программы на Ideone
Засчитанное решение

Related Images:

e-olymp 8283. Музыка

14/12/2019 by Евгений Радчин

Задача

Малыши и малышки очень любили музыку, а Гусля был замечательный музыкант. У него были разные музыкальные инструменты, и он часто играл на них. Их было много, поэтому он развесил их на стенах своей комнаты. Инструмент, расположенный справа от входной двери имел номер $1$, дальше они нумеровались по кругу, а последний инструмент с номером $n$ висел слева от этой двери.

Малыши часто просили его научить играть на каком-нибудь инструменте. Гусля не отказывал, но сначала предлагал взять инструмент с первым номером, а если ученику хотелось играть на другом, то он выбирал шестой следующий по кругу и так далее. Напишите программу, которая определяла номер попытки, с которой ученик мог получить желаемый инструмент с номером $k$.

Например, если количество инструментов $n = 11$, то последовательность будет следующей: $(1) 2 3 4 5 6 (7) 8 9 10 11 1 (2) 3 4 5 6 7 (8) 9 10 11 1 2 (3) 4 5$ …, то есть при $k = 3$ инструмент с номером $3$ можно было бы получить с пятой попытки.

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

Два натуральных числа $n$ и $k$ $(1 \leqslant k \leqslant n \leqslant 100)$.

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

Вывести номер попытки, в который «выпадал» инструмент с номером $k$. Если это никогда не происходило, следует вывести $0$.

Тесты

№	Входные данные	Выходные данные
1	11 3	5
2	6 2	0
3	13 13	3
4	9 8	0
5	5 5	5

Код

#include <iostream>  
using namespace std;

int main() {
    int quantity, instrument, counter = 1;
    cin >> quantity >> instrument;
    if ((quantity == 6 && instrument != 1) || (quantity == instrument && quantity % 2 == 0)) {
        cout << 0;
    } else if (quantity == instrument) {
        for (int num = 1; num % quantity != 0; num += 6) {
            if (num != 1 && num % quantity == 1) {
                cout << 0;
                return 0;
            } else {
                counter++;
            }   
        }
        cout << counter;
    } else {
        for (int num = 1; num % quantity != instrument; num += 6) {
            if (num != 1 && num % quantity == 1) {
                cout << 0;
                return 0;
            } else {
                counter++;
            }   
        }
        cout << counter;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int quantity, instrument, counter = 1;

cin >> quantity >> instrument;

if ((quantity == 6 && instrument != 1) || (quantity == instrument && quantity % 2 == 0)) {

cout << 0;

} else if (quantity == instrument) {

for (int num = 1; num % quantity != 0; num += 6) {

if (num != 1 && num % quantity == 1) {

cout << 0;

return 0;

} else {

counter++;

}

cout << counter;

} else {

for (int num = 1; num % quantity != instrument; num += 6) {

if (num != 1 && num % quantity == 1) {

cout << 0;

return 0;

} else {

counter++;

}

cout << counter;

}

return 0;

}

Решение

Для решения задачи нам необходимо рассмотреть ряд натуральных чисел, начиная с единицы и прибавляя каждый раз $6$. С помощью операции деления с остатком мы можем реализовать алгоритм нахождения номера музыкального инструмента. Однако логика решения изменяется в зависимости от введенных пользователем данных. Имеется два случая:

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

В первом случае мы рассматриваем две ситуации:
1) если пользователь вводит количество инструментов $6$, то единственным решением будет инструмент под номером $1$, так как Гусля выбирает инструменты через $6$ штук по кругу;
2) если количество инструментов не равно $6$ то мы реализовываем алгоритм нахождения номера путем деления с остатком, а именно: если текущее число при делении на количество инструментов не дает в остатке искомый номер, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае мы нашли число попыток.
Еще здесь, так же, как и во втором случае, есть подводный камень: если мы уже сделали какое-то количество попыток и текущее число при делении на количество инструментов дает в остатке $1$, мы никогда не попадем на нужный нам номер инструмента.

Во втором случае мы также рассматриваем две ситуации:
1) если количество инструментов делится нацело на $2$, то нам никогда не выпадет нужный инструмент;
2) если текущее число при делении на количество инструментов не дает в остатке $0$, мы прибавляем $1$ к числу попыток, а число увеличиваем на $6$, в противном случае ответ найден.
Также не забываем про подводный камень, указанный выше.

Ссылки

Условие задачи на e-olymp
Код программы на ideone.com
Засчитанное решение на e-olymp

Related Images:

e-olymp 6387. Острова в потоке данных

13/12/2019 by Нина Хоробрых

Задача

Задана последовательность целых чисел $a_{1}, a_{2}, a_{3}, \ldots, a_{n}$. Островом в последовательности называется набор последовательно идущих чисел, каждый из которых больше элементов, находящихся перед и после самой подпоследовательности. В приведенных ниже примерах каждый остров в последовательности обозначен внизу скобкой. Скобка острова, который находится в другом острове, находится под соответствующей скобкой.

Напишите программу, на вход которой поступает последовательность из $15$ неотрицательных целых чисел, где каждое число отличается от предыдущего не более чем на $1$, и выводит количество островов в последовательности.

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

Первая строка содержит количество тестов $p \ (1 \leqslant p \leqslant 1000)$.

Каждый тест состоит из одной строки. Она содержит номер теста $k$, за которым следует $15$ неотрицательных целых чисел, разделенных пробелом. Первое и последнее число последовательности равны $0$. Каждое число отличается от предыдущего не более чем на $1$.

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

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

Тесты

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

Код

#include <iostream>
using namespace std;
#define AMNT 15
 
int main() {
    int p, k;
    int current, previous; 
    cin >> p;
    while ( p--) {
        cin >> k; 
        int isl = 0; 
        cin >> current;       // ввод 1-го элемента последовательности
        previous = current;     
        for ( int j = 1; j < AMNT ; j++ ){
            cin >> current;        //ввод остальных элементов
            if ( current > previous ) { 
                isl++;
            }
            previous = current;
        }
        cout << k << " " << isl << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

#define AMNT 15

int main() {

int p, k;

int current, previous;

cin >> p;

while ( p--) {

cin >> k;

int isl = 0;

cin >> current; // ввод 1-го элемента последовательности

previous = current;

for ( int j = 1; j < AMNT ; j++ ){

cin >> current; //ввод остальных элементов

if ( current > previous ) {

isl++;

}

previous = current;

}

cout << k << " " << isl << endl;

}

return 0;

}

Решение

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

Ссылки

Код на ideone
Задача на e-olymp
Засчитанное решение на e-olymp

Related Images:

e-olymp 2524. Строки Фибоначчи

26/05/2019 by Дария Даниленко

Задача

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

Одним из примеров строк, задаваемых рекуррентным соотношением являются строки Фибоначчи $F_{0} = a$, $F_{1} = b$, … . Они задаются следующим образом: $F_{0} = a$, $F_{1} = b$, $F_{i} = F_{i-2}F_{i-1}$, $i >1$. Первые семь строк Фибоначчи выглядят следующим образом: $a$, $b$, $ab$, $bab$, $abbab$, $bababbab$, $abbabbababbab$.

Дима занимается в кружке олимпиадного программирования и интересуется алгоритмами на строках. Недавно он узнал о строках Фибоначчи. Он быстро понял, что их длина с увеличением номера $n$ растет очень быстро, поэтому задача нахождения всех символов строки $F_{n}$ требует слишком большого объема памяти. Поэтому он решил ограничиться задачей нахождения некоторых символов.

Напишите программу, которая находит $k$-ый символ строки $F_{n}$.

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

Первая строка содержит количество тестов $t$ ($1 ≤ t ≤ 100$). Каждая из следующих $t$ строк содержит два целых числа $n$ и $k$ ($0 ≤ n ≤ 45$, $1 ≤ k ≤ |F_{n}|$, через $|F_{n}|$ обозначена длина строки $F_{n}$, позиции символов в строке нумеруются с единицы).

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

Выведите $t$ строк, каждая из которых содержит $k$-ый символ строки $F_{n}$.

Тесты

Входные данные	Выходные данные
4 0 1 1 1 3 2 7 7	a b a a
1 10 15	a
6 45 6 38 30 6 5 24 40 0 1 2 2	b a b b a b

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

#include <iostream>
using namespace std;

int fib[45];

char solve(int n, int k) {
    if (n == 0) return 'a';
    if (n == 1) return 'b';
    if (k <= fib[n - 2]) return solve(n - 2, k);
    return solve(n - 1, k - fib[n - 2]);
}

int main() {
    int n, k, tests;
    fib[0] = 1;
    fib[1] = 1;
    for (int i = 2; i < 45; i++) fib[i] = fib[i - 1] + fib[i - 2];
    cin >> tests;
    while (tests--) {
        cin >> n >> k;
        cout << solve(n, k) << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int fib[45];

char solve(int n, int k) {

if (n == 0) return 'a';

if (n == 1) return 'b';

if (k <= fib[n - 2]) return solve(n - 2, k);

return solve(n - 1, k - fib[n - 2]);

}

int main() {

int n, k, tests;

fib[0] = 1;

fib[1] = 1;

for (int i = 2; i < 45; i++) fib[i] = fib[i - 1] + fib[i - 2];

cin >> tests;

while (tests--) {

cin >> n >> k;

cout << solve(n, k) << endl;

}

return 0;

}

Решение

Воспользуемся тем, что длина $i$-той строки Фибоначчи будет равна $i$-тому числу Фибоначчи, так как для них справедливо одно и то же рекуррентное соотношение. Заводим массив fib[45]; , куда мы вычислим первые ($n ≤ 45$) числа Фибоначчи. Функция solve(int n, int k) находит $k$-ый символ строки $F_{n}$: так как $F_{i} = F_{i-2}F_{i-1}$, то если $k ≤ |F_{n-2}|$, то $k$-ый символ строки следует искать в $F_{n-2}$, в другом случае следует искать $(k — F_{n-2})$-ый символ в $F_{n-1}$. Таким образом, постепенно углубляясь в рекурсию, программа будет иметь дело с задачами все меньших размеров, пока наконец не выйдет на одну из единичных строк ( n == 0 или n == 1 ), и не выведет $a$ или $b$ соответственно.

Ссылки

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

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

Related Images:

e-olymp 919. Номер на 3

24/01/2019 by Лиза Севастьянова

Задача

Условие

Задана последовательность действительных чисел $a_{1}$, $a_{2}$,…, $a_{n}$. Определить сумму и количество положительных элементов, индексы которых делятся на $3$ без остатка.

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

В первой строке задано количество элементов $n$ ($n \leq 100$) в последовательности. В следующей строке находится $n$ вещественных чисел, значение каждого из которых по модулю не превышает $100$.

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

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

Тесты

№	Входные данные	Выходные данные
1	6 6 7.5 2.1 2.0 0 -3	1 2.10
2	3 12 0.33 -14	0 0.00
3	1 -3.4	0 0.00
4	12 0 15.3 -1 144 0.333 17.5 -69 456 2.5 0 3 13	3 33.00

Решение

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

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

#include <iostream>
#include <iomanip> // для setprecision()
using namespace std;

int main() {
    int n; // количество элементов последовательности
    cin >> n;
    int num = 0; // счётчик количества выбранных элементов
    double sum = 0; // сумма выбранных элементов
    for (int i = 1; i <= n; i++) { // цикл для просмотра всех элементов последовательности
        double a; // элемент последовательности
        cin >> a;
        if ((i%3) == 0 and a > 0) { // проверка на соответствие условиям
            num++;
            sum += a;
        }
    }
    cout << num << " " << fixed << setprecision(2) << sum << endl;
    return 0;
}

#include <iostream>

#include <iomanip> // для setprecision()

using namespace std;

int main() {

int n; // количество элементов последовательности

cin >> n;

int num = 0; // счётчик количества выбранных элементов

double sum = 0; // сумма выбранных элементов

for (int i = 1; i <= n; i++) { // цикл для просмотра всех элементов последовательности

double a; // элемент последовательности

cin >> a;

if ((i%3) == 0 and a > 0) { // проверка на соответствие условиям

num++;

sum += a;

}

cout << num << " " << fixed << setprecision(2) << sum << endl;

return 0;

}

Ссылки

Related Images:

e-olymp 2060 Сказка о яблоке

20/11/2018 by Николай Козиний

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

Задача

Однажды царь наградил крестьянина яблоком из своего сада. Пошёл крестьянин к саду и видит: весь сад огорожен $n$ заборами, в каждом заборе только одни ворота, и в каждых воротах стоит сторож. Подошёл крестьянин к первому сторожу и показал царский указ, а сторож ему в ответ: «Иди возьми, но при выходе отдашь мне половину тех яблок, что несёшь, и ещё одно». То же ему сказали и второй, и третий сторож и т.д. Сколько яблок должен взять крестьянин, чтобы после расплаты со сторожами у него осталось одно яблоко?

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

Количество заборов $n (1 \leqslant n \leqslant 62)$ в саду.

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

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

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1	4
2	3	22
3	30	50331646
4	60	3458764513820540926
5	62	13835058055282163710

Решение

Циклы

Последовательность необходимых количеств яблок задается формулой $x_{n+1}=2 \cdot (x_{n}+1);x_{1}=1.$ Мы можем поочередно вычислять элементы последовательности через цикл.

#include <iostream>
int main() {
    int n;
    std::cin>>n;
    unsigned long long k = 1;
    for(int i = 0; i<n; i++)k = (k + 1) * 2;
    std::cout<<k;
}

#include <iostream>

int main() {

int n;

std::cin>>n;

unsigned long long k = 1;

for(int i = 0; i<n; i++)k = (k + 1) * 2;

std::cout<<k;

}

Линейное решение

Преобразуем исходное выражение для $x_{n+1}=2 \cdot x_{n}+2.$ Можно видеть, что каждая следующая итерация увеличивает степень всех двоек входящих в предыдущую на 1 и добавляет 2. Выпишем формулу для $x_{n+m}=2^{m}x_n+2^{m-1}x_n+\cdots+2.$ Можно увидеть, что $x_{n+m}$ содержит слагаемое $2^{m}x$, а так же сумму слагаемых вида $\displaystyle \sum_{i=1}^{m}2^i \displaystyle.$ Если учесть, что $x_{1}=1$, то $\displaystyle x_n=2^{n}+ \sum_{i=1}^{n}2^i \displaystyle=2^{n+1}+2^n-2=2^{n}\cdot(2+1) -2.$ Следовательно формула $n$-го члена — [latex]x_n=3\cdot 2^n-2.[/latex]

#include <iostream>
int main() {
    int n;
    std::cin>>n;
    unsigned long long t = 2;
    std::cout<<3*(t<<n-1)-2;
}

#include <iostream>

int main() {

int n;

std::cin>>n;

unsigned long long t = 2;

std::cout<<3*(t<<n-1)-2;

}

Решения на ideone

Related Images:

e-olymp 9. N-значные числа

02/01/2018 by Андрей Лисовой

Задача

Найти количество [latex]N[/latex]-значных чисел, у которых сумма цифр равна их произведению. Вывести наименьшее среди таких чисел для заданного [latex]N[/latex] ([latex]N < 10[/latex]).

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

Число [latex]N[/latex] не превышающее [latex]10[/latex].

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

В выходном файле через пробел вывести [latex]2[/latex] числа: количество искомых чисел и наименьшее среди них.

Тесты

Входные данные	Выходные данные
[latex]1[/latex]	[latex]10[/latex] [latex]0[/latex]
[latex]2[/latex]	[latex]1[/latex] [latex]22[/latex]
[latex]4[/latex]	[latex]12[/latex] [latex]1124[/latex]
[latex]5[/latex]	[latex]40[/latex] [latex]11125[/latex]
[latex]9[/latex]	[latex]144[/latex] [latex]111111129[/latex]

Код программы (Цикл)

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

int Sum(int a) {
    int sum=0;
    while(a>0) {
        sum+=a%10;
        a/=10;
    }
    return sum;
}

int Mult(int a) {
    int mult=1;
    while(a>0) {
        mult*=a%10;
        a/=10;
    }
    return mult;
}

int main() {
    int n,ch=0,sum=0,mult=0,a;
    bool b=true;
    cin>>n;
    if(n==1) cout<<10<<" "<<0;
    else {
        if(n>1 and n<8) {
            for(int i=pow(10,n-1); i<pow(10,n); i++) {
                sum=Sum(i);
                mult=Mult(i);
                if((sum==mult) and b==true) {a=i;ch++;b=false;}
                else {
                    if(sum==mult) ch++;
                }
            }
            cout<<ch<<" "<<a;
        }
        else {
            if(n==8) cout<<224<<" "<<11111128;
            if(n==9) cout<<144<<" "<<111111129;
        }
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int Sum(int a) {

int sum=0;

while(a>0) {

sum+=a%10;

a/=10;

}

return sum;

}

int Mult(int a) {

int mult=1;

while(a>0) {

mult*=a%10;

a/=10;

}

return mult;

}

int main() {

int n,ch=0,sum=0,mult=0,a;

bool b=true;

cin>>n;

if(n==1) cout<<10<<" "<<0;

else {

if(n>1 and n<8) {

for(int i=pow(10,n-1); i<pow(10,n); i++) {

sum=Sum(i);

mult=Mult(i);

if((sum==mult) and b==true) {a=i;ch++;b=false;}

else {

if(sum==mult) ch++;

}

cout<<ch<<" "<<a;

}

else {

if(n==8) cout<<224<<" "<<11111128;

if(n==9) cout<<144<<" "<<111111129;

}

return 0;

}

Решение задачи (Цикл)

Для решения задачи напишем функции [latex]Sum[/latex] и [latex]Mult[/latex]. Первая считает сумму цифр [latex]N[/latex]-значного числа, а вторая — произведение цифр. С помощью цикла создаем последовательность [latex]N[/latex]-значных чисел и вводим каждое из них в функции [latex]Sum[/latex] и [latex]Mult[/latex]. Если возращаемые значения равны между собой, то мы выводим данное число и присваиваем переменной [latex]b[/latex] значение [latex]false[/latex]. Также продолжаем считать количество [latex]N[/latex]-значных чисел у которых сумма цифр равна их произведению. Также создаем случаи, когда [latex]N=1[/latex], [latex]N=8[/latex] и [latex]N=9[/latex], ибо в цикле эти значения долго считаются. Задача решена.

Код программы (Массив)

#include <iostream>
using namespace std;

int main() {
    int x[18]= {10,0,1,22,6,123,12,1124,40,11125,30,111126,84,1111127,224,11111128,144,111111129};
    int n;
    cin>>n;
    cout<<x[2*n-2]<<" "<<x[2*n-1];
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int x[18]= {10,0,1,22,6,123,12,1124,40,11125,30,111126,84,1111127,224,11111128,144,111111129};

int n;

cin>>n;

cout<<x[2*n-2]<<" "<<x[2*n-1];

return 0;

}

Решение задачи (Массив)

Для решения задачи заранее просчитали все ответы и записали их в массив [latex]x[/latex]. Так как ответы идут подряд составили формулу для вывода искомых значений: для количества чисел у которых сумма цифр совпадает с их произведением — [latex]2n-2[/latex], для минимального числа — [latex]2n-1[/latex]. Задача решена (также задачу можно решить с помощью циклов).

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com (цикл)
Код решения на ideone.com (массив)

Related Images:

e-olymp 165. Симметрия

21/12/2017 by Даниил Крутоголов

Задача

Предприимчивая и умелая рукодельница решила подзаработать изготовлением «фенечек» из бисера. Любительница симметрии в искусстве, она использовала в своих орнаментах бусинки разных цветов (будем обозначать цвет целым положительным числом) по следующим правилам:

1) при длине ряда рисунка равной [latex]1[/latex] использовала бусинку первого цвета;

2) при длине ряда рисунка равной [latex]3[/latex] использовала бусинки двух цветов: [latex]1 2 1[/latex];

3) при необходимости добавления в рисунок еще одного цвета строился ряд: [latex]1 2 1 3 1 2 1[/latex] и так всякий раз в зависимости от числа используемых цветов, например, при использовании четырех цветов: [latex]1 2 1 3 1 2 1 4 1 2 1 3 1 2 1[/latex].

Напишите программу, которая помогла бы автоматизировать подбор цвета бусинки в ряду по её порядковому номеру.

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

В первой строке целое число [latex]k[/latex] [latex] (1 ≤ k ≤ 10^9) [/latex] – номер бусинки, цвет которой нужно определить, в ряду рисунка. Нумерация бусинок в ряду начинается с единицы.

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

В первой строке одно целое число – номер цвета заданной бусинки.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	[latex]10[/latex]	[latex]2[/latex]
2	[latex]116[/latex]	[latex]3[/latex]
3	[latex]1[/latex]	[latex]1[/latex]
4	[latex]454[/latex]	[latex]2[/latex]
5	[latex]12301230[/latex]	[latex]2[/latex]

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

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    int n, m;
    double k;
    cin >> n;
    m = log2(n);
    k = log2(n);
    while (m != k){
        n = n - (pow(2,m));
        m = log2(n);
        k = log2(n);
    }
    cout << m + 1;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

int n, m;

double k;

cin >> n;

m = log2(n);

k = log2(n);

while (m != k){

n = n - (pow(2,m));

m = log2(n);

k = log2(n);

}

cout << m + 1;

return 0;

}

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

Рассматривая ряды с большим количеством цветов можно заметить закономерность: каждый чётный элемент равен единице, каждый последующий новый цвет будет на месте [latex]n·2[/latex]. Отсюда следует соответствие [latex]n[/latex] и [latex]2^{n-1}[/latex]. Формула для нахождения среднего элемента — [latex]\log_{2}n[/latex]. Программа будет искать средний элемент всегда, пока не найдёт нужный нам. Для чисел, из которых целый логарифм извлечь нельзя, найдем ближайший к нему и от числа отнимем [latex]2[/latex] в степени [latex]\log_{2}n[/latex]. К полученному ответу добавляем единицу, из-за приведённой ранее формулы [latex]2^{n-1}[/latex], и получаем правильный ответ.

Ссылки

• Задача на e-olymp.

• Решение на сайте ideone.

Related Images:

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

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

Задача

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

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

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

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

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

Тесты

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

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

#include <iostream>
using namespace std;

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

#include <iostream>

using namespace std;

int main()

{

unsigned long long int n, a, answer;

cin >> n >> a;

if (a > 1)

{

answer = n*a;

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

answer = (answer+i)*a;

}

else

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

cout << answer;

return 0;

}

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

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

import java.util.*;

import java.lang.*;

import java.io.*;

public class Main

{

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

{

Scanner in = new Scanner(System.in);

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

if (a > 1)

{

ans = n*a;

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

ans = (ans+i)*a;

}

else

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

System.out.println(ans);

}

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

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

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

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

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

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

Ссылки

Related Images:

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:

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

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

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

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

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

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

Тесты

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

Код на C++

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

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

#include <iostream>

#include <vector>

using namespace std;

int main() {

vector <double> a, b;

double cur, sum = 0;

while(cin >> cur){

a.push_back(cur);

sum += cur;

}

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

if(a.size() < 2){

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

}

else{

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

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

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

}

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

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

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

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

}

return 0;

}

Код на Java

import java.util.*;

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

import java.util.*;

class Main

{

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

{

Scanner in = new Scanner(System.in);

Vector a,b;

a = new Vector();

b = new Vector();

double cur, sum = 0;

while(in.hasNext()){

cur = in.nextDouble();

a.add(cur);

sum += cur;

}

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

if(a.size() < 2){

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

}

else{

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

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

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

}

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

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

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

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

}

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

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

Related Images:

Просто 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)

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

}

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

Для решения данной задачи необходимо использовать данную в условии формулу [latex]GCD \left( n, \ldots, n_k \right) = GCD \left( GCD \left( n, \ldots, n_{k-1} \right), n_k \right)[/latex] [latex]\left(\right)[/latex].
Также необходимо воспользоваться алгоритмом Евклида для реализации рекурсивной функции [latex]GCD[/latex]:
Пусть [latex]m[/latex] и [latex]n[/latex] — одновременно не равные нулю целые неотрицательные числа и пусть [latex]m \ge n[/latex]. Тогда если [latex]n=0[/latex], то [latex]GCD\left(n, m\right)=m[/latex], а если [latex]n\ne0[/latex], то для чисел [latex]m[/latex], [latex]n[/latex] и [latex]r[/latex], где [latex]r[/latex] — остаток от деления [latex]m[/latex] на [latex]n[/latex], выполняется равенство [latex]GCD\left(m, n\right)=GCD\left(n, r\right)[/latex]. (задача 89 задачника С. Абрамова)
Программа записывает в переменную m число [latex]m[/latex], а в result — [latex]n_1[/latex].
Затем, используя формулу [latex]\left(\right)[/latex], программа до окончания цикла считывает следующие числа из последовательности поверх предыдущих в переменную n и находит сперва [latex]GCD\left(n_1, n_2\right)=x_1[/latex], [latex]GCD\left(x_1, n_3 \right)=x_2[/latex], затем [latex]GCD\left(x_2, n_4\right)=x_3[/latex] и так далее, вплоть до нахождения [latex]GCD[/latex] всех чисел, постоянно записывая новые [latex]GCD[/latex] поверх старых в переменную result. В итоге, программа выводит результирующий [latex]GCD[/latex], который и является ответом.

Ссылки

Related Images:

D2655Б. Сумма ряда с заданной точностью

23/10/2016 by Вадим Гордийчук

Задача

Сколько примерно надо взять членов ряда, чтобы найти его сумму с точностью до [latex]10^{-5}[/latex], если [latex]\sum\limits_{n=1}^\infty \frac{2^n}{\left(n+1\right)!}[/latex]?

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

Заданная точность.

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

Количество взятых членов ряда и их сумма.

Тесты

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

[latex]\varepsilon[/latex] [latex]k[/latex] [latex]\sum\limits_{n=1}^{k} \frac{2^n}{\left(n+1\right)!}[/latex]

1e-5 11 2.194527283416172

1 2 1.666666666666667

0.5 3 2.000000000000000

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

Программа для решения задачи D2655b
C++

#include <iostream> #include <iomanip> using namespace std; int main() { double Xn = 1, Sn = 0, epsilon; unsigned int n = 0; cin >> epsilon; while (Xn >= epsilon) { n++; Xn *= 2.0 / (n+1); Sn += Xn; } cout << fixed << setprecision(15) << n << " " << Sn << endl; return 0; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

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

int main()
{
    double Xn = 1, Sn = 0, epsilon; unsigned int n = 0;
    cin >> epsilon;
    while (Xn >= epsilon)
    {
        n++;
        Xn *= 2.0 / (n+1);
        Sn += Xn;
    }
    cout << fixed << setprecision(15) << n << " " << Sn << endl;
    return 0;
}

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

Для удобства введём обозначение: [latex]x_{n}=\frac{2^n}{\left(n+1\right)!}[/latex].
Чтобы доказать, что данный нам ряд [latex]\sum\limits_{n=1}^\infty \frac{2^n}{\left(n+1\right)!}[/latex] сходится, воспользуемся признаком Даламбера:
Пускай [latex]\lim\limits_{n \to \infty} \frac{x_{n+1}}{x_{n}} = D[/latex]. Ряд [latex]\sum\limits_{n=1}^\infty x_n[/latex] сходится, если [latex]D < 1[/latex]. В частности, если [latex]D = 0[/latex]
Найдём [latex]\lim\limits_{n \to \infty} \frac{x_{n+1}}{x_{n}}[/latex].
[latex]\lim\limits_{n \to \infty} \frac{x_{n+1}}{x_{n}} = \lim\limits_{n \to \infty} \left( \frac{2^{n+1}}{\left( n+2 \right)!} \div \frac{2^{n}}{\left( n+1 \right)!} \right) = \lim\limits_{n \to \infty} \left( \frac{2 \cdot 2^{n}}{\left( n+1 \right)! \cdot \left( n+2 \right)} \cdot \frac{\left( n+1 \right)!}{2^{n}} \right) = \lim\limits_{n \to \infty} \frac{2}{n+2} = 0[/latex] Для доказательства последнего равенства [latex]\left( \lim\limits_{n \to \infty} \frac{2}{n+2} = 0 \right)[/latex] воспользуемся определением предела последовательности:
Число [latex]a[/latex] называют пределом последовательности, если для любой точности [latex]\varepsilon>0[/latex] найдётся/существует такой номер, зависящий от [latex]\varepsilon[/latex], начиная с которого все элементы последовательности попадают в интервал [latex]\left( a-\varepsilon; a+\varepsilon \right)[/latex].
В нашем случае число [latex]a[/latex] равно нулю. Поэтому доказательство будет следующим:
[latex]\forall \varepsilon>0[/latex] [latex]\exists N_{\varepsilon} \in \mathbb{N}[/latex]: [latex]\forall n\ge N_{\varepsilon}[/latex], [latex]\left| \frac{2}{n+2} \right| < \varepsilon[/latex]. Находим [latex]N_{\varepsilon}[/latex]:
[latex]\left| \frac{2}{n+2} \right| < \left| \frac{2}{n} \right| = \frac{2}{n} < \varepsilon [/latex]
[latex]\frac{2}{n} < \varepsilon[/latex]
[latex]n > \frac{2}{\varepsilon} \Rightarrow N_{\varepsilon} = \left[ \frac{2}{\varepsilon} \right] + 1 \Rightarrow \lim\limits_{n \to \infty} \frac{2}{n+2} = 0[/latex].

Итог:
Так как ряд сходится, сумма ряда стремится к некоторой константе, и можно определить точный номер [latex]k[/latex], при котором элемент (а следовательно — и сумма) ряда будет удовлетворять заданной точности. Этой точностью будет значение переменной epsilon, которое задаёт пользователь.

Ссылки

Условие задачи (страница 259);

Оригинал кода программы.

Related Images:

Входные данные	Выходные данные
[latex]\varepsilon[/latex]	[latex]k[/latex]	[latex]\sum\limits_{n=1}^{k} \frac{2^n}{\left(n+1\right)!}[/latex]
1e-5	11	2.194527283416172
1	2	1.666666666666667
0.5	3	2.000000000000000

Posted in 3. Циклы. Tagged последовательность, сумма, циклы.

D2655B. Cумма ряда с заданной точностью

15/10/2016 by Эммануил Прокопов

4

Задача
Сколько примерно надо взять членов ряда, чтобы найти его сумму с точностью до
[latex]\varepsilon [/latex], если [latex]\sum\limits _{ n=1 }^{ \infty }{ \frac { 1 }{ (2n-1)! } } [/latex]
Тесты

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

Точность Кол-во взятых членов ряда Значение суммы

1 1 2 1.1666666667

2 1е-5 5 1.1752011684

3 100 1 1

4 1e-10 7 1.1752011936

Код на C++

C++

#include <iostream> #include <iomanip> #include <cmath> using namespace std; double e = exp(1); double bin_pow(double x, int n){ if(n == 1) return x; if(n%2 == 1) return bin_pow(x, n-1)*x; double b = bin_pow(x, n/2); return b*b; } double Rn(int n){ double v = e/(2*n+1); return bin_pow(v, 2*n+1)/(1-v*v); } int main() { double eps, sum = 0, last=0; int n = 0; cin >> eps; do{ n++; if(n > 1) last /= (2*n-2)*(2*n-1); else last = 1; sum += last; } while(Rn(n) > eps); cout << fixed << setprecision(10) << "Количество взятых членов ряда: " << n << "\nЗначение суммы: " << sum; return 0; }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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

double e = exp(1);

double bin_pow(double x, int n){
    if(n == 1) return x;
    if(n%2 == 1) return bin_pow(x, n-1)*x;
    double b = bin_pow(x, n/2);
    return b*b;
}

double Rn(int n){
    double v = e/(2*n+1);
    return bin_pow(v, 2*n+1)/(1-v*v);
}

int main() {
    double eps, sum = 0, last=0;
    int n = 0;
    cin >> eps;
    do{
        n++;
        if(n > 1) last /= (2*n-2)*(2*n-1);
        else last = 1;
        sum += last;
    } while(Rn(n) > eps);
    cout << fixed << setprecision(10) << "Количество взятых членов ряда: " << n << "\nЗначение суммы: " << sum;
    return 0;
}

Код на Java

Java

import java.util.*; class Main { static double e = Math.exp(1); static double bin_pow(double x, int n){ if(n == 1) return x; if(n%2 == 1) return bin_pow(x, n-1)*x; double b = bin_pow(x, n/2); return b*b; } static double Rn(int n){ double v = e/(2*n+1); return bin_pow(v, 2*n+1)/(1-v*v); } public static void main (String[] args) { Scanner in = new Scanner(System.in); double eps, sum = 0, last=0; int n = 0; eps = in.nextDouble(); do{ n++; if(n > 1) last /= (2*n-2)*(2*n-1); else last = 1; sum += last; } while(Rn(n) > eps); System.out.print("Количество взятых членов ряда: " + n + "\nЗначение суммы: " + String.format("%.10f",sum)); } }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

import java.util.*;

class Main
{
    static double e = Math.exp(1);

    static double bin_pow(double x, int n){
        if(n == 1) return x;
        if(n%2 == 1) return bin_pow(x, n-1)*x;
        double b = bin_pow(x, n/2);
        return b*b;
    }

    static double Rn(int n){
        double v = e/(2*n+1);
        return bin_pow(v, 2*n+1)/(1-v*v);
    }

    public static void main (String[] args)
    {
        Scanner in = new Scanner(System.in);
        double eps, sum = 0, last=0;
        int n = 0;
        eps = in.nextDouble();
        do{
            n++;
            if(n > 1) last /= (2*n-2)*(2*n-1);
            else last = 1;
            sum += last;
        } while(Rn(n) > eps);
        System.out.print("Количество взятых членов ряда: " + n + "\nЗначение суммы: " + String.format("%.10f",sum));
    }
}

Решение
Очевидно, ряд является положительным, и общий член ряда стремится к нулю. Ряд сходится по признаку Д’аламбера:
[latex] \lim\limits_{n \rightarrow \infty } \frac{ a_{n+1} }{a_{n}} = \lim\limits_{n \rightarrow \infty } \frac{ \big(2n-1\big)! }{ \big(2n+1\big)! } = \lim\limits_{n \rightarrow \infty } \frac{1}{2n \big(2n+1\big) } =0 < 1[/latex].
Оценим остаток ряда, исходя из того, что [latex]k! > \left( \frac{k}{e} \right) ^{k} , \big(k=1,2,\dots\big) [/latex]:
[latex]R_{N}<\sum\limits_{n=N+1}^\infty \left(\frac{e}{2n-1}\right)^{2n-1}\leq\sum\limits_{n=N+1}^\infty \left(\frac{e}{2N+1}\right)^{2n-1}=\left(\frac{e}{2N+1}\right)^{2N+1}\sum\limits_{i=0}^\infty \left(\frac{e}{2N+1}\right)^{2i}[/latex] Поскольку при [latex]N\geq1[/latex] [latex]\frac{e}{2N+1}<1[/latex]:
[latex]R_{N} < \left(\frac{e}{2N+1}\right)^{2N+1}\frac{1}{1-\left(\frac{e}{2N+1}\right)^2}[/latex]
В переменной sum хранится текущее значение суммы ряда, в last — последний рассмотренный член ряда. В начале работы программы вводится требуемая точность eps. Можно заметить, что для получения [latex]n[/latex]-го члена ряда достаточно разделить предыдущий на [latex]\left(2n-2\right)\cdot\left(2n-1\right)[/latex], однако необходимо отдельно рассмотреть случай, когда [latex]n = 1[/latex]. В цикле увеличиваем [latex]n[/latex], находим значение следующего члена ряда и прибавляем к sum, пока остаток ряда не станет достаточно маленьким. Оцениваем остаток ряда при помощи функции Rn(int n). Во время её работы может потребоваться возведение числа в большую степень, делаем это по алгоритму бинарного возведения в степень.

Ссылка на код на ideone.com: здесь (C++) и здесь (Java).
Условие задачи (стр. 259)

Related Images:

Posted in 3. Циклы. Tagged последовательность, сумма, факториал, циклы.

Post navigation

← Older posts

Search

1. Линейные вычисления

2. Программы с ветвлением

3. Циклы

4. Потоковая обработка

5. Массивы

6. Многомерные массивы

7. Строки c-string

8. Строки string

9. Последовательные контейнеры

A. Сортировки и жадность

B. Стеки-деки-очереди

C. Ассоциативные контейнеры

D. Графы

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

F. Динамическое программирование

Игры программистов

Спортивное программирование

Творческие задачи

Численный анализ

⌂ Организационные

Студенты 2020

Введите адрес для отправки новостей

E-mail

Іванов Вячеслав Володимирович (22)
Ілларіонова Марія Валеріївна (20)
Зелінський Вячеслав Олександрович (19)
Вустянюк Ігор Дмитрович (19)
Сплошнов Кирилл (18)
Таран Таня (17)
Гордийчук Вадим (15)
Корнилова Таня (14)
Денисова Ольга (14)
Калачьов Андрій Сергійович (14)
Студенты 2019

Студенты 2018

№	Входные данные	Выходные данные
	Точность	Кол-во взятых членов ряда	Значение суммы
1	1	2	1.1666666667
2	1е-5	5	1.1752011684
3	100	1	1
4	1e-10	7	1.1752011936

Задача

Вхідні дані

Вихідні дані

Тести

Код

Рішення

Посилання

Related Images:

Задача

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

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

Тесты

Код

Решение

Ссылки

Related Images:

Задача

$\frac{1}{1\cdot2}+\frac{1}{2\cdot3}+ … +\frac{1}{n\cdot(n+1)}$

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

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

Тесты

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

Решение

$\frac{1}{i \cdot (i + 1)}$

Ссылки

Related Images:

Условие

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

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

Тесты

Код

Решение

Ссылки

Related Images:

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

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

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

Тесты

Программный код

Решение

Ссылки

Related Images:

﻿Задача

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

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

Тесты

Код

Решение

Ссылки

Related Images:

Задача

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

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

Тесты

Код

Решение

Ссылки

Related Images:

Задача

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

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

Тесты

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

Решение

Ссылки

Related Images:

Задача

Условие

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

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

Тесты

Решение

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

Ссылки

Related Images:

Задача

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

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

Тесты

Решение

Задача