e-olymp 8530. Печать матрицы

11/11/2018 by Александр Дьяченко

Задача

Задана матрица $n \times n$ — назовем ее $[1 \ldots n] \times [1 \ldots n]$ массивом. Для заданных $r$ и $c$ следует вывести $[1 \ldots r] \times [1 \ldots c]$ массив ($r$ строк и $c$ столбцов исходного массива).

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

Первая строка содержит число $n \space (1 \leq n \leq 100)$. Следующие строки содержат матрицу $n \times n$. Последняя строка содержит два числа $r$ и $c \space (1 \leq r, c \leq n)$. Все числа в матрице не превышают по модулю $100$.

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

Выведите матрицу $r \times c$.

Тесты

Входные данные	Выходные данные
4 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 3 2	1 2 5 6 9 1
5 18 25 34 44 -43 54 65 75 85 -32 95 15 25 35 -3 -4 15 -6 37 0 44 43 23 3 -12 4 3	18 25 34 54 65 75 95 15 25 -4 15 -6
6 30 -10 30 -69 -84 75 -3 -39 60 15 75 -74 36 68 35 23 25 -44 16 42 83 15 59 -18 71 43 35 -81 -38 51 37 -49 55 26 6 33 4 5	30 -10 30 -69 -84 -3 -39 60 15 75 36 68 35 23 25 16 42 83 15 59

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

#include <iostream>
using namespace std;

int main() {
    unsigned short n, r, c;
    cin >> n;
    int ** x = new int * [n];
    for (int i = 0; i < n; i++)
        x[i] = new int[n];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> x[i][j];
    cin >> r >> c;
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++)
            cout << x[i][j] << " ";
        cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned short n, r, c;

cin >> n;

int ** x = new int * [n];

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

x[i] = new int[n];

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

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

cin >> x[i][j];

cin >> r >> c;

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

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

cout << x[i][j] << " ";

cout << endl;

}

return 0;

}

Решение

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

первый цикл ($14$ строка кода) будет отвечать за количество выводимых строк матрицы — по условию, нужно вывести первые $r$ строк;
второй цикл ($15$ строка кода) будет отвечать за количество выводимых столбцов матрицы — по условию, нужно вывести первые $c$ столбцов.

Ссылки

Условие задачи на e-olymp
Код решения на Ideone

Александр Дьяченко

e-olymp 2501. Круговая диаграмма

04/11/2018 by Александр Дьяченко

Задача

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

Исходными данными для этой диаграммы является набор чисел $a_1,\ldots, a_n, а$ диаграмма представляет собой круг радиуса $r$, разделенный на секторы. При этом каждому из чисел соответствует ровно один сектор, площадь которого пропорциональна этому числу. Общая площадь секторов равна площади круга.

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

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

Первая строка содержит два целых числа $n$ и $r \space (1 \leq n, r \leq 100)$. Вторая строка содержит $n$ целых чисел $a_1,\ldots, a_n \space (1 \leq a_i \leq 100$ для всех $i$ от $1$ до $n)$.

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

Выведите $n$ вещественных чисел — площади секторов, соответствующих числам $a_1,\ldots, a_n$. Выводите каждое из чисел в отдельной строке.

Все эти числа должны быть выведены с точностью не хуже $10^{-6}$.

Тесты

Входные данные	Выходные данные
3 2 1 4 3	1.570796327 6.283185307 4.712388980
2 3 3 8	7.711181968 20.563151914
4 5 2 5 9 1	9.239978393 23.099945982 41.579902768 4.619989196
5 9 4 16 8 20 11	17.252135928 69.008543713 34.504271856 86.260679641 47.443373803

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

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

int main() {
    int n, r, sum = 0;
    double S;
    cin >> n >> r;
    int *x = new int[n];
    for (int i = 0; i < n; i++)
        cin >> x[i];
    for (int i = 0; i < n; i++)
        sum += x[i];
    S = M_PI * r * r;
    for (int i = 0; i < n; i++)
        cout << fixed << setprecision(9) << (S / sum) * x[i] << endl;
    return 0;
}

#include <iostream>

#include <iomanip>

#include <cmath>

using namespace std;

int main() {

int n, r, sum = 0;

double S;

cin >> n >> r;

int *x = new int[n];

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

cin >> x[i];

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

sum += x[i];

S = M_PI * r * r;

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

cout << fixed << setprecision(9) << (S / sum) * x[i] << endl;

return 0;

}

Решение

Найдем сперва сумму всех чисел $a_i$ и площадь диаграммы (по известной формуле площади круга). Теперь можем легко посчитать площади каждого из секторов нашей диаграммы, разделив площадь последней на ранее найденную сумму и умножив их частное на соответствующее число $a_i$.

Ссылки

Условие задачи на e-olymp
Код решения на Ideone

Александр Дьяченко

e-olymp 1507. История Лаурела-Харди

26/09/2018 by Александр Дьяченко

Задача

Лаурел и Харди — два известных киногероя $50$-ых. Они известны своей разницей в весе, как можно увидеть на картинке. Если Вы еще не разобрались, кто из них кто, то я добавлю, что Лаурел легче. В свои юношеские годы Лаурел и Харди любили играть со странными качелями, и когда качели находились в равновесии, то Харди всегда был у земли. Мы рассмотрим двумерную версию качель.

Качели, которыми пользовались Лаурел и Харди, представляют собой часть окружности радиуса $r$, как показано на картинке (они закрашены серым и имеют вид буквы $D$). Харди сел на точку $B$ (самая правая точка качель), а Лаурел сел на точку $A$ (самая левая точка отрезка $AB$). $d = EF$ — расстояние между центром отрезка $AB$ и дуги $AFB$. То есть $E$ — середина отрезка $AB$, а $F$ — середина дуги $AFB$. $MN$ — основа качель, является горизонтальной прямой. $BD = h_1$ — расстояние от Харди до земли. Вам необходимо найти расстояние от Лаурела до земли (обозначаемое $h_2 = AC$).

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

Первая строка содержит количество тестов $N \space (0 < N ≤ 1000)$. Каждая из следующих $N$ строк представляет собой отдельный тест, который имеет следующий формат:

Каждая строка содержит три целых числа $r \space (10 ≤ r ≤ 100), \space$ $d \space (5 ≤ d ≤ r), \space$ $h_1 \space (5 ≤ h_1 ≤ d)$. Значение этих чисел приведено выше.

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

Для каждого теста в отдельной строке вывести его номер и действительной число — значение $h_2$. Это число должно содержать четыре десятичных знака. Формат вывода приведен в примере.

Тесты

Входные данные	Выходные данные
2 10 10 10 10 7 6	Case 1: 10.0000 Case 2: 8.0342
3 12 7 7 11 11 8 54 12 6	Case 1: 7.0000 Case 2: 14.0000 Case 3: 19.7383
5 94 21 12 23 9 8 5 4 3 2 2 1 43 26 20	Case 1: 32.1226 Case 2: 10.0439 Case 3: 5.0440 Case 4: 3.0000 Case 5: 32.4231

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

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

int main() {
    unsigned short N;
    double r, d, h_1, a, b;
    cin >> N;
    for (int i = 1; i <= N; i++) {
        cin >> r >> d >> h_1;
        cout << "Case " << i << ": ";
        a = asin((r - h_1) / r) - asin((r - d) / r);
        if (a == 0)
            cout << fixed << setprecision(4) << h_1 << endl;
        else{
            b = 2 * sqrt(r * r - (r - d) * (r - d)) + h_1 / sin(a);
            cout << fixed << setprecision(4) << b * sin(a) << endl;
        }
    }
    return 0;
}

#include <iostream>

#include <iomanip>

#include <cmath>

using namespace std;

int main() {

unsigned short N;

double r, d, h_1, a, b;

cin >> N;

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

cin >> r >> d >> h_1;

cout << "Case " << i << ": ";

a = asin((r - h_1) / r) - asin((r - d) / r);

if (a == 0)

cout << fixed << setprecision(4) << h_1 << endl;

else{

b = 2 * sqrt(r * r - (r - d) * (r - d)) + h_1 / sin(a);

cout << fixed << setprecision(4) << b * sin(a) << endl;

}

return 0;

}

Решение

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

