e-olymp 1243. Наименьшее общее кратное

20/12/2020 by Максим Ливитчук

Условие

Наименьшим общим кратным ($НОК$) множества натуральных чисел называется такое наименьшее натуральное число, которое делится на каждое число в этом множестве. Например, $НОК$ чисел $5$, $7$ и $15$ равно $105$.

Вам необходимо найти $НОК$ $m$ заданных чисел.

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

Первая строка содержит количество тестов. Каждый тест состоит из одной строки и содержит числа $m$ $n_1$ $n_2$ $n_3$ $\ldots$ $n_m$, где $m$($1 \leqslant m \leqslant 100$) — количество заданных чисел, $n_1$ $\ldots$ $n_m$ — сами числа. Все числа натуральные и лежат в границах $32$-битового целого.

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

Для каждого теста в отдельной строке вывести соответствующее значение $НОК$. Все выводимые числа лежат в границах $32$-битового целого.

Тесты

№	ввод	вывод
1	2 3 5 7 15 6 4 10296 936 1287 792 1	105 10296
2	3 1 36 5 2 2 2 2 2 5 987 1597 2584 4181 6765 10946 17711	36 2 38400890173772280
3	0

Код

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

int main() {
    int n, m;
    cin >>n;
    for(int i=0; i<n; i++) {
        cin >>m;
        int temp, ans;
        cin >>ans;
        for(int j=1; j<m; j++) {
            cin >>temp;
            ans = ans/__gcd(ans, temp)*temp;
        }
        cout <<ans <<endl;
    }
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int n, m;

cin >>n;

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

cin >>m;

int temp, ans;

cin >>ans;

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

cin >>temp;

ans = ans/__gcd(ans, temp)*temp;

}

cout <<ans <<endl;

}

Код с алгоритмом Евклида

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

int gcd(int a, int b) {
  while(a and b) {
    if(a>b)
      a %= b;
    else
      b %= a;
  }
  return a+b;
}

int main() {
    int n, m;
    cin >>n;
    for(int i=0; i<n; i++) {
        cin >>m;
        int temp, ans;
        cin >>ans;
        for(int j=1; j<m; j++) {
            cin >>temp;
            ans = ans/gcd(ans, temp)*temp;
        }
        cout <<ans <<endl;
    }
}

#include <iostream>

#include <algorithm>

using namespace std;

int gcd(int a, int b) {

while(a and b) {

if(a>b)

a %= b;

else

b %= a;

}

return a+b;

}

int main() {

int n, m;

cin >>n;

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

cin >>m;

int temp, ans;

cin >>ans;

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

cin >>temp;

ans = ans/gcd(ans, temp)*temp;

}

cout <<ans <<endl;

}

Решение

$\DeclareMathOperator{\lcm}{lcm}$
$НОК$ ($\lcm$) проще всего считается по формуле $\operatorname {lcm}(a,b)={\frac {|a\cdot b|}{\operatorname {gcd}(a,b)}}$, где $\gcd$ — $НОД$. Для $\lcm$ от более чем двух чисел справедлива следующая формула: $\operatorname {lcm}(a_{1},a_{2},\ldots ,a_{n})=\operatorname {lcm}(\operatorname {lcm}(a_{1},a_{2},\ldots ,a_{{n-1}}),a_{n})$, из которой видно, что подсчёт $\lcm$ от $n$ чисел сводится к вычислению $n-1$-ого $\lcm$ от очередного числа и предыдущего результата вычислений.

$НОД$ ($\gcd$) в коде считается при помощи стандартной функции __gcd(a, b) из стандартной библиотеки algorithm в первом варианте кода или по алгоритму Евклида во втором.

Ссылки

Related Images:

e-olymp 1679. Честная цепочка

19/12/2020 by Максим Ливитчук

Условие

В подземных норах в долине рядом со скалами Крейд-Моор долгое время жили в мире и согласии два гномьих племени. Гномы обоих племен работали в шахтах, добывая драгоценные камни. Первое племя добывало исключительно изумруды, а второе племя — рубины. Однажды в честь великого праздника Файрвинд гномы решили принести в дар своей богине Мирабель цепочку из изумрудов и рубинов. Самые искусные кузнецы обоих племен работали над созданием этой цепочки, собирая на ней один за одним драгоценные камни. Но как только работа была окончена, решили вожди племен пересчитать камни каждого вида. Ведь если каких-то камней окажется меньше, то богиня может отвернуться от племени, которое пожадничало. Чтобы избежать подобных последствий, было решено подарить некоторый непустой фрагмент цепочки (то есть цепь, состоящую из нескольких камней, расположенных друг за другом в исходной цепочке), в котором будет рубинов ровно столько же, сколько и изумрудов. Возможно это может быть сделано несколькими способами. Для того, чтобы узнать сколько таких способов существует, гномы обратились за помощью к вам.

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

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

