e-olymp 4843. Равные подстроки

26/12/2018 by Юлиана Боурош

Задача

Дана строка $S = s_1 s_2 s_3\cdots s_n$и множество запросов вида $(l_1, r_1, l_2, r_2)$.

Для каждого запроса требуется ответить, равны ли подстроки $s_{l1} … s_{r1}$ и $s_{l2} \cdots s_{r2}$.

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

В первой строке записана строка $S$, состоящая из строчных латинских букв. Эта строка непустая и имеет длину не более $100000$ символов. Во второй строке записано целое число $q (1 \leq q \leq 50000)$ — количество запросов. В каждой из следующих $q$ строк записаны числа $l_1, r_1, l_2, r_2 (1\leq l_1 \leq r_1 \leq |S|; 1\leq l_2 \leq r_2 \leq |S|)$.

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

Для каждого запроса выведите «$+$», если соответствующие подстроки равны, и «$-$», в противном случае.

Тесты

№	Входные данные	Выходные данные
1	abacaba 4 1 1 7 7 1 3 5 7 3 4 4 5 1 7 1 7	++-+
2	qa 3 1 1 1 1 2 2 2 2 1 1 2 2	++-
3	barcarbank 3 2 3 5 6 1 2 7 8 1 3 7 9	++-
4	abbabdad 4 1 3 4 6 2 3 5 6 1 2 4 5 3 5 6 8	—++

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

#include <iostream>
#include <string>
using namespace std;

