e-olymp 145. Квадраты

25/06/2019 by Алина Гук

Задача взята с сайта e-olymp

Задача

Заданы длины $n$ отрезков. Какое наибольшее количество квадратов можно из них составить? Сторона каждого квадрата должна состоять только из одного отрезка.

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

В первой строке находится количество отрезков $n \left(1 \leqslant n\leqslant 10^6\right)$. Во второй строке заданы $n$ натуральных чисел — длины отрезков, числовые значения которых не превышают $100$.

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

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

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	9 2 2 4 2 3 2 1 2 4	1
2	11 2 2 4 2 2 4 2 2 1 2 2	2
3	5 8 9 8 9 11	0

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

#include <iostream>
#define MAX 101
using namespace std;

int a[MAX];

int main() {
    int n, l, res = 0, i;
    cin >> n;
    for(l = 0; l < n; l++) cin >> i, a[i]++;
    for(i = 1; i <= MAX - 1; i++) res += a[i] / 4;
    cout << res << "\n";
    return 0;
}

#include <iostream>

#define MAX 101

using namespace std;

int a[MAX];

int main() {

int n, l, res = 0, i;

cin >> n;

for(l = 0; l < n; l++) cin >> i, a[i]++;

for(i = 1; i <= MAX - 1; i++) res += a[i] / 4;

cout << res << "\n";

return 0;

}

Решение

Пусть имеется $k$ отрезков одинаковой длины. Тогда из них можно составить $\frac{k}{4}$ квадрата. Длины отрезков изменяются от $1$ до $100$. Подсчитываем количество отрезков длины $i\left(1\leqslant i\leqslant 100\right)$ в массив $a\left[i\right]$. Тогда максимально возможное количество квадратов, которое можно составить из данных отрезков, равно $$\frac{a\left[1\right]+a\left[2\right]+\dots +a\left[100\right]}{4}.$$

Для этого совершим сортировку подсчетом. В ячейке a[i] подсчитываем количество отрезков длины i . В переменную res подсчитываем количество квадратов, которое можно построить.

Ссылки

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

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

Сортировка подсчетом на Wikipedia

Related Images:

e-olymp 7534. Замкнутое сокровище

03/06/2019 by Алина Гук

Задача взята с сайта e-olymp

Задача

Группа из $n$ бандитов спрятала украденное сокровище в комнате. Дверь в комнату следует отпереть только когда понадобится вынести сокровище. Так как бандиты не доверяют друг другу, они хотят иметь возможность открыть комнату и унести украденное только если этого захотят не менее $m$ из них.

Они решили разместить несколько замков на двери таким образом, чтобы она открывалась только когда открыты все замки. Каждый замок может иметь до $n$ ключей, распределенных среди некоторого подмножества бандитов. Группа бандитов может открыть замок, только если кто-то в группе имеет ключ к этому замку.

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

Например, если $n = 3$ и $m = 2$, то достаточно $3$ замков — ключи от замка $1$ получают бандиты $1$ и $2$, ключи от замка $2$ получают бандиты $1$ и $3$, ключи от замка $3$ получают бандиты $2$ и $3$. Ни один из бандитов не может открыть все замки самостоятельно, но любая группа из $2$ бандитов может открыть все замки. Можно убедиться, что $2$ замков для этого случая не достаточно.

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

Первая строка содержит количество тестов. Каждая следующая строка является отдельным тестом и содержит два числа $n(1 \leqslant n \leqslant 30)$ и $m(1 \leqslant m \leqslant n)$.

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

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

Тесты

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

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

#include <iostream>
#include <cstring>
#define MAX 31
using namespace std;

int main() {
    int tests, n, m;
    long long c[MAX][MAX];
    memset(c, 0, sizeof(c));
    for(int i = 0; i < MAX; i++) c[i][0] = 1;
    for(int i = 0; i < MAX; i++)
        for(int j = 1; j <= MAX; j++)
            c[i][j] = c[i - 1][j] + c[i - 1][j - 1];
    cin >> tests;
    while(tests--) {
        cin >> n >> m;
        cout << c[n][m - 1] << "\n";
    }
    
    return 0;
}

#include <iostream>

#include <cstring>

#define MAX 31

using namespace std;

int main() {

int tests, n, m;

long long c[MAX][MAX];

memset(c, 0, sizeof(c));

for(int i = 0; i < MAX; i++) c[i][0] = 1;

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

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

c[i][j] = c[i - 1][j] + c[i - 1][j - 1];

cin >> tests;

while(tests--) {

cin >> n >> m;

cout << c[n][m - 1] << "\n";

}

return 0;

}

Решение

Для каждой группы из $m-1$ бандитов существует замок такой, что его могут открыть все остальные группы, кроме этой. Потому что, просто обьеденив две группы с одинаковыми замками, мы получим одну большую чем $m-1$, которая не может открыть замок. Таким образом, всего должно быть столько замков, сколько существует способов выбрать $m-1$ группу из $n$ бандитов. То есть $C_{n}^{m-1}$.

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

