e-olymp 1099. Говорящий Галчонок

27/03/2019 by Николай Козиний

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

Задача

«Ура-a-a! Заработало!» – радостно воскликнул Матроскин, услышав первую произнесенную Галчонком фразу.

Э.Успенский «Трое из Простоквашино»

Как Вам всем известно, Галчонок из мультфильма «Трое из Простоквашино» при стуке в дверь всегда спрашивал: «Кто там?». Статистика, как и вся математика, наука точная и она утверждает, что Галчонок мог запоминать как отдельные слова, так и целые предложения, только в том случае, если слово было произнесено не менее $n$ раз, а предложение – не менее чем $m$ раз $\left(n\leqslant m\right)$.

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

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

В первой строке находится два натуральных числа $n$ и $m$ $\left(n , m \leqslant 100 \right)$. Во второй строке находится сам текст. Текст написан грамматически верно.

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

Два числа через пробел: сначала количество запомненных слов $s$, а потом количество запомненных предложений $p$.

Тесты

N,M	ТЕКСТ	ВЫХОДНЫЕ ДАННЫЕ
2,4	Blessed are the peacemakers, for they will be called children of God.	0 0
2,3	Kto tam? It is Pechkin. Kto tam? My name is Fedor. Kto tam? Pechkin!	4 1
1,1	Hey you! out there on the road Always doing what you’re told Can you help me Hey you! out there beyond the wall Breaking bottles in the hall Can you help me Hey you! don’t tell me there’s no hope at all Together we stand, divided we fall	33 3
2,2	Yes! No. Yes Yes! No Yes no no. No yes No No.	2 1
1,1	Workers of the world, unite!	5 1

Решение

#include <iostream>
#include <map>
using namespace std;
int main() {
    map <string,int> s;
    map <string,int> w;
    int n, m, a = 0,b = 0;
    cin >> n >> m;
    string word, sent;
    while(cin >> word){
        if(word.back() == ',')word.pop_back();
        sent = sent + word;
        if(word.back() == '.' or word.back() == '?' or word.back() == '!'){
            word.pop_back();
            sent.pop_back();
            if((++s[sent]) == m)a++;
            sent = "";
        }
        if((++w[word]) == n)b++;
    }
    cout << b << ' ' << a;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

map <string,int> s;

map <string,int> w;

int n, m, a = 0,b = 0;

cin >> n >> m;

string word, sent;

while(cin >> word){

if(word.back() == ',')word.pop_back();

sent = sent + word;

if(word.back() == '.' or word.back() == '?' or word.back() == '!'){

word.pop_back();

sent.pop_back();

if((++s[sent]) == m)a++;

sent = "";

}

if((++w[word]) == n)b++;

}

cout << b << ' ' << a;

}

Для решения данной задачи найдем все слова и все предложения в тексте. Слова будем считать одинаковыми, если они совпадают без знаков препинания в нижнем регистре они совпадают. Одинаковыми предложениями, соответственно, будем считать предложения, что совпадают без пробелов и знаков препинания. Увеличивая значения ассоциативных массивов, соответствующих предложению или слову на 1, увеличим на 1 значение b, если слова совпали больше чем $n$ раз и значение a, если предложения совпали больше чем $m$ раз.

Код задачи на ideone

Засчитанное решение на e-olymp

Related Images:

e-olymp 7504. Три прямоугольника

19/01/2019 by Николай Козиний

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

Задача

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

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

Одно число — количество закрашенных клеток

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

В трех строках по четыре целых числа — координаты двух противоположных вершин каждого прямоугольника (значения по модулю не превышают 100).

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	0 0 1 1 1 1 2 2 0 0 2 2	4
2	2 -2 -2 2 -1 -1 1 1 40 40 41 41	17
3	-1 2 2 -1 1 0 4 2 1 0 3 6	21
4	-100 -100 -99 -99 100 100 99 99 -100 -100 100 100	40000
5	3 0 4 1 1 0 3 3 1 0 3 3	7

Решение

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

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

После этого задача сводится к написанию функции общей площади. То, что решение, в котором мы просто суммируем площадь трех прямоугольников проходит лишь на один тест, наводит на мысль о том, что мы добавляем площадь пересечений несколько раз. Следовательно, от суммы площадей трех прямоугольников отнимем площадь их пересечения друг с другом и добавим площадь пересечения всех трех(поскольку в случае, если существует пересечение трех, то мы лишний раз отнимаем его площадь).

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