В единственной строке задается последовательность камней в исходной цепочке: символ E обозначает изумруд, символ R — рубин. Количество символов в строке не превышает $500000$.

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

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

Тесты

№	ввод	вывод
1	REER	3
2	REERREER	12
3	RRRRRRRR	0
4	EREREERERERREREREEERERERERERRREREREERERERERE	273
5	REEERREE	7

Код

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

int main() {
    int cnt = 0;
    char buf;
    map<int, long long> mp;
    mp[0] = 1;
    while(cin >>buf) {
        if(buf=='R')
            cnt++;
        else
            cnt--;
        mp[cnt]++;
    }
    long long answer = 0;
    for(auto e: mp) {
        answer += e.second*(e.second-1)/2;
    }
    cout <<answer;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

int cnt = 0;

char buf;

map<int, long long> mp;

mp[0] = 1;

while(cin >>buf) {

if(buf=='R')

cnt++;

else

cnt--;

mp[cnt]++;

}

long long answer = 0;

for(auto e: mp) {

answer += e.second*(e.second-1)/2;

}

cout <<answer;

}

Компактный код

#include 
#include <map>
using namespace std;
 
int main() {
    int cnt = 0;
    char buf;
    map mp;
    mp[0] = 1;
    while(cin >>buf) mp[buf=='R'?++cnt:--cnt]++;
    long long a = 0;
    for(auto e: mp) a += e.second*(e.second-1)/2;
    cout <<a;
}

#include

#include <map>

using namespace std;

int main() {

int cnt = 0;

char buf;

map mp;

mp[0] = 1;

while(cin >>buf) mp[buf=='R'?++cnt:--cnt]++;

long long a = 0;

for(auto e: mp) a += e.second*(e.second-1)/2;

cout <<a;

}

Решение

Составим массив из $n+1$ чисел, каждое из которых будет располагаться в месте возможного начала или конца фрагмента цепочки, который гномы должны вручить богине. Число в самом начале цепочки возьмём равным $0$, а все следующие числа будут представлять из себя количество R минус количество E, встречающихся в фрагменте с начала до этого числа.

Наглядный пример такого массива для пятого примера (подписан как cnt)

На таком массиве наглядно видно, что правильным фрагментом будет любой, начинающийся и кончающийся одинаковым числом, ведь это значит что между этими числами равное количество как R($+1$), так и E($-1$), которые сокращаются.

Выделенные в том же примере фрагменты с началом и концом в 0 и -2

Так как нам не важны конкретные правильные фрагменты, а только их суммарное количество, нам будет достаточно знать, сколько раз в массиве встречается то или иное число. В коде эту информацию хранит ассоциативная таблица mp. Запись mp[cnt]++; создаёт новый равный нулю элемент по ключу cnt, если раньше в структуре его не было, после чего инкрементирует значение.
Сам же массив воспроизводится на ходу из ввода, в переменной cnt. В конце программы количество фрагментов считается как сумма $\frac{n(n-1)}{2}$, где $n$ — mp[i] для всех встречавшихся в массиве чисел.

Ссылки

Related Images:

e-olymp 7213. Шашка на кубе

12/12/2020 by Максим Ливитчук

Условие

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

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

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

Содержит натуральные числа $l$ и $m$ ($l < 52$, $m < 200$).

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

Вывести искомое количество способов.

Тесты

l	m	вывод
3	3	1
3	4	0
3	5	25
51	199	4009263689513240276071196173369495212494629453793821392879244551766927964742684514532573281589075237363501397360
3	199	11954860546705755218324706261555627152268568460810054501274297031890136116190373877274924800908756150285132065690107399

Код

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

#define cr(a, b, x, y) case a: return CellCoord{b, x, y}
#define SIDENUM 3 //количество сторон куба которые хранятся
#define MAX_L 51 //максимальное значение L

#define BASE 1000000000 //10^9, основание системы счисления для длинной арифметики 
#define DNUM 9 //количество цифр 10-ичной системы счисления в 1 "цифре" длинной арифметики

struct LongNum {
    //реализация длинной арифметики на векторах со сложением и выводом
    vector<int> v;
    LongNum() {} //стандартный конструктор
    LongNum(int s) { //конструктор из int
        v.push_back(s);
    }
    void print() { //вывод числа
        cout <<(v.empty() ? 0 : v.back());
        for (int i = (int)v.size() - 2; i>=0; i--)
            cout <<setfill('0') <<setw(DNUM) <<v[i];
    }
    void add(LongNum term) { //прибавление длинного числа
        auto b = term.v;
        int carry = 0;
        for (size_t i = 0; i < max(v.size(), b.size()) || carry; i++) {
            if (i == v.size())
                v.push_back(0);
            v[i] += carry + (i < b.size() ? b[i] : 0);
            carry = v[i] >= BASE;
            if (carry)  v[i] -= BASE;
        }
    }
};

