e-olymp 7623. Счастливые случаи

26/06/2018 by Даниил Крутоголов

Счастливые случаи

Счастливый случай — это лотерея. Каждый лотерейный билет имеет игровое поле и закрытую область. Игровое поле представляет собой прямоугольник размера $r \times c$, заполненный числами. Закрытая область скрывает номер строки и колонки, на пересечении которых находится игровая ячейка.
Существует четыре возможных выигрышных направления: вверх, вниз, влево и вправо. Направление считается выигрышным, если все числа в этом направлении от игровой ячейки в точности меньше числа в самой игровой ячейке. Если игровая ячейка находится на краю таблицы, то Вы автоматически имеете выигрышное направление!

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

В первой строке находятся два целых числа $r$ и $c$ $(1 \leqslant r, c \leqslant 100)$ — количество строк и колонок в таблице.
Каждая из следующих $r$ строк содержит $c$ чисел — значения на игровом поле. Каждое число положительно и не превосходит 1000.

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

Вывести одно число $w$ — общее количество выигрышных направлений для заданной таблицы.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	$1$ $1$ $4$	$4$
2	$2$ $4$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ $0$	$12$
3	$3$ $2$ $10$ $10$ $10$ $10$ $4$ $5$	$13$
4	$2$ $2$ $1$ $2$ $3$ $4$	$12$
5	$0$ $0$	$0$

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

#include <iostream>

using namespace std; 

int main() {
    int r, c, a, b, e, d, w = 0;
    cin >> r >> c;
    int **x = new int * [r];
    for (int i = 0; i < r; i++) x[i] = new int[c];
    for (int i = 0; i < r; i++){
        for (int j = 0; j > x[i][j];
        }
    }
    for (int i = 0; i < r; i++){
        for (int j = 0; j < c; j++){
            a = b = e = d = 1;
        for (int q = 0; q < i; q++){
            if (x[i][j] <= x[q][j])
                a = 0;
        }
        for (int q = i+1; q < r; q++){
            if (x[i][j] <= x[q][j])
                b = 0;
        }
        for (int k = 0; k < j; k++){
            if (x[i][j] <= x[i][k])
                e = 0;
        }
        for (int k = j+1; k < c; k++){
            if (x[i][j] <= x[i][k])
                d = 0;
        }
        w+= a + b + e + d;
        }
    }
    cout << w;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int r, c, a, b, e, d, w = 0;

cin >> r >> c;

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

for (int i = 0; i < r; i++) x[i] = new int[c];

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

for (int j = 0; j > x[i][j];

}

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

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

a = b = e = d = 1;

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

if (x[i][j] <= x[q][j])

a = 0;

}

for (int q = i+1; q < r; q++){

if (x[i][j] <= x[q][j])

b = 0;

}

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

if (x[i][j] <= x[i][k])

e = 0;

}

for (int k = j+1; k < c; k++){

if (x[i][j] <= x[i][k])

d = 0;

}

w+= a + b + e + d;

}

cout << w;

return 0;

}

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

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

Ссылки

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

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

Related Images:

e-olymp 52. Сыр для Анфисы

13/05/2018 by Даниил Крутоголов

Сыр для Анфисы

Готовя обед для Анфисы — символа 2008 года, хозяин использовал для разрезания сыра специальный нож, который разрезал сыр на одинаковые прямоугольные паралелепипеды с основанием в виде квадрата со стороной [latex]a[/latex] и высотой [latex]b[/latex].
Но Анфиса, как и подобает даме года, любила употреблять сыр несколько меньших размеров, для чего она всегда разрезала предложенный кусочек деликатеса на две части, предварительно установив его строго вертикально квадратом к столу. При разрезании нож всегда размещался по диагонали квадрата, но Анфисе не всегда удавалось разрезать кусочек пополам, так как плоскость лезвия ножа образовывала двугранный угол [latex]z^o[/latex] с плоскостью основания.
Найти площадь [latex]s[/latex] созданного Анфисой сечения.

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

Целые числа [latex]a[/latex], [latex]b[/latex], [latex]z[/latex], не превышающие [latex]90^o[/latex].

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