#include <iostream>
#include <cmath>
using namespace std;
struct point{int x;int y;};
struct rect{point a;point b;};
rect getrect(point a, point b, rect c){
    if(a.x > b.x)swap(a.x,b.x);
    if(a.y > b.y)swap(a.y,b.y);
    c.a = a;
    c.b = b;
    return c;
}
rect getrekt(rect c){
    point a,b;
    cin >> a.x >> a.y >> b.x >> b.y;
    return getrect(a,b,c);
}
int area(rect sq){return (sq.b.x - sq.a.x) * (sq.b.y - sq.a.y);}

rect cross(rect l,rect r){
    rect cr;
    point a1,b1;
    a1.x = ((l.a.x > r.b.x or r.a.x > l.b.x)?0:max(l.a.x,r.a.x));
    a1.y = ((l.a.y > r.b.y or r.a.y > l.b.y)?0:max(l.a.y,r.a.y));
    b1.x = ((l.a.x > r.b.x or r.a.x > l.b.x)?0:min(l.b.x,r.b.x));
    b1.y = ((l.a.y > r.b.y or r.a.y > l.b.y)?0:min(l.b.y,r.b.y));
    return getrect(a1,b1,cr);
}
int farea(rect *q){
    return area(q[0]) + area(q[1]) + area(q[2]) - area(cross(q[0],q[1])) - area(cross(q[0],q[2])) - area(cross(q[2],q[1])) + area(cross(q[0],cross(q[1],q[2])));
}
int main() {
    rect *q = new rect [3];
    for(int i = 0;i < 3;i++)q[i] = getrekt(q[i]);
    cout<<farea(q);
}

#include <iostream>

#include <cmath>

using namespace std;

struct point{int x;int y;};

struct rect{point a;point b;};

rect getrect(point a, point b, rect c){

if(a.x > b.x)swap(a.x,b.x);

if(a.y > b.y)swap(a.y,b.y);

c.a = a;

c.b = b;

return c;

}

rect getrekt(rect c){

point a,b;

cin >> a.x >> a.y >> b.x >> b.y;

return getrect(a,b,c);

}

int area(rect sq){return (sq.b.x - sq.a.x) * (sq.b.y - sq.a.y);}

rect cross(rect l,rect r){

rect cr;

point a1,b1;

a1.x = ((l.a.x > r.b.x or r.a.x > l.b.x)?0:max(l.a.x,r.a.x));

a1.y = ((l.a.y > r.b.y or r.a.y > l.b.y)?0:max(l.a.y,r.a.y));

b1.x = ((l.a.x > r.b.x or r.a.x > l.b.x)?0:min(l.b.x,r.b.x));

b1.y = ((l.a.y > r.b.y or r.a.y > l.b.y)?0:min(l.b.y,r.b.y));

return getrect(a1,b1,cr);

}

int farea(rect *q){

return area(q[0]) + area(q[1]) + area(q[2]) - area(cross(q[0],q[1])) - area(cross(q[0],q[2])) - area(cross(q[2],q[1])) + area(cross(q[0],cross(q[1],q[2])));

}

int main() {

rect *q = new rect [3];

for(int i = 0;i < 3;i++)q[i] = getrekt(q[i]);

cout<<farea(q);

}

Решение. Многомерные массивы

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

#include <iostream>
#include <cmath>
#define N 100
using namespace std;
 
int main() {
    int rect[3][4];
    int field[2*N][2*N];
    int count = 0;
    for(int i = 0;i < 2*N;i++)for(int k = 0;k < 2*N;k++)field[i][k] = 0;
    for(int i = 0;i < 3;i++){
        for(int k = 0;k < 4;k++){
            cin >> rect[i][k];
            rect[i][k] = rect[i][k] + N;
        }
    }
    for(int k = 0;k<3;k++){
        for(int i = min(rect[k][0],rect[k][2]);i < max(rect[k][0],rect[k][2]);i++){
            for(int j = min(rect[k][1],rect[k][3]);j < max(rect[k][1],rect[k][3]);j++){
                field[i][j]=1;
            }
        }
    }
    for(int i = 0;i < 2*N;i++){
        for(int k = 0;k < 2*N;k++){
            if(field[i][k] & 1)count++;
        }
    }
    cout<<count;
}

