e-olymp 5338. Полный граф — 2

23/05/2019 by Инна Литвиненко

Задача

Обсуждая личную жизнь всевозможных злодеев, мы обделили своим вниманием графа Дуку. Так вот, граф Дуку на досуге любит складывать оригами. Он давно систематизировал свои познания в этой области следующим образом: всего граф знает n фигурок, причем для некоторых из них он знает, как получать из одной другую. Для обучения начинающих ситхов Дуку разработал специальную таблицу. В ячейке $[i, j]$ таблицы стоит «1», если граф может получить из фигурки $i$ фигурку $j$ одним сгибом. Иначе там стоит «0». Изначально в руках у графа Дуку чистый лист, то есть фигурка номер $x$ по его системе, сложить же он желает журавлика – фигурку номер $y$.
Найдите, за сколько операций граф достигнет желаемого.

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

В первой строке находится число $n (1 \leq n \leq 1000)$. В следующих $n$ строках задана таблица Дуку. В $(n + 1)$ — ой строке стоят числа $x$ и $y$.

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

Выведите минимальное количество операций, которые придется осуществить. Если же коварным планам Графа не суждено осуществиться, выведите «-1».

Тесты

№	Ввод	Вывод
1	4 0 0 1 0 0 0 0 1 1 0 0 1 0 1 1 0 1 2	3
2	4 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 2	-1
3	5 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 1 5	4
4	2 0 1 1 0 2 1	1
5	6 0 1 1 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 5 2	-1

Код

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

int main() {
    int n, x, y, v;
    cin >> n;
    int matrix[n + 1][n + 1], dist[n + 1]; 
    queue <int> plan;
    for (int i = 1; i <= n; i++) 
        for (int j = 1; j <= n; j++)
            cin >> matrix[i][j];
    cin >> x >> y;
    for (int i = 1; i <= n; i++)
        dist[i] = -1;
    plan.push(x);
    dist[x] = 0;
    while (!plan.empty()) {
        v = plan.front();
        plan.pop();
        for (int i = 1; i <= n; i++) {
            if (dist[i] == -1 && matrix[v][i]) {
                plan.push(i);
                dist[i] = dist[v] + 1;
            }
        }
        if (v == y) plan.empty(); // если обработали вершину y, прекращаем обход
    } 
    cout << dist[y];
    return 0;
}

#include <iostream>

#include <queue>

using namespace std;

int main() {

int n, x, y, v;

cin >> n;

int matrix[n + 1][n + 1], dist[n + 1];

queue <int> plan;

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

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

cin >> matrix[i][j];

cin >> x >> y;

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

dist[i] = -1;

plan.push(x);

dist[x] = 0;

while (!plan.empty()) {

v = plan.front();

plan.pop();

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

if (dist[i] == -1 && matrix[v][i]) {

plan.push(i);

dist[i] = dist[v] + 1;

}

if (v == y) plan.empty(); // если обработали вершину y, прекращаем обход

}

cout << dist[y];

return 0;

}

Решение

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

Ссылки

Условие задачи на e-olymp
Код на Ideone
Описание алгоритма на сайте e-maxx.ru

Related Images:

e-olymp 390. Анаграммы

01/05/2019 by Инна Литвиненко

Задача

Анаграммой слова называется любая перестановка всех букв слова. Например, из слова SOLO можно получить 12 анаграмм: SOLO, LOSO, OSLO, OLSO, OSOL, OLOS, SLOO, LSOO, OOLS, OOSL, LOOS, SOOL.

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

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

Слово, количество букв в котором не превышает 14.

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

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

Тесты

№	Ввод	Вывод
1	SOLO	12
2	ANAGRAM	840
3	PERMUTATION	19958400
4	AAAAA	1
5	AABBBCCC	560

Код (string)

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

int main() {
    string s;
    map <char, int> m;
    cin >> s;
    int l = s.size(), count = 1;
    long long fact[15];
    fact[1] = 1;
    for (int i = 2; i <= l; i++) //заполняем массив факториалов
        fact[i] = fact[i - 1] * i;
    for (int i = 0; i < l; i++) //подсчитываем повторения
        ++m[s[i]];
    for (auto it = m.begin(); it != m.end(); it++) 
        if (it -> second > 1) count *= fact[it -> second];
    cout << fact[l] / count; 
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

string s;

map <char, int> m;

cin >> s;

int l = s.size(), count = 1;

long long fact[15];

fact[1] = 1;

for (int i = 2; i <= l; i++) //заполняем массив факториалов

fact[i] = fact[i - 1] * i;

for (int i = 0; i < l; i++) //подсчитываем повторения

++m[s[i]];

for (auto it = m.begin(); it != m.end(); it++)

if (it -> second > 1) count *= fact[it -> second];

cout << fact[l] / count;

return 0;

}