Площадь [latex]s[/latex] образованного сечения с точностью до трех десятичных знаков.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	[latex]2[/latex] [latex]3[/latex] [latex]90[/latex]	[latex]8.485[/latex]
2	[latex]2[/latex] [latex]4[/latex] [latex]0[/latex]	[latex]0.000[/latex]
3	[latex]1[/latex] [latex]2[/latex] [latex]3[/latex]	[latex]0.501[/latex]
4	[latex]1[/latex] [latex]1[/latex] [latex]100[/latex]	[latex]1.615[/latex]
5	[latex]3[/latex] [latex]10[/latex] [latex]48[/latex]	[latex]6.725[/latex]

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

#include <iostream>
#include <cmath>
#include <iomanip>

using namespace std; 

int main() {
    double a, b, z, s;
    cin >> a >> b >> z;
    if ((1 / (tan (z * M_PI / 180)) > a / sqrt(2) / b) && (z != 0) && (z != 90)){
        s = a * a / 2 / cos (z * M_PI / 180);
    }
    else if (z == 0) {
        s = 0;
    }
    else if (z == 90) {
        s = a * b * sqrt(2);
    }
    else {
        s = (a * sqrt(2) - b * 1 / (tan (z * M_PI / 180))) * b / sin (z * M_PI / 180);
    }
    cout << setprecision(3) << fixed << s;
    return 0;
}

#include <iostream>

#include <cmath>

#include <iomanip>

using namespace std;

int main() {

double a, b, z, s;

cin >> a >> b >> z;

if ((1 / (tan (z * M_PI / 180)) > a / sqrt(2) / b) && (z != 0) && (z != 90)){

s = a * a / 2 / cos (z * M_PI / 180);

}

else if (z == 0) {

s = 0;

}

else if (z == 90) {

s = a * b * sqrt(2);

}

else {

s = (a * sqrt(2) - b * 1 / (tan (z * M_PI / 180))) * b / sin (z * M_PI / 180);

}

cout << setprecision(3) << fixed << s;

return 0;

}

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

Для решения данной задачи нам нужно рассмотреть 4 случая:
1) Если [latex]\cot[/latex] заданного угла не будет превышать [latex]\frac{a} {\sqrt{2} \cdot b}[/latex] и также не будет равен [latex]0^o[/latex] и [latex]90^o[/latex], то фигурой сечения получится треугольник. Его площадь мы сможем найти по формуле [latex]s = \frac {a^{2}} {2 \cos (z \cdot \frac {\pi} {180})}[/latex].
2) Заданный угол = [latex]0^o[/latex], следовательно площадь сечения также будет = 0, так как сыр нормально и не порежут.
3) Заданный угол = [latex]90^o[/latex], фигурой сечения будет прямоугольник, площадь которого мы сможем найти по формуле [latex]s = a \cdot b \cdot \sqrt{2}[/latex].
4) В любом другом случае, получится трапеция, площадь которой мы найдем по формуле [latex]s = \frac {a \cdot \sqrt{2} — b \cdot 1} {tan(z \cdot \frac{\pi}{180})} \cdot \frac {b} {sin (z \cdot \frac {\pi}{180})}[/latex].

Ссылки

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

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

Related Images:

e-olymp 179. Распределение

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

Распределение

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

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

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

Первая строка входного файла содержит целое число [latex]N[/latex] [latex](1 ≤ N ≤ 10000)[/latex] – количество отрядов. Вторая строка содержит изначальное распределение воинов по отрядам – [latex]N[/latex] чисел, каждое из которых определяет количество воинов в соответствующем отряде. А в третьей строке – требуемое распределение солдат. Количество солдат в одном отряде не превышает [latex]10^6[/latex]. Гарантируется, что общее число воинов в изначальном распределении и требуемом совпадает.

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

В выходной файл выведите минимально возможное количество переводов.

Тесты

ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
2 4 2 5 1	1
1 4 4	0
3 2 2 2 4 1 1	2
3 6 3 1 0 0 10	9

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

#include <iostream>
 
using namespace std;
 
