OCPC2021. Задача A. Колёса деда Панаса (код решения)

20/01/2024 by Александр Мармалюк

Условие

Дед Панас, постоялец палаты номер 17 заведения «Покосившийся Скворечник», срочно должен был принять свои таблетки умиротворения. К сожалению, нянечка рассыпала их по столу и теперь дед Панас твёрдо уверен, что он – Генри Форд, а на столе лежат колёса, из которых нужно собирать автомобили и мотоциклы. Сосед деда Панаса, дед Архип, также не дождавшийся своих таблеток, убеждён, что он – Блез Паскаль, и, заметив, что колёс на столе четное количество, донимает нянечку вопросом: «Сколькими способами можно распределить эти колёса между автомобилями и мотоциклами так, чтобы не оставалось лишних?» Поскольку дед Архип не уймётся, пока не получит ответа, и будет мешать нянечке собирать таблетки со стола, на помощь позвали вас и просят подсказать ей правильный ответ.

На ввод поступает единственное целое четное число $n$ $(2 \leqslant n \leqslant 10^9)$ – количество таблеток на столе.

Выведите одно число – количество способов распределить колёса между автомобилями и мотоциклами. Помните, что для автомобиля нужно $4$ колеса, для мотоцикла – $2$. Два способа считаются различными, если в одном из них количество автомобилей не совпадает с количеством автомобилей в другом; то же самое справедливо и для мотоциклов.

Тесты

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

6	2
2	1
12	4
1000000000	250000001

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

#include <iostream>
using namespace std;
int main() {
    int n;
    cin >> n;
    cout << ((n / 4) + 1);
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

cout << ((n / 4) + 1);

return 0;

}

Решение

Некоторое количество колёс уходит на автомобили, а все остальные — на мотоциклы. Тогда заметим, что каждому способу разделить колёса между автомобилями и мотоциклами соответствует количество автомобилей, которые используются в этом разделении. Всего мы можем взять от $0$ до $\frac{n}{4}$ автомобилей включительно (целочисленное деление).

Решение задачи на ideone.com

Ссылка на контест

Related Images:

OCPC2021. Задача F. Электрик наносит ответный удар (код решения)

20/01/2024 by Александр Мармалюк

Условие

В заведении «Покосившийся Скворечник» главврач экономит на зарплате системного администратора, поэтому эту должность в свободное от уколов время занимает электрик Геннадий из палаты номер 404. На сегодняшнем дежурстве одна из розеток внезапно заговорила с Геннадием и посулила тому суперспособности, если он её раскрутит. Результатом их общения, однако, стал лишь удар тока по нерадивому электрику, и теперь Геннадий задумал месть: он устроит лживой розетке Очень Длинное Замыкание!

Дата-центр «Покосившегося Скворечника» устроен следующим образом: помимо разной аппаратуры, из стены в ряд торчат 2∙n коннекторов: это n штепселей и n розеток. Геннадий планирует разбить их на пары розетка-штепсель и соединить каждую пару одним проводом таким образом, что штепсель всегда находится левее соответствующей розетки – эту идею ему навеяли правила средневекового этикета. Чтобы замыкание было Очень Длинным, Геннадий хочет, чтобы суммарная длина проводов, использованных для его коварного замысла, была максимально возможной. Помогите ему! Ну, или не мешайте хотя бы, и просто подскажите, провод какой длины он должен отрезать от соседней линии электропередач, чтобы распилить его на столь нужные ему провода.

Первая строка ввода содержит целое число $n$ $(2 \leqslant n \leqslant 1000).$ Вторая строка содержит n целых чисел – координаты штепселей слева направо. Третья строка содержит n чисел – координаты розеток слева направо. Все числа во второй и третьей строках различны и находятся в диапазоне от $0$ до $10^5$.

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

Тесты

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

2 1 4 6 8	9
2 1 4 2 5	2
4 2 5 6 9 3 7 12 22	22
3 2 3 4 12 13 17	33

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

#include <iostream>
using namespace std;
int main() {
    int n, res = 0;
    cin >> n;
    for (int tmp, i = 0; i < n; i++) {
        cin >> tmp;
        res -= tmp;
    }
    for (int tmp, i = 0; i < n; i++) {
        cin >> tmp;
        res += tmp;
    }
    cout << res;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, res = 0;

cin >> n;

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

cin >> tmp;

res -= tmp;

}

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

cin >> tmp;

res += tmp;

}

cout << res;

return 0;

}

Решение

Обратим внимание на то, что оптимальным будет решение подключать $i$-й штепсель к $i$-й розетке. В условии задачи сказано, что существует хотя бы один способ подключить все коннекторы так, чтобы соблюсти средневековое правило этикета. Значит, последовательно подключая самый левый свободный штепсель в самую левую свободную розетку (а поскольку коннекторы изначально упорядочены, это и значит $i$-й штепсель в $i$-й розетку), мы удовлетворим правило этикета. Теперь покажем, что суммарная длина проводов в любом другом подключении не меньше. Предположим, мы подключили $i$-й штепсель в $j$-ю розетку (и это первый случай подключения штепселя не на «свое» место). Поскольку все предыдущие розетки, если они есть, уже заняты, $j \gt i$. Если можно подключить $j$-й штепсель в $i$-ю розетку (т.е. $j$-й штепсель левее $i$-й розетки), то суммарная длина проводов не изменится. Если же $j$-й штепсель правее $i$-й розетки, то чтобы иметь возможность его подключить, надо переподключить штепсели между $i$-м и $j$-м (надо заметить, что такая возможность не гарантирована). В результате этого мы сэкономим провода на не более, чем расстояние между $i$-й розеткой и $j$-м штепселем. Но поскольку $k$-я розетка, в которую мы подключим $j$-й штепсель, обязательно правее самого штепселя, то суммарная длина проводов нового подключения будет больше исходной как минимум на расстояние между $k$-й розеткой и $j$-м штепселем, поскольку этот фрагмент провода «дублируется» подключением $i$-го штепселя в $j$-ю розетку.

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

Решение задачи на ideone.com

Ссылка на контест

Related Images:

OCPC-2021. Задача B. Палиндромонойя (код решения)

20/01/2024 by Александр Мармалюк

Условие