Код (c-string)

#include <iostream>
#include <cstring>
#include <map>
using namespace std;
 
int main() {
    char s[15]; //равносильно char * s = new char [15], где 15 - максимальный размер строки
    map <char, int> m;
    cin >> s;
    int l, count = 1;
    l = strlen(s);
    long long fact[15];
    fact[1] = 1;
    for (int i = 2; i <= l; i++) //заполняем массив факториалов
        fact[i] = fact[i - 1] * i;
    for (int i = 0; i < l; i++) //подсчитываем повторения
        ++m[s[i]];
    for (auto it = m.begin(); it != m.end(); it++) 
        if (it -> second > 1) count *= fact[it -> second];
    cout << fact[l] / count; 
    return 0;
}

#include <iostream>

#include <cstring>

#include <map>

using namespace std;

int main() {

char s[15]; //равносильно char * s = new char [15], где 15 - максимальный размер строки

map <char, int> m;

cin >> s;

int l, count = 1;

l = strlen(s);

long long fact[15];

fact[1] = 1;

for (int i = 2; i <= l; i++) //заполняем массив факториалов

fact[i] = fact[i - 1] * i;

for (int i = 0; i < l; i++) //подсчитываем повторения

++m[s[i]];

for (auto it = m.begin(); it != m.end(); it++)

if (it -> second > 1) count *= fact[it -> second];

cout << fact[l] / count;

return 0;

}

Решение

Данная задача решается с помощью единой формулы \begin{equation} N_s =\frac {length!}{p_1! × p_2! × \ldots\ × p_n!}\end{equation} где $ length$ — длина строки, а $p_i$ — количество повторений одной буквы $(i = 1, 2, \ldots\ , n$, $ n$ — количество различных букв). Буквы, повторяющиеся один раз, можем опустить, так как их факториал даст единицу, что никак не повлияет на результат.
Длину строки найдем с помощью метода size()(или strlen()), а количество повторений для удобства будем подсчитывать в контейнере map.

Ссылки

Задача 390 на e-olymp

Код на Ideone (string)

Код на Ideone (c-string)

Related Images:

e-olymp 1488. Шахматная головоломка

22/02/2019 by Инна Литвиненко

Задача

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

В этот раз Борис задал Вове следующую головоломку: на шахматном поле размером $8 × 8$ клеток стоит одна шахматная фигура — конь. Необходимо расположить на поле еще две шахматные фигуры — ладью и слона, таким образом, чтобы они били коня, но не били друг друга, и конь не бил их. Так как Вова еще не очень силен в программировании, он попросил вас помочь ему с решением данной головоломки.

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

Ладья бьет те клетки, которые находятся на той же горизонтали или вертикали, что и она. Слон бьет те клетки, которые находятся на той же диагонали, что и он.

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

Первая строка входного файла содержит положение коня в следующем формате. Сначала буква от $a$ до $h$, обозначающая номер столбца в котором находится конь, потом цифра от $1$ до $8$, обозначающая номер строки.

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

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

Гарантируется, что требуемая расстановка всегда существует.

Тесты

№	Ввод	Вывод
1	a1	d1 b2
2	h8	e8 g7
3	e5	b5 d4
4	c8	f8 d7
5	h6	e6 g5

Код

#include <iostream>
using namespace std;