#include <iostream>

#include <cmath>

#define N 100

using namespace std;

int main() {

int rect[3][4];

int field[2*N][2*N];

int count = 0;

for(int i = 0;i < 2*N;i++)for(int k = 0;k < 2*N;k++)field[i][k] = 0;

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

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

cin >> rect[i][k];

rect[i][k] = rect[i][k] + N;

}

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

for(int i = min(rect[k][0],rect[k][2]);i < max(rect[k][0],rect[k][2]);i++){

for(int j = min(rect[k][1],rect[k][3]);j < max(rect[k][1],rect[k][3]);j++){

field[i][j]=1;

}

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

for(int k = 0;k < 2*N;k++){

if(field[i][k] & 1)count++;

}

cout<<count;

}

Код задачи на ideone
Еще один код задачи на ideone(многомерные массивы)
Засчитанное решение на e-olymp

Related Images:

e-olymp 914. Модуль максимального

23/12/2018 by Николай Козиний

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

Задача

Задана послідовність дійсних чисел. Обчислимо їх модулі. Знайдіть максимальне значення серед цих модулей.

Вхідні дані

У першому рядку задано кількість елементів $n\left(n \leqslant 100 \right)$ у послідовності. У наступному рядку задано $n$ дійсних чисел — елементи послідовності, значення яких не первищують за модулем 100.

Вихідні дані

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

Тести

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	0 -1 1	1.00
2	3 -1.1 1.2 -1.3	1.30
3	5 5.16 0 -7.18 3 4.99	7.18
4	4 -75.111 7.5 -5.1 75.110	75.11
5	10 -1 -2 -3 -4 -5 -6 -7 -8 -9 1	9.00

Решение

Задача сходиться до пошуку максимального елемента послідовності. Зрозуміло, що найменше можливе значення модуля числа — 0. Тому, считуючи дані зі вхідного потоку будемо порівнювати їх зі змінною, що дорівнює 0. Якщо значення модуля числа більше за змінну — надаємо змінній значення модуля числа. Таким чином після завершення вхідного потоку змінна буде дорівнювати найбільшому числу послідовності за модулем.

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
int main() {
    int n;
    cin >> n;
    double max = 0;
    for(int i = 0;i < n;i++){
        double a;
        cin >> a;
        if(abs(a) > max)max = abs(a);
    }
    cout<< fixed << setprecision(2) << max;
}

#include <iostream>

#include <iomanip>

#include <cmath>

using namespace std;

int main() {

int n;

cin >> n;

double max = 0;

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

double a;

cin >> a;

if(abs(a) > max)max = abs(a);

}

cout<< fixed << setprecision(2) << max;

}

Зараховане рішення на e-olymp
Код задачі на ideone

Related Images:

e-olymp 8654. Целочисленное умножение

22/12/2018 by Николай Козиний

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

Задача

Даны три целых числа $a, b, c.$ Вычислить значение выражения $a \cdot b \text{ mod } c.$

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

Три целых положительных числа $a, b, c \left( a, b, c < 2^{63} \right).$

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

Вывести значение выражения $ a \cdot b \text{ mod } c.$

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	2 3 2	0
2	11 3 2	1
3	123456789 987654321 17	0
4	5000400000023 23000400400500 100000000070707	68238553233174
5	10000018585 10000000000005 101020304050607080	85850050000993845

Решение

Для решения задачи напишем рекурсивную функцию умножения, основанную на том, что [latex]\displaystyle a\cdot b =\displaystyle[/latex][latex] \begin{cases}\left(a+a\right)\cdot\frac{b}{2} &\text{} b\equiv_{2} 0 \\a+a\cdot\left(b-1\right) & \text{} b \not \equiv_{2} 0\ \end{cases}.[/latex] Поскольку максимальное значение из условия задачи в два раза меньше максимального числа из 64-битных беззнаковых чисел и[latex]\left(a\cdot b\right)\text{ mod } c =\left(a\text{ mod } с \cdot b\text { mod }c\right)\text{ mod }c,[/latex] мы можем на каждом шагу применять к $a$ и $b$ операцию остатка от деления на $c$ , за счет чего произведение никогда не будет превосходить $2^{64}-1$.