Студент Илья, постоялец палаты номер 101 заведения «Покосившийся Скворечник», попавший сюда во время сессии на почве экзамена по программированию, убеждён, что его повсюду преследуют затаившиеся палиндромы. «Они среди нас! Как же вы этого не замечаете?!» – то и дело слышат от него нянечки Алла и Анна. По убеждению Ильи, палиндром – это слово, читающееся одинаково, как слева направо, так и справа налево. Если же на первый взгляд слово таковым не является, то студент не опускает рук и переносит буквы по одной из начала слова в конец, пока оно не станет палиндромом. Если из слова таким образом удалось получить палиндром за 0 или более операций, Илья называет его затаившимся палиндромом, после чего студент начинает бегать по потолку с воплями отчаяния, чем доставляет неудобства окружающим. Например, Илью может довести до исступления слово «масса», ведь из него можно получить «самас», перенеся 3 буквы из начала в конец. Главврач хочет выкинуть из палаты номер 101 Илью, но вместо этого выкинет все предметы, названия которых являются затаившимися палиндромами. Осталось только проверить их все, а здесь без программы не обойтись!

На ввод поступает строка, содержащая одно слово, длиной от 1 до 100 латинских строчных букв.

Выведите одну строку: «yes» без кавычек, если предмет с этим названием стоит выбросить и «no» без кавычек, если его стоит оставить в палате номер 101.

Тесты

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

array	yes
iliya	no
anna	yes
cbaabcb	yes
arrya	no
anana	yes
bcdcbaa	yes

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