int main() {
    int k1;
    char k0;
    cin >> k0 >> k1;
    int n = 8; //Вводим n, чтобы иметь возможность изменить размер доски 
    char mid = char (('a' + n) - n / 2); //Находим середину доски
    if ( k1 != 1) {
        if (k0 < mid) cout << char(k0 + 3) << k1 << "\n" << char(k0 + 1) << k1 - 1;
        else cout << char(k0 - 3) << k1 << "\n" << char(k0 - 1) << k1-1;
    }
    else {
        if (k0 < mid) cout << char(k0 + 3) << k1 << "\n" << char(k0 + 1) << k1 + 1;
        else cout << char(k0 - 3) << k1 << "\n" << char(k0 - 1) << k1 + 1;
    } 
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int k1;

char k0;

cin >> k0 >> k1;

int n = 8; //Вводим n, чтобы иметь возможность изменить размер доски

char mid = char (('a' + n) - n / 2); //Находим середину доски

if ( k1 != 1) {

if (k0 < mid) cout << char(k0 + 3) << k1 << "\n" << char(k0 + 1) << k1 - 1;

else cout << char(k0 - 3) << k1 << "\n" << char(k0 - 1) << k1-1;

}

else {

if (k0 < mid) cout << char(k0 + 3) << k1 << "\n" << char(k0 + 1) << k1 + 1;

else cout << char(k0 - 3) << k1 << "\n" << char(k0 - 1) << k1 + 1;

}

return 0;

}

Решение

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

Ссылки

Задача 1488 на e-olymp

Код задачи на Ideone

Related Images:

e-olymp 1485. Серия степеней матриц

26/01/2019 by Инна Литвиненко

Задача

По заданной матрице A размера n×n и положительному целому значению $k$ вычислить сумму $S = A + A^2+ A^3 + … + A^k.$

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

Первая строка содержит три положительных целых числа $n (n ≤ 30)$, $k (k ≤ 10^9)$ и $m (m < 10^4)$. Каждая из следующих $n$ строк содержит $n$ неотрицательных целых чисел меньших $32768$, задающих элементы матрицы $A$ в порядке возрастания строк.

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

Вывести элементы матрицы $S$ по модулю $m$ в таком же виде как и входная матрица $A$.

Тесты

№	Ввод	Вывод
1	2 2 4 0 1 1 1	1 2 2 3
2	4 7 2 3 5 12 10 8 9 2 16 7	1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 0
3	5 10 78 7 6 0 1 6 12 9 1 1 8 1 1 3 1 9 8 5 34 1 7 5 5 5 5 5	2 67 36 32 48 2 6 10 49 65 67 14 58 4 29 64 54 33 45 46 41 4 50 8 55
4	3 2 4 3 3 3 3 3 3 3 3 3	2 2 2 2 2 2 2 2 2
5	5 100 1000 1846 4675 8090 4539 1234 4567 7453 9564 6548 1111 5674 9876 5432 1010 1515 0 478 3 11 0 68303 7777 32767 14 8008	614 7 945 925 381 22 332 981 689 527 351 627 130 686 420 340 628 819 758 629 913 426 396 871 91

Код

#include <iostream>
using namespace std;

struct matrix {
    int mat[31][31];
};

long n, m;
matrix E; //единичная матрица

matrix mul(matrix A, matrix B) {
    matrix C;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) {
            C.mat[i][j] = 0;
            for (int v = 0; v < n; v++)
                C.mat[i][j] += A.mat[i][v] * B.mat[v][j] % m;
        }
    return C;
}

matrix sum(matrix A, matrix B) { 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            A.mat[i][j] += B.mat[i][j] % m;
    return A;
}

matrix power(matrix A, int k) { 
    if (k == 1)
        return A;
    matrix B = power(A, k / 2);
    B = mul(B, B);
    if (k % 2 != 0)
        B = mul(B, A);
    return B;
}

matrix res(matrix A, int k) {
    if (k == 1)
        return A;
    if (k % 2 == 0) {
        matrix B = res(A, k / 2);
        return mul(sum(power(A, k / 2), E), B);
    }
    else {
        matrix B = res(A, k / 2);
        matrix C = power(A, (k + 1) / 2);
        return sum(C, mul(B, sum(C, E)));
    }
}

int main() {
    long long k;
    matrix A;
    cin >> n >> k >> m;
    for (int i = 0; i < n; i++) {
        E.mat[i][i] = 1;
        for (int j = 0; j < n; j++) 
            cin >> A.mat[i][j];
    }
    matrix ans = res(A, k);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
           if (j != 0)
                cout << " ";
            cout << ans.mat[i][j] % m;
        }
        cout << "\n";
    }
    return 0;
}

#include <iostream>

using namespace std;

struct matrix {

int mat[31][31];

};

long n, m;

matrix E; //единичная матрица