struct CellCoord {
    //хранит данные о положении клетки
    short side;
    short x, y;
};

struct CellNeighbors {
    //хранит данные о положении всех(4) соседей определённой клетки
    CellCoord n[4];
};

CellCoord FixNeighbor(short l, short side, short x, short y) {
    //исправляет данные о положении клетки, если она выходит за края грани
    if(x == -1) { //если сосед находится левее грани
        switch(side) {
        //если координаты выходят за левую границу 0-ой грани - меняет грань на 1-ую,
        //обнуляя y, а в x записывает старый y 
        cr(0, 1, y,     0); //и так далее
        cr(1, 1, l-1,   y);
        cr(2, 1, l-y-1, l-1);
        }
    } else if(x == l) {//правее
        switch(side) {
        cr(0, 1, l-y-1, 0);
        cr(1, 1, 0,     y);
        cr(2, 1, y,     l-1);
        }
    } else if(y == -1) {//выше
        switch(side) {
        cr(0, 1, l-x-1, 0);
        cr(1, 0, x,     l-1);
        cr(2, 1, x,     l-1);
        }
    } else if(y == l) {//ниже
        switch(side) {
        cr(0, 1, x,     0);
        cr(1, 2, x,     0);
        cr(2, 1, l-x-1, l-1);
        }
    } else {
        // если координаты не вышли за границы грани просто возвращаем неизменёные координаты
        return CellCoord{side, x, y};
    }
}

CellNeighbors GetNeighbors(short l, short side, short x, short y) {
    //возвращает исправленные координаты всех(4) соседних клеток
    return CellNeighbors{{
        FixNeighbor(l, side, x-1, y),
        FixNeighbor(l, side, x+1, y),
        FixNeighbor(l, side, x, y-1),
        FixNeighbor(l, side, x, y+1)
    }};
}