#include <iostream>
#include <string>
using namespace std;
bool palindrome (string const *s) {
    for (int i = 0; i < (*s).size() / 2; ++i) {
        if ((*s)[i] != (*s)[(*s).size() - i - 1]) return false;
    }
    return true;
}
int main() {
    string s;
    cin >> s;
    for (int i = 0; i <= s.length(); i++) {
        s += s[0];
        s.erase(s.begin());
        if (palindrome(&s)) {
            cout << "yes";
            return 0;
        }
    }
    cout << "no";
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

bool palindrome (string const *s) {

for (int i = 0; i < (*s).size() / 2; ++i) {

if ((*s)[i] != (*s)[(*s).size() - i - 1]) return false;

}

return true;

}

int main() {

string s;

cin >> s;

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

s += s[0];

s.erase(s.begin());

if (palindrome(&s)) {

cout << "yes";

return 0;

}

cout << "no";

return 0;

}

Решение №1

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

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

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

int main() {
    string s;
    cin >> s;
    int n = s.length();
    //дублируем строку, чтобы иметь возможность просмотреть все циклические перестановки
    s += s;
    const int p = 31;
    vector <long long> p_pow (2*n); //вектор степеней числа p
    p_pow[0] = 1;
    for (int i = 1; i < 2*n; ++i) p_pow[i] = p * p_pow[i-1];
    long long P1 = 0, P2 = 0;
    for (int i = 0; i < n; ++i) {
        P1 += (s[i] - 'a' + 1) * p_pow[i];
        P2 += (s[n - i - 1] - 'a' + 1) * p_pow[i];
    }
    if (P1 == P2) {
        bool check = true;
        for (int i = 0; i < n; ++i)
            if (s[i] != s[n - i - 1]) check = false;
        if (check) {
            cout << "yes";
            return 0;
        }
    }
    for (int i = 0; i < n; ++i) {
        P1 += (s[i+n] - 'a' + 1)*p_pow[i+n] - (s[i] - 'a' + 1)*p_pow[i];
        P2 = (P2 - (s[i] - 'a' + 1)*p_pow[n + i - 1]) * p_pow[2] + (s[i+n]-'a' + 1) * p_pow[i+1];
        if (P1 == P2) {
            bool check = true;
            for (int j = i + 1; j < i + 1 + n; ++j)
                if (s[j] != s[2*i + 1 + n - j]) check = false;
            if (check) {
                cout << "yes";
                return 0;
            }
        }
    }
    cout << "no";
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

string s;

cin >> s;

int n = s.length();

//дублируем строку, чтобы иметь возможность просмотреть все циклические перестановки

s += s;

const int p = 31;

vector <long long> p_pow (2*n); //вектор степеней числа p

p_pow[0] = 1;

for (int i = 1; i < 2*n; ++i) p_pow[i] = p * p_pow[i-1];

long long P1 = 0, P2 = 0;

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

P1 += (s[i] - 'a' + 1) * p_pow[i];

P2 += (s[n - i - 1] - 'a' + 1) * p_pow[i];

}

if (P1 == P2) {

bool check = true;

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

if (s[i] != s[n - i - 1]) check = false;

if (check) {

cout << "yes";

return 0;

}

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

P1 += (s[i+n] - 'a' + 1)*p_pow[i+n] - (s[i] - 'a' + 1)*p_pow[i];

P2 = (P2 - (s[i] - 'a' + 1)*p_pow[n + i - 1]) * p_pow[2] + (s[i+n]-'a' + 1) * p_pow[i+1];

if (P1 == P2) {

bool check = true;

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

if (s[j] != s[2*i + 1 + n - j]) check = false;

if (check) {

cout << "yes";

return 0;

}

cout << "no";

return 0;

}

Решение №2

Для решения задачи можно воспользоваться техникой хеширования строк. Изначально продублируем строку, поскольку тогда все циклические перестановки исходной строки будут подстроками длины $n$ продублированной строки, где $n$ — длина исходной строки.
Можно сначала сравнить хеши исходного слова и «перевернутого» к нему. Далее будем строить значения полиномиальных хешей, умноженных на $p$ в соответствующей степени, всех следующих подстрок длины $n$ и «перевернутых» к ним.
Заметим, что вычислять значение хеша «перевернутой» строки можно без её копирования, поскольку отличается она от «прямой строки только тем, что степени числа $p$ умножаются на преобразованые коды соответствующих символов строки в обратном порядке. Поэтому для вычисления хеша следующей «перевернутой» подстроки надо вычесть из предыдущего значения элемент с наибольшей степенью числа $p$, домножить полученное значение на $ p^2 $, т.к. мы, с одной стороны, решили смещать края подстроки, для которой мы проверяем на палиндром, умножая её хеш на соответствующую степень числа $p$, а с другой — текущая предпоследняя степень должна стать последней (из-за того, что рассматривается перевёрнутая подстрока и новый символ к ней присоединяется «в начало»).

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

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

#include <iostream>
#include <vector>
using namespace std;
int main() {
    string s;
    cin >> s;
    int n = s.length();
    s += s;
    int len = s.length();
    vector <int> d (len);
    int l = 0, r = -1;
    if (n % 2) {
        for (int i = 0; i < len; ++i) {
            d[i] = (i > r)? 1 : min(d[l + r - i], r - i + 1);
            while (i - d[i] >= 0 and i + d[i] < len and s[i - d[i]] == s[i + d[i]])
                d[i]++;
            if (i + d[i] - 1 > r) {
                r = i + d[i] - 1;
                l = i - d[i] + 1;
            }
            if (r - l + 1 >= n) {
                cout << "yes";
                return 0;
            }
        }
    }
    else {
        for (int i = 0; i < len; ++i) {
            d[i] = (i > r)? 0 : min(d[l + r - i + 1], r - i + 1);
            while (i - d[i] - 1 >= 0 and i + d[i] < len and s[i - d[i] - 1] == s[i + d[i]])
                d[i]++;
                if (i + d[i] - 1 > r) {
                    r = i + d[i] - 1;
                    l = i - d[i];
                }
            if (r - l >= n) {
                cout << "yes";
                return 0;
            }
        }
    }
    cout << "no";
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

string s;

cin >> s;

int n = s.length();

s += s;

int len = s.length();

vector <int> d (len);

int l = 0, r = -1;

if (n % 2) {

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

d[i] = (i > r)? 1 : min(d[l + r - i], r - i + 1);

while (i - d[i] >= 0 and i + d[i] < len and s[i - d[i]] == s[i + d[i]])

d[i]++;

if (i + d[i] - 1 > r) {

r = i + d[i] - 1;

l = i - d[i] + 1;

}

if (r - l + 1 >= n) {

cout << "yes";

return 0;

}

else {

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

d[i] = (i > r)? 0 : min(d[l + r - i + 1], r - i + 1);

while (i - d[i] - 1 >= 0 and i + d[i] < len and s[i - d[i] - 1] == s[i + d[i]])

d[i]++;

if (i + d[i] - 1 > r) {

r = i + d[i] - 1;

l = i - d[i];

}

if (r - l >= n) {

cout << "yes";

return 0;

}

cout << "no";

return 0;

}

Решение №3

Для решения задачи можно воспользоваться алгоритмом Манакера. Алгоритм позволяет находить все подпалиндромы строки, поэтому мы снова продублируем строку и будем искать в ней подпалиндром, длина которого равна длине $n$ исходной строки. Заметим, что нам достаточно проверять подпалиндомы, четность длины которых совпадает с четностью $n$. Далее будем сравнивать расстояние между концами $l$ и $r$ текущего палиндрома с $n$ (расстояние между концами может быть и больше $n$, т.к. мы уже определили, что четность этих величин будет совпадать, а если в строке найден подпалиндром длиной $s$, то существуют подпалиндромы и длиной $s-2$, $s-4$, … ).

Решение №1 задачи на ideone.com

Решение №2 задачи на ideone.com

Решение №3 задачи на ideone.com

Ссылка на контест

Related Images:

OCPC-2021. Задача D. Столовая (код решения)

20/01/2024 by Александр Мармалюк

Условие

В столовой заведения «Покосившийся Скворечник» имеется ровно $k$ тарелок, а в самом заведении – $n$ палат. По старой традиции, чтобы постояльцы не пугались новых знакомых и не обменивались симптомами, их приводят в столовую так, чтобы одновременно там находились только обитатели одной палаты. При этом, порядок посещения столовой палатами строго зафиксирован – от меньшего номера к большему.

Замечено, что некоторые постояльцы всегда моют за собой посуду, другие же – напротив, никогда не моют. Наутро, перед обходом главврача, вся посуда должна быть вымыта нянечками, поэтому завхоз хочет составить такой план выдачи тарелок, чтобы к концу смены нянечкам пришлось мыть их как можно меньше. Конечно же, в этих целях можно выдавать грязные тарелки, оставшиеся от предыдущих палат, постояльцам текущей. Ваша задача – посчитать, какое количество тарелок останется чистым.

Первая строка ввода содержит два целых числа $n$ и $k$ $(1 \leqslant n \leqslant 10^5, 1 \leq k \leqslant 10^5)$ – количество палат и тарелок, соответственно. Следующие n строк содержат по 2 целых числа $a_i$ и $bi$ $(0 \leqslant a_i + b_i \leqslant k)$ – количество постояльцев в очередной палате, моющих и не моющих за собой посуду, соответственно.

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

Тесты

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

2 4 1 2 1 1	3
4 10 2 6 4 5 1 1 2 2	8
3 12 2 8 1 4 0 1	5
3 5 2 2 1 3 0 5	0

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

#include <iostream>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    int dirty = 0;
    for (int i = 0; i < n; ++i) {
        int wash, not_wash; //кол-во моющих и не моющих за собой постояльцев
        cin >> wash >> not_wash;
        if (not_wash < dirty) {
            int free_dirty = dirty - not_wash; //оставшиеся грязные тарелки
            dirty -= min(wash, free_dirty);
        }
        else
        if (not_wash > dirty)
            dirty = not_wash;
    }
    cout << k - dirty;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, k;

cin >> n >> k;

int dirty = 0;

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

int wash, not_wash; //кол-во моющих и не моющих за собой постояльцев

cin >> wash >> not_wash;

if (not_wash < dirty) {

int free_dirty = dirty - not_wash; //оставшиеся грязные тарелки

dirty -= min(wash, free_dirty);

}

else

if (not_wash > dirty)

dirty = not_wash;

}

cout << k - dirty;

return 0;

}

Решение

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

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

Если же грязных тарелок меньше, чем «грязнуль»-постояльцев, то после посещения столовой этой палатой грязных тарелок останется столько, сколько там было «грязнуль».
Остается в конце посчитать количество чистых тарелок, зная количество грязных.

Решение задачи на ideone.com

Ссылка на контест

Related Images:

OCPC2021 K: Нобелевская премия

13/11/2021 by Мазурок Игорь Евгеньевич

Ограничение времени:	`500 мс`
Ограничение реального времени:	`5 с`
Ограничение памяти:	`256M`

Нобелевская премия

Дед Архип и дед Игнат, постояльцы палаты номер 17 заведения «Покосившийся Скворечник», убеждены, что они – великие математики – Блез Паскаль и Пьер Ферма соответственно. А как ещё должны проводить время математики, если не играя друг с другом в азартные игры? Вот и дед Архип с дедом Игнатом придумали себе развлечение – они раздобыли три баночки с таблетками умиротворения: по одной им вручили санитары, а третью прикарманил дед Архип («Во имя науки!» – воскликнул он, унося таблетки), воспользовавшись тем, что их соседа, деда Панаса, сморило прослушивание доказательства Великой теоремы Игната.

Правила игры следующие: игроки ходят по очереди в порядке старшинства. За один ход великий математик выбирает целое положительное число x и съедает x таблеток из какой-то одной баночки, либо съедает по x таблеток из всех трёх баночек сразу. Проигрывает тот, кто не может сделать ход, а его противник награждается магарычем от деда Пахома, убеждённого, что он – Альфред Нобель. Магарычем в области экономики, разумеется, ведь именно так награждают лучших математиков.

Дед Архип и дед Игнат с удовольствием бы сыграли, чтобы установить победителя, но предыдущий опыт подобных развлечений убедил их, что они необъяснимым образом теряют интерес к игре уже после первого хода. Поэтому они просят Вас назвать победителя по исходным данным, а таблетки они оставят для завтрашней игры. Не сомневайтесь, что великие математики всегда ходят оптимальным образом.

Единственная строка ввода содержит три целых числа a, b, c (0 ≤ a, b, c ≤ 1000) – количество таблеток в каждой из трёх баночек.

Выведите единственную строку «Ignat», если Нобелевскую премию получит дед Игнат, и «Arkhip», если удача на стороне деда Архипа.

Примеры

Входные данные	Результат работы
2 0 2	Arkhip
1 2 4	Ignat

Видеоразбор решения задач здесь.

Related Images:

OCPC2021 J: Театр теней

13/11/2021 by Мазурок Игорь Евгеньевич

Ограничение времени:	`3 с`
Ограничение реального времени:	`6 с`
Ограничение памяти:	`256M`

Театр теней

Тиктокеры Стас и Ян, постояльцы палаты номер 66 заведения «Покосившийся Скворечник», решили устроить перфоманс в прямом эфире. Они разместили на прямоугольном полу своей палаты n свечей в разных точках и готовятся провести представление, состоящее из m актов. В каждом акте должен гореть только определённый набор свечей, который будет таким образом создавать новую картину из теней на стене палаты, остальные свечи должны быть потушены. Область, попадающая в кадр, имеет ширину w, длину l, по ширине перекрывает палату целиком, а по длине оставляет небольшое пространство слева и справа, как показано на рисунке.

Сами тиктокеры в кадре появляться не должны, с этой целью они могут находиться либо у левой, либо у правой стенки палаты за кадром. Чтобы тушить и зажигать свечи, Стас и Ян могут делать перерывы между актами перфоманса, во время которых стрим отключается, и они будут выбегать в кадр: Стас будет только зажигать свечи, а Ян – только гасить, после чего они должны успеть скрыться из кадра до начала нового акта. Перед перфомансом Стас находится за кадром слева, а Ян – за кадром справа. Также изначально зажжены свечи, необходимые для первого акта.

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

Первая строка ввода содержит пять чисел – w, l, v₁, v₂ и n (1 ≤ w, l ≤ 50, 1 ≤ v₁, v₂ ≤ 20, 1 ≤ n ≤ 15) – размеры кадра, скорости Стаса и Яна и количество свечей на полу. Далее идут n строк с координатами свечей x_i, y_i (0 < x_i < l, 0 < y_i < w). Следующая строка содержит число m (1 ≤ m ≤ 10⁴) – количество актов перфоманса. Далее идут m строк, каждая из которых начинается с количества свечей, которые должны гореть в очередном акте и продолжается номерами этих свечей.

Единственная строка вывода должна содержать число – минимально возможное суммарное время перерывов между актами перфоманса с точностью до 10^-5.

Примеры

Входные данные	Результат работы
5 6 1 1 3 1 2 3 4 5 3 1 1 3	0.000000
5 6 1 1 3 1 2 3 4 5 3 3 1 3 2 1 2 3 1 2 3	8.828427

Видеоразбор решения задачи здесь.

Related Images:

OCPC2021: I Белка в колесе

13/11/2021 by Мазурок Игорь Евгеньевич

Ограничение времени:	`5 с`
Ограничение реального времени:	`10 с`
Ограничение памяти:	`256M`

Белка в колесе

Журналистка Ксюша, постоялица палаты номер 13 заведения «Покосившийся Скворечник», убеждена, что она – белка. Сейчас, стоя у окна своей палаты, она смотрит на растущее за окном дерево (как известно любой белке, это связный граф без циклов) и воображает, как резвится, перебегая по нему с ветки на ветку и обратно. Главред Аркаша, сосед Ксюши, возмущён таким бесцельным и беспорядочным расходованием энергии, поэтому он хочет соорудить из какой-то части (возможно, всего) дерева колесо, то есть, добавить в граф несколько рёбер, чтобы создать цикл, по которому и будет бегать Ксюша, вырабатывая сверхценные идеи для издания. Но, к сожалению, у Аркаши есть всего две подтяжки, которые он готов пожертвовать на это благое дело, а значит, он может добавить не более, чем два ребра в дерево, при этом, он хочет получить цикл максимальной длины, и каждая вершина должна входить в него не более одного раза, не то Ксюша запутается и выдаст что-то не передовое или социально неодобряемое. Длина цикла, как знает любой главред, считается по количеству рёбер в нём. Поскольку Аркаша не привык работать сам, он ждёт, что Вы подскажете ему максимальную длину колеса для белки и между какими вершинами вешать подтяжки, а не то он Вас закенселит.

Первая строка ввода содержит единственное целое число n (3 ≤ n ≤ 10⁵) – количество вершин дерева, растущего за окном. Следующие n-1 строк содержат пары целых чисел – номера вершин дерева, соединённых ребрами.

Первая строка вывода должна содержать одно число – максимальную достижимую длину колеса. Следующие 1 или 2 строки должны содержать пары целых чисел – какие пары вершин нужно соединить подтяжками, чтобы получить колесо нужной длины.

Примеры

Входные данные	Результат работы
4 1 2 2 3 3 4	4 1 4
4 1 2 1 3 1 4	4 2 3 2 4

Видеоразбор решения задачи здесь.

Related Images:

OCPC2021 H: Счастья всем даром!

13/11/2021 by Мазурок Игорь Евгеньевич

Ограничение времени:	`1 с`
Ограничение реального времени:	`5 с`
Ограничение памяти:	`256M`

Счастья всем даром!

В заведении «Покосившийся Скворечник» проходит традиционная воскресная перекличка. Во время этого мероприятия все постояльцы выстраиваются в ряд и по очереди, начиная с самого правого, выкрикивают свой порядковый номер в ряду. Кондуктор Кондрат, постоялец палаты номер 11, убежден, что если сегодня он выкрикнет счастливый номер, то удача наконец-то повернётся к нему лицом, и ему наконец-то выплатят зарплату за все те годы, что он обилечивал каждого встречного в «Покосившемся Скворечнике». Любому кондуктору известно, что счастливое число – это такое число, сумма цифр на чётных позициях которого совпадает с суммой на нечётных. Только что Кондрат услышал номер, который выкрикнул его сосед справа и теперь у кондуктора есть всего две секунды, чтобы понять, какой следующий номер – счастливый и, сломя голову, побежать занимать соответствующее место в ряду. Вы – его сосед слева, шепните правильный ответ Кондрату и на радостях он подарит Вам проездной!

Единственная строка ввода содержит натуральное число – номер, который выкрикнул сосед Кондрата. Этот номер содержит не более 100 цифр.

Выведите одно число – следующий по порядку счастливый номер.

Примеры

Входные данные	Результат работы
123123	123134
99	110

Видеоразбор решения задачи здесь.

Related Images:

OCPC021 G: Электрик возвращается

13/11/2021 by Мазурок Игорь Евгеньевич

Ограничение времени:	`1 с`
Ограничение реального времени:	`5 с`
Ограничение памяти:	`256M`

Электрик возвращается

Электрик Геннадий, постоялец палаты номер 404 заведения «Покосившийся Скворечник», прокрался ночью к ближайшей ЛЭП, чтобы наконец воплотить в жизнь свой план – отрезать кусок провода, находящийся между двумя соседними опорами, и отомстить лживой розетке из предыдущей задачи.

Он планирует реализовать это следующим образом: сначала просто забраться на вершину одной из опор, отрезать провод, закреплённый там, после чего спуститься на некоторую высоту вниз, возможно до земли. Далее Геннадий рассчитывает воспользоваться способностями человека-паука, которые, по его убеждению, открылись в нём после недавнего удара током: он выстрелит паутиной в некоторую произвольную точку соседнего столба, оттолкнется от первого столба и спустится по дуге окружности либо до второго столба, либо до земли. Разница высот в начале и конце такого спуска не должна превышать некоторую величину l, иначе наш новоявленный человек-паук рискует слишком сильно разогнаться и превратиться в человека-лепёшку. Затем электрик поднимется на вершину второго столба, чтобы отрезать закреплённый там провод, и спустится на землю.

Высоты столбов – h₁ и h₂, расстояние между ними – d. Геннадий не очень любит лазать вверх, поэтому он хочет разработать план таким образом, чтобы суммарная дистанция подъёмов была минимально возможной. Раз уж Вы взялись помогать ему, то доведите начатое до конца!

Единственная строка ввода содержит четыре целых числа d, h₁, h₂, l (1 ≤ d, h₁, h₂, l ≤ 10⁶).

Выведите одно число – минимальную суммарную дистанцию подъёма Геннадия с точностью не хуже 10^-5.

Примеры

Входные данные	Результат работы
5 5 5 5	10.00000
4 5 8 5	10.00000
4 8 5 1	13.00000
3 4 6 1	9.00000

Видеоразбор решения задачи здесь.

Related Images:

OCPC2021 F: Электрик наносит ответный удар

13/11/2021 by Мазурок Игорь Евгеньевич

Ограничение времени:	`1 с`
Ограничение реального времени:	`5 с`
Ограничение памяти:	`256M`

Электрик наносит ответный удар

Дата-центр «Покосившегося Скворечника» устроен следующим образом: помимо разной аппаратуры, из стены в ряд торчат 2∙n коннекторов: это n штепселей и n розеток. Геннадий планирует разбить их на пары розетка-штепсель и соединить каждую пару одним проводом таким образом, что штепсель всегда находится левее соответствующей розетки – эту идею ему навеяли правила средневекового этикета. Чтобы замыкание было Очень Длинным, Геннадий хочет, чтобы суммарная длина проводов, использованных для его коварного замысла, была максимально возможной. Помогите ему! Ну, или не мешайте хотя бы, и просто подскажите, провод какой длины он должен отрезать от соседней линии электропередач, чтобы распилить его на столь нужные ему провода.

Первая строка ввода содержит целое число n (2 ≤ n ≤ 1000). Вторая строка содержит n целых чисел – координаты штепселей слева направо. Третья строка содержит n чисел – координаты розеток слева направо. Все числа во второй и третьей строках различны и находятся в диапазоне от 0 до 10⁵.

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

Примеры

Входные данные	Результат работы
2 1 4 6 8	9
2 1 4 2 5	2

Видеоразбор решения задачи здесь.

Related Images:

OCPC2021 E: Объясните теперь нам, вахтёры…

13/11/2021 by Мазурок Игорь Евгеньевич

Ограничение времени:	`500 мс`
Ограничение реального времени:	`5 с`
Ограничение памяти:	`256M`

Объясните теперь нам, вахтёры…

В заведении «Покосившийся Скворечник» ЧП: на фоне ежеквартального обострения синдрома вахтёра из палаты номер 99 вырвался ночной сторож Михалыч и перегородил вход в уборную. Для пропуска внутрь он требует пароль, который он тут же записал на стене в виде строки из m строчных латинских символов. Но не всё так просто: недостаточно назвать пароль тщеславному Михалычу – нужно составить его из букв стихотворения, сочиненного ночным сторожем. И действительно, над паролем Михалыч записал стихи: n строк по m строчных латинских символов каждая. Чтобы получить искомый пароль, над ними разрешено проделывать следующую операцию: выбрать две различные строки с номерами i и j, выбрать номер символа k, а затем поменять местами k-й символ в строках номер i и j. Например, если мы меняем 3-й символ в паре строк «abcde» и «fghij», то получим «abhde» и «fgcij». Так нужно делать до тех пор, пока одна из строк не совпадёт с паролем.

Проверено, что санитары не в состоянии совладать с Михалычем, поэтому единственный способ разблокировать проход – это написать программу, которая по заданным строкам и паролю найдёт самый быстрый (мы же в уборную пытаемся попасть!) способ получить пароль из заданных строк.

Первая строка ввода содержит целое число n (2 ≤ n ≤ 100) – количество строк в стихотворении Михалыча. Каждая из последующих n строк состоит из строчных латинских символов и имеет одинаковую длину m (2 ≤ m ≤ 100). Последняя строка содержит пароль Михалыча длины m.

Первая строка вывода должна содержать минимальное число x операций над строками. Если получить пароль никак невозможно, выведите -1. В следующих x строках, если возможно получить пароль, выведите последовательность операций в формате i j k – номера первой и второй строк стихотворения Михалыча, над которыми производится операция обмена и номер символа в этих строках.

Примеры

Входные данные	Результат работы
3 cab abc bca cba	2 1 3 3 1 2 2
3 dbc aeb cca acd	-1

Видео разбор решения задачи здесь.

Related Images:

OCPC2021 D: Столовая

13/11/2021 by Мазурок Игорь Евгеньевич

Ограничение времени:	`2 с`
Ограничение реального времени:	`5 с`
Ограничение памяти:	`256M`

Столовая

В столовой заведения «Покосившийся Скворечник» имеется ровно k тарелок, а в самом заведении – n палат. По старой традиции, чтобы постояльцы не пугались новых знакомых и не обменивались симптомами, их приводят в столовую так, чтобы одновременно там находились только обитатели одной палаты. При этом, порядок посещения столовой палатами строго зафиксирован – от меньшего номера к большему.

Первая строка ввода содержит два целых числа n и k (1 ≤ n ≤ 10⁵, 1 ≤ k ≤ 10⁵) – количество палат и тарелок, соответственно. Следующие n строк содержат по 2 целых числа a_i и b_i (0 ≤ a_i + b_i ≤ k) – количество постояльцев в очередной палате, моющих и не моющих за собой посуду, соответственно.

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

Примеры

Входные данные	Результат работы
2 4 1 2 1 1	3

Видеоразбор решения здесь.

Related Images:

OCPC2021 C: Перепись чисел

13/11/2021 by Мазурок Игорь Евгеньевич

Ограничение времени:	`1 с`
Ограничение реального времени:	`5 с`
Ограничение памяти:	`256M`

Перепись чисел

Учительница младших классов Марь Ивановна, постоялица палаты номер 9 ³/₄ заведения «Покосившийся Скворечник», насмотрелась «Гарри Поттера» и теперь боится, что Волдеморт сотрёт у неё из памяти какое-нибудь число. Чтобы не допустить этого преступления, Марь Ивановна решила выписать все числа от 1 до n (числа, большие, чем n, ей для работы всё равно не пригодятся) подряд в одну строку на стене палаты. При этом, для экономии времени (Волдеморт уже рядом!), она решила приписывать очередное число к своей строке только в том случае, если его десятичная запись еще не содержится в уже записанной строке. Например, в строке «1234567891011» уже содержится запись числа 12, а значит, приписывать это число не нужно.

Сосед Марь Ивановны, трудовик Василий Семёныч, убеждён, что Волдеморт уже стёр какое-то число из памяти учительницы младших классов. Чтобы удостовериться в своей правоте, он требует, чтобы Вы показали ему, как должна выглядеть верная строка, составленная по правилам Марь Ивановны, для сравнения с тем, что в итоге появится на стене палаты. В награду за помощь он обещает выстрогать бузинную палочку для вас. Поскольку в руках у Василия Семёныча лобзик, лучше с ним не спорить!

На ввод поступает единственное целое число n (1 ≤ n ≤ 10⁵) – максимальное число, важное для работы учительницы младших классов.

Выведите одну строку, содержащую запись всех чисел от 1 до n по правилам Марь Ивановны.

Примеры

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

Результат работы

1234

1234567891011131415

1	1234567891011131415

Видеоразбор решения здесь.

Related Images:

OCPC2021 B: Палиндромонойя

13/11/2021 by Мазурок Игорь Евгеньевич

Ограничение времени:	`500 мс`
Ограничение реального времени:	`5 с`
Ограничение памяти:	`256M`

Палиндромонойя

Студент Илья, постоялец палаты номер 101 заведения «Покосившийся Скворечник», попавший сюда во время сессии на почве экзамена по программированию, убеждён, что его повсюду преследуют затаившиеся палиндромы. «Они среди нас! Как же вы этого не замечаете?!» – то и дело слышат от него нянечки Алла и Анна. По убеждению Ильи, палиндром – это слово, читающееся одинаково, как слева направо, так и справа налево. Если же на первый взгляд слово таковым не является, то студент не опускает рук и переносит буквы по одной из начала слова в конец, пока оно не станет палиндромом. Если из слова таким образом удалось получить палиндром за 0 или более операций, Илья называет его затаившимся палиндромом, после чего студент начинает бегать по потолку с воплями отчаяния, чем доставляет неудобства окружающим. Например, Илью может довести до исступления слово «масса», ведь из него можно получить «самас», перенеся 3 буквы из начала в конец. Главврач хочет выкинуть из палаты номер 101 Илью, но вместо этого выкинет все предметы, названия которых являются затаившимися палиндромами. Осталось только проверить их все, а здесь без программы не обойтись!

На ввод поступает строка, содержащая одно слово, длиной от 1 до 100 латинских строчных букв.

Примеры

Входные данные	Результат работы
array	yes
iliya	no
anna<	yes<

Ссылки

Related Images:

OCPC2021 A: Колёса деда Панаса

13/11/2021 by Мазурок Игорь Евгеньевич

Ограничение времени:	`500 мс`
Ограничение реального времени:	`5 с`
Ограничение памяти:	`256M`

Колёса деда Панаса

На ввод поступает единственное целое четное число n (2 ≤ n ≤ 10⁹) – количество таблеток на столе.

Выведите одно число – количество способов распределить колёса между автомобилями и мотоциклами. Помните, что для автомобиля нужно 4 колеса, для мотоцикла – 2. Два способа считаются различными, если в одном из них количество автомобилей не совпадает с количеством автомобилей в другом; то же самое справедливо и для мотоциклов.

Примеры

Входные данные	Результат работы
6	2

Видеоразбор решения здесь.

Related Images:

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:

Минимальная реализация алгоритма RSA на C++

06/06/2019 by Андрей Зиновьев

Описание программы

Алгоритм асимметричного шифрования RSA основан на практической сложности факторизации больших чисел, что делает его на сегодняшний день одним из самых популярных криптографических алгоритмов.
Однако он имеет свои отрицательные стороны, например среди них достаточно низкая скорость шифрования, поэтому зачастую используют смешанную криптосистему, в которой сначала две стороны передают симметричный ключ с помощью RSA, а затем шифруют сообщение с помощью какого-либо симметрического алгоритма, например AES.
О самом алгоритме можно почитать например тут.
RSA может шифровать числа до так называемого модуля, который является частью ключа. В настоящее время используются модули длиной в 1024, 2048 и даже 4096 бит. В нашей реализации без длинной арифметики получится иметь дело максимум с 64-битными ключами, однако для наглядности этого хватит. Для того, чтобы сообщение при шифровании многократно не увеличивалось в размере, шифровать его надо блоками по $k — 1$ бит, где $k$ — битность ключа. При этом каждый блок перейдет в $k$-битное число, то есть на больших файлах прирост размера составит всего лишь $\frac{k}{k-1}$ раз, и чем больше ключ — тем меньше этот прирост.
В программе делением массива чисел одной битности на числа другой битности занимается функция resize, дополняя недостающие биты нулями.
Шифрованием и одновременно дешифрованием занимается функция process_bytes, так как в RSA оба этих процесса имеют идентичные алгоритмы, отличающиеся только размером блока входа и выхода. Для этого используется алгоритм быстрого возведения в степень.
Также программа может генерировать ключи на основании предустановленных простых чисел (в будущем случайных), или на основании простых чисел, введенных пользователем. Для этого используется нахождении обратного в кольце по модулю расширенным алгоритмом Евклида.
Программа реализована в интерактивном виде, список команд можно вызвать командой h.

Continue reading →

Related Images:

Анаграммы

26/11/2018 by Иван Киреев

Анаграммы

Игорю стало интересно какое количество перестановок букв его фамилии существует. Для этого он выписал на листке бумаге все буквы своей фамилии по алфавиту и начал создавать новые перестановки этих букву в лексикографическом порядке, записывая их на листок.

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

Игоря будут интересовать только слова которые записаны в словаре, так как других он не знает.

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

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

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

Задан словарь английских слов. Каждое слово в новой строке. Длинна слова не более $255$ символов. Количество слов любое.

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

Вывести все слова что имеют максимальное количество анаграмм в нем.

Решение

Прочитаем словарь. Запишем в структуру pair строку с исходным словом в first и отсортированную в second. Анаграммами будут являться слова с одинаковыми second строками. Так как они будут состоять из одних и тех же букв, которые выстроены в одинаковом порядке. Отсортируем множество слов из словаря по second. Таким образом все слова анаграммы будут находиться рядом.

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

На выходе получим массив индексов слов у которых существует максимальное количество анаграмм, в данном словаре. Выведем эти слова и все анаграммы к ним в исходном варианте. Для этого нам и нужна строка first.

Тесты

№

Ввод

Вывод

2500 слов английского языка

trace react crate

dear dare read

post stop spot

Код

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#define DIFFERENCE ('A' - 'a') // разность регистров
using namespace std;
bool IsBigAlpha(char a) {
	return (a >= 'A' && a <= 'Z');
}
bool IsSmalAlpha(char a) {
	return (a >= 'a' && a <= 'z');
}
string edit(const string &str) { // приводим всё к нижнему регистру и  убираем лишние символы
	string rez = "";
	for(char a : str) {
		if (IsBigAlpha(a)) a -= DIFERENSE;
		if (IsSmalAlpha(a)) rez += a;
	}
	return rez;
}
bool comp(const pair<string, string> &a, const pair<string, string> &b) { // сравнитель по второй строке
	return a.second < b.second;
}
int main() {
	vector <pair<string, string>> words; // словарь
	string str;
	while (getline(cin, str, '\n')) {
		pair<string, string> word; // слово
		word.first = str;
		word.second = edit(str);
		sort(word.second.begin(), word.second.end()); // сортируем буквы в слове
		words.push_back(word);
	}
	sort(words.begin(), words.end(), comp); // сортируем словарь по анаграммам
	vector <int> indeces; // массив индексов
	int Count = 0, MaxCount = 0, n = words.size();
	for (int i = 1; i < n; i++) {
		if (words[i-1].second == words[i].second) Count++; 
		else {
			if (Count > MaxCount) { 
				MaxCount = Count;
				indeces.clear();
				indeces.push_back(i-1);
			} else if (Count == MaxCount) indeces.push_back(i-1);
			Count = 0;
		}
	}
	if (Count > MaxCount) {  // обрабатываем последний найденный набор анаграмм
				MaxCount = Count;
				indeces.clear();
				indeces.push_back(n-1);
	} else if (Count == MaxCount) indeces.push_back(n-1);
	bool first = 1;
	for (int index : indeces) { // выводим
		if (!first) cout << endl << "---------------" << endl;
		else first = 0;
		for (int i = 0; i <= MaxCount; i++) {
			if (i != 0) cout << endl;
			cout << words[index - i].first;
		}
	}
	return 0;
}

#include <iostream>

#include <string>

#include <algorithm>

#include <vector>

#define DIFFERENCE ('A' - 'a') // разность регистров

using namespace std;

bool IsBigAlpha(char a) {

return (a >= 'A' && a <= 'Z');

}

bool IsSmalAlpha(char a) {

return (a >= 'a' && a <= 'z');

}

string edit(const string &str) { // приводим всё к нижнему регистру и убираем лишние символы

string rez = "";

for(char a : str) {

if (IsBigAlpha(a)) a -= DIFERENSE;

if (IsSmalAlpha(a)) rez += a;

}

return rez;

}

bool comp(const pair<string, string> &a, const pair<string, string> &b) { // сравнитель по второй строке

return a.second < b.second;

}

int main() {

vector <pair<string, string>> words; // словарь

string str;

while (getline(cin, str, '\n')) {

pair<string, string> word; // слово

word.first = str;

word.second = edit(str);

sort(word.second.begin(), word.second.end()); // сортируем буквы в слове

words.push_back(word);

}

sort(words.begin(), words.end(), comp); // сортируем словарь по анаграммам

vector <int> indeces; // массив индексов

int Count = 0, MaxCount = 0, n = words.size();

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

if (words[i-1].second == words[i].second) Count++;

else {

if (Count > MaxCount) {

MaxCount = Count;

indeces.clear();

indeces.push_back(i-1);

} else if (Count == MaxCount) indeces.push_back(i-1);

Count = 0;

}

if (Count > MaxCount) { // обрабатываем последний найденный набор анаграмм

MaxCount = Count;

indeces.clear();

indeces.push_back(n-1);

} else if (Count == MaxCount) indeces.push_back(n-1);

bool first = 1;

for (int index : indeces) { // выводим

if (!first) cout << endl << "---------------" << endl;

else first = 0;

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

if (i != 0) cout << endl;

cout << words[index - i].first;

}

return 0;

}

Код на ideone

Related Images:

Сумма делителей — 2

12/07/2018 by Алиса Ворохта

Задача

Профессор из тридевятого царства решил, что посчитать сумму делителей числа $n$ до $10^{10}$ сможет любой троечник, поэтому усложнил для Кости задачу, дав числа с большим количеством цифр. Но наш герой не хотел сдаваться, уж больно он хотел стать отличником.
Костя очень просит Вас помочь ему в этом деле, ведь он помнит, как успешно Вы справились с предыдущей задачей.

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

Одно целое число $n \left(1 \leqslant n < 10^{15}\right).$

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

Выведите сумму делителей числа $n.$

Тесты

Входные данные	Выходные данные
$100000000000031$	$100000000000032$
$10000019$	$10000020$
$400001520001444$	$700002730002667$
$9$	$13$
$304250263527210$	$1281001468723200$
$94083986096100$	$457766517350961$
$1234567898765$	$1517681442816$
$100000000000000$	$249992370597277$
$562949953421312$	$1125899906842623$
$81795$	$161280$
$9999999999999$	$14903272088640$
$997$	$998$
$1325$	$1674$
$2468013$	$3290688$
$951641320$	$2447078400$
$71675429738641$	$71695352830464$
$1100000000033$	$1200000000048$
$6300088$	$11859480$
$98$	$171$
$9102837465$	$15799834440$

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

#include <iostream>
#include <map>
using namespace std;
int main ()
{
    long long n, sumOfDivisors = 1;
    cin >> n;
    map<long long, long long> primeDivInPow;
    for(long long i = 2; i * i <= n; i++){
        while(n % i == 0){
            if(primeDivInPow.find(i) == primeDivInPow.end()){
                primeDivInPow[i] = 1;
            }
            primeDivInPow[i] *= i;
            n /= i;
        }
    }
    if(n != 1){
        primeDivInPow[n] = n;
    }
    for(map<long long, long long>::iterator p = primeDivInPow.begin(); p != primeDivInPow.end(); p++){
        sumOfDivisors *= (p -> second - 1) / (p -> first - 1) + p -> second;
    }
    cout << sumOfDivisors;
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int main ()

{

long long n, sumOfDivisors = 1;

cin >> n;

map<long long, long long> primeDivInPow;

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

while(n % i == 0){

if(primeDivInPow.find(i) == primeDivInPow.end()){

primeDivInPow[i] = 1;

}

primeDivInPow[i] *= i;

n /= i;

}

if(n != 1){

primeDivInPow[n] = n;

}

for(map<long long, long long>::iterator p = primeDivInPow.begin(); p != primeDivInPow.end(); p++){

sumOfDivisors *= (p -> second - 1) / (p -> first - 1) + p -> second;

}

cout << sumOfDivisors;

return 0;

}

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

Пусть $n$ имеет каноническое разложение $n = p_1^{\alpha_1}\cdot p_2^{\alpha_2}\cdot\ldots p_k^{\alpha_k},$ где $p_1 < p_2 < \ldots <p_k$ — простые делители числа $n$, $\alpha_1, \alpha_2,\ldots, \alpha_k \in \mathbb {N}$. Тогда сумма натуральных делителей числа $n$ равна $\sigma\left(n\right) = \left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\times$$\times\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right).$
Доказательство.
Рассмотрим произведение:
$\left(1 + p_1 + p_1^2 +\ldots + p_1^{\alpha_1}\right)\cdot\left(1 + p_2 + p_2^2 +\ldots + p_2^{\alpha_2}\right)\cdot\ldots\cdot\left(1 + p_k + p_k^2 +\ldots + p_k^{\alpha_k}\right)$
Если раскрыть скобки, то получим сумму членов ряда:
$p_1^{\beta_1}\cdot p_2^{\beta_2}\cdot\ldots\cdot p_k^{\beta_k},$ где $0\leqslant\beta_m\leqslant\alpha_m \left(m = 1, 2, \ldots, k\right)$
Но такие члены являются делителями $n$, причем каждый делитель входит в сумму только один раз. Поэтому рассмотренное нами произведение равно сумме всех делителей $n,$ т.е. равно $\sigma\left(n\right).$ Итак, $\sigma\left(n\right)$ можно вычислить по нашей формуле. С другой стороны, каждая сумма $1 + p_m + p_m^2+\ldots+p_m^{\alpha_m}$ является суммой геометрической прогрессии с первым членом $1$ и знаменателем $p_m$. Поэтому иначе данную формулу можно переписать так:
$$\sigma\left(n\right) = \frac{p_1^{\alpha_1+1}-1}{p_1-1}\cdot\frac{p_2^{\alpha_2+1}-1}{p_2-1}\cdot\ldots\cdot\frac{p_k^{\alpha_k+1}-1}{p_k-1}.$$
Для того, чтобы не вычислять $p_k^{\alpha_k+1}$, перепишем данную формулу в следующем виде:
$$\sigma\left(n\right) = \left(\frac{p_1^{\alpha_1}-1}{p_1-1}+p_1^{\alpha_1}\right)\cdot\left(\frac{p_2^{\alpha_2}-1}{p_2-1}+p_2^{\alpha_2}\right)\cdot\ldots\cdot\left(\frac{p_k^{\alpha_k}-1}{p_k-1}+p_k^{\alpha_k}\right).$$

Ссылки

Код решения

Related Images:

Псевдо строчная таблица

12/07/2018 by Костя Григорян

Задача

В тридесятом государстве объявлено новое соревнование. Каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, имеющую размер $m \times n$. При этом для каждой ячейки таблицы указана минимальная площадь, которую должна эта ячейка занимать. Все строки таблицы равны между собой. Задача участников — начертить таблицу наименьшей высоты. Алиса снова очень хочет победить, но она все еще плохо знает математику, поэтому она просит Вас помочь ей в этом непростом деле.

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

Первая строка содержит два натуральных числа $m$ и $n$, $(1 \leqslant m,n \leqslant 100).$ Далее идут $m$ строк содержащие по $n$ натуральных чисел — $s_1, s_2, \cdots , s_{n-1}, s_n$ — минимальные площади каждой ячейки $(1 \leqslant s_i \leqslant 100).$

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

Вывести минимальную высоту таблицы.

Тесты

$2 \ 3$	$12$
$1 \ 2 \ 3 \\ 1 \ 2 \ 3$
$1 \ 3$	$10$
$2 \ 3 \ 5$
$4 \ 4$	$96$
$3 \ 5 \ 7 \ 9 \\ 3 \ 5 \ 7 \ 9 \\ 3 \ 5 \ 7 \ 9 \\ 3 \ 5 \ 7 \ 9$
$3 \ 1$	$6$
$2 \\ 2 \\ 2$
$5 \ 3$	$430$
$46 \ 28 \ 12 \\ 46 \ 28 \ 12 \\ 46 \ 28 \ 12 \\ 46 \ 28 \ 12 \\ 46 \ 28 \ 12$
$2 \ 6$	$216$
$7 \ 32 \ 3 \ 23 \ 12 \ 31 \\ 7 \ 32 \ 3 \ 23 \ 12 \ 31$
$7 \ 5$	$945$
$5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78$
$1 \ 1$	$5$
$5$
$3 \ 7$	$210$
$10 \ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \\ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \\ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \ 10$
$2 \ 2$	$202$
$100 \ 1 \\ 100 \ 1$

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

#include <iostream>
using namespace std;
 
int main() {
    int n, m;
    cin >> m >> n;
    long long s[m][n], h=0;
    for(int i=0; i<m; i++)
    {
        for(int j=0; j<n; j++)
        {
            cin >> s[i][j];
        }
    }
    for(int i=0; i<n; i++)
    {
        h+=s[0][i];
    }
    cout << m*h;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m;

cin >> m >> n;

long long s[m][n], h=0;

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

{

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

{

cin >> s[i][j];

}

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

{

h+=s[0][i];

}

cout << m*h;

return 0;

}

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

Так как все строки равны между собой, тогда решение задачи состоит в том, чтобы разбить таблицу на строки размером $1 \times n$ и найти их минимальную высоту. Как находить высоту $h$ для каждой такой строки было показано тут. Тогда минимальная высота всей таблицы равна $m \cdot h.$

Ссылки

Код решения