В $9$ строке введем число $N$ из входного потока, а в $10$ — запустим цикл, который будет работать $N$ раз. Далее за каждый проход цикла будем читать по $3$ следующих числа из входного потока и выводить на экран номер текущего теста. Перед тем, как идти дальше, разберемся в рисунке. Так как по условию отрезок $EF$ делит сегмент $AFB$ пополам, то по свойствам хорд и дуг окружности, он является частью радиуса $r$ нашей окружности с центром в точке $O$ и перпендикулярен хорде $AB$, что и показано на чертеже. Кроме того, я дорисовал радиусы $OA$ и $OB$ окружности к соответствующим точкам и начертил отрезок $BH$, как продолжение $AB$, от точки $B$ до прямой $MN$. Также, я построил прямоугольный треугольник $\triangle OGB$, в котором катет $OG = r-BD$.
Достроив все необходимые отрезки, легко заметить, что мы имеем прямоугольный треугольник $\triangle ACH$ с катетом $AC$, длину которого нам и нужно найти по условию задачи. Предлагаю сделать это, воспользовавшись формулой $AC = AH \cdot \sin(\angle AHC)$. Найдем значения сомножителей.

Из рисунка очевидно, что $\angle AHC = \angle BHD = \angle EBG = \angle OBG-\angle OBE.$
Сначала найдем $\angle OBG$. Для этого рассмотрим треугольник $\triangle OGB$. Длины его гипотенузы и противолежащего к искомому углу катета нам уже известны, так что можем сразу найти $\angle OBG = \arcsin \frac{OG}{OB}$.
Теперь найдем $\angle OBE$. Рассмотрим прямоугольный треугольник $\triangle OEB$. В нем противолежащий искомому углу катет $OE = r-d$, а гипотенуза $OB = r$. Значит, $\angle OBE = \arcsin \frac{OE}{OB}$.
В итоге остаётся только найти разницу этих углов, которая и будет являться величиной искомого $\angle AHC$. В коде же значение этого угла считается в $13$ строке и присваивается переменной a.

Стоит заметить, что если $\angle OBG-\angle OBE = 0$, то длины отрезков $AC$ и $BD$, очевидно, совпадают. В таком случае можем сразу вывести на экран $h_2 = h_1$, как мы и поступили в $15$ строке, и перейти к нахождению $AC$ уже для следующего тестового случая.

Если же величина $\angle AHC$ отлична от $0$, то нам все еще предстоит посчитать длину гипотенузы $AH$ треугольника $\triangle ACH$. Она состоит из хорды $AB$ и отрезка $BH$.
Сперва найдем длину хорды. Известно, что $OF$ делит ее на $2$ одинаковых по длине отрезка, значит, следует опять рассмотреть треугольник $\triangle OEB$. Длину его гипотенузы и одного из катетов мы уже находили, так что просто применим теорему Пифагора и найдем $EB = \sqrt{OB^2-OE^2}$. Тогда $AB = 2 \cdot EB$.
Для нахождения длины $BH$, рассмотрим треугольник $\triangle BDH$, в котором этот отрезок является гипотенузой. Длину катета $BD$ и величину угла $\angle BHD$ мы уже знаем, значит, можем применить формулу $BH = \frac{BD}{\sin(\angle BHD)}$.
Сложим найденные значения длин хорды $AB$ и отрезка $BH$, чтобы получить $AH$. В коде эта длина находится в $17$ строке и присваивается переменной b.

Теперь остается только подставить найденные значения в ранее приведенную формулу и получить наконец длину $h_2$, которую выведем на экран в $18$ строке.

Ссылки

Условие задачи на e-olymp
Код решения на Ideone

Александр Дьяченко

e-olymp 446. Ровные делители

18/09/2018 by Александр Дьяченко

Задача

Натуральное число $m$ называется ровным делителем числа $n$, если частное и остаток от деления $n$ на $m$ равны. По заданному натуральному числу $n$ найти количество его ровных делителей.

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

Натуральное число $n \space (1 ≤ n ≤ 10^{6})$.

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

Выведите искомое количество ровных делителей числа $n$.

Тесты

Входные данные	Выходные данные
5	1
20	2
200	6
653	1
5982	4

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

#include <iostream>
using namespace std;

int main() {
    unsigned n, q = 0;
    cin >> n;
    for (int m = 1; m <= n; m++)
        if (n / m == n % m)
            q += 1;
    cout << q;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned n, q = 0;

cin >> n;

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

if (n / m == n % m)

q += 1;

cout << q;

return 0;

}

Решение

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

Ссылки

Условие задачи на e-olymp
Код решения на Ideone

Александр Дьяченко

e-olymp 58. Биллиард

05/08/2018 by Александр Дьяченко

Задача