Ссылки

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

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

Треугольник Паскаля на Wikipedia

Related Images:

e-olymp 7368. Средний балл для фигуристов

25/12/2018 by Алина Гук

Задача взята с сайта e-olymp

Задача

Спортсменам-фигуристам [latex]n[/latex] судей выставляют оценки. Технический работник соревнований изымает все максимальные и все минимальные оценки, а для остальных оценок вычисляет среднее арифметическое значение. Этот результат считается баллом, полученным спортсменом. Найти такой балл для каждого спортсмена.

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

В первой строке находятся два целых числа: количество судей [latex]n[/latex] и количество спортсменов [latex]m[/latex]. В следующих [latex]m[/latex] строках находятся [latex]n[/latex] целых чисел – оценки всех судей[latex]\left( 0 \lt n \leqslant 10, 0 \lt m \leqslant 100 \right)[/latex] для каждого из фигуристов.

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

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

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 4 7 8 9 8 10 6 5 5 4 7 9 9 10 7 7 7 7 10 9 8	8.33 5.33 9.00 8.50
2	3 4 1 2 3 3 5 2 7 1 6 9 8 3	2.00 3.00 6.00 8.00
3	10 2 1 2 3 4 5 6 7 8 9 10 1 1 1 2 2 2 3 3 3 4	5.50 2.50

Код программы (Потоковая обработка)

#include <iostream>
#include <iomanip>
using namespace std;
 
int main() {
    cout << fixed << setprecision(2);
    int n, m, tmp, sumGl, sumMin, sumMax, valMin, valMax, countMin, countMax;
    cin >> n >> m;
    for(int j = 0 ; j < m ; j++){
        sumGl = sumMin = sumMax = 0;
        valMin = 11;
        valMax = 0;
        countMin = countMax = 0;
        for(int i = 0 ; i < n; i++) {
            cin >> tmp;
            sumGl += tmp;
            if(tmp < valMin) {
                sumMin = tmp;
                valMin = tmp;
                countMin = 1;
            }
            else if(tmp == valMin) {
                sumMin += tmp;
                countMin++;
            }
            if(tmp > valMax) {
                sumMax = tmp;
                valMax =tmp;
                countMax = 1;
            }
            else if(tmp == valMax) {
                sumMax += tmp;
                countMax++;
            }
        }
        cout << (sumGl - sumMax - sumMin) / (double)(n - countMax - countMin) << " ";
    }
    return 0;
}

#include <iostream>

#include <iomanip>

using namespace std;

int main() {

cout << fixed << setprecision(2);

int n, m, tmp, sumGl, sumMin, sumMax, valMin, valMax, countMin, countMax;

cin >> n >> m;

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

sumGl = sumMin = sumMax = 0;

valMin = 11;

valMax = 0;

countMin = countMax = 0;

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

cin >> tmp;

sumGl += tmp;

if(tmp < valMin) {

sumMin = tmp;

valMin = tmp;

countMin = 1;

}

else if(tmp == valMin) {

sumMin += tmp;

countMin++;

}

if(tmp > valMax) {

sumMax = tmp;

valMax =tmp;

countMax = 1;

}

else if(tmp == valMax) {

sumMax += tmp;

countMax++;

}

cout << (sumGl - sumMax - sumMin) / (double)(n - countMax - countMin) << " ";

}

return 0;

}

Решение

Читая каждую оценку:

Добавляем оценку к общей сумме;
Если введенная оценка равна минимальной, то добавляем ее к сумме минимальных и увеличиваем счётчик количества минимальных.
Если введенная оценка меньше минимальной, то минимальной становится введённая оценка. Счетчик количества минимальных равен [latex]1.[/latex] Сумма минимальных равна введённой оценке.
Если введенная оценка равна максимальной, то добавляем ее к сумме максимальных и увеличиваем счётчик количества максимальных.
Если введенная оценка больше максимальной, то максимальной становится введённая оценка. Счетчик количества максимальных равен [latex]1.[/latex] Сумма максимальных равна введённой оценке.

Тогда после введения всех [latex]n[/latex] оценок имеем:

[latex]sumMax[/latex] — сумма максимальных оценок.
[latex]sumMin[/latex] — сумма минимальных оценок.
[latex]countMax[/latex] — количество максимальных оценок.
[latex]countMin[/latex] — количество минимальных оценок.
[latex]sumGl[/latex] — общая сумма оценок.

Для нахождения среднего арифметического значения оценок, соответствующего условию будем применять формулу: [latex]S_с = \frac{sumGL-sumMin-sumMax}{n-countMin-countMax}[/latex]

Код программы (Массивы)

#include <iostream> 
#include <iomanip> 
using namespace std; 
 