int main()
{
    int size;
    cin >> size;
    long *arr1 = new long[size];
    long *arr2 = new long[size];
    for(int i = 0; i < size; i++){
        cin >> arr1[i];
    }
    for(int i = 0; i < size; i++){
        cin >> arr2[i];
    }
    long tmp = 0;
    for(int i = 0; i < size; i++){
        tmp+= abs(arr2[i] - arr1[i]);
    }
    cout << tmp / 2;
    delete []arr1;
    delete []arr2;
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int size;

cin >> size;

long *arr1 = new long[size];

long *arr2 = new long[size];

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

cin >> arr1[i];

}

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

cin >> arr2[i];

}

long tmp = 0;

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

tmp+= abs(arr2[i] - arr1[i]);

}

cout << tmp / 2;

delete []arr1;

delete []arr2;

return 0;

}

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

Данная задача решается вычислением и суммированием разности соответствующих элементов второго массива и первого. Таким образом мы найдем количество воинов, которых не хватает и которых надо перевести в другой отряд. Возьмём эту разность по модулю, затем поделим на [latex]2[/latex], так как мы учитывали всех воинов. В итоге получим минимальное количество переводов из одного отряда в другой.

Ссылки

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

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

Related Images:

e-olymp 520. Сумма всех

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

Сумма всех

Вычислите сумму всех заданных чисел.

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

Содержит [latex]n[/latex] [latex] (1 ≤ n ≤ 10^5) [/latex] целых чисел. Все числа не превосходят [latex]10^9[/latex] по абсолютной величине.

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

Выведите сумму всех заданных чисел.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	[latex]2[/latex] [latex]4[/latex]	[latex]6[/latex]
2	[latex]3[/latex]	[latex]3[/latex]
3	[latex]1[/latex] [latex]2[/latex] [latex]3[/latex] [latex]2[/latex] [latex]1[/latex]	[latex]9[/latex]
4	[latex]1[/latex] [latex]2[/latex] [latex]3[/latex] [latex]4[/latex]	[latex]10[/latex]
5	[latex]0[/latex] [latex]0[/latex] [latex]0[/latex] [latex]0[/latex]	[latex]0[/latex]

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

#include <iostream>
 
using namespace std;
 
int main() {
    long x;
    long sum = 0;
    while (cin >> x){
        sum+= x;
    }
    cout << sum;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long x;

long sum = 0;

while (cin >> x){

sum+= x;

}

cout << sum;

return 0;

}

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

Пользователь вводит числа до тех пор, пока программа не завершит работу. Как только это случается, программа выдаёт ответ в виде суммы всех ранее введённых чисел. Также, стоит использовать переменную типа long из-за того, что сумма чисел может быть довольно большой и явно превышать максимальное допустимое значение для переменной типа int.

Ссылки

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

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

Related Images:

e-olymp 7944. Площадь прямоугольника

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

Площадь прямоугольника

Найдите площадь прямоугольника.

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

Целочисленные стороны прямоугольника [latex]a[/latex] и [latex]b[/latex] [latex](1 ≤ a, b ≤ 1000)[/latex].

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

Выведите площадь прямоугольника.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	[latex]1[/latex] [latex]1[/latex]	[latex]1[/latex]
2	[latex]2[/latex] [latex]4[/latex]	[latex]8[/latex]
3	[latex]511[/latex] [latex]428[/latex]	[latex]218708[/latex]
4	[latex]5555[/latex] [latex]4444[/latex]	[latex]24686420[/latex]
5	[latex]11[/latex] [latex]11[/latex]	[latex]121[/latex]

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

#include <iostream>

using namespace std;

int main()
{
    int a, b;
    cin >> a >> b;
    cout << a * b << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int a, b;

cin >> a >> b;

cout << a * b << endl;

return 0;

}

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

Прямоугольником называется четырехугольник, у которого все углы равны. Все углы в прямоугольнике прямые, т.е. составляют [latex]90°[/latex]. Площадь прямоугольника равна произведению его сторон [latex](a, b)[/latex]. Следовательно формула решения задачи будет такой: [latex]a · b[/latex].

Ссылки

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

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

Related Images:

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

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

Задача

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

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

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

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

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

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

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

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

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

Тесты

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

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

#include <iostream>
#include <cmath>

using namespace std;

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

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

int n, m;

double k;

cin >> n;

m = log2(n);

k = log2(n);

while (m != k){

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

m = log2(n);

k = log2(n);

}

cout << m + 1;

return 0;

}

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

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

Ссылки

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

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