matrix mul(matrix A, matrix B) {

matrix C;

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

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

C.mat[i][j] = 0;

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

C.mat[i][j] += A.mat[i][v] * B.mat[v][j] % m;

}

return C;

}

matrix sum(matrix A, matrix B) {

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

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

A.mat[i][j] += B.mat[i][j] % m;

return A;

}

matrix power(matrix A, int k) {

if (k == 1)

return A;

matrix B = power(A, k / 2);

B = mul(B, B);

if (k % 2 != 0)

B = mul(B, A);

return B;

}

matrix res(matrix A, int k) {

if (k == 1)

return A;

if (k % 2 == 0) {

matrix B = res(A, k / 2);

return mul(sum(power(A, k / 2), E), B);

}

else {

matrix B = res(A, k / 2);

matrix C = power(A, (k + 1) / 2);

return sum(C, mul(B, sum(C, E)));

}

int main() {

long long k;

matrix A;

cin >> n >> k >> m;

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

E.mat[i][i] = 1;

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

cin >> A.mat[i][j];

}

matrix ans = res(A, k);

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

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

if (j != 0)

cout << " ";

cout << ans.mat[i][j] % m;

}

cout << "\n";

}

return 0;

}

Решение

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

Далее создадим функцию быстрого возведения в степень. $A^k$ представим как $\left(A^2\right)^\frac{k}{2}$ при четном $k$ и $A × \left(A^2\right)^{\frac{k — 1}{2}}$ в противном случае. Такой алгоритм позволяет значительно уменьшить количество умножений.

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

Все, что еще необходимо сделать — вывести результат по модулю $m$.

Замечание

Тесты на e-olymp требуют отсутствия пробела после последнего столбца.

Ссылки

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

Код задачи на Ideone

Related Images:

e-olymp 8374. Нечетное количество раз

09/12/2018 by Инна Литвиненко

Задача

Найдите число, которое встречается в последовательности нечетное количество раз.

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

Первая строка содержит натуральное число $n (n < 500000)$. Далее следуют $n$ натуральных чисел, каждое из которых меньше $10^6$.

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

Во входной последовательности только одно число $x$ повторяется нечетное количество раз. Другие числа повторяются четное число раз. Выведите $x$.

Замечание

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

Тесты

№	Ввод	Вывод
1	9 3 1 2 2 17 1 3 17 3	3
2	5 12 13 14 13 12	14
3	3 20 0 20	0
4	15 5 7 1 2 3 5 7 2 7 5 1 2 3 5 2	7
5	11 10 100 1000 100 100 100 1000 10 100 1000 100	1000

Код 1

#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    long long n, *x;
    cin >> n;
    x = new long long[n];
    for (int i = 0; i < n; i++)
        cin >> x[i];
    sort(x, x + n);
    long long k, y;
    k = 1;
    y = x[0];
    for (int i = 1; i < n; i++) {
        if (x[i] == y)
            k++;
        else {
            if (k % 2 != 0) {
                cout << y;
                return 0;
            }
            else {
                k = 1;
                y = x[i];
            }
        }
    }
    cout << x[n - 1];
    delete []x;
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

long long n, *x;

cin >> n;

x = new long long[n];

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

cin >> x[i];

sort(x, x + n);

long long k, y;

k = 1;

y = x[0];

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

if (x[i] == y)

k++;

else {

if (k % 2 != 0) {

cout << y;

return 0;

}

else {

k = 1;

y = x[i];

}

cout << x[n - 1];

delete []x;

return 0;

}

Код 2

#include <iostream>
using namespace std;
 
int main() {
    long long n, *x;
    cin >> n;
    x = new long long[n];
    for (int i = 0; i < n; i++)
        cin >> x[i];
    long res = 0;
    for (int i = 0; i < n; i++)
		res ^= x[i];
    cout << res;
    delete []x;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long long n, *x;

cin >> n;

x = new long long[n];

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

cin >> x[i];

long res = 0;

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

res ^= x[i];

cout << res;

delete []x;

return 0;

}

Код 3 (без массива)

#include <iostream>
using namespace std;

int main() {
	long long n, res = 0, x;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> x;
		res ^= x;
	}
	cout << res;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

long long n, res = 0, x;

cin >> n;

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

cin >> x;

res ^= x;

}

cout << res;

return 0;

}