int main() {
    short l, m;
    bool flag = false;
    cin >>l >>m;
    LongNum cubes[2][SIDENUM][MAX_L][MAX_L];

    cubes[0][0][l/2][l/2] = LongNum(1);
    //за 0 ходов можно дойти 1 путём в изначальную точку

    CellNeighbors nbs[SIDENUM][MAX_L][MAX_L];
    //массив координат соседей

    for(short side=0; side<SIDENUM; side++) {
        for(short xi=0; xi<l; xi++) {
            for(short yi=0; yi<l; yi++) { //перебор координат всех клеток
                nbs[side][xi][yi] = GetNeighbors(l, side, xi, yi);
                //кэш координат соседних клеток
            }
        }
    }

    for(short i=0; i<m; i++) {
        for(short side=0; side<SIDENUM; side++) {
            for(short xi=0; xi<l; xi++) {
                for(short yi=0; yi<l; yi++) { //перебор всех клеток
                    LongNum neighbor_sum;
                    for(auto e: nbs[side][xi][yi].n) { //перебор всех соседей
                        neighbor_sum.add(cubes[flag][e.side][e.x][e.y]);
                        //сложение количества путей ко всем соседям на предыдущем шаге
                    }
                    cubes[!flag][side][xi][yi] = neighbor_sum;
                    //запись получившейся суммы в клетку
                }
            }
        }
        flag = !flag; //замена местами массива для предыдущего шага и нынешнего
    }
    cubes[flag][1][l/2][l/2].print();
    //вывод количества путей к центру соседней грани на m-ом шаге
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

#include <iostream>

#include <iomanip>

#include <vector>

using namespace std;

#define cr(a, b, x, y) case a: return CellCoord{b, x, y}

#define SIDENUM 3 //количество сторон куба которые хранятся

#define MAX_L 51 //максимальное значение L

#define BASE 1000000000 //10^9, основание системы счисления для длинной арифметики

#define DNUM 9 //количество цифр 10-ичной системы счисления в 1 "цифре" длинной арифметики

struct LongNum {

//реализация длинной арифметики на векторах со сложением и выводом

vector<int> v;

LongNum() {} //стандартный конструктор

LongNum(int s) { //конструктор из int

v.push_back(s);

}

void print() { //вывод числа

cout <<(v.empty() ? 0 : v.back());

for (int i = (int)v.size() - 2; i>=0; i--)

cout <<setfill('0') <<setw(DNUM) <<v[i];

}

void add(LongNum term) { //прибавление длинного числа

auto b = term.v;

int carry = 0;

for (size_t i = 0; i < max(v.size(), b.size()) || carry; i++) {

if (i == v.size())

v.push_back(0);

v[i] += carry + (i < b.size() ? b[i] : 0);

carry = v[i] >= BASE;

if (carry) v[i] -= BASE;

}

};

struct CellCoord {

//хранит данные о положении клетки

short side;

short x, y;

};

struct CellNeighbors {

//хранит данные о положении всех(4) соседей определённой клетки

CellCoord n[4];

};

CellCoord FixNeighbor(short l, short side, short x, short y) {

//исправляет данные о положении клетки, если она выходит за края грани

if(x == -1) { //если сосед находится левее грани

switch(side) {

//если координаты выходят за левую границу 0-ой грани - меняет грань на 1-ую,

//обнуляя y, а в x записывает старый y

cr(0, 1, y, 0); //и так далее

cr(1, 1, l-1, y);

cr(2, 1, l-y-1, l-1);

}

} else if(x == l) {//правее

switch(side) {

cr(0, 1, l-y-1, 0);

cr(1, 1, 0, y);

cr(2, 1, y, l-1);

}

} else if(y == -1) {//выше

switch(side) {

cr(0, 1, l-x-1, 0);

cr(1, 0, x, l-1);

cr(2, 1, x, l-1);

}

} else if(y == l) {//ниже

switch(side) {

cr(0, 1, x, 0);

cr(1, 2, x, 0);

cr(2, 1, l-x-1, l-1);

}

} else {

// если координаты не вышли за границы грани просто возвращаем неизменёные координаты

return CellCoord{side, x, y};

}

CellNeighbors GetNeighbors(short l, short side, short x, short y) {

//возвращает исправленные координаты всех(4) соседних клеток

return CellNeighbors{{

FixNeighbor(l, side, x-1, y),

FixNeighbor(l, side, x+1, y),

FixNeighbor(l, side, x, y-1),

FixNeighbor(l, side, x, y+1)

}};

}

int main() {

short l, m;

bool flag = false;

cin >>l >>m;

LongNum cubes[2][SIDENUM][MAX_L][MAX_L];

cubes[0][0][l/2][l/2] = LongNum(1);

//за 0 ходов можно дойти 1 путём в изначальную точку

CellNeighbors nbs[SIDENUM][MAX_L][MAX_L];

//массив координат соседей

for(short side=0; side<SIDENUM; side++) {

for(short xi=0; xi<l; xi++) {

for(short yi=0; yi<l; yi++) { //перебор координат всех клеток

nbs[side][xi][yi] = GetNeighbors(l, side, xi, yi);

//кэш координат соседних клеток

}

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

for(short side=0; side<SIDENUM; side++) {

for(short xi=0; xi<l; xi++) {

for(short yi=0; yi<l; yi++) { //перебор всех клеток

LongNum neighbor_sum;

for(auto e: nbs[side][xi][yi].n) { //перебор всех соседей

neighbor_sum.add(cubes[flag][e.side][e.x][e.y]);

//сложение количества путей ко всем соседям на предыдущем шаге

}

cubes[!flag][side][xi][yi] = neighbor_sum;

//запись получившейся суммы в клетку

}

flag = !flag; //замена местами массива для предыдущего шага и нынешнего

}

cubes[flag][1][l/2][l/2].print();

//вывод количества путей к центру соседней грани на m-ом шаге

}

Решение

Из условия можно понять, что задача про специфического вида граф, по которому движется шашка. Его вершинами являются клетки на гранях куба, а дуги лежат между клетками с общими границами. Очевидно количество путей за $m$ шагов до любой точки в графе будет равняться сумме количества путей за $m-1$ шагов ко всем соседним вершинам, то есть мы можем получать решение задачи для $m$ шагов из решения меньшей задачи для $m-1$ шагов, из чего можно понять что это задача на динамическое программирование.
Для решения создадим массив со всеми вершинами и будем хранить в нём количество путей к каждой из них на i-ом шаге. Удобнее всего задать такой массив как 6 числовых матриц размером $ l \times l$, по одной на каждую грань куба.

Раскладка шести граней куба с переходами между границами

Соседство будем определять, прибавляя или отнимая единицу от одной из координат клетки в матрице, например $(x-1, y)$ всегда будет соседом $(x, y)$, не считая крайних случаев, когда $x-1$ будет меньше нуля. Такие ситуации в коде обрабатывает функция FixNeighbor(...), в которой прописаны все подобные крайние случаи.

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

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

Оптимизированный вариант хранения куба

Так как для получения значения клетки через $i$ шагов нужны значения всех её соседей через $i-1$ шагов, а для получения значения соседей через $i$ шагов нужно значение клетки через $i-1$ шагов, нам не хватит только одного массива для перезаписи, надо использовать минимум два для хранения предыдущего и нынешнего состояния. В программе это реализовано с помощью булевой переменной flag — сначала мы вычисляем следующее состояние на основании 0-ого массива ( flag), записывая результат 1-ый ( !flag), а потом инвертируем значение переменной на противоположное и массивы в алгоритме меняются местами.