include <iostream>
unsigned long long mult(unsigned long long x,unsigned long long y,unsigned long long const z){
    if(y == 1)return x % z;
    else if(y == 0)return 0;
    else if( y & 1 )return (x % z + mult(x % z,(y - 1) % z,z))%z;
    else return mult((x + x)%z,(y / 2) % z,z);
 
}
int main() {
    unsigned long long a,b,c;
    std::cin >> a >> b >> c;
    std::cout << mult(a,b,c);
}

include <iostream>

unsigned long long mult(unsigned long long x,unsigned long long y,unsigned long long const z){

if(y == 1)return x % z;

else if(y == 0)return 0;

else if( y & 1 )return (x % z + mult(x % z,(y - 1) % z,z))%z;

else return mult((x + x)%z,(y / 2) % z,z);

}

int main() {

unsigned long long a,b,c;

std::cin >> a >> b >> c;

std::cout << mult(a,b,c);

}

Засчитанное решение на e-olymp
Код на ideone

Related Images:

e-olymp 2060 Сказка о яблоке

20/11/2018 by Николай Козиний

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

Задача

Однажды царь наградил крестьянина яблоком из своего сада. Пошёл крестьянин к саду и видит: весь сад огорожен $n$ заборами, в каждом заборе только одни ворота, и в каждых воротах стоит сторож. Подошёл крестьянин к первому сторожу и показал царский указ, а сторож ему в ответ: «Иди возьми, но при выходе отдашь мне половину тех яблок, что несёшь, и ещё одно». То же ему сказали и второй, и третий сторож и т.д. Сколько яблок должен взять крестьянин, чтобы после расплаты со сторожами у него осталось одно яблоко?

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

Количество заборов $n (1 \leqslant n \leqslant 62)$ в саду.

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

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

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1	4
2	3	22
3	30	50331646
4	60	3458764513820540926
5	62	13835058055282163710

Решение

Циклы

Последовательность необходимых количеств яблок задается формулой $x_{n+1}=2 \cdot (x_{n}+1);x_{1}=1.$ Мы можем поочередно вычислять элементы последовательности через цикл.

#include <iostream>
int main() {
    int n;
    std::cin>>n;
    unsigned long long k = 1;
    for(int i = 0; i<n; i++)k = (k + 1) * 2;
    std::cout<<k;
}

#include <iostream>

int main() {

int n;

std::cin>>n;

unsigned long long k = 1;

for(int i = 0; i<n; i++)k = (k + 1) * 2;

std::cout<<k;

}

Линейное решение

Преобразуем исходное выражение для $x_{n+1}=2 \cdot x_{n}+2.$ Можно видеть, что каждая следующая итерация увеличивает степень всех двоек входящих в предыдущую на 1 и добавляет 2. Выпишем формулу для $x_{n+m}=2^{m}x_n+2^{m-1}x_n+\cdots+2.$ Можно увидеть, что $x_{n+m}$ содержит слагаемое $2^{m}x$, а так же сумму слагаемых вида $\displaystyle \sum_{i=1}^{m}2^i \displaystyle.$ Если учесть, что $x_{1}=1$, то $\displaystyle x_n=2^{n}+ \sum_{i=1}^{n}2^i \displaystyle=2^{n+1}+2^n-2=2^{n}\cdot(2+1) -2.$ Следовательно формула $n$-го члена — [latex]x_n=3\cdot 2^n-2.[/latex]

#include <iostream>
int main() {
    int n;
    std::cin>>n;
    unsigned long long t = 2;
    std::cout<<3*(t<<n-1)-2;
}

#include <iostream>

int main() {

int n;

std::cin>>n;

unsigned long long t = 2;

std::cout<<3*(t<<n-1)-2;

}

Задача

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

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

Тесты

Решение

Related Images:

Задача

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

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

Тесты

Решение

Решение. Многомерные массивы

Related Images:

Задача

Вхідні дані

Вихідні дані

Тести

Решение

Related Images:

Задача

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

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

Тесты

Решение

Related Images:

Задача

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

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

Тесты

Решение

Циклы

Линейное решение

Решения на ideone

Related Images: