e-olymp 1442. Одномерная Кликомания

26/06/2019 by Наталья Федина

Задача

«Одномерная Кликомания» — это логическая компьютерная игра. Для нее используется полоска размеров $1 \times N$, разбитая на $N$ квадратов $1 \times 1.$ Каждый из квадратов окрашен в красный или желтый цвет.
За один ход игрок может выбрать любой из квадратов и щелкнуть по нему мышкой. В результате компьютер выделяет на полоске группу максимальной длины, состоящую из стоящих подряд квадратов одинакового цвета и содержащую выделенный квадрат, и удаляет все квадраты из этой группы. При этом все квадраты, находящиеся правее удаленной группы (если они существуют), сдвигаются влево так, чтобы пристыковаться к квадратам, находящимся левее удаленной группы (если они существуют) и сохранить целостность полоски:

Игрок может удалять группы квадратов любой длины, в том числе, состоящие из одного квадрата. Игра продолжается до тех пор, пока все квадраты не удалены.
В начале игры количество баллов у игрока равно нулю. После каждого его хода количество баллов пересчитывается. Если игрок очередным ходом удалил группу из $L$ квадратов, то вычисляется число $X = A \cdot L + B$, где $A$ и $B$ — некоторые целочисленные константы. Если число $X$ неотрицательное, то количество баллов игрока увеличивается на $X$, иначе оно уменьшается на $-X$.
Цель игрока — набрать по окочанию игры как можно больше баллов. Напишите программу, оптимально играющую в «Одномерную Кликоманию». Программа должна получать на входе цвета всех квадратов исходной полоски, а также целые числа $A$ и $B$, и возвращать максимальное количество баллов, которое может набрать игрок по окончанию игры.

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

В первой строке задана строка, состоящая из символов $’R’/’Y’$, перечисляющих слева направо цвета всех квадратов исходной полоски. Символ $’R’$ соответствует квадрату красного цвета, а символ $’Y’$ — квадрату желтого цвета.
Во второй и третьей строках соответственно целые числа $A(1 \leq A \leq 1000)$ и $B(-100 \leq B \leq 100)$, задающие константы в формуле начисления очков за каждый сделанный ход.

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

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

Тесты

	Входные данные	Выходные данные
1	YYYYYYY 73 14	525
2	RYRYRYR 100 -100	300
3	YYYRRR 1 -100	-194
4	YRYYRRRYYYYY 12 34	314

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

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
int main() {
 int a, b, count = 1;
 vector <int> vec;
 string str;
 getline(cin, str);
 int n = str.length();
 for (int i = 1; i < n; i++) if (str[i - 1] != str[i]) {
        vec.push_back(count);
        count = 1;
    } else count++;
 vec.push_back(count);
 cin >> a >> b;
 int sum = 0;
 for (int e : vec) sum += e;
 int len = vec.size();
 cout << a * sum + ((b < 0) ? (len / 2 + 1) : len) * b;
 return 0;
}

#include <iostream>

#include <string>

#include <vector>

using namespace std;

int main() {

int a, b, count = 1;

vector <int> vec;

string str;

getline(cin, str);

int n = str.length();

for (int i = 1; i < n; i++) if (str[i - 1] != str[i]) {

vec.push_back(count);

count = 1;

} else count++;

vec.push_back(count);

cin >> a >> b;

int sum = 0;

for (int e : vec) sum += e;

int len = vec.size();

cout << a * sum + ((b < 0) ? (len / 2 + 1) : len) * b;

return 0;

}

Решение

По условию задачи необходимо определить максимальное количество очков которое можно получить в игре. Число $a$ всегда положительное и умножается на количество квадратов удалённых за один ход. В конце игры будут удалены все квадраты, а значит этот вклад в общий счёт игры равен $a \cdot n$, где $n$ — количество квадратиков в игре. Число $b$ может быть как положительным так и отрицательным. В первом случае, нам выгодно, что бы игрок совершил максимальное число ходов, то есть ровно столько, сколько содержится последовательностей из квадратиков одного цвета. Если $b$ меньше нуля, то счёт будет наибольший, если игрок сделает наименьшее количество ходов, а именно избавиться от чередования цветов и за один ход удалит все квадраты, это количество последовательностей пополам, плюс один.
Считаем необходимые данные и выводим ответ в зависимости от положительности $b$.

Ссылки

Related Images:

e-olymp 8382. Пароль

27/05/2019 by Наталья Федина

Задача

Назовем пароль криптостойким*, если выполнены $5$ критериев

Пароль содержит строчные латинские буквы
Пароль содержит заглавные латинские буквы
Пароль содержит цифры
Символы: ! » # $ % & ‘ ( ) * +
Длина пароля не менее $8$ символов

Требуется по данному паролю определить, сколько критериев криптостойкости выполнено.

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

Вводится одна строка, состоящая только из латинских букв и цифр. Количество символов в строке не превышает $100$.

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

Выведите количество критериев криптостойкости, которым удовлетворяет пароль.

Тесты

	Входные данные	Выходные данные
1	1aA	3
2	AaBbCc12	4
3	AAAaaaAAA	3
4	#Abc23$$$	5

Код программы (string)

#include <iostream>
using namespace std;
 
bool isspecial (char c) {
    return (c == '!' || c == '"' || c == '#' ||
            c == '$' || c == '%' || c == '&' || 
            c == '+' || c == '(' || c == ')'  ||
            c == '*' || c == '\'');
}
 
int main() {
    string password;
    cin >> password;
    bool test_lc, test_uc, test_dig, test_sp, 
    test_len = password.length() >= 8;
    int length = password.length();
    test_lc = test_uc = test_dig = test_sp = false;
    for (int i = 0; i < length; i++) {
        if (!test_lc) test_lc = islower(password[i]);
        if (!test_uc) test_uc = isupper(password[i]);
        if (!test_dig) test_dig = isdigit(password[i]);
        if (!test_sp) test_sp = isspecial(password[i]);
    }
    cout << test_len + test_lc + test_uc + test_dig + test_sp;
    return 0;
}

#include <iostream>

using namespace std;

bool isspecial (char c) {

return (c == '!' || c == '"' || c == '#' ||

c == '$' || c == '%' || c == '&' ||

c == '+' || c == '(' || c == ')' ||

c == '*' || c == '\'');

}

int main() {

string password;

cin >> password;

bool test_lc, test_uc, test_dig, test_sp,

test_len = password.length() >= 8;

int length = password.length();

test_lc = test_uc = test_dig = test_sp = false;

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

if (!test_lc) test_lc = islower(password[i]);

if (!test_uc) test_uc = isupper(password[i]);

if (!test_dig) test_dig = isdigit(password[i]);

if (!test_sp) test_sp = isspecial(password[i]);

}

cout << test_len + test_lc + test_uc + test_dig + test_sp;

return 0;

}

Код программы (c-string)

#include <iostream>
#include <cstring>
using namespace std;
 
bool isspecial (char c) {
  return (c == '!' || c == '"' || c == '#' ||
      c == '$' || c == '%' || c == '&' || 
      c == '+' || c == '(' || c == ')'  ||
      c == '*' || c == '\'');
}
 
int main() {
  char password[101];
  cin >> password;
  bool test_lc, test_uc, test_dig, test_sp, 
  test_len = strlen(password) >= 8;
  int length = strlen(password);
  test_lc = test_uc = test_dig = test_sp = false;
  for (int i = 0; i < length; i++) {
    if (!test_lc) test_lc = islower(password[i]);
    if (!test_uc) test_uc = isupper(password[i]);
    if (!test_dig) test_dig = isdigit(password[i]);
    if (!test_sp) test_sp = isspecial(password[i]);
  }
  cout << test_len + test_lc + test_uc + test_dig + test_sp;
  return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

bool isspecial (char c) {

return (c == '!' || c == '"' || c == '#' ||

c == '$' || c == '%' || c == '&' ||

c == '+' || c == '(' || c == ')' ||

c == '*' || c == '\'');

}

int main() {

char password[101];

cin >> password;

bool test_lc, test_uc, test_dig, test_sp,

test_len = strlen(password) >= 8;

int length = strlen(password);

test_lc = test_uc = test_dig = test_sp = false;

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

if (!test_lc) test_lc = islower(password[i]);

if (!test_uc) test_uc = isupper(password[i]);

if (!test_dig) test_dig = isdigit(password[i]);

if (!test_sp) test_sp = isspecial(password[i]);

}

cout << test_len + test_lc + test_uc + test_dig + test_sp;

return 0;

}

Решение