double res(int *arr, int len) {
    int min,max;
    min = arr[0];
    max = arr[0];
    for(int i = 1; i < len; i++) {
        if(arr[i] > max) {
            max = arr[i];
        }   
        if(arr[i]<min) {
            min = arr[i];
        }
    }
    int sum = 0;
    int count = 0;
    for(int i = 0; i < len; i++) {
        if(arr[i] != max && arr[i] != min) {
            sum += arr[i];
            count++;
        }
    }  
    return sum/((double)count);
 
} 
 
int main() {  
    int m, n;
    cin >> n >> m;
    cout << fixed << setprecision(2);
    for(int i = 0; i < m; i++) {
        int* arr = new int[n];
        for(int j = 0 ; j < n; j++) {
            cin >> arr[j];
        }
        cout << res(arr, n) << " ";
        delete[] arr;
    }
    return 0;
}

#include <iostream>

#include <iomanip>

using namespace std;

double res(int *arr, int len) {

int min,max;

min = arr[0];

max = arr[0];

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

if(arr[i] > max) {

max = arr[i];

}

if(arr[i]<min) {

min = arr[i];

}

int sum = 0;

int count = 0;

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

if(arr[i] != max && arr[i] != min) {

sum += arr[i];

count++;

}

return sum/((double)count);

}

int main() {

int m, n;

cin >> n >> m;

cout << fixed << setprecision(2);

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

int* arr = new int[n];

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

cin >> arr[j];

}

cout << res(arr, n) << " ";

delete[] arr;

}

return 0;

}

Решение

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

Ссылки

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

Код программы на ideone (Потоковая обработка)

Код программы на ideone (Массивы)

Related Images:

e-olymp 8519. Сумма четных цифр

21/11/2018 by Алина Гук

Задача взята с сайта e-olymp.

Задача

Задано длинное число. Найти сумму его четных цифр.

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

Одно натуральное число $n (n ≤ 10^{100} )$.

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

Вывести сумму четных цифр числа $n$.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	2345	6
2	3458937487534533459	32
3	888888888888888888888888888888	240

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

#include <iostream>
using namespace std;

int main() {
    char c; 
    int sum = 0;
    while(cin >> c) 
        if((c - '0') % 2 == 0) 
            sum += (c - '0');
    cout << sum << '\n';
    return 0;
}

#include <iostream>

using namespace std;

int main() {

char c;

int sum = 0;

while(cin >> c)

if((c - '0') % 2 == 0)

sum += (c - '0');

cout << sum << '\n';

return 0;

}

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

Переменная c — является переменной типа char, что означает, что cin в этом случае будет считывать по одному символу с потока. По этой причине, чтобы решить данную задачу, нужно считывать заданное число с помощью cin в цикле while до тех пор, пока происходит ввод данных с клавиатуры. Проверяя каждую цифру введенного числа на четность, будем прибавлять четные к переменной sum.
Для работы с символом c как с числом, будем писать c - '0'.

Ссылки

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

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

Related Images:

e-olymp 8372. Составить треугольник

28/09/2018 by Алина Гук

Задача взята с сайта e-olymp

Задача

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

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

Три натуральных числа $a, b, c (1 ≤ a, b, c ≤ 1000)$ — длины трех отрезков.

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

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

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 6 7	YES
2	3 7 4	NO
3	16 24 32	YES
4	54 1 100	NO
5	1 1 1	YES

Код программы (Ветвление)

#include <iostream>
using namespace std;

int main() {
  int a, b, c;
  cin >> a >> b >> c;
  cout << (a < b + c && b < a + c && c < a + b ? "YES" : "NO");
  return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b, c;

cin >> a >> b >> c;

cout << (a < b + c && b < a + c && c < a + b ? "YES" : "NO");

return 0;

}

Код программы (Линейные вычисления)

#include <iostream>
using namespace std;
 
int main() {
  int a, b, c;
  cin >> a >> b >> c;
  bool condition = (a < b + c && b < a + c && c < a + b); 
  cout  << (char)(condition * 'Y' + !condition * 'N')
        << (char)(condition * 'E' + !condition * 'O')
        << (char)(condition * 'S' + !condition * ' ');
  return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b, c;

cin >> a >> b >> c;

bool condition = (a < b + c && b < a + c && c < a + b);

cout << (char)(condition * 'Y' + !condition * 'N')

<< (char)(condition * 'E' + !condition * 'O')

<< (char)(condition * 'S' + !condition * ' ');

return 0;

}

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

Пусть $a, b, c$ – длины трех отрезков. Из них можно составить невырожденный треугольник, если длина каждых двух отрезков больше длины третьего (это условие известно как неравенство треугольника): | $b$ | < | $a$ | + | $c$ | \begin{cases} b + c > a\\a + c > b\\a + b > c\end{cases}

Ссылки

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

Код программы на ideone (Линейные вычисления)

Код программы на ideone (Ветвление)