int main() {
    string s;
    int q, begin1, end1, begin2, end2;
    getline(cin, s);
    cin >> q;
    while (q--) {
        cin >> begin1 >> end1 >> begin2 >> end2;
        end1 -= --begin1; // в begin1/2 останется индекс начала подстроки
        end2 -= --begin2; // в end1/2 - кол-во последующих букв
        cout << (s.substr(begin1, end1) == s.substr(begin2, end2) ? '+' : '-'); 
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

int q, begin1, end1, begin2, end2;

getline(cin, s);

cin >> q;

while (q--) {

cin >> begin1 >> end1 >> begin2 >> end2;

end1 -= --begin1; // в begin1/2 останется индекс начала подстроки

end2 -= --begin2; // в end1/2 - кол-во последующих букв

cout << (s.substr(begin1, end1) == s.substr(begin2, end2) ? '+' : '-');

}

return 0;

}

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

#include <iostream>
#include <cstring>
using namespace std;

int main() {
    char str[100001], substr1[100001], substr2[100001];
    cin >> str;
    int q, l1, r1, l2, r2;
    cin >> q;
    while (q--) {
        cin >> l1 >> r1 >> l2 >> r2;
        strncpy(substr1, &str[l1 - 1], r1 - l1 + 1);
        strncpy(substr2, &str[l2 - 1], r2 - l2 + 1);
        cout <<( strcmp(substr1,substr2) == 0 ? '+': '-');
        memset(substr1, 0, sizeof(substr1)/sizeof(substr1[0]));
        memset(substr2, 0, sizeof(substr2)/sizeof(substr2[0]));
        
    }
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

char str[100001], substr1[100001], substr2[100001];

cin >> str;

int q, l1, r1, l2, r2;

cin >> q;

while (q--) {

cin >> l1 >> r1 >> l2 >> r2;

strncpy(substr1, &str[l1 - 1], r1 - l1 + 1);

strncpy(substr2, &str[l2 - 1], r2 - l2 + 1);

cout <<( strcmp(substr1,substr2) == 0 ? '+': '-');

memset(substr1, 0, sizeof(substr1)/sizeof(substr1[0]));

memset(substr2, 0, sizeof(substr2)/sizeof(substr2[0]));

}

return 0;

}

Решение

Циклично находим указанные подстроки на введённых отрезках символов и сравниваем их.

Ссылки

string

c-string

Related Images:

e-olymp 458. Черно-белая графика

24/12/2018 by Юлиана Боурош

Задача

Одна из базовых задач компьютерной графики – обработка черно-белых изображений. Изображения можно представить в виде прямоугольников шириной $w$ и высотой $h,$ разбитых на $w × h$ единичных квадратов, каждый из которых имеет либо белый, либо черный цвет. Такие единичные квадраты называются пикселами. В памяти компьютера сами изображения хранятся в виде прямоугольных таблиц, содержащих нули и единицы.

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

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

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

Первая строка содержит два целых числа $w$ и $h$ $(1 \leq w, h \leq 100).$ Последующие $h$ строк описывают первое изображение и каждая из этих строк содержит $w$ символов, каждый из которых равен нулю или единице. Далее следует описание второго изображения в аналогичном формате. Последняя строка содержит описание логической операции в виде четырех чисел, каждое из которых – ноль или единица. Первое из них есть результат применения логической операции в случае, если оба аргумента нули, второе – результат в случае, если первый аргумент ноль, второй единица, третье – результат в случае если первый аргумент единица, второй ноль, а четвертый – в случае, если оба аргумента единицы.

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

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

Тесты

	Входные данные	Выходные данные
1	5 3 01000 11110 01000 10110 00010 10110 0110	11110 11100 11110
2	2 3 010 111 000 101 1010	11 10 10
3	4 4 1111 0101 0000 1110 0011 0101 0111 1111 0011	1111 0101 0000 1110
4	3 6 100011 000111 000000 111011 001100 010101 1000	000 100 110 000 101 010

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

( использован одномерный массив)

#include <iostream>
using namespace std;

bool my_operation (bool a, bool b, bool* res) {
    if (!a and !b) return res[0];
    else if (!a and b) return res[1];
    else if (a and !b) return res[2];
    else return res[3];
}

int main() {
    int w, h, n;
    bool truth_t[4];
    cin >> w >> h;
    n = w * h;
    bool *first_t = new bool [n];
    bool *second_t = new bool [n];
    char c;
    for (int i = 0; i < n; i++) {
        cin >> c;
        first_t[i] = (c == '1' ? true : false);
    }
    for (int i = 0; i < n; i++) {
        cin >> c;
        second_t[i] = (c == '1' ? true : false);
    }
    for (int i = 0; i < 4; i++) {
        cin >> c;
        truth_t[i] = (c == '1' ? true : false);
    }
    for (int i = 0; i < n; i++) {
        if (i != 0 && i % w == 0)
        cout << endl;
        cout << my_operation(first_t[i], second_t[i], truth_t);
    }
    return 0;
}

#include <iostream>

using namespace std;

bool my_operation (bool a, bool b, bool* res) {

if (!a and !b) return res[0];

else if (!a and b) return res[1];

else if (a and !b) return res[2];

else return res[3];

}

int main() {

int w, h, n;

bool truth_t[4];

cin >> w >> h;

n = w * h;

bool *first_t = new bool [n];

bool *second_t = new bool [n];

char c;

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

cin >> c;

first_t[i] = (c == '1' ? true : false);

}

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

cin >> c;

second_t[i] = (c == '1' ? true : false);

}

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

cin >> c;

truth_t[i] = (c == '1' ? true : false);

}

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

if (i != 0 && i % w == 0)

cout << endl;

cout << my_operation(first_t[i], second_t[i], truth_t);

}

return 0;

}

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

(использован двумерный массив)

#include <iostream>
using namespace std;

bool my_operation (bool a, bool b, bool* res) {
    if (!a and !b) return res[0];
    else if (!a and b) return res[1];
    else if (a and !b) return res[2];
    else return res[3];
}

int main() {
    int w, h;
    bool truth_t[4];
    cin >> w >> h;
    bool **first_t = new bool *[h];
    bool **second_t = new bool *[h];
    for (int i = 0; i < h; i++) {
        first_t[i] = new bool [w];
        second_t[i] = new bool [w];
    }
    char c;
    for (int i = 0; i < h; i++){
        for (int j = 0; j < w; j++) {
            cin >> c;
            first_t[i][j] = (c == '1' ? true : false);
        }
    }
    for (int i = 0; i < h; i++){ 
        for (int j = 0; j < w; j++) {
            cin >> c;
            second_t[i][j] = (c == '1' ? true : false);
        }
    }
    for (int i = 0; i < 4; i++) {
        cin >> c;
        truth_t[i] = (c == '1' ? true : false);
    }
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cout << my_operation(first_t[i][j], second_t[i][j], truth_t);
        }
        if (i < h - 1) cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