Для подсчёта удовлетворённых критериев криптостойкости будем использовать 5 булевских флагов, соответствующих каждому из критериев. Длину пароля определим сразу, а наличие символов определенного типа будем проверять в цикле. Для проверки наличия цифр и латинских букв нижнего и верхнего регистров используем встроенные функции isdigit() , islower() и isupper() , а для специальных символов напишем функцию isspecial() .

Ссылки

Для string:

Для c-string:

* В условии задачи — «крипто стойким».

Related Images:

e-olymp 5090. На перекрёстке

24/12/2018 by Наталья Федина

Задача

Есть таблица $n × n.$ Оживленностью строки или столбца назовем сумму чисел в ней. Нам очень хочется определить число на перекрестке самой оживленной строки и самого неоживленного столбца. Причем, чем выше будет этот перекресток (а среди них – чем левее), тем больше будет вероятность прохождения теста.

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

В первой строке находится число $n (1 \leq n \leq 100).$ В следующих $n$ строчках задана таблица. Числа в таблице натуральные и не превышают $100000.$

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

Выведите число на перекрестке самой оживленной строки и самого неоживленного столбца.

Тесты

	Входные данные	Выходные данные
1	2 4 3 2 1	3
2	3 1 1 1 1 1 1 1 1 1	1
3	5 13 15 17 2 9 4 56 8 90 0 4 3 5 7 5 23 4 5 71 4 5 6 7 8 10	0
4	4 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1	1

Код

С помощью одномерного массива

#include <iostream>
using namespace std;
 
int main() {
    int n, ns;
    cin >> n;
    ns = n*n;
    int *x = new int[ns];
    for (int i = 0; i < ns; i++)
        cin >> x[i];
    int I, J, min, max;
    for (int i = 0; i < ns; i += n) {
        int lmax = 0;
        for (int j = 0; j < n; j++)
            lmax += x[i + j];
        if (lmax > max || i == 0) {
            max = lmax;
            I = i;
        }
    }
    for (int j = 0; j < n; j++) {
        int lmin = 0;
        for (int i = 0; i < ns; i += n)
            lmin += x[i + j];
        if (lmin < min || j == 0) {
            min = lmin;
            J = j;
        }
    }
    cout << x[I + J];
    delete []x;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, ns;

cin >> n;

ns = n*n;

int *x = new int[ns];

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

cin >> x[i];

int I, J, min, max;

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

int lmax = 0;

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

lmax += x[i + j];

if (lmax > max || i == 0) {

max = lmax;

I = i;

}

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

int lmin = 0;

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

lmin += x[i + j];

if (lmin < min || j == 0) {

min = lmin;

J = j;

}

cout << x[I + J];

delete []x;

return 0;

}

С помощью двумерного массива

#include <iostream>
using namespace std;

int main() {
    int n;
    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];
    int I, J, min, max;
    for (int i = 0; i < n; i++) {
        int lmax = 0;
        for (int j = 0; j < n; j++)
            lmax += x[i][j];
        if (lmax > max || i == 0) {
           max = lmax;
           I = i;
        }
    }
    for (int j = 0; j < n; j++) {
        int lmin = 0;
        for (int i = 0; i < n; i++)
            lmin += x[i][j];
        if (lmin < min || j == 0) {
            min = lmin;
            J = j;
        }
    }
    cout << x[I][J];
    for (int i = 0; i < n; i++)
        delete []x[i];
        delete []x;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

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];

int I, J, min, max;

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

int lmax = 0;

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

lmax += x[i][j];

if (lmax > max || i == 0) {

max = lmax;

I = i;

}

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

int lmin = 0;

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

lmin += x[i][j];

if (lmin < min || j == 0) {

min = lmin;

J = j;

}

cout << x[I][J];

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

delete []x[i];

delete []x;

return 0;

}

Решение

Для решения данной задачи используем двумерный массив размера $n \times n$. С помощью цикла for ищем самую оживленную строку, затем самый неоживленный столбец, и выводим элемент таблицы на их перекрёстке.
Для решения с помощью одномерного массива действуем аналогично, работая с массивом длинны $n^2$, используя следующее соответствие: $x[i][j] \sim x[i \cdot n + j]$

Ссылки

С помощью одномерного массива
- e-olymp
- ideone
С помощью двумерного массива
- ideone
- e-olymp

Related Images:

e-olymp 8525. Четные отрицательные в матрице

24/12/2018 by Наталья Федина

Задача

Задана матрица размера $n \times n.$ Найдите количество и сумму ее четных отрицательных чисел.

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

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

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

Выведите в одной строке количество и сумму четных отрицательных чисел в матрице.

Тесты

	Входные данные	Выходные данные
1	3 4 -2 5 1 -4 -12 0 1 -3	3 -18
2	2 4 -7 2 9	0 0
3	5 3 4 -5 7 2 1 2 3 4 -2 -2 -4 -6 -8 4 2 -4 0 -1	6 -26
4	4 1 2 3 4 -1 -2 -4 -3 4 -5 -8 -12 -4 -5 -7 0	5 -30

Код

С помощью двумерного массива

#include <iostream>
using namespace std;

int main() {
    int x[100][100];
    int n, sum = 0, count = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> x[i][j]; 
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (x[i][j] < 0 and x[i][j] % 2 == 0) {
               sum += x[i][j]; 
               count++;
            }
        }
    }
    cout << count << " " << sum; 
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int x[100][100];

int n, sum = 0, count = 0;

cin >> n;

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

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

cin >> x[i][j];

}

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

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

if (x[i][j] < 0 and x[i][j] % 2 == 0) {

sum += x[i][j];

count++;

}

cout << count << " " << sum;

return 0;

}

Без использования массива

#include <iostream>
using namespace std;

int main() {
    int n, count = 0, sum = 0, k;
    cin >> n;
    for (int i = 0; i < n * n; i++) {
        cin >> k;
        if (k < 0 && k % 2 == 0) {
            sum += k;
            count++;
        }
    }
    cout << count << " " << sum;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, count = 0, sum = 0, k;

cin >> n;

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

cin >> k;

if (k < 0 && k % 2 == 0) {

sum += k;

count++;

}

cout << count << " " << sum;

return 0;

}

Решение

С помощью массива

Создаем массив. С помощью цикла for проверяем: если число отрицательное и чётное, то прибавляем его к sum. Выводим количество таких чисел и их сумму.

Без массива

С помощью цикла for проверяем: если число отрицательное и четное, то прибавляем его к sum. Выводим количество таких чисел и их сумму.

Ссылки

e-olymp (С массивом)
ideone (С массивом)
e-olymp (Без массива)
ideone (Без массива)

Related Images:

e-olymp 904. Увеличить на 2

23/12/2018 by Наталья Федина

Задача

Задана последовательность целых чисел. Увеличить на $2$ каждый ее неотрицательный элемент.

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

В первой строке задано количество элементов последовательности $n(n ≤ 100).$ Во второй строке заданы сами элементы, значение каждого из которых по модулю не превышает $100.$

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

Вывести в одной строке $n$ чисел: новые значения элементов последовательности в том же порядке, в котором они были заданы.

Тесты

	Входные данные	Выходные данные
1	4 1 2 3 -4	3 4 5 -4
2	7 7 -3 4 -2 5 0 -1	9 -3 6 -2 7 0 -1
3	5 6 -12 28 -32 -1	8 -12 30 -32 -1
4	3 -2 -3 -4	-2 -3 -4

Код

#include <iostream>
using namespace std;
 
int main() {
    int k, x; 
    cin >> k;
    for (int i = 0; i < k; i++) {
        cin >> x;
        cout << (x < 0? x: x + 2) << " ";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int k, x;

cin >> k;

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

cin >> x;

cout << (x < 0? x: x + 2) << " ";

}

return 0;

}

Решение

Вводим количество элементов последовательности. С помощью цикла for вводим элементы последовательности, в то же время проверяя: если число положительное, увеличиваем его на два, если же отрицательное, то оставляем без изменений, выводим новые элементы.

Ссылки

Related Images:

e-olymp 6777. Автобус

19/12/2018 by Наталья Федина

Задача

Автобус с $n$ пассажирами открывает двери на автобусной остановке. В точности половина пассажиров плюс полпассажира выходит. На следующей остановке снова половина пассажиров плюс полпассажира выходит из автобуса. Так продолжается $k$ остановок. Зная, что на последней остановке автобус стал пустым, и никто не пострадал во время поездки, определите начальное количество людей $n$ в автобусе.

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

Первая строка содержит количество тестов $t$. Каждый тест содержит в отдельной строке количество остановок $k(1 \leq k \leq 30).$

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

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

Тесты

	Входные данные	Выходные данные
1	2 1 3	1 7
2	3 0 15 12	0 32767 4095
3	7 5 8 10 19 4 1 9	31 255 1023 524287 15 1 511
4	4 23 17 2 8	8388607 131071 3 255

Код

#include <iostream>
using namespace std;

int main() {
    int n;
    int k;
    cin >> n;
    while (n-- > 0) {
        cin >> k;
        cout << (1 << k) - 1 << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

int k;

cin >> n;

while (n-- > 0) {

cin >> k;

cout << (1 << k) - 1 << endl;

}

return 0;

}

Решение

Число пассажиров обязано быть нечётным, так как если бы оно было чётным, то какого-то пассажира пришлось бы резать пополам, что противоречит условию.
На последней остановке должен выйти всего один пассажир, потому что обязательно из автобуса выйдет пол пассажира и половина от всех едущих, и при этом автобус опустеет.
Значит:
$$\frac{x}{2} + 0.5 = x$$
$$\frac{x}{2} = x — 0.5$$
$$x = 2x — 1$$
$$x = 1,$$
где $x$ — число пассажиров в автобусе.
Тогда на предпоследней остановке было:
$$x = x_0 + \frac{x}{2} + 0.5$$
$$\frac{x}{2} = x_0 + 0.5$$
$$x = 2(x_0 + 0.5) = 2x_0 + 1,$$
где $x_0$ — число пассажиров оставшихся в автобусе. Значит $x = 3$
И так далее. А значит на $k$-ой остановке перед выходом пассажиров было:
$x = 2\cdot \left(2\cdot\left(2\cdot\left( \cdots 2\cdot\left(0\right) + 1\right) + \ldots +1\right) + 1\right) + 1$ или $x = 2^n \cdot 0 + 2^{n-1} + \ldots + 2 + 1$
Свернём по формуле суммы геометрической прогрессии, где $b = 1$ и $q = 2.$
[latex]S_k = \frac{b\left(q^k -1\right)}{q-1} = 2^{k} — 1.[/latex]

Ссылки

Related Images:

e-olymp 8534. Хлопці на ім’я Валя

09/12/2018 by Наталья Федина

Задача

У літньому таборі $n$ дітей. Серед будь-яких $L$ дітей є хоча б одна дівчинка. Серед будь-яких $v$ дітей є дитина на ім’я Валя (це ім’я можуть мати і хлопчик, і дівчинка). Напишіть програму, що визначає умову наявності в таборі хоча б одного Валентина.

Вхідні дані

$100≤n≤200$, $40≤L≤140$, $20≤v≤70$. Вхідні дані ввести зі стандартного пристрою введення в один рядок, розділяючи значення пропусками.

Вихідні дані

На стандартний пристрій виведення вивести $1$, якщо відповідь на питання умови стверджувальне. Інакше вивести $0$.

Тесты

Входные данные	Выходные данные
110 80 27	1
100 70 30	1
70 50 30	0
85 35 20	1
90 50 50	0

Код програми

#include <iostream>
using namespace std;

int main() {
	int n, v, l;
	cin >> n >> v >> l;
	cout << (n > v + l - 1);
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, v, l;

cin >> n >> v >> l;

cout << (n > v + l - 1);

return 0;

}

Решение

Так як серед $v$ дітей точно знайдеться Валя, то нам необхідно, щоб $n — v + 1$ було додатним. Іншими словами, дітей було більше, ніж достатня для Валь їх кількість. Але так як Валею може бути ще й дівчинка, необхідно, щоб ця різниця була більшою, ніж $l$. Таким чином, завжди знайдеться Валя з інших $v$ дітей, хоча б один з яких не увійшов в $l$. Звідси і формула: $n>v+ l-1$ або $n> = l + v$.

e-olymp

ideone

Related Images:

e-olymp 7401. Друзья Степана

02/10/2018 by Наталья Федина

Задача

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

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

Одно число $n$ (1 ≤ $n$ ≤ 100).

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

Выведите одно число — количество друзей Степана.

Пояснение к примеру

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

Тесты

Входные данные	Выходные данные
2	1
3	2
6	5
50	49
100	99

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

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;
    cout << n - 1;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

cout << n - 1;

return 0;

}

Решение

Известно, что Степан разделил камни между своими друзьями таким образом, что каждому из друзей досталось по 1 камню, и 1 камень остался. Значит количество камней при делении на количество друзей равно единице с единицей в остатке, из чего следует, что количество друзей разнится от количества камней на единицу, то есть — равно $n-1$.

Ссылки

e-olymp

https://ideone.com