Решение

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

Первый способ

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

Затем, заведём две переменные: счётчик и число. Последней присваиваем значение первого элемента массива. Сравниваем следующий элемент с тем, что лежит в переменной. Если они равны, увеличиваем счетчик. В счетчик с самого начала положим единицу, так как предполагаем, что в массиве есть хоть один элемент.

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

Второй способ

Применим исключающее «или» ко всем элементам массива. Предварительно создадим переменную равную нулю, в которой будем это проделывать.

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

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

Третий способ

Идейно такой же как предыдущий. Отличается только тем, что мы не записываем числа в массив, а исключающее «или» работает сразу после того как число было прочитано.

Ссылки

Задача 8374 на e-olymp

Код 1 на Ideone

Код 2 на Ideone

Код 3 на Ideone

Related Images:

e-olymp 8376. Рамка

05/12/2018 by Инна Литвиненко

Задача

Рамка $x × y$ представляет собой прямоугольник $x × y$, из середины которого вырезали прямоугольник размером $(x — 2) × (y — 2)$. У нас имеется неограниченный запас плиток $a × 1$. Можно ли полностью замостить рамку $x × y$ плитками $a × 1$?

Например, рамку $5 × 6$ можно замостить плитками $3 × 1$, но нельзя плитками $4 × 1$.

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

Первая строка содержит два натуральных числа $x$ и $y (3 ≤ x, y ≤ 10^6)$. Вторая строка содержит количество типов плиток $n (1 ≤ n ≤ 1000)$. Третья строка содержит n натуральных чисел, не больших $10^6$ — длины плиток.

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

Выведите n строк, содержащих YES или NO. i-ая строка содержит YES если можно замостить рамку плитками i-го типа. Выведите NO иначе.

Тесты

№	Ввод	Вывод
1	5 6 2 3 4	YES NO
2	18 5 2 6 3	NO YES
3	3 3 1 1	YES
4	200 4 3 2 3 4	YES NO NO
5	1000000 1000000 5 100000 2 1689 11 9004	NO YES NO YES NO

Код

#include <iostream>
using namespace std;