bool my_operation (bool a, bool b, bool* res) {

if (!a and !b) return res[0];

else if (!a and b) return res[1];

else if (a and !b) return res[2];

else return res[3];

}

int main() {

int w, h;

bool truth_t[4];

cin >> w >> h;

bool **first_t = new bool *[h];

bool **second_t = new bool *[h];

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

first_t[i] = new bool [w];

second_t[i] = new bool [w];

}

char c;

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

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

cin >> c;

first_t[i][j] = (c == '1' ? true : false);

}

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

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

cin >> c;

second_t[i][j] = (c == '1' ? true : false);

}

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

cin >> c;

truth_t[i] = (c == '1' ? true : false);

}

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

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

cout << my_operation(first_t[i][j], second_t[i][j], truth_t);

}

if (i < h - 1) cout << endl;

}

return 0;

}

Решение

Объявляем два булевых динамических массива под две пиксельные таблицы и один статический для таблицы истинности, вводим входные данные. Затем поочерёдно сравниваем соответствующие элементы массивов с помощью функции my_operation, которая принимает две переменные a и b булевского типа и булев массив res с таблицей истинности, и возвращает соответствующее значение из таблицы для комбинации значений a и b. Результат сравнения выводим.

Ссылки

Одномерный массив
- ideone.com
- e-olymp.com
Двумерный массив
- ideone.com
- e-olymp.com

Related Images:

e-olymp 1753. Младший бит

23/12/2018 by Юлиана Боурош

Задача

Для заданного положительного целого $A$ $(1 \leq A \leq 100),$ вывести младший бит $A$.

Например, если $A = 26$, то его мы можем записать в двоичном виде, как $11010$, и младший бит $A$ есть $10$, и на выходе должно быть $2.$

Другой пример выглядит следующим образом: при $A = 88$, это число $A$ мы можем записать в двоичной форме $1011000$, младший бит в $A$ есть $1000,$ и на выходе должно быть $8.$

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

Каждая строка входных данных содержит только одно целое число $A$ $(1 \leq A \leq 100).$ Строка, содержащая «0» означает конец ввода, и эта строка не является частью входных данных.

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

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

Тесты

	Входные данные	Выходные данные
1	26 88 0	2 8
2	99 45 66 20	1 1 2 4
3	100 0 6	4
4	66 33 98 42 84 39	2 1 2 2 4 1

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

#include <iostream>
using namespace std;