Биллиард представляет собой прямоугольник размерами $M \times N$, где $M$ и $N$ — натуральные числа. Из верхней левой лузы вылетает шар под углом $45^{\circ}$ к соседним сторонам. Лузы размещено только в углах биллиарда. Определите количество столкновений шара с бортами биллиарда, после которых он опять попадет в одну из луз, и номер лузы, в которую упадет шар. Считать, что трение отсутствует, столкновения абсолютно упругие, а шар — материальная точка.

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

Во входной строке два числа $M$ и $N$, $1 ≤ M, N ≤ 2000000000$. Нумерация луз по часовой стрелке, начиная с левой верхней лузы, из которой вылетел шар, согласно рисунка. $M$ — горизонтальная сторона биллиарда, $N$ — вертикальная сторона биллиарда.

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

Два числа: количество отражений шара и номер лузы в которую упадет шар.

Тесты

Входные данные	Выходные данные
2 1	1 2
5 6	9 4
12 33	13 2
156 156	0 3
654 236	443 4

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

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

int main() {
    long m, n;
    cin >> m >> n;
    long g = __gcd(m, n);
    m /= g;
    n /= g;
    cout << (n + m - 2) << " ";
    if(n % 2 == 0 and m % 2 != 0) cout << 4;
    if(n % 2 != 0 and m % 2 != 0) cout << 3;
    if(n % 2 != 0 and m % 2 == 0) cout << 2;
    return 0;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

long m, n;

cin >> m >> n;

long g = __gcd(m, n);

m /= g;

n /= g;

cout << (n + m - 2) << " ";

if(n % 2 == 0 and m % 2 != 0) cout << 4;

if(n % 2 != 0 and m % 2 != 0) cout << 3;

if(n % 2 != 0 and m % 2 == 0) cout << 2;

return 0;

}

Решение

Чтобы решить эту задачу, необходимо найти НОД значений $M$ и $N$ из условия. Для этого, сперва нужно подключить библиотеку, содержащую функцию для нахождения НОД двух чисел, что мы и сделали во $2$ строке. Далее, в $8$ строке, введем перемененную g и присвоим ей значение НОД для $M$ и $N$. Теперь же, зная наш НОД, с его помощью можем подобрать эквивалентные числам из входного потока значения, которые будут, возможно, гораздо меньшими, чем изначальные, и работать уже с ними. В последующих строках находим искомые данные, причем количество отражений шара всегда находится по одной и той же формуле, в то время как номер лузы, в которую упадет шар, зависит от выполнения одного из трех условий, что и видно в коде.

Ссылки

Условие задачи на e-olymp
Код решения на Ideone

Александр Дьяченко

e-olymp 2860. Сумма чисел на промежутке

05/12/2017 by Александр Дьяченко

Задача

Найти сумму целых чисел на промежутке от $a$ до $b$.

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

Два целых числа $a$ и $b$, по модулю не превышающих $10^9$.

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

Сумма целых чисел на промежутке от $a$ до $b$.

Тесты

Входные данные	Выходные данные
2 5	14
249 318	19845
23 69	2162
124 200	12474
478 653	99528

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

#include <iostream>
using namespace std;

int main() {
    long a, b, n, S;
    cin >> a >> b;
    n = b - a + 1;
    S = (a + b) * n / 2;
    cout << S;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long a, b, n, S;

cin >> a >> b;

n = b - a + 1;

S = (a + b) * n / 2;

cout << S;

return 0;

}

Решение

Для того, что бы найти ответ, нам необходимо знание формул прогрессии, так как решением данной задачи является сумма $n$ первых членов арифметической прогрессии. Вычислить её можно по формуле $\displaystyle S_n = \frac{a_1 + a_n}{2} \cdot n$, где $a_1$ — это a из входного потока, а $a_n$ — это b. Тем не менее, мы все ещё не можем применить вышеприведенную формулу, так как нам неизвестно $n$. Выведем же его из формулы $n$-ого члена арифметической прогрессии: $a_n = a_1 + d \cdot (n-1)$, где $d$ — это разность арифметической прогрессии, которая по условию (хоть и негласно) равна единице. Зная это, из последней формулы выведем, что $n = a_n-a_1 + 1$. Теперь же, когда мы знаем все необходимые значения, остается только подсчитать сумму арифметической прогрессии по ранее данной формуле и подать результат на выход.

Ссылки

Условие задачи на e-olymp
Код решения на Ideone

Александр Дьяченко