int main() {
    long long x, y, n, a;
    cin >> x >> y >> n;
    while (n--) {
        cin >> a;
        if ((a == 2) || (x % a == 0 && (y - 2) % a == 0) || ((x - 1) % a == 0 && (y - 1) % a == 0) || ((x - 2) % a == 0 && y % a == 0))
            cout << "YES"
                 << "\n";
        else
            cout << "NO"
                 << "\n";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long long x, y, n, a;

cin >> x >> y >> n;

while (n--) {

cin >> a;

if ((a == 2) || (x % a == 0 && (y - 2) % a == 0) || ((x - 1) % a == 0 && (y - 1) % a == 0) || ((x - 2) % a == 0 && y % a == 0))

cout << "YES"

<< "\n";

else

cout << "NO"

<< "\n";

}

return 0;

}

Решение

Рассмотрим три случая размещения плиток. Для примера возьмем входные данные c e-olymp — $5 × 6$.

Обратим внимание, что ширина плитки равна одному.

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

Второй случай. На рисунке длина плитки равна двум. Тут по горизонтали плитки занимают всю длину без одного уголка. Это означает, что длина рамки минус один кратна длине плитки. Ширине ничего не остается как тоже «отдать» свою единицу. В результате, ширина рамки минус один тоже кратна длине плитки.

Третий случай. На рисунке длина плитки равна трём. Плитки укладываются тут не от края до края, а оставляя уголки рамки свободными. Так получаем, что длина рамки минус две единицы (уголки) кратна длине плитки. Ширина тоже кратна длине плитки, но только в полном размере.

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

Ссылки

Задача на e-olymp

Код задачи на Ideone

Related Images:

e-olymp 8362. Множители

28/10/2018 by Инна Литвиненко

Задача

Найти число от $1$ до $n$ включительно такое, что в разложении его на простые множители количество множителей максимально. Если таких чисел несколько, выбрать максимальное из них.

Например, если $n = 7$, то ответом будет число $6$, как наибольшее число, имеющее в своем разложении $2$ простых множителя $2$ и $3$.

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

Одно целое число $n$ $(1 ≤ n ≤ 2^{31}- 1)$.

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

Вывести одно искомое число.

Тесты

№	Ввод	Вывод
1	1	1
2	10	8
3	100	96
4	363	256
5	2147483647	1610612736

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

#include <iostream>
using namespace std;

int main() {
    long long int n, a = 2, b = 3;
    cin >> n;
    if (n <= 3) cout << n;
    else {
        while (a * 2 <= n) a *= 2;
        while (b * 2 <= n) b *= 2;
        cout << max(a, b);
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long long int n, a = 2, b = 3;

cin >> n;

if (n <= 3) cout << n;

else {

while (a * 2 <= n) a *= 2;

while (b * 2 <= n) b *= 2;

cout << max(a, b);

}

return 0;

}

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

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

int main()
{
    long long n;
    cin >> n;
    if (n <= 3)
        cout << n;
    else {
        long long pow, a = 2, b = 3;
        pow = log(n) / log(2);
        a = a << (pow - 1);
        b = b << (pow - 1);
        if (a <= n && b <= n)
            cout << max(a, b);
        else if (a > n)
            cout << b;
        else
            cout << a;
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

long long n;

cin >> n;

if (n <= 3)

cout << n;

else {

long long pow, a = 2, b = 3;

pow = log(n) / log(2);

a = a << (pow - 1);

b = b << (pow - 1);

if (a <= n && b <= n)

cout << max(a, b);

else if (a > n)

cout << b;

else

cout << a;

}

return 0;

}

Решение

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

Заметим, что если заданное число будет единицей, двойкой или тройкой, то его и надо вывести на экран.

Условные операторы

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

Далее возьмём двойку и тройку (как наименьшие возможные простые множители искомого числа) и сдвинем их битово влево на показатель степени двойки минус один, так как эта первая степень уже заложена в самих 2 и 3. Сдвигать нужно для того, чтоб повысить степень двойки в нашем числе, тем самым увеличив количество простых множителей.

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

Цикл

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

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

Ссылки

Задача множители на e-olymp

Решение задачи на Ideone циклом

Решение задачи на Ideone условными операторами

Related Images:

e-olymp 421. Йо-йо

01/10/2018 by Инна Литвиненко

Задача

Игрушка йо-йо состоит из катушки, на которую намотана нитка. Если, держа за конец нитки, отпустить катушку, то она будет, вращаясь, сначала опускаться вниз, а затем по инерции подниматься вверх. Но высота, на которую катушка поднимется, будет в $k$ раз меньше, чем высота, с которой она опустилась. Будем считать, что катушка остановилась, если высота её очередного подъема не превышает $1$.

Напишите программу, которая по длине нитки $l$ и коэффициенту $k$ считает количество подъемов катушки до остановки. Например, пусть $l = 17$ и $k = 2$, тогда катушка будет подниматься на высоты $8.5$, $4.25$, $2.1254$, $1.0625$, а затем остановится. Таким образом получится $4$ подъема.

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

Два целых числа $l (1 ≤ l ≤$ 10⁹$)$ и $k (2 ≤ k ≤ 100)$.

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

Вывести одно число – количество подъемов.

Тесты

№	Ввод	Вывод
1	17 2	4
2	4 2	1
3	135 9	2
4	1 2	0
5	1000000000 100	4

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

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

int main() {
    double l, k;
    cin >> l >> k;
    const double c = 1e-5; //вводим константу 
    cout << int ( log (l - c) / log (k));
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double l, k;

cin >> l >> k;

const double c = 1e-5; //вводим константу

cout << int ( log (l - c) / log (k));

return 0;

}

Решение

Для решения данной задачи достаточно найти максимальную степень $k$, которая будет меньше числа $l$. Значение показателя степени и будет количеством подъемов йо-йо. Ответ найдем с помощью логарифма, подключив библиотеку <cmath>. Используем формулу перехода логарифма к новому основанию, а каким будет это основание значения не имеет. Заметим, что нас интересует только целая часть логарифма — число подъемов.

Также необходимо учесть, что кaтушка остановится в случае, если высота её очередного подъема будет меньше либо равна $1$. Это означает, что, если $l$ будет степенью $k$, полученный с помощью логарифма ответ будет на единицу больше верного. Введем очень маленькую константу с для разрешения этой проблемы. На ответ она особо не повлияет, а вот от единицы поможет избавиться.

Ссылки

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

Задача 421 на e-olymp