int main() {
    int a;
    while (cin >> a && a != 0) {
        int LSB = 1; // Least Significant Bit
        while ((a & LSB) == 0){
            LSB = LSB << 1;
        }
        cout << LSB << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a;

while (cin >> a && a != 0) {

int LSB = 1; // Least Significant Bit

while ((a & LSB) == 0){

LSB = LSB << 1;

}

cout << LSB << endl;

}

return 0;

}

Решение

Объявляем переменную a. Начинается цикл while, условием окончания которого будет введённая a, неравная нулю. В цикле объявляем переменную LSB = 1, после чего начинается новый цикл while, который сдвигает бит LSB влево, пока выражение побитовой конъюнкции a & LSB нулевое. Соответственно, как только выражение будет ненулевым — будет найден первый общий бит, который и будет младшим битом числа a. Его и выводим.

Ссылки

Related Images:

e-olymp 1151. Кладоискатель

16/12/2018 by Юлиана Боурош

Задача

Юный кладоискатель Рома прошел курс обучения по специальности «кладовое дело», и теперь проходит летнюю практику. Летняя практика проходит близ поселка «Каменные Зори» и длится ровно $b$ дней. Каждый день Рома находит $a$ закопанных в окрестности монет. Таким образом, в конце первого дня у него было $a$ монет, в конце второго — $2a,$ а по окончании практики у Ромы должно накопиться $b\cdot a$ монет.

Если в конце дня ответственный преподаватель замечал, что число Роминых монет делится на $b,$ то Роме разрешалось взять с полки пирожок, который он тут же съедал. Помогите Роме посчитать, сколько пирожков он съест за время прохождения практики.

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

Первая строка входного файла содержит два целых числа $a$ и $b$ ($1 \le a, b \le 10^9$).

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

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

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1 2	1
2	2 2	2
3	10 5	5
4	56000 35	35
5	300 1000000000	100

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

#include <iostream>
using namespace std;
int GCD(int a, int b){
  if (b == 0) return a;
  else return GCD(b, a % b);
}

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

#include <iostream>

using namespace std;

int GCD(int a, int b){

if (b == 0) return a;

else return GCD(b, a % b);

}

int main() {

int a, b;

cin >> a >> b;

cout << GCD(a,b);

return 0;

}

Решение

Нам заданы $a$ и $b$.
Существует 3 случая их отношения между собой:

$a$ кратно $b$. Тогда в последовательности $a, 2a, 3a,\ldots,b \cdot a$ кратным $b$ будет каждый элемент последовательности. То есть количество дней равно $b$. Или НОД от $a$ и $b$, поскольку $a$ кратно $b$.
Существует такое $k, k \in (1; b), k \in N.$ При котором: $k \cdot a$ кратно $b.$ $\frac{ka}{b} = c, c \in N$. Тогда у $b$ и $a$ есть НОД. $(b, a) = p, p > 1, p \in N$. $a = \tilde a \cdot p$, $b = \tilde b \cdot p.$ Тогда в последовательности $a, 2a, 3a,\ldots, b \cdot a$, а кратным $b$ будет каждый $k$-ый элемент данной последовательности. $c = \frac{ka}{b} = \frac{k \cdot \tilde a \cdot p}{\tilde b \cdot p} = \frac{k\tilde a }{\tilde b },$ $k$ обязан равняться $\tilde b $так как $\tilde a $и $\tilde b$ взаимно простые исходя из определения НОД и $c \in N.$ Отсюда $\frac{b}{k} = \frac{\tilde b p}{\tilde b}=p$ — количество кратных элементов последовательности.
Не существует такого $k, k \in (1; b), k \in N$. При котором: $k \cdot a$ кратно $b$. И $a$ не кратно $b.$ Тогда в последовательности $a, 2a, 3a,\dots,b\cdot a$ кратным $b$ будет только последний элемент последовательности. Так как числа взаимно простые, то НОД равен $1.$

Исходя из этих рассуждений решение задачи сводится к нахождению НОД для $a$ и $b.$ Используем рекурсивную реализацию алгоритма Евклида.

Ссылки

Код на ideone.com
Задача на e-olymp.com

Related Images:

e-olymp 6275. Удвоение

02/10/2018 by Юлиана Боурош

Задача

Удвоить каждую цифру заданного трицифрового числа.

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

Трицифровое целое число.

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

Ответ к задаче.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	123	112233
2	564	556644
3	124	112244
4	100	110000
5	202	220022

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

#include <iostream>
using namespace std;

int main() {
    int n , a , b , c;
    cin >> n;
    a = n / 100;
    b = ( n / 10 ) % 10;
    c = n % 10;
    cout << a*110000 + b*1100 + c*11;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n , a , b , c;

cin >> n;

a = n / 100;

b = ( n / 10 ) % 10;

c = n % 10;

cout << a*110000 + b*1100 + c*11;

return 0;

}

Решение

Задаём трёхзначное число n с помощью оператора cin. Разобьём его на цифры, которые сохраним в переменных a, b и c. Тогда для эффекта удвоения цифр числа выведем сумму произведений этих цифр с числами, соответствующих им разрядам, также удвоенными поцифрово (1 → 11, 10 → 1100, 100 → 110000).

Ссылки

e-olymp

ideone.com