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 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 48. Красные и синие квадраты

30/06/2018 by Павел Жуков

Задача

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

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

В первой строке находится количество синих квадратов $n$ ($0 < n < 40404$). Далее идут $n$ строк, каждая из которых содержит координаты $x$, $y$ ($-101 \leq x, y \leq 101$) левых нижних углов синих квадратов.

Каждый синий квадрат имеет хотя бы одну общую точку хотя бы с одним другим синим квадратом. Фигура, образованная синими квадратами, является связной.

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

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

Тесты

Входные данные	Выходные данные
$3$ $1$ $2$ $2$ $1$ $3$ $1$	$3$
$3$ $1$ $1$ $2$ $2$ $1$ $3$	$6$
$10$ $1$ $1$ $2$ $2$ $1$ $3$ $2$ $4$ $1$ $5$ $2$ $6$ $1$ $7$ $2$ $8$ $1$ $9$ $2$ $10$	$90$

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

#include <iostream>
using namespace std;

#define MAX_PAGE_SIZE 210

int squares[MAX_PAGE_SIZE][MAX_PAGE_SIZE];

int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i){ int x, y; cin >> x >> y;
        squares[x + MAX_PAGE_SIZE / 2][y + MAX_PAGE_SIZE / 2] = 1;
    }
    int perimiter = 0;
    for (int i = 0; i < MAX_PAGE_SIZE; ++i){
        for (int j = 0; j < MAX_PAGE_SIZE; ++j){
            if (squares[i][j]){
                perimiter += !squares[i + 1][j] + !squares[i - 1][j] + !squares[i][j + 1] + !squares[i][j - 1];
            }
        }
    }
    int max = 0;
    for (int j = 1; (perimiter - 2 * j) / 2 > 0; ++j){ 
        int i = (perimiter - 2 * j) / 2; 
        if (i * j - n > max) {
            max = i * j - n;
        }
    }
    cout << max;
    return 0;
}

#include <iostream>

using namespace std;

#define MAX_PAGE_SIZE 210

int squares[MAX_PAGE_SIZE][MAX_PAGE_SIZE];

int main() {

int n;

cin >> n;

for (int i = 0; i < n; ++i){ int x, y; cin >> x >> y;

squares[x + MAX_PAGE_SIZE / 2][y + MAX_PAGE_SIZE / 2] = 1;

}

int perimiter = 0;

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

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

if (squares[i][j]){

perimiter += !squares[i + 1][j] + !squares[i - 1][j] + !squares[i][j + 1] + !squares[i][j - 1];

}

int max = 0;

for (int j = 1; (perimiter - 2 * j) / 2 > 0; ++j){

int i = (perimiter - 2 * j) / 2;

if (i * j - n > max) {

max = i * j - n;

}

cout << max;

return 0;

}

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

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

Чтобы доказать это, пусть сторона квадрата равна $1$. Тогда периметр фигуры, составленной из этих квадратов, всегда будет делится на $2$ (это легко понять, строя такие фигуры на листке бумаги: добавление каждого нового квадрата в фигуру может изменить периметр только на $-4, -2, 0, 2, 4$). А так как периметр прямоугольника равен $2 * (a + b)$, где $a, b$ – стороны прямоугольника, то для существования прямоугольника с таким-же периметром должно выполняться условие $\forall p \in \mathbb{N} , p > 2 \rightarrow \exists a,b \in \mathbb{N} : 2p = 2*( a + b )$. Очевидно, что условие действительно выполняется для всех $p>2$.

Запишем нашу фигуру в массив squares. После чего посчитаем ее периметр: каждый непустой квадратик фигуры добавляет $1$ к периметру за каждую пустую клеточку слева, справа, сверху или снизу от него. Далее будем искать все подходящие прямоугольники, записывая максимальную площадь в переменную max: перебирая значения первой стороны $j$, высчитываем через периметр вторую сторону $i = \displaystyle \frac{p}{2} — j$. Площадь будем считать, как разницу площади прямоугольника и изначальной фигуры (число $n$ равно площади фигуры, потому что площадь каждого квадрата равна $1$).
В конце, выводим разницу максимальной площади и площади изначальной фигуры (площадь изначальной фигуры равна $n$, ведь площадь каждого квадрата равна $1$).

Ссылки

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

Related Images:

e-olymp 2612. Разрезание на квадраты

14/12/2017 by Александр Волынец

Задача

Полоска бумаги имеет размеры [latex]A×B[/latex]. Каждый раз от нее отрезается квадрат максимального размера до тех пор, пока не получится квадрат. Сколько квадратов получится?

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

Программе даны числа [latex]A[/latex] и [latex]B[/latex] [latex](1 ≤ A, B ≤ 10^9).[/latex]

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

Требуется вывести количество квадратов.

Тесты

Входные данные	Выходные данные
12 4	3
15 3	5
20 20	1
8 12	3

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

#include <iostream>
using namespace std;

int main() {
    int a, b, temp = 0;
    bool need = 1;
    cin >> a >> b;
    while (need) {
        if (a >= b) {
            temp = temp + a / b;
            a = a%b;
        }
        else
        {
            temp = temp + b / a;
            b = b%a;
        }
        if (a == 0 || b == 0) {
            need = 0;
        }
    }
    cout << temp;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b, temp = 0;

bool need = 1;

cin >> a >> b;

while (need) {

if (a >= b) {

temp = temp + a / b;

a = a%b;

}

else

{

temp = temp + b / a;

b = b%a;

}

if (a == 0 || b == 0) {

need = 0;

}

cout << temp;

return 0;

}

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

Нам было дана высота и ширина полоски бумаги. Есть три варианта:

Высота равна ширине
Высота больше ширины
Высота меньше ширины

В первом случае нам надо вывести на экран единицу. Во втором случаем начинаем вычитать a - b до того момента, как a не будет меньше b или a не будет равняться 0. В третьем случае начинаем вычитать b - a до того момента, как b не будет меньше a или b не будет равняться 0.

Ссылки

Задача на сайте e-olymp
Код решения в Ideone

Related Images:

e-olymp 8. Спички

12/11/2017 by Алиса Ворохта

Задача

Какое минимальное количество спичек необходимо для того, чтобы выложить на плоскости [latex]n[/latex] квадратов со стороной в одну спичку? Спички нельзя ломать и класть друг на друга. Вершинами квадратов должны быть точки, где сходятся концы спичек, а сторонами – сами спички.

Напишите программу, которая по количеству квадратов [latex]n[/latex], которое необходимо составить, находит минимальное необходимое для этого количество спичек.

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

Одно целое число [latex]n[/latex] [latex](1 ≤ n ≤ 10^9)[/latex].

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

Вывести минимальное количество спичек, требуемых для составления [latex]n[/latex] квадратов.

Тесты

Входные данные	Выходные данные
[latex]1[/latex]	[latex]4[/latex]
[latex]2[/latex]	[latex]7[/latex]
[latex]4[/latex]	[latex]12[/latex]
[latex]7[/latex]	[latex]20[/latex]
[latex]150[/latex]	[latex]325[/latex]
[latex]10000[/latex]	[latex]20200[/latex]

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

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
    long long  n, k;
    long double length, width;
    cin >> n;
    length = floor(sqrt(n));
    width = ceil(n/length);
    k = 2*n + length + width;
    cout << k << endl;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

long long n, k;

long double length, width;

cin >> n;

length = floor(sqrt(n));

width = ceil(n/length);

k = 2*n + length + width;

cout << k << endl;

return 0;

}

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

Один квадрат можно составить из [latex]4[/latex] спичек. Два квадрата — из [latex]7[/latex] спичек. Очевидно, что квадраты следует располагать так, чтобы они образовывали прямоугольник, “близкий” к квадрату.
Например, на рисунке 1 мы использовали меньшее количество спичек, чем на рисунке 2, хотя количество квадратов одинаковое:

Зададим размеры прямоугольника. Пусть [latex]width = \sqrt n[/latex] — его ширина. Округлим значение [latex]width[/latex] к наибольшему целому числу, не превышающему данное. Тогда его длина будет [latex]length = \frac {n} {width}[/latex]. Если округлить значение [latex]length[/latex] к наибольшему целому числу, не превышающему данное, то мы сможем построить лишь те квадраты, которые входят в наш прямоугольник. Округляя же значение [latex]length[/latex] к наименьшему целому числу, которое не меньше данного, мы сможем достроить квадраты, не поместившиеся в наш прямоугольник.
Если отложить вниз количество спичек, равное [latex]width[/latex], и вправо — [latex]length[/latex], получается следующий рисунок (разумеется, количество отложенных спичек меняется в зависимости от [latex]n[/latex]):

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