OCPC-2021. Задача B. Палиндромонойя (код решения)

20/01/2024 by Александр Мармалюк

Условие

Студент Илья, постоялец палаты номер 101 заведения «Покосившийся Скворечник», попавший сюда во время сессии на почве экзамена по программированию, убеждён, что его повсюду преследуют затаившиеся палиндромы. «Они среди нас! Как же вы этого не замечаете?!» – то и дело слышат от него нянечки Алла и Анна. По убеждению Ильи, палиндром – это слово, читающееся одинаково, как слева направо, так и справа налево. Если же на первый взгляд слово таковым не является, то студент не опускает рук и переносит буквы по одной из начала слова в конец, пока оно не станет палиндромом. Если из слова таким образом удалось получить палиндром за 0 или более операций, Илья называет его затаившимся палиндромом, после чего студент начинает бегать по потолку с воплями отчаяния, чем доставляет неудобства окружающим. Например, Илью может довести до исступления слово «масса», ведь из него можно получить «самас», перенеся 3 буквы из начала в конец. Главврач хочет выкинуть из палаты номер 101 Илью, но вместо этого выкинет все предметы, названия которых являются затаившимися палиндромами. Осталось только проверить их все, а здесь без программы не обойтись!

На ввод поступает строка, содержащая одно слово, длиной от 1 до 100 латинских строчных букв.

Выведите одну строку: «yes» без кавычек, если предмет с этим названием стоит выбросить и «no» без кавычек, если его стоит оставить в палате номер 101.

Тесты

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

array	yes
iliya	no
anna	yes
cbaabcb	yes
arrya	no
anana	yes
bcdcbaa	yes

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

#include <iostream>
#include <string>
using namespace std;
bool palindrome (string const *s) {
    for (int i = 0; i < (*s).size() / 2; ++i) {
        if ((*s)[i] != (*s)[(*s).size() - i - 1]) return false;
    }
    return true;
}
int main() {
    string s;
    cin >> s;
    for (int i = 0; i <= s.length(); i++) {
        s += s[0];
        s.erase(s.begin());
        if (palindrome(&s)) {
            cout << "yes";
            return 0;
        }
    }
    cout << "no";
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

bool palindrome (string const *s) {

for (int i = 0; i < (*s).size() / 2; ++i) {

if ((*s)[i] != (*s)[(*s).size() - i - 1]) return false;

}

return true;

}

int main() {

string s;

cin >> s;

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

s += s[0];

s.erase(s.begin());

if (palindrome(&s)) {

cout << "yes";

return 0;

}

cout << "no";

return 0;

}

Решение №1

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

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

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

int main() {
    string s;
    cin >> s;
    int n = s.length();
    //дублируем строку, чтобы иметь возможность просмотреть все циклические перестановки
    s += s;
    const int p = 31;
    vector <long long> p_pow (2*n); //вектор степеней числа p
    p_pow[0] = 1;
    for (int i = 1; i < 2*n; ++i) p_pow[i] = p * p_pow[i-1];
    long long P1 = 0, P2 = 0;
    for (int i = 0; i < n; ++i) {
        P1 += (s[i] - 'a' + 1) * p_pow[i];
        P2 += (s[n - i - 1] - 'a' + 1) * p_pow[i];
    }
    if (P1 == P2) {
        bool check = true;
        for (int i = 0; i < n; ++i)
            if (s[i] != s[n - i - 1]) check = false;
        if (check) {
            cout << "yes";
            return 0;
        }
    }
    for (int i = 0; i < n; ++i) {
        P1 += (s[i+n] - 'a' + 1)*p_pow[i+n] - (s[i] - 'a' + 1)*p_pow[i];
        P2 = (P2 - (s[i] - 'a' + 1)*p_pow[n + i - 1]) * p_pow[2] + (s[i+n]-'a' + 1) * p_pow[i+1];
        if (P1 == P2) {
            bool check = true;
            for (int j = i + 1; j < i + 1 + n; ++j)
                if (s[j] != s[2*i + 1 + n - j]) check = false;
            if (check) {
                cout << "yes";
                return 0;
            }
        }
    }
    cout << "no";
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

string s;

cin >> s;

int n = s.length();

//дублируем строку, чтобы иметь возможность просмотреть все циклические перестановки

s += s;

const int p = 31;

vector <long long> p_pow (2*n); //вектор степеней числа p

p_pow[0] = 1;

for (int i = 1; i < 2*n; ++i) p_pow[i] = p * p_pow[i-1];

long long P1 = 0, P2 = 0;

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

P1 += (s[i] - 'a' + 1) * p_pow[i];

P2 += (s[n - i - 1] - 'a' + 1) * p_pow[i];

}

if (P1 == P2) {

bool check = true;

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

if (s[i] != s[n - i - 1]) check = false;

if (check) {

cout << "yes";

return 0;

}

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

P1 += (s[i+n] - 'a' + 1)*p_pow[i+n] - (s[i] - 'a' + 1)*p_pow[i];

P2 = (P2 - (s[i] - 'a' + 1)*p_pow[n + i - 1]) * p_pow[2] + (s[i+n]-'a' + 1) * p_pow[i+1];

if (P1 == P2) {

bool check = true;

for (int j = i + 1; j < i + 1 + n; ++j)

if (s[j] != s[2*i + 1 + n - j]) check = false;

if (check) {

cout << "yes";

return 0;

}

cout << "no";

return 0;

}

Решение №2

Для решения задачи можно воспользоваться техникой хеширования строк. Изначально продублируем строку, поскольку тогда все циклические перестановки исходной строки будут подстроками длины $n$ продублированной строки, где $n$ — длина исходной строки.
Можно сначала сравнить хеши исходного слова и «перевернутого» к нему. Далее будем строить значения полиномиальных хешей, умноженных на $p$ в соответствующей степени, всех следующих подстрок длины $n$ и «перевернутых» к ним.
Заметим, что вычислять значение хеша «перевернутой» строки можно без её копирования, поскольку отличается она от «прямой строки только тем, что степени числа $p$ умножаются на преобразованые коды соответствующих символов строки в обратном порядке. Поэтому для вычисления хеша следующей «перевернутой» подстроки надо вычесть из предыдущего значения элемент с наибольшей степенью числа $p$, домножить полученное значение на $ p^2 $, т.к. мы, с одной стороны, решили смещать края подстроки, для которой мы проверяем на палиндром, умножая её хеш на соответствующую степень числа $p$, а с другой — текущая предпоследняя степень должна стать последней (из-за того, что рассматривается перевёрнутая подстрока и новый символ к ней присоединяется «в начало»).

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

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

#include <iostream>
#include <vector>
using namespace std;
int main() {
    string s;
    cin >> s;
    int n = s.length();
    s += s;
    int len = s.length();
    vector <int> d (len);
    int l = 0, r = -1;
    if (n % 2) {
        for (int i = 0; i < len; ++i) {
            d[i] = (i > r)? 1 : min(d[l + r - i], r - i + 1);
            while (i - d[i] >= 0 and i + d[i] < len and s[i - d[i]] == s[i + d[i]])
                d[i]++;
            if (i + d[i] - 1 > r) {
                r = i + d[i] - 1;
                l = i - d[i] + 1;
            }
            if (r - l + 1 >= n) {
                cout << "yes";
                return 0;
            }
        }
    }
    else {
        for (int i = 0; i < len; ++i) {
            d[i] = (i > r)? 0 : min(d[l + r - i + 1], r - i + 1);
            while (i - d[i] - 1 >= 0 and i + d[i] < len and s[i - d[i] - 1] == s[i + d[i]])
                d[i]++;
                if (i + d[i] - 1 > r) {
                    r = i + d[i] - 1;
                    l = i - d[i];
                }
            if (r - l >= n) {
                cout << "yes";
                return 0;
            }
        }
    }
    cout << "no";
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

string s;

cin >> s;

int n = s.length();

s += s;

int len = s.length();

vector <int> d (len);

int l = 0, r = -1;

if (n % 2) {

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

d[i] = (i > r)? 1 : min(d[l + r - i], r - i + 1);

while (i - d[i] >= 0 and i + d[i] < len and s[i - d[i]] == s[i + d[i]])

d[i]++;

if (i + d[i] - 1 > r) {

r = i + d[i] - 1;

l = i - d[i] + 1;

}

if (r - l + 1 >= n) {

cout << "yes";

return 0;

}

else {

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

d[i] = (i > r)? 0 : min(d[l + r - i + 1], r - i + 1);

while (i - d[i] - 1 >= 0 and i + d[i] < len and s[i - d[i] - 1] == s[i + d[i]])

d[i]++;

if (i + d[i] - 1 > r) {

r = i + d[i] - 1;

l = i - d[i];

}

if (r - l >= n) {

cout << "yes";

return 0;

}

cout << "no";

return 0;

}

Решение №3

Для решения задачи можно воспользоваться алгоритмом Манакера. Алгоритм позволяет находить все подпалиндромы строки, поэтому мы снова продублируем строку и будем искать в ней подпалиндром, длина которого равна длине $n$ исходной строки. Заметим, что нам достаточно проверять подпалиндомы, четность длины которых совпадает с четностью $n$. Далее будем сравнивать расстояние между концами $l$ и $r$ текущего палиндрома с $n$ (расстояние между концами может быть и больше $n$, т.к. мы уже определили, что четность этих величин будет совпадать, а если в строке найден подпалиндром длиной $s$, то существуют подпалиндромы и длиной $s-2$, $s-4$, … ).

Решение №1 задачи на ideone.com

Решение №2 задачи на ideone.com

Решение №3 задачи на ideone.com

Ссылка на контест

Related Images:

e-olymp 6253. Репликация вируса

23/12/2020 by Євчук Даяна

Задача

Некоторые вирусы реплицируются путем замены фрагмента ДНК в живой клетке фрагментом ДНК, который вирус несет с собой. Это заставляет клетку создавать вирусы, идентичные оригинальной, зараженной клеткой. Группа биологов заинтересована в том, чтобы узнать, сколько ДНК вносит вирус в геном хозяина. Чтобы узнать об этом, они упорядочили полный геном здоровой клетки, а также идентичную клетку, инфицированную вирусом.

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

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

Состоит из двух строк, содержащих последовательность ДНК до и после вирусной инфекции, соответственно. Последовательность ДНК задается как строка, содержащая от 1 до $10^5$ букв верхнего регистра из алфавита {A, G, C, T}.

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

Выведите одно целое число — минимальную длину ДНК, вставленную вирусом.

Тесты

№	Входные данные	Выходные данные
1	AAAAA AGCGAA	3
2	GTTTGACACACATT GTTTGACCACAT	4
3	SMMSMM SMAHMA	4

Код

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

int main() {
    //Инициализируем массивы, удовлетворяющие условия
    char b[100001], a[100001];
    cin >> b >> a;
    // b-строка до (before), a-строка после (after)
    int s = 0, l1 = strlen(b), l2 = strlen(a), e1 = l1, e2 = l2;
    //определяем длины первой и второй строк, без учёта нуль-символа. 
    
    // Проверяем есть ли символ в массиве b[s], 
    // Если есть и он такой же, как и в массиве a[s] - счётчик увеличивается
    // в результате мы узнаём на каком, крайнем слева, символе начинаются расхождения (s)
    for (; b[s] && b[s] == a[s]; ++s);
    
    // Цикл проходиться по массиву a и b с конца введённых в них строк
    // Цикл двигается по массиву до первого расхождения в буквах (b[e1]!=a[e2])
    // в результате мы узнаём на каком, крайнем справа, символе начинаются расхождения (e2)
    for (; e1>=0 && e2>=0 && b[e1]==a[e2]; --e1, --e2);
    
    // Считаем максимальное количество букв, которые подверглись расхождению, ища максимальное от
    // максимального между 0 и разницей в кол-ве символов второй строки от первой и
    // разницей между крайним правым и крайним левым номером элемента на котором начались расхождения + 1
    cout << max(max(0,l2-l1),e2-s+1) << endl;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

//Инициализируем массивы, удовлетворяющие условия

char b[100001], a[100001];

cin >> b >> a;

// b-строка до (before), a-строка после (after)

int s = 0, l1 = strlen(b), l2 = strlen(a), e1 = l1, e2 = l2;

//определяем длины первой и второй строк, без учёта нуль-символа.

// Проверяем есть ли символ в массиве b[s],

// Если есть и он такой же, как и в массиве a[s] - счётчик увеличивается

// в результате мы узнаём на каком, крайнем слева, символе начинаются расхождения (s)

for (; b[s] && b[s] == a[s]; ++s);

// Цикл проходиться по массиву a и b с конца введённых в них строк

// Цикл двигается по массиву до первого расхождения в буквах (b[e1]!=a[e2])

// в результате мы узнаём на каком, крайнем справа, символе начинаются расхождения (e2)

for (; e1>=0 && e2>=0 && b[e1]==a[e2]; --e1, --e2);

// Считаем максимальное количество букв, которые подверглись расхождению, ища максимальное от

// максимального между 0 и разницей в кол-ве символов второй строки от первой и

// разницей между крайним правым и крайним левым номером элемента на котором начались расхождения + 1

cout << max(max(0,l2-l1),e2-s+1) << endl;

}

Решение

Нам нужно определить длину самой маленькой одной последовательной части ДНК, которая может быть вставлена в первую последовательность, чтобы превратить ее во вторую.

В циклах for мы узнаём крайний слева и справа элемент обоих массивов, на которых буквы первой строки начинают не совпадать с буквами второй, s и e2 соответственно. Чтобы узнать результат необходимо проверить является ли l2 > l1 и больше ли l2-l1 чем e2-s1+1.

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

Related Images:

e-olymp 7824. Без повторений

22/12/2020 by Максим Алексеев

Задача

В натуральном числе $A$ удалили некоторые цифры так, чтобы получить наибольшее натуральное число $B$ с разными цифрами. Какое это число?

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

Натуральное число $x \ (1 \leqslant x \leqslant 10^{100})$.

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

Натуральное число $B$.

Тесты

№	Входные данные	Выходные данные
1	575747	754
2	123231	321
3	314159265359	4192653
4	1092010	9210
5	112221332	213

Код

#include <iostream>
#include <cstring>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    string current_number;
    string ansver = "";
    cin >> current_number;
    set<char> digits_set;    // Инициализируем и заполняем множество со всеми цифрами начального числа
    for (int i = 0; i < current_number.size(); i++){
        char element = current_number[i];
        digits_set.insert(element);
    }
    std::vector<char> digits;
    for (char i : digits_set){
        digits.push_back(i);
    }
    std::reverse(digits.begin(), digits.end());    // Располагаем цифры в порядке убывания
    while (digits.size() != 1){    // Повторяем, пока не нашли все цифры кроме последней
        for (int i=0; i < digits.size(); i++){    // Перебираем цифры в порядке убывания
            char local_max = digits[i];
            int position = current_number.find(local_max);
            string new_number;
            for (int j = position; j < current_number.size(); j++){    // Делаем срез по элементу
                new_number += current_number[j];
            }
            set<char> digits_on_the_right;
            for (int j = 0; j < new_number.size(); j++){    // Находим цифры нового числа
                digits_on_the_right.insert(new_number[j]);
            }
            if (digits.size() == digits_on_the_right.size()){    // Проверяем, сохранится ли ранг ответа
                ansver += local_max;
                digits.erase(digits.begin() + i);
                string number_without_digit = "";
                for (int t = 0; t < new_number.size(); t++){    // Удаляем добавленную в ответ цифру из числа
                    if (new_number[t] != local_max){
                        number_without_digit += new_number[t];
                    }
                }
                current_number = number_without_digit;
                break;    // Останавливаем цикл, т.к. необходимая цифра на позицию уже найдена
            }
        }
    }
    cout << ansver + digits[0];    // Добавляем к ответу последнюю оставшуюся цифру
    return 0;
}

#include <iostream>

#include <cstring>

#include <set>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

string current_number;

string ansver = "";

cin >> current_number;

set<char> digits_set; // Инициализируем и заполняем множество со всеми цифрами начального числа

for (int i = 0; i < current_number.size(); i++){

char element = current_number[i];

digits_set.insert(element);

}

std::vector<char> digits;

for (char i : digits_set){

digits.push_back(i);

}

std::reverse(digits.begin(), digits.end()); // Располагаем цифры в порядке убывания

while (digits.size() != 1){ // Повторяем, пока не нашли все цифры кроме последней

for (int i=0; i < digits.size(); i++){ // Перебираем цифры в порядке убывания

char local_max = digits[i];

int position = current_number.find(local_max);

string new_number;

for (int j = position; j < current_number.size(); j++){ // Делаем срез по элементу

new_number += current_number[j];

}

set<char> digits_on_the_right;

for (int j = 0; j < new_number.size(); j++){ // Находим цифры нового числа

digits_on_the_right.insert(new_number[j]);

}

if (digits.size() == digits_on_the_right.size()){ // Проверяем, сохранится ли ранг ответа

ansver += local_max;

digits.erase(digits.begin() + i);

string number_without_digit = "";

for (int t = 0; t < new_number.size(); t++){ // Удаляем добавленную в ответ цифру из числа

if (new_number[t] != local_max){

number_without_digit += new_number[t];

}

current_number = number_without_digit;

break; // Останавливаем цикл, т.к. необходимая цифра на позицию уже найдена

}

cout << ansver + digits[0]; // Добавляем к ответу последнюю оставшуюся цифру

return 0;

}

Нажмите здесь, чтобы выполнить этот код.

Решение

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

Рассмотрим пример: для числа $121323$ правильным ответом будет $213$.

Ход рассуждений следующий: поскольку в числе содержатся три цифры, ответ также будет трехзначным. Наибольшая цифра в числе — 3, следовательно, она должна быть первой цифрой ответа. Для выполнения этого условия придется «вычеркнуть» все предыдущие цифры, но тогда мы сможем получить лишь двухзначное число $32$. Следующим кандидатом является двойка, и этот выбор нас полностью устраивает, поскольку справа от нее есть остальные цифры «входного» числа. Записав в ответ $2$, рассмотрим число за ней: $1323$. Мы можем видеть, что двойка повторяется, однако в ответе ее быть уже не может по условию задачи. Отбросим ее за ненадобностью и рассмотрим получившееся число $133$. Для полученного числа нам необходимо выполнить те же операции, что и для предыдущего, а значит, мы столкнулись с задачей на динамическое программирование (о чем нам, правда, уже заботливо сообщил e-olymp прямо под условием). Рассуждения аналогичны: взять $3$ мы не можем, поскольку это вынудит нас отбросить $1$, что в результате даст нам число $23$, то есть даже меньшее, чем то, что мы получали в начале. Следовательно, добавляем к ответу $1$. Последнюю оставшуюся цифру можно сразу добавлять к ответу, поскольку сравнивать ее не с чем. Получаем искомый ответ — $213$.

Как и оговаривалось вначале, работать будем со строчным представлением числа. До объявления цикла в строке 22 выполняются подготовительные процедуры: создается множество с целью определения цифр, составляющих число, а затем массив, в который помещаются элементы множества в порядке убывания. В теле цикла проходим по всем элементам массива, пока не находим такой, справа от которого будут все остальные элементы. Здесь важно отметить две вещи: во-первых, меня не интересуют сами цифры, имеет значение лишь их количество в соответствующих множествах; во-вторых, поскольку справа от элемента могут находится ему идентичные, включаем его в срез строки и проверяем, можно ли опустить левую часть числа без ущерба количеству цифр в нем. Если да, то этот элемент добавляется в ответ и извлекается из массива для следующего прохода, а если нет — программа переходит к следующему по старшинству элементу.

Ссылки

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

Related Images:

e-olymp 8851. Число навпаки

15/02/2020 by Нина Хоробрых

Умова задачі

Записати чотиризначне натуральне число в зворотному порядку.

Вхідні дані

Задане чотиризначне натуральне число.

Вихідні дані

Відповідь до задачі.

Тести

№	Входные данные	Выходные данные
1	1234	4321
2	1984	4891

Розвязок №1

#include <iostream>
using namespace std;

int main() {
    int num, a, b, c, d;
    cin >> num;
    a = num % 10;
    b = num / 10 % 10;
    c = num / 100 % 10;
    d = num / 1000;
    cout << a << b << c << d;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int num, a, b, c, d;

cin >> num;

a = num % 10;

b = num / 10 % 10;

c = num / 100 % 10;

d = num / 1000;

cout << a << b << c << d;

return 0;

}

Для отримання потрібного числа, відділимо кожну цифру та привласнемо до неї змінну. Виводимо у потрібному порядку.

Розвязок №2

#include <iostream>
using namespace std;
 
int main() {
    string num;
    cin >> num;
    for (int i = 3; i >= 0; i-- )  {
        cout << num[i];
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

string num;

cin >> num;

for (int i = 3; i >= 0; i-- ) {

cout << num[i];

}

return 0;

}

Представимо вводиме число як строку. Виводимо у циклі від третього до останньго елемента.

Посилання

Задача на e-olymp
Зарахований розв’язок №1
Зарахований розв’язок №2
Код на ideone №1
Код на ideone №2

Related Images:

e-olymp 9531. Комплексные числа: сложение и вычитание

20/12/2019 by Никита Гербали

Условие

Даны два комплексных числа. Найдите их сумму или разность.

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

В каждой строке задан пример на сложение или вычитание комплексных чисел. Комплексное число задается в формате $a+bi$ или $a-bi$, где $a$ целое, $b$ целое неотрицательное. Действительная и мнимая часть каждого комплексного числа по модулю не превышает $10^{9}$.

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

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

Тесты

№	Входные данные	Выходные данные
1	2+3i + 7-4i	9-1i
2	-1-1i — -1-1i	0+0i
3	56743+876i — 1234-124i	55509+1000i
4	331+10i — 331+10i	0+0i

Код

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

struct complex_number {  //создадим структуру комплексных чисел
    int real;
    int imagine;
};

complex_number convert(string term) {
    complex_number x;
    x.real = 1;  //чтобы не вводить отдельные переменные для знака присвоим начальное значение не 0, а 1
    x.imagine = 1;
    if (term[0] == '-') {  //если нулевой символ минус, то меняем значение действительной части на -1;
        x.real *= -1;
        term.erase(term.begin(), term.begin() + 1);  //удаляем минус на нулевой позиции, если он есть, чтобы было легче найти второй знак
    }
    int index = term.find('+');  //находим индекс знака, если это плюс
    if (index == -1) {
        index = term.find('-');  //находим индекс знака, если это минус
        x.imagine = -1;  //меняем значение мнимой части на -1, если второй знак минус
    }
    x.real *= atoi(&term.substr(0, index)[0]);  //находим действительную часть
    x.imagine *= atoi(&term.substr(index + 1, term.size() - 2)[0]);  //находим мнимую часть
    return x;  //возвращаем полученное комплексное число
}

int main() {
    string term1, term2;
    char sign;
    complex_number convert_term1, convert_term2;
    while (cin >> term1 >> sign >> term2) {
        convert_term1 = convert(term1);  //переводим первую строку в первое слагаемое
        convert_term2 = convert(term2);  //переводим вторую строку во второе слагаемое
        if (sign == '+') { //выполняем действие соответствующее считанному знаку
            convert_term1.real += convert_term2.real;
            convert_term1.imagine += convert_term2.imagine;
        }
        else {
            convert_term1.real -= convert_term2.real;
            convert_term1.imagine -= convert_term2.imagine;
        }  //если мнимая часть отрицательная, то минус между мнимой и действительной частями выведется сам, а если она положительная, то мы должны вывести плюс вручную
        cout << convert_term1.real << (convert_term1.imagine >= 0 ? "+" : "") << convert_term1.imagine << "i" << endl;
    }
}

#include <iostream>

#include <string>

using namespace std;

struct complex_number { //создадим структуру комплексных чисел

int real;

int imagine;

};

complex_number convert(string term) {

complex_number x;

x.real = 1; //чтобы не вводить отдельные переменные для знака присвоим начальное значение не 0, а 1

x.imagine = 1;

if (term[0] == '-') { //если нулевой символ минус, то меняем значение действительной части на -1;

x.real *= -1;

term.erase(term.begin(), term.begin() + 1); //удаляем минус на нулевой позиции, если он есть, чтобы было легче найти второй знак

}

int index = term.find('+'); //находим индекс знака, если это плюс

if (index == -1) {

index = term.find('-'); //находим индекс знака, если это минус

x.imagine = -1; //меняем значение мнимой части на -1, если второй знак минус

}

x.real *= atoi(&term.substr(0, index)[0]); //находим действительную часть

x.imagine *= atoi(&term.substr(index + 1, term.size() - 2)[0]); //находим мнимую часть

return x; //возвращаем полученное комплексное число

}

int main() {

string term1, term2;

char sign;

complex_number convert_term1, convert_term2;

while (cin >> term1 >> sign >> term2) {

convert_term1 = convert(term1); //переводим первую строку в первое слагаемое

convert_term2 = convert(term2); //переводим вторую строку во второе слагаемое

if (sign == '+') { //выполняем действие соответствующее считанному знаку

convert_term1.real += convert_term2.real;

convert_term1.imagine += convert_term2.imagine;

}

else {

convert_term1.real -= convert_term2.real;

convert_term1.imagine -= convert_term2.imagine;

} //если мнимая часть отрицательная, то минус между мнимой и действительной частями выведется сам, а если она положительная, то мы должны вывести плюс вручную

cout << convert_term1.real << (convert_term1.imagine >= 0 ? "+" : "") << convert_term1.imagine << "i" << endl;

}

Решение

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

После перевода обеих введённых строк в структуру, останется только выполнить сложение или вычитание соответствующих элементов этих структур.

Ссылки

E-olymp

Ideone

Related Images:

e-olymp 9407. Слияние строк

18/12/2019 by Даниил Кулык

Задача

Имеются две строки $A$ и $B$.

Ваша задача — найти такую строку $C$, которая содержит в себе и $A$ и $B$ в качестве подстрок и является кратчайшей среди всех таких возможных строк.

Подстрокой строки называется последовательно идущая подпоследовательность этой строки. Например, строка $kbtu$ является подстрокой строки $kbtu open$, но строка $fall$ подстрокой не является.

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

Первая строка содержит строку $A$ $(1 \leqslant |A| \leqslant 10^5)$.

Вторая строка содержит строку $B$ $(1 \leqslant |B| \leqslant 10^5)$.

Гарантируется, что обе строки содержат только строчные латинские буквы.

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

Выведите одну строку $C$.

Тесты

№	Входные данные	Выходные данные
1.	compressing single	compressingle
2.	can you	canyou
3.	compressiondoneright doner	compressiondoneright
4.	details tail	details
5.	essential code	essentialcode

Код

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

int main() 
{
    int n, m, z;
    string a, b, c, d;
    cin>>a; // Вводим строку A
    cin>>b; // Вводим строку B
    d = b; // Строку B будем хранить в переменной d
    n = b.length(); // В переменной n храним длину строки B
    m = a.length(); // В переменной m храним длину строки A
    c = a.substr(m - n, n); // Создаём подстроку
    if(a.find(b) == EOF) // Ищем в строке A строку B
    {
        for (int i = 1; i<=n && b != c; i++) // Удаляем символы в конце первой строки и начале второй, пока они не будут равны
        {
            b.erase(n - i,1);  
            c.erase(0, 1);
        }
        z = c.length(); // В переменной z храним длину подстроки
        d.erase(0,z); // Удаляем из строки B элементы подстроки
        cout << a + d; // Выводим такую строку, которая содержит в себе и A и B
    }
    else cout << a; // Выводим строку A
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main()

{

int n, m, z;

string a, b, c, d;

cin>>a; // Вводим строку A

cin>>b; // Вводим строку B

d = b; // Строку B будем хранить в переменной d

n = b.length(); // В переменной n храним длину строки B

m = a.length(); // В переменной m храним длину строки A

c = a.substr(m - n, n); // Создаём подстроку

if(a.find(b) == EOF) // Ищем в строке A строку B

{

for (int i = 1; i<=n && b != c; i++) // Удаляем символы в конце первой строки и начале второй, пока они не будут равны

{

b.erase(n - i,1);

c.erase(0, 1);

}

z = c.length(); // В переменной z храним длину подстроки

d.erase(0,z); // Удаляем из строки B элементы подстроки

cout << a + d; // Выводим такую строку, которая содержит в себе и A и B

}

else cout << a; // Выводим строку A

return 0;

}

Решение

В данной задаче необходимо создать строку $C$, которая будет содержать в себе строки $A$ и $B$. Рассмотрим два варианта решения задачи. Первый – если строка $B$ полностью содержится в строке $A$, то выводим строку $A$. Второй – если строка $B$ содержится в $A$ частично или не содержится вообще, выводим строку $A$ $+$ элементы строки $B$, которых нет в $A$.

Для проверки, находится ли строка $B$ в $A$, воспользуемся функцией find(). Если попадаем в первый вариант решения задачи, то выводим $A$. Иначе, создаём цикл, который будет удалять символы в конце первой строки и символы в начале второй, пока они не будут равны. Затем из строки $B$ удаляем элементы, которые входят в строку $A$, и на выход подаём строку $C$, которая состоит из строки $A$ и оставшихся элементов строки $B$.

Ссылки

Условие задачи на e-olymp
Код программы на ideone.com
Засчитанное решение на e-olymp

Related Images:

e-olymp 6260. Организация соревнования

12/12/2019 by Александр Шкафер

Задача

Маленькие Дима и Петя хотят организовать соревнование. Их маленькие друзья выслали им несколько задач. Теперь Дима и Петя должны выбрать несколько задач для соревнования. Поскольку они еще маленькие, то не могут оценить качество задач, однако они знают что в хорошем контесте заглавия первой задачи начинаются с буквы $ A $ , заглавия второй задачи — с буквы $ B $ и так далее.

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

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

Первая строка содержит одно число $ n $ — количество предложенных задач, полученных маленькими братьями [latex](1 \leqslant n \leqslant 100)[/latex]

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

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

Вывести одно число — наибольшее возможное количество задач в хорошем соревновании. Если хорошего соревнования устроить нельзя, вывести $0$.

Тесты

№	Входные данные	Выходные данные
1.	10 Use Algorithm_of Branch Chill Cout_Hello_World General Duck Ping_pong Pong_ping End	5
2.	4 Spasibo_tebe John_von_Neumann Za Nuli_i_edunichki	0
3.	6 All Sample Simple Games_of_mind Google Bee	2
4.	7 Andreev_Borys Borys_Andreev C_P_P Demo_version E_Olymp Fraction General	7

Код

#include <iostream>
using namespace std;
 
int m[26];
 
int main() {
    int n;
    cin >> n;
    string s;
    for (int j = 0; j <= n; j++) {
        getline(cin, s);
        m[int(s[0] - 'A')]++; // от первой буквы названий задач отнимаем А, чтобы получить её номер в алфавите
    }
    int k = 0;
    for (int i = 0; i < 26; i++) { 
        if (m[i] != 0) k++;
        if (m[i] == 0) break;
    }
    cout << k;
    return 0;
}

#include <iostream>

using namespace std;

int m[26];

int main() {

int n;

cin >> n;

string s;

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

getline(cin, s);

m[int(s[0] - 'A')]++; // от первой буквы названий задач отнимаем А, чтобы получить её номер в алфавите

}

int k = 0;

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

if (m[i] != 0) k++;

if (m[i] == 0) break;

}

cout << k;

return 0;

}

Объяснение

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

Алгоритм решения задачи:

Создаем массив.
Читаем строку циклом и определяем первую букву.
Кладем первую букву в массив, если разница отлична от нуля.

Ссылки

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

Related Images:

e-olymp 1344. Личные дела

20/06/2019 by Михаил Бутник

Задача

Однажды, неловкая секретарша перепутала личные дела учащихся. Теперь их снова необходимо упорядочить сначала по классам, а внутри класса по фамилиям.

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

В первой строке дано число $N \left(1 \leqslant N \leqslant 1000\right)$ – количество личных дел. Далее для каждого из $N$ учащихся следующие данные (каждое в своей строке): фамилия и имя, класс, дата рождения. Фамилия и имя – строки не более чем из $20$ символов, класс – строка состоящая из числа (от $1$ до $11$) и латинской буквы (от «A» до «Z»), дата рождения – дата в формате «ДД.ММ.ГГ». Гарантируется, что внутри одного класса нет однофамильцев.

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

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

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	3 Sidorov Sidor 9A 20.07.93 Petrov Petr 10B 23.10.92 Ivanov Ivan 9A 10.04.93	9A Ivanov Ivan 10.04.93 9A Sidorov Sidor 20.07.93 10B Petrov Petr 23.10.92
2	4 Petrov Sidor 9A 20.07.02 Sidorov Petr 10B 23.10.01 Ivanov Bogdan 9A 10.04.02 Tereshkova Olga 9B 17.08.02	9A Ivanov Bogdan 10.04.02 9A Petrov Sidor 20.07.02 9B Tereshkova Olga 17.08.02 10B Sidorov Petr 23.10.01
3	2 Borisevich Sidor 9A 20.03.02 Burkalo Petr 9A 23.12.01	9A Borisevich Sidor 20.03.02 9A Burkalo Petr 23.12.01
4	1 Zadorozhniy Pavel 11A 20.03.02	11A Zadorozhniy Pavel 20.03.02

Код 1

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

struct student {
    string name, surname;
    char letter;
    int Class;
    string date;
};

bool operator > (const student &a, const student &b) {
    bool res = false;
    if (a.Class > b.Class) res = true;
    else if (a.Class == b.Class) {
        if (a.letter > b.letter) res = true;
        else if (a.letter == b.letter) {
            if (a.surname > b.surname) res = true;
        }
    }
    return res;
};

int main() {
    int n;
    cin >> n;
    student *a = new student[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i].surname >> a[i].name >> a[i].Class >> a[i].letter >> a[i].date;
    }
    for (int k = 2; k <= n; k++) {
        for (int i = 0; i <= n - k; i++) {
            if (a[i] > a[i + 1]) {
                swap(a[i], a[i + 1]);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cout << a[i].Class << a[i].letter << " " << a[i].surname << " " << a[i].name << " " << a[i].date << endl;
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

struct student {

string name, surname;

char letter;

int Class;

string date;

};

bool operator > (const student &a, const student &b) {

bool res = false;

if (a.Class > b.Class) res = true;

else if (a.Class == b.Class) {

if (a.letter > b.letter) res = true;

else if (a.letter == b.letter) {

if (a.surname > b.surname) res = true;

}

return res;

};

int main() {

int n;

cin >> n;

student *a = new student[n];

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

cin >> a[i].surname >> a[i].name >> a[i].Class >> a[i].letter >> a[i].date;

}

for (int k = 2; k <= n; k++) {

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

if (a[i] > a[i + 1]) {

swap(a[i], a[i + 1]);

}

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

cout << a[i].Class << a[i].letter << " " << a[i].surname << " " << a[i].name << " " << a[i].date << endl;

}

return 0;

}

Код 2

#include <iostream>
using namespace std;
 
struct student {
  char name[21];
  char surname[21];
  char letter;
  int Class;
  char date[9];
};
 
bool operator > (const student & a,
  const student & b) {
  bool res = false;
  bool tmp = true;
  if (a.Class > b.Class) res = true;
  else if (a.Class == b.Class) {
    if (a.letter > b.letter) res = true;
    else if (a.letter == b.letter) {
      for (int i = 0; i < 21; i++) {
        if (a.surname[i] < b.surname[i]) {
          tmp = false;
          break;
        } else if (a.surname[i] > b.surname[i]) {
          tmp = true;
          break;
        }
      }
      if (tmp) res = true;
    }
  }
  return res;
};
 
int main() {
  int n;
  cin >> n;
  student *a = new student[n];
  for (int i = 0; i < n; i++) {
    cin >> a[i].surname >> a[i].name >> a[i].Class >> a[i].letter >> a[i].date;
  }
  for (int k = 2; k <= n; k++) {
    for (int i = 0; i <= n - k; i++) {
      if (a[i] > a[i + 1]) {
        swap(a[i], a[i + 1]);
      }
    }
  }
  for (int i = 0; i < n; i++) {
    cout << a[i].Class << a[i].letter << " " << a[i].surname << " " << a[i].name << " " << a[i].date << endl;
  }
  return 0;
}

#include <iostream>

using namespace std;

struct student {

char name[21];

char surname[21];

char letter;

int Class;

char date[9];

};

bool operator > (const student & a,

const student & b) {

bool res = false;

bool tmp = true;

if (a.Class > b.Class) res = true;

else if (a.Class == b.Class) {

if (a.letter > b.letter) res = true;

else if (a.letter == b.letter) {

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

if (a.surname[i] < b.surname[i]) {

tmp = false;

break;

} else if (a.surname[i] > b.surname[i]) {

tmp = true;

break;

}

if (tmp) res = true;

}

return res;

};

int main() {

int n;

cin >> n;

student *a = new student[n];

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

cin >> a[i].surname >> a[i].name >> a[i].Class >> a[i].letter >> a[i].date;

}

for (int k = 2; k <= n; k++) {

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

if (a[i] > a[i + 1]) {

swap(a[i], a[i + 1]);

}

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

cout << a[i].Class << a[i].letter << " " << a[i].surname << " " << a[i].name << " " << a[i].date << endl;

}

return 0;

}

Решение

Для решения этой задачи напишем структуру student, в которой каждый элемент будет охарактеризован именем, фамилией, номером и буквой класса, а также датой рождения. Затем определим оператор >, которым будем сравнивать личные дела учащихся по номеру и букве класса, а также по фамилии. Сравнение по имени нам не нужно, так как в условии сказано, что в одном классе однофамильцев не будет. Введём всю информацию, что нам дана и в цикле сравним все личные дела учащихся с помощью этого оператора, при этом меняя личные дела местами при помощи функции swap, если это необходимо. Затем также в цикле выведем в правильном порядке личные дела в заданном виде.

Запустить код 1 (ideone) можно здесь
Запустить код 2 (ideone) можно здесь
Задача на E-olymp

Related Images:

e-olymp 2496. Конкатенация строк

23/05/2019 by Анна Неделева

Задача

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

В результате разворота строки $s$ получается строка $sR$, которая состоит из тех же символов, что и $s$, но идущих в обратном порядке. Например, в результате разворота строки «$abcde$» получается строка «$edcba$». Далее в этой задаче вместо обозначения $sR$ будет использоваться обозначение ($s$).

В результате конкатенации двух строк $s$ и $t$ получается строка $st$, в которой сначала записаны символы строки $s$, а затем — символы строки $t$. Аналогичным образом определяется конкатенация трех, четырех и большего числа строк. Например, при конкатенации строк «$abc$» и «$cda$» получается строка «$abccda$».

Ваша задача — определить результат конкатенации нескольких строк, часть из которых необходимо развернуть.

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

Состоит из единственной строки, которая содержит только строчные буквы латинского алфавита и круглые скобки. Ее длина не превышает $200$ символов. Эта строка описывает конкатенацию нескольких строк, часть из которых необходимо развернуть.

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

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

Выведите результат конкатенации.

Тесты

№	Входные данные	Выходные данные
1	russ(ai)(edocn)cup	russiancodecup
2	(bi).mazurok	ib.mazurok
3	acm.(cpci)	acm.icpc
4	Od(asse)	Odessa
5	(inu)ver(ytis)	university

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

#include <iostream>
using namespace std;

void revers(string & str) {
  char a;
  cin.get(a);
  if (a != ')') revers(str);
  else return;
  str += a;
}

int main() {
  string str = "";
  char a;
  while (cin.get(a))
    if (a == '(') revers(str);
    else str += a;
  cout << str;
  return 0;
}

#include <iostream>

using namespace std;

void revers(string & str) {

char a;

cin.get(a);

if (a != ')') revers(str);

else return;

str += a;

}

int main() {

string str = "";

char a;

while (cin.get(a))

if (a == '(') revers(str);

else str += a;

cout << str;

return 0;

}

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

#include <iostream>
using namespace std;

const int N = 200;

void revers(char * res, int &n) {
   char a;
   cin >> a;
   if (a == ')') return;
   else revers(res, n);
   res[n++] = a;
}

int main() {
   char res[N];
   char a;
   int n = 0;
   while (cin >> a) {
      if (a == '(') revers(res, n);
      else res[n++] = a;
   }
   for (int i = 0; i < n; i++)
      cout << res[i];
   return 0;
}

#include <iostream>

using namespace std;

const int N = 200;

void revers(char * res, int &n) {

char a;

cin >> a;

if (a == ')') return;

else revers(res, n);

res[n++] = a;

}

int main() {

char res[N];

char a;

int n = 0;

while (cin >> a) {

if (a == '(') revers(res, n);

else res[n++] = a;

}

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

cout << res[i];

return 0;

}

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

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

Ссылки

Related Images:

e-olymp 909. Количество слов

29/04/2019 by Яна Юрковская

Задача

Определить количество слов в заданном фрагменте текста.

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

В одной строке задан фрагмент текста на английском языке, количество символов в котором не превышает 250. Гарантируется, что в тексте отсутствуют тире, дефисы, цифры и числа.

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

Вывести количество слов в фрагменте текста.

Тесты

№	Ввод	Вывод
1	Hello world!	2
2	Hello world! Hello, country!	4
3	What do you think?..	4
4	How are you?	3
5	Alice was beginning to get very tired of sitting by her sister on the bank, and of having nothing to do: once or twice she had peeped into the book her sister was reading, but it had no pictures or conversations in it.	43

Код. Вариант 1

#include <iostream>
using namespace std;

int main() {
    string s;
    int count = 0;
    while (cin >> s) count++;
    cout << count;
}

#include <iostream>

using namespace std;

int main() {

string s;

int count = 0;

while (cin >> s) count++;

cout << count;

}

Код. Вариант 2

#include <iostream> 
using namespace std;

int main() {
    char *word = new char[251];
    int count = 0;
    while(cin >> word) count++;
    cout << count;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

char *word = new char[251];

int count = 0;

while(cin >> word) count++;

cout << count;

return 0;

}

Решение

Считаем текст до пробела как слово. При помощи цикла while считываем по слову пока в потоке есть текст. И подсчитываем количество слов, используя счётчик count.

Ссылки

Related Images:

e-olymp 1114. Символьные узоры на ткани

22/03/2019 by Николь Метри

Задача

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

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

В единой строке входного файла задано сначала символ узора S, затем через пробелы [latex]3[/latex] натуральных числа: ширина узора [latex]w[/latex] [latex](w < 80)[/latex], его высота [latex]h[/latex] [latex](h <= 40)[/latex] и повторяемость [latex]t[/latex] [latex](t <= 40)[/latex]. В примере выходных данных пробелы для наглядности заменены на точки.

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

Вывести требуемый узор.

Тесты

№	Ввод	Вывод
1	W 7 9 1	WWWWWWW .W.W.W.W ..WWWWWWW …W.W.W.W ….WWWWWWW …W.W.W.W ..WWWWWWW .W.W.W.W WWWWWWW
2	E 9 6 2	EEEEEEEEE .E.E.E.E.E ..EEEEEEEEE ..E.E.E.E.E .EEEEEEEEE E.E.E.E.E .EEEEEEEEE ..E.E.E.E.E ..EEEEEEEEE .E.E.E.E.E EEEEEEEEE
3	D 2 2 2	DD D DD
4	N 9 6 3	NNNNNNNNN .N.N.N.N.N ..NNNNNNNNN ..N.N.N.N.N .NNNNNNNNN N.N.N.N.N .NNNNNNNNN .N.N.N.N.N ..NNNNNNNNN .N.N.N.N.N NNNNNNNNN .N.N.N.N.N ..NNNNNNNNN ..N.N.N.N.N .NNNNNNNNN N.N.N.N.N
5	K 7 11 2	KKKKKKK .K.K.K.K ..KKKKKKK …K.K.K.K ….KKKKKKK …..K.K.K.K ….KKKKKKK …K.K.K.K ..KKKKKKK .K.K.K.K KKKKKKK .K.K.K.K ..KKKKKKK …K.K.K.K ….KKKKKKK …..K.K.K.K ….KKKKKKK …K.K.K.K ..KKKKKKK .K.K.K.K KKKKKKK

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

#include <iostream>
#include <string>

using namespace std;

int main() {
    char S;
    cin >> S;
    int w, h, t; 
    cin >> w >> h >> t;
    string line_1(w, S); // строка без пробелов, каждая нечетная 
    int times; 
    times = (t * h) - (t - 1);// количество строк узора
    int num = 0; // количество пробелов перед строкой
    bool flag = true; // необходим для контроля уменьшения и увеличения числа 
    //пробелов перед четными строками;
    for (int i = 1; i <=times; i++) {
        if(num < 0) num = 0;
        string tmp(num, ' '); //подстрока с пробелами
        cout << tmp;
        if (i % 2) cout << line_1;//вывод нечетной строки
        else {
            for (int q = 0; q < w / 2 + w % 2; q++) {
                cout << S;
                if (q != w / 2 + w % 2 - 1) cout << " ";
            }// вывод символов, чередующихся пробелами в четной строке
        }
        if (!flag) num--;
        else num++;
        if (num == h / 2) flag = false;
        if (num == 0) flag = true;
        if (num == h / 2 && h % 2 == 0) num--;//данное действие необходимо для
        //того, чтобы у "серединных" двух строк при четной высоте было одинаковое 
        //число пробелов
        if (i != times) cout << endl;
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

char S;

cin >> S;

int w, h, t;

cin >> w >> h >> t;

string line_1(w, S); // строка без пробелов, каждая нечетная

int times;

times = (t * h) - (t - 1);// количество строк узора

int num = 0; // количество пробелов перед строкой

bool flag = true; // необходим для контроля уменьшения и увеличения числа

//пробелов перед четными строками;

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

if(num < 0) num = 0;

string tmp(num, ' '); //подстрока с пробелами

cout << tmp;

if (i % 2) cout << line_1;//вывод нечетной строки

else {

for (int q = 0; q < w / 2 + w % 2; q++) {

cout << S;

if (q != w / 2 + w % 2 - 1) cout << " ";

}// вывод символов, чередующихся пробелами в четной строке

}

if (!flag) num--;

else num++;

if (num == h / 2) flag = false;

if (num == 0) flag = true;

if (num == h / 2 && h % 2 == 0) num--;//данное действие необходимо для

//того, чтобы у "серединных" двух строк при четной высоте было одинаковое

//число пробелов

if (i != times) cout << endl;

}

return 0;

}

Либо так:

#include <iostream>
using namespace std;

int main() {
    char S;
    cin >> S;
    int w, h, t; 
    cin >> w >> h >> t;
    char *s1 = new char[w];
    for (int i = 0; i < w; i++) s1[i] = S;
    int times; 
    times = (t * h) - (t - 1);
    int num = 0; 
    bool flag = true;
    char *tmp;
    for (int i = 1; i <=times; i++) {
        if(num < 0) num = 0;
        tmp = new char [num];
        for (int i = 0; i < num; i++) tmp[i] = ' ';
        cout << tmp;
        if (i % 2) cout << s1;
        else {
            for (int q = 0; q < w / 2 + w % 2; q++) {
                cout << S;
                if (q != w / 2 + w % 2 - 1) cout << " ";
            }
        }
        if (!flag) num--;
        else num++;
        if (num == h / 2) flag = false;
        if (num == 0) flag = true;
        if (num == h / 2 && h % 2 == 0) num--;
        if (i != times) cout << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

char S;

cin >> S;

int w, h, t;

cin >> w >> h >> t;

char *s1 = new char[w];

for (int i = 0; i < w; i++) s1[i] = S;

int times;

times = (t * h) - (t - 1);

int num = 0;

bool flag = true;

char *tmp;

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

if(num < 0) num = 0;

tmp = new char [num];

for (int i = 0; i < num; i++) tmp[i] = ' ';

cout << tmp;

if (i % 2) cout << s1;

else {

for (int q = 0; q < w / 2 + w % 2; q++) {

cout << S;

if (q != w / 2 + w % 2 - 1) cout << " ";

}

if (!flag) num--;

else num++;

if (num == h / 2) flag = false;

if (num == 0) flag = true;

if (num == h / 2 && h % 2 == 0) num--;

if (i != times) cout << endl;

}

return 0;

}

Решение

Считываем все входные данные. Создаём строку из [latex]w[/latex] символов, идущих подряд — из неё и пробелов будет состоять каждая нечётная строка. Далее заводим 3 переменные: times, num и flag. Предназначение каждой описано в комментариях в коде решения. После в цикле необходимо вывести узор, чередуя строки, в которых символы идут подряд и с пробелами. Перед каждой подстрокой с символами выводится подстрока с пробелами tmp. Число пробелов регулируется уже упомянутыми переменными num и flag. От нулевой строки до середины flag имеет значение true и num увеличивается с каждым проходом цикла на единицу, с середины до нуля — наоборот. При этом для того, чтобы узор с чётной высотой не шел полностью «ёлочкой» создаём условие, при котором по достижению середины количество дважды уменьшится.

Ссылки

Related Images:

Анаграммы

26/11/2018 by Иван Киреев

Анаграммы

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

После того как он закончил выписывать все перестановки Игорь устал и пошел учиться. Он взял словарь и начал учить новые слова. Через некоторое время Игорь заметил что некоторые из слов в словаре совпадают с записанными им перестановками на листке и задался вопросом, — а какие можно получить слова переставляя буквы из других в словаре.

Игоря будут интересовать только слова которые записаны в словаре, так как других он не знает.

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

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

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

Задан словарь английских слов. Каждое слово в новой строке. Длинна слова не более $255$ символов. Количество слов любое.

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

Вывести все слова что имеют максимальное количество анаграмм в нем.

Решение

Прочитаем словарь. Запишем в структуру pair строку с исходным словом в first и отсортированную в second. Анаграммами будут являться слова с одинаковыми second строками. Так как они будут состоять из одних и тех же букв, которые выстроены в одинаковом порядке. Отсортируем множество слов из словаря по second. Таким образом все слова анаграммы будут находиться рядом.

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

На выходе получим массив индексов слов у которых существует максимальное количество анаграмм, в данном словаре. Выведем эти слова и все анаграммы к ним в исходном варианте. Для этого нам и нужна строка first.

Тесты

№

Ввод

Вывод

2500 слов английского языка

trace react crate

dear dare read

post stop spot

Код

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#define DIFFERENCE ('A' - 'a') // разность регистров
using namespace std;
bool IsBigAlpha(char a) {
	return (a >= 'A' && a <= 'Z');
}
bool IsSmalAlpha(char a) {
	return (a >= 'a' && a <= 'z');
}
string edit(const string &str) { // приводим всё к нижнему регистру и  убираем лишние символы
	string rez = "";
	for(char a : str) {
		if (IsBigAlpha(a)) a -= DIFERENSE;
		if (IsSmalAlpha(a)) rez += a;
	}
	return rez;
}
bool comp(const pair<string, string> &a, const pair<string, string> &b) { // сравнитель по второй строке
	return a.second < b.second;
}
int main() {
	vector <pair<string, string>> words; // словарь
	string str;
	while (getline(cin, str, '\n')) {
		pair<string, string> word; // слово
		word.first = str;
		word.second = edit(str);
		sort(word.second.begin(), word.second.end()); // сортируем буквы в слове
		words.push_back(word);
	}
	sort(words.begin(), words.end(), comp); // сортируем словарь по анаграммам
	vector <int> indeces; // массив индексов
	int Count = 0, MaxCount = 0, n = words.size();
	for (int i = 1; i < n; i++) {
		if (words[i-1].second == words[i].second) Count++; 
		else {
			if (Count > MaxCount) { 
				MaxCount = Count;
				indeces.clear();
				indeces.push_back(i-1);
			} else if (Count == MaxCount) indeces.push_back(i-1);
			Count = 0;
		}
	}
	if (Count > MaxCount) {  // обрабатываем последний найденный набор анаграмм
				MaxCount = Count;
				indeces.clear();
				indeces.push_back(n-1);
	} else if (Count == MaxCount) indeces.push_back(n-1);
	bool first = 1;
	for (int index : indeces) { // выводим
		if (!first) cout << endl << "---------------" << endl;
		else first = 0;
		for (int i = 0; i <= MaxCount; i++) {
			if (i != 0) cout << endl;
			cout << words[index - i].first;
		}
	}
	return 0;
}

#include <iostream>

#include <string>

#include <algorithm>

#include <vector>

#define DIFFERENCE ('A' - 'a') // разность регистров

using namespace std;

bool IsBigAlpha(char a) {

return (a >= 'A' && a <= 'Z');

}

bool IsSmalAlpha(char a) {

return (a >= 'a' && a <= 'z');

}

string edit(const string &str) { // приводим всё к нижнему регистру и убираем лишние символы

string rez = "";

for(char a : str) {

if (IsBigAlpha(a)) a -= DIFERENSE;

if (IsSmalAlpha(a)) rez += a;

}

return rez;

}

bool comp(const pair<string, string> &a, const pair<string, string> &b) { // сравнитель по второй строке

return a.second < b.second;

}

int main() {

vector <pair<string, string>> words; // словарь

string str;

while (getline(cin, str, '\n')) {

pair<string, string> word; // слово

word.first = str;

word.second = edit(str);

sort(word.second.begin(), word.second.end()); // сортируем буквы в слове

words.push_back(word);

}

sort(words.begin(), words.end(), comp); // сортируем словарь по анаграммам

vector <int> indeces; // массив индексов

int Count = 0, MaxCount = 0, n = words.size();

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

if (words[i-1].second == words[i].second) Count++;

else {

if (Count > MaxCount) {

MaxCount = Count;

indeces.clear();

indeces.push_back(i-1);

} else if (Count == MaxCount) indeces.push_back(i-1);

Count = 0;

}

if (Count > MaxCount) { // обрабатываем последний найденный набор анаграмм

MaxCount = Count;

indeces.clear();

indeces.push_back(n-1);

} else if (Count == MaxCount) indeces.push_back(n-1);

bool first = 1;

for (int index : indeces) { // выводим

if (!first) cout << endl << "---------------" << endl;

else first = 0;

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

if (i != 0) cout << endl;

cout << words[index - i].first;

}

return 0;

}

Код на ideone

Related Images:

Псевдо строчная таблица

12/07/2018 by Костя Григорян

Задача

В тридесятом государстве объявлено новое соревнование. Каждому участнику дается лист бумаги, ширина которого строго равна одному магическому метру, на котором надо начертить таблицу, имеющую размер $m \times n$. При этом для каждой ячейки таблицы указана минимальная площадь, которую должна эта ячейка занимать. Все строки таблицы равны между собой. Задача участников — начертить таблицу наименьшей высоты. Алиса снова очень хочет победить, но она все еще плохо знает математику, поэтому она просит Вас помочь ей в этом непростом деле.

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

Первая строка содержит два натуральных числа $m$ и $n$, $(1 \leqslant m,n \leqslant 100).$ Далее идут $m$ строк содержащие по $n$ натуральных чисел — $s_1, s_2, \cdots , s_{n-1}, s_n$ — минимальные площади каждой ячейки $(1 \leqslant s_i \leqslant 100).$

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

Вывести минимальную высоту таблицы.

Тесты

$2 \ 3$	$12$
$1 \ 2 \ 3 \\ 1 \ 2 \ 3$
$1 \ 3$	$10$
$2 \ 3 \ 5$
$4 \ 4$	$96$
$3 \ 5 \ 7 \ 9 \\ 3 \ 5 \ 7 \ 9 \\ 3 \ 5 \ 7 \ 9 \\ 3 \ 5 \ 7 \ 9$
$3 \ 1$	$6$
$2 \\ 2 \\ 2$
$5 \ 3$	$430$
$46 \ 28 \ 12 \\ 46 \ 28 \ 12 \\ 46 \ 28 \ 12 \\ 46 \ 28 \ 12 \\ 46 \ 28 \ 12$
$2 \ 6$	$216$
$7 \ 32 \ 3 \ 23 \ 12 \ 31 \\ 7 \ 32 \ 3 \ 23 \ 12 \ 31$
$7 \ 5$	$945$
$5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78 \\ 5 \ 21 \ 23 \ 8 \ 78$
$1 \ 1$	$5$
$5$
$3 \ 7$	$210$
$10 \ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \\ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \\ 10 \ 10 \ 10 \ 10 \ 10 \ 10 \ 10$
$2 \ 2$	$202$
$100 \ 1 \\ 100 \ 1$

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

#include <iostream>
using namespace std;
 
int main() {
    int n, m;
    cin >> m >> n;
    long long s[m][n], h=0;
    for(int i=0; i<m; i++)
    {
        for(int j=0; j<n; j++)
        {
            cin >> s[i][j];
        }
    }
    for(int i=0; i<n; i++)
    {
        h+=s[0][i];
    }
    cout << m*h;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m;

cin >> m >> n;

long long s[m][n], h=0;

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

{

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

{

cin >> s[i][j];

}

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

{

h+=s[0][i];

}

cout << m*h;

return 0;

}

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

Так как все строки равны между собой, тогда решение задачи состоит в том, чтобы разбить таблицу на строки размером $1 \times n$ и найти их минимальную высоту. Как находить высоту $h$ для каждой такой строки было показано тут. Тогда минимальная высота всей таблицы равна $m \cdot h.$

Ссылки

Код решения

Related Images:

e-olymp 1119. Пирамида из символов

26/06/2018 by Георгий Мартынюк

Задача

Вася хочет напечатать на принтере пирамиду из какого-то символа высоты $h$. Напишите программу, которая поможет ему в этом, не забывая, что программа должна быть «экономически выгодной», т.е печатать наименьшее количество символов.

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

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

В одной строке задан сначала символ, при помощи которого должна быть напечатана пирамида, а затем через пробел натуральное число, задающее высоту пирамиды $h (h ≤ 50)$.

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

В первой сроке выведите общее количество напечатанных «печатных» символов а ниже саму пирамиду.

Тесты

Входные данные	Выходные данные
A 3	12 A AAA AAAAA
M 9	117 M MMM MMMMM MMMMMMM MMMMMMMMM MMMMMMMMMMM MMMMMMMMMMMMM MMMMMMMMMMMMMMM MMMMMMMMMMMMMMMMM

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

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

int main() {
    string s;
    char a;
    cin >> a;
    float b;
    s = a;
    cin >> b;
    cout << ((2 + 3 * (b - 1)) * b)/2 << endl;
    for(int i; i < b; i++) {
        for(int j=1; j < b-i; j++)
               cout << " ";
        cout << s;
        s = a + s + a;
        cout<<endl;
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

char a;

cin >> a;

float b;

s = a;

cin >> b;

cout << ((2 + 3 * (b - 1)) * b)/2 << endl;

for(int i; i < b; i++) {

for(int j=1; j < b-i; j++)

cout << " ";

cout << s;

s = a + s + a;

cout<<endl;

}

return 0;

}

Решение

Для решения данной задачи потребуется выводить пробелы для отступов в каждой строке и заданный символ в виде пирамиды. Для этого напишем цикл, который будет перебирать строки. Для нахождения количества символов в пирамиде используем формулу: по арифметической прогрессии, где первый элемент это $1$, а каждый следующий больше предыдущего на $2$. В вывод пишется столько пробелов, сколько нужно для правильного расположения (с каждой следующей строчкой пробелов на $1$ меньше, в первой строке $b$ пробелов).

Ссылки

e-olymp
Ideone

Related Images:

e-olymp 7340. Поле-чудес

16/05/2018 by Данила Савчак

Задача

Петрик і Марічка захопились грою поле-чудес: Марічка записує слово, що складається з великих англійських букв, а Петрик старається розпізнати його, причому відгадана буква відкривається на всіх позиціях, де вона міститься. За яку найменшу кількість ходів Петрик зможе відгадати задане слово.

Вхідні дані

Слово записане великими англійськими буквами (не більше [latex]100[/latex] символів).

Вихідні дані

Відповідь до задачі.

Тести

Вхідні дані	Вихідні дані
[latex]GOOGLE[/latex]	[latex]4[/latex]
[latex]ALBUS[/latex]	[latex]5[/latex]
[latex]OOO[/latex]	[latex]1[/latex]

Код програми

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

int main() {
    char s[101];
    cin >> s;
    sort( s, s + strlen(s) );
    int k = 1;
    char c = s[0];
    for(int i = 0; i < strlen(s); i++){
        if( s[i] != c ){
            c = s[i];
            k++;
        }
    }
    cout << k;
    return 0;
}

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

int main() {

char s[101];

cin >> s;

sort( s, s + strlen(s) );

int k = 1;

char c = s[0];

for(int i = 0; i < strlen(s); i++){

if( s[i] != c ){

c = s[i];

k++;

}

cout << k;

return 0;

}

Рішення завдання

Створимо місце для слова і прочитаємо його, далі використаємо функцію sort ( з бібліотеки algorithm ) для того, щоб однакові букви йшли поряд і заведемо змінну, спочатку рівну [latex]1[/latex], так як слово складається мінімум з однієї букви, і будемо збільшувати її на [latex]1[/latex], якщо зустрінеться нова буква.

Код програми з классом string

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

int main() {
    string s;
    cin >> s;
    for (int j = 0; j < s.size(); j++) {
        int i = j + 1;
        while (i < s.size()) {
            if(s[j] == s[i] and i != j) {
                s.erase(i,1);
            }
            else i++;
        }
    }
    cout << s.size();
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

string s;

cin >> s;

for (int j = 0; j < s.size(); j++) {

int i = j + 1;

while (i < s.size()) {

if(s[j] == s[i] and i != j) {

s.erase(i,1);

}

else i++;

}

cout << s.size();

return 0;

}

Рішення завдання

Створимо місце для слова і прочитаємо його, далі будемо перевіряти для кожної букви чи повторюється вона і якщо повторюється, то всі букви, окрім тої від якої перевіряємо, будемо видаляти. У кінці виведемо кількість елементів строки.

Код програми з множиною

#include <iostream>
#include <set>
using namespace std;
 
int main() {
    set<char> k;
    set<char>::iterator iter;
    char s[101];
    cin >> s;
    for(int i = 0; i < strlen(s); i++){
        k.insert(s[i]);
    }
    cout << k.size();
    return 0;
}

#include <iostream>

#include <set>

using namespace std;

int main() {

set<char> k;

set<char>::iterator iter;

char s[101];

cin >> s;

for(int i = 0; i < strlen(s); i++){

k.insert(s[i]);

}

cout << k.size();

return 0;

}

Рішення завдання

Створимо місце і прочитаємо слово. Подалі кожну букву слова запишемо, як елемент множини [latex]і.[/latex] Так як множина автоматично видаляє всі однакові елементи, то відповіддю до завдання буде кількість елементів множини.

Посилання

Умова завдання на e-olymp.com.

Код рішення на ideone.com.

Код рішення з множиною на ideone.com.

Код рішення з классом string ideone.com.

Related Images:

e-olymp 2197. Антипалиндром

10/12/2017 by Сытников Дан

Антипалиндром

Условие задачи:

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

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

Выходные данные
В выходной файл выведите ответ на задачу, если ответов несколько — выберите лексикографически минимальный. Если все подстроки s являются палиндромами, выведите в выходной файл NO SOLUTION.

Тесты

№	Входные данные	Выходные данные
1	abba	abb
2	aaaaaaa	NO SOLUTION
3	abcghgcba	abcghgcb
4	abaaabbb	abaaabbb

Код на языке C++:

#include <iostream>
using namespace std;

bool eqchar(string s) {     // Проверка, является ли строка множеством одинаковых символов
    for (int i = 0; i < s.length(); i++) {
        if (s[i] != s[0]) return false;
    }
    return true;
}

bool ispal(string s) {      // Проверка, является ли строка палиндромом
    for (int i = 0; i < s.length()/2; i++) {
        if (s[i] != s[s.length() - i - 1])  return false;
    }
    return true;
}

int main() {
    string s;
    cin >> s;
    if (eqchar(s)) cout << "NO SOLUTION";
    else {
        if (!ispal(s))  cout << s;
        else {
            if (s[0] < s[1]) cout << s.substr(0, s.length() - 1);
            else cout << s.substr(1, s.length());
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

bool eqchar(string s) { // Проверка, является ли строка множеством одинаковых символов

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

if (s[i] != s[0]) return false;

}

return true;

}

bool ispal(string s) { // Проверка, является ли строка палиндромом

for (int i = 0; i < s.length()/2; i++) {

if (s[i] != s[s.length() - i - 1]) return false;

}

return true;

}

int main() {

string s;

cin >> s;

if (eqchar(s)) cout << "NO SOLUTION";

else {

if (!ispal(s)) cout << s;

else {

if (s[0] < s[1]) cout << s.substr(0, s.length() - 1);

else cout << s.substr(1, s.length());

}

return 0;

}

Код на языке Java:

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static boolean eqchar(String s) {
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) != s.charAt(0)) return false;
        }
        return true;
    }

    public static boolean ispal(String s) {
        for (int i = 0; i < s.length() / 2; i++) {
            if (s.charAt(i) != s.charAt(s.length() - i - 1)) return false;
        }
        return true;
    }

    public static void main(String[] args) throws java.lang.Exception {
        Scanner in = new Scanner(System.in);
        String s = in .nextLine();
        if (eqchar(s)) System.out.println("NO SOLUTION");
        else {
            if (!ispal(s)) System.out.println(s);
            else {
                if (s.charAt(0) < s.charAt(1)) System.out.println(s.substring(0, s.length() - 1));
                else System.out.println(s.substring(1));
            }
        }
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main {

public static boolean eqchar(String s) {

for (int i = 1; i < s.length(); i++) {

if (s.charAt(i) != s.charAt(0)) return false;

}

return true;

}

public static boolean ispal(String s) {

for (int i = 0; i < s.length() / 2; i++) {

if (s.charAt(i) != s.charAt(s.length() - i - 1)) return false;

}

return true;

}

public static void main(String[] args) throws java.lang.Exception {

Scanner in = new Scanner(System.in);

String s = in .nextLine();

if (eqchar(s)) System.out.println("NO SOLUTION");

else {

if (!ispal(s)) System.out.println(s);

else {

if (s.charAt(0) < s.charAt(1)) System.out.println(s.substring(0, s.length() - 1));

else System.out.println(s.substring(1));

}

Решение задачи:
Сперва необходимо проверить, является ли строка множеством одинаковых символов. В этом случае найти подстроку, не являющуюся палиндромом, не представляется возможным. Затем проверим, является ли входная строка палиндромом. Если нет, выведем исходную строку. Иначе необходимо вывести подстроку без первого или последнего символа (в зависимости от лексикографического порядка строки).

Условие задачи на e-olymp
Засчитанная задача на e-olymp: на языке C++
Засчитанная задача на e-olymp: на языке Java
Код задачи на C++: Ideone
Код задачи на Java: Ideone

Related Images:

e-olymp 6128. Простой дек

01/06/2017 by Сабиров Ильдар

Задача. Простой дек

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

push_front

Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.

push_back

Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.

pop_front
Извлечь из дека первый элемент. Программа должна вывести его значение.

pop_back

Извлечь из дека последний элемент. Программа должна вывести его значение.

front

Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.

back

Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.

size

Вывести количество элементов в деке.

clear

Очистить дек (удалить из него все элементы) и вывести ok.

exit

Программа должна вывести bye и завершить работу.

Гарантируется, что количество элементов в деке в любой момент не превосходит 100. Все операции:

pop_front
pop_back
front
back

всегда корректны.

Объяснение: Количество элементов во всех структурах данных не превышает 10000, если это не указано особо.

Тесты

№

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

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

push_back 3

push_back 14

size

clear

push_front 1

back

push_back 2

front

pop_back

size

pop_front

size

exit

bye

size

push_back 8

push_front 4

size

front

back

push_back 3

pop_front

front

pop_back

back

exit

bye

Решение

#include <iostream>
#include <vector>
#include <string>
using namespace std;
struct Deque
{
    vector<int> box1;
    vector<int> box2;
    int n, box_size=0;
    void push_front(int n)
    {
        box1.push_back(n);
        box_size++;
    }
    void push_back(int n)
    {
        box2.push_back(n);
        box_size++;
    }
    int pop_front()
    {
        if(box1.size()>0)
        {
            int a=box1[box1.size()-1];
            box1.erase(box1.end()-1);
            box_size--;
            return a;
        }
        else if(box2.size()>0)
        {
            int a=box2[0];
            box2.erase(box2.begin());
            box_size--;
            return a;
        }
        return 1;
    }
    int pop_back()
    {
        if(box2.size()>0)
        {
            int a=box2[box2.size()-1];
            box2.erase(box2.end()-1);
            box_size--;
            return a;
        }
        else if(box1.size()>0)
        {
            int a=box1[0];
            box1.erase(box1.begin());
            box_size--;
            return a;
        }
        return 1;
    }
    int front()
    {
        if(box1.size()>0)
        {
            int a=box1[box1.size()-1];
            return a;
        }
        else if(box2.size()>0)
        {
            int a=box2[0];
            return a;
        }
        return 1;
    }
    int back()
    {
        if(box2.size()>0)
        {
            int a=box2[box2.size()-1];
            return a;
        }
        else if(box1.size()>0)
        {
            int a=box1[0];
            return a;
        }
        return 1;
    }
    int size()
    {
        return box_size;
    }
    string clear()
    {
        box1.erase(box1.begin(), box1.end());
        box2.erase(box2.begin(), box2.end());
        box_size=0;
        return "ok";
    }
    string exit()
    {
        return "bye";
    }
};
int main() 
{
    Deque a;
    string s;
    while(cin>>s)
    {
        if(s=="push_front")
        {
            int n;
            cin>>n;
            a.push_front(n);
            cout<<"ok"<<endl;
        }
        if(s=="push_back")
        {
            int n;
            cin>>n;
            a.push_back(n);
            cout<<"ok"<<endl;
        }
        if(s=="pop_front")
        {
            cout<<a.pop_front()<<endl;
        }
        if(s=="pop_back")
        {
            cout<<a.pop_back()<<endl;
        }
        if(s=="front")
        {
            cout<<a.front()<<endl;
        }
        if(s=="back")
        {
            cout<<a.back()<<endl;
        }
        if(s=="size")
        {
            cout<<a.size()<<endl;
        }
        if(s=="clear"){
            a.clear();
            cout<<a.clear()<<endl;
        }
        if(s=="exit")
        {
            cout<<a.exit()<<endl;
            break;
        }
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

#include <iostream>

#include <vector>

#include <string>

using namespace std;

struct Deque

{

vector<int> box1;

vector<int> box2;

int n, box_size=0;

void push_front(int n)

{

box1.push_back(n);

box_size++;

}

void push_back(int n)

{

box2.push_back(n);

box_size++;

}

int pop_front()

{

if(box1.size()>0)

{

int a=box1[box1.size()-1];

box1.erase(box1.end()-1);

box_size--;

return a;

}

else if(box2.size()>0)

{

int a=box2[0];

box2.erase(box2.begin());

box_size--;

return a;

}

return 1;

}

int pop_back()

{

if(box2.size()>0)

{

int a=box2[box2.size()-1];

box2.erase(box2.end()-1);

box_size--;

return a;

}

else if(box1.size()>0)

{

int a=box1[0];

box1.erase(box1.begin());

box_size--;

return a;

}

return 1;

}

int front()

{

if(box1.size()>0)

{

int a=box1[box1.size()-1];

return a;

}

else if(box2.size()>0)

{

int a=box2[0];

return a;

}

return 1;

}

int back()

{

if(box2.size()>0)

{

int a=box2[box2.size()-1];

return a;

}

else if(box1.size()>0)

{

int a=box1[0];

return a;

}

return 1;

}

int size()

{

return box_size;

}

string clear()

{

box1.erase(box1.begin(), box1.end());

box2.erase(box2.begin(), box2.end());

box_size=0;

return "ok";

}

string exit()

{

return "bye";

}

};

int main()

{

Deque a;

string s;

while(cin>>s)

{

if(s=="push_front")

{

int n;

cin>>n;

a.push_front(n);

cout<<"ok"<<endl;

}

if(s=="push_back")

{

int n;

cin>>n;

a.push_back(n);

cout<<"ok"<<endl;

}

if(s=="pop_front")

{

cout<<a.pop_front()<<endl;

}

if(s=="pop_back")

{

cout<<a.pop_back()<<endl;

}

if(s=="front")

{

cout<<a.front()<<endl;

}

if(s=="back")

{

cout<<a.back()<<endl;

}

if(s=="size")

{

cout<<a.size()<<endl;

}

if(s=="clear"){

a.clear();

cout<<a.clear()<<endl;

}

if(s=="exit")

{

cout<<a.exit()<<endl;

break;

}

return 0;

}

Алгоритм решения

Реализация двусторонней очереди идет посредством векторов [latex]box1[/latex] и [latex]box2[/latex], поэтому нет необходимости делать проверку на переполнение. Команды [latex]push_front[/latex] и [latex]push_back[/latex] соответственно добавляют в концы векторов [latex]box1[/latex] и [latex]box2[/latex] элементы и увеличивают размер дека box_size (на единицу за каждый добавленный элемент). Рассмотрим команду [latex]front[/latex]. Проверяя присутствие элементов в [latex]box1[/latex] мы выводим последний элемент вектора, так как добавляли элемент с помощью [latex]push_front[/latex] в конец вектора [latex]box1[/latex]. Если же вектор [latex]box1[/latex] пуст, то выводим первый элемент вектора [latex]box2[/latex], который в случае пустого вектора [latex]box1[/latex] является первым элементом дека. Команда [latex]back[/latex] относительно [latex]front[/latex] с векторами работает инверсивно. Т.е. Проверяя присутствие элементов в [latex]box2[/latex] выводим последний элемент данного вектора. Если же вектор [latex]box2[/latex] пуст, то выводим первый элемент вектора [latex]box1[/latex] , который в случае пустого вектора [latex]box2[/latex] является последним элементом дека. С командами [latex]pop_front[/latex] и [latex]pop_back[/latex] работают идентично [latex]front[/latex] и [latex]back[/latex]. Отличие лишь в том, что команды [latex]pop[/latex] в дополнении к выводу элемента удаляют его, уменьшая размер дека [latex]box_size[/latex] (на единицу за каждый удаленный элемент). Команда [latex]size[/latex] выводит размер дека [latex]box_size[/latex]. Команда clear удаляет все элементы векторов [latex]box1[/latex], [latex]box2[/latex] и обнуляет размер дека. Команда [latex]exit[/latex] выводит «bye» и завершает работу программы. Команды принимаются из потока ввода посредством строки s.

Ссылка на код.

e-olymp.

Related Images:

e-olymp 7447. Обрезка строки

12/05/2017 by Эммануил Прокопов

Задача с сайта e-olymp.com.

Условие задачи

Имеется строка [latex]s[/latex]. Разрешается взять два любых одинаковых соседних символа и удалить их из строки. Эту операцию можно производить пока имеется возможность. Сначала Вы можете выбрать любое количество символов в строке и удалить их. Определить наименьшее количество символов, которое Вы можете удалить сначала так, чтобы затем выполняя разрешенную операцию, получить пустую строку.

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

Содержит строку [latex]s[/latex] ([latex]1 ≤[/latex] длина[latex]\left( s \right) [/latex] [latex]≤ 100)[/latex].

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

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

Тесты

№	Входные данные	Выходные данные
1	abbcddka	2
2	ABBA	0
3	abcde	5
4	abbac	1

Код на C++

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

int **answers;
string s;

int calculate(int l, int r){
    if(l > r) return 0;  //Если индекс левой границы отрезка больше индекса правой.
    if(answers[l][r] == -1){ //Если ответ для данного отрезка ещё не известен, находим его.
        answers[l][r] = s.size();
        if(s[l] == s[r]) answers[l][r] = min(answers[l][r], calculate(l+1, r-1));
        for(int i = l; i < r; ++i){
            answers[l][r] = min(answers[l][r], calculate(l, i) + calculate(i+1, r));
        }
    }
    return answers[l][r];
}

int main() {
    getline(cin, s); //Ввод строки.
    
    answers = new int*[s.size()];
    for(int i = 0; i < s.size(); ++i){
        answers[i] = new int[s.size()];
    }
    //Заполнение массива начальными значениями.
    for(int i = 0; i < s.size(); ++i){
        for(int j = 0; j <= s.size(); ++j){
            if(i == j) answers[i][j] = 1;
            else answers[i][j] = -1;
        }
    }
    //Вывод ответа.
    cout<<calculate(0, s.size()-1);
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int **answers;

string s;

int calculate(int l, int r){

if(l > r) return 0; //Если индекс левой границы отрезка больше индекса правой.

if(answers[l][r] == -1){ //Если ответ для данного отрезка ещё не известен, находим его.

answers[l][r] = s.size();

if(s[l] == s[r]) answers[l][r] = min(answers[l][r], calculate(l+1, r-1));

for(int i = l; i < r; ++i){

answers[l][r] = min(answers[l][r], calculate(l, i) + calculate(i+1, r));

}

return answers[l][r];

}

int main() {

getline(cin, s); //Ввод строки.

answers = new int*[s.size()];

for(int i = 0; i < s.size(); ++i){

answers[i] = new int[s.size()];

}

//Заполнение массива начальными значениями.

for(int i = 0; i < s.size(); ++i){

for(int j = 0; j <= s.size(); ++j){

if(i == j) answers[i][j] = 1;

else answers[i][j] = -1;

}

//Вывод ответа.

cout<<calculate(0, s.size()-1);

return 0;

}

Код на Java

import java.util.*;

class Main
{
    static int[][] answers;
    static String s;

    static int calculate(int l, int r){
        if(l > r) return 0;  //Если индекс левой границы отрезка больше индекса правой.
        if(answers[l][r] == -1){ //Если ответ для данного отрезка ещё не известен, находим его.
            answers[l][r] = s.length();
            if(s.charAt(l) == s.charAt(r)) answers[l][r] = Math.min(answers[l][r], calculate(l+1, r-1));
            for(int i = l; i < r; ++i){
                answers[l][r] = Math.min(answers[l][r], calculate(l, i) + calculate(i+1, r));
            }
        }
        return answers[l][r];
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        s = in.nextLine();  //Ввод строки.
        
        answers = new int[s.length()][s.length()];
        //Заполнение массива начальными значениями.
        for(int i = 0; i < s.length(); ++i){
            for(int j = 0; j < s.length(); ++j){
                if(i == j) answers[i][j] = 1;
                else answers[i][j] = -1;
            }
        }
        //Вывод ответа.
        System.out.print(calculate(0, s.length()-1));
    }
}

import java.util.*;

class Main

{

static int[][] answers;

static String s;

static int calculate(int l, int r){

if(l > r) return 0; //Если индекс левой границы отрезка больше индекса правой.

if(answers[l][r] == -1){ //Если ответ для данного отрезка ещё не известен, находим его.

answers[l][r] = s.length();

if(s.charAt(l) == s.charAt(r)) answers[l][r] = Math.min(answers[l][r], calculate(l+1, r-1));

for(int i = l; i < r; ++i){

answers[l][r] = Math.min(answers[l][r], calculate(l, i) + calculate(i+1, r));

}

return answers[l][r];

}

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

s = in.nextLine(); //Ввод строки.

answers = new int[s.length()][s.length()];

//Заполнение массива начальными значениями.

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

for(int j = 0; j < s.length(); ++j){

if(i == j) answers[i][j] = 1;

else answers[i][j] = -1;

}

//Вывод ответа.

System.out.print(calculate(0, s.length()-1));

}

Описание

Идея решения состоит в том, чтобы разбить строку на меньшие по длине подстроки и найти ответ на задачу для каждой из них. Для хранения строки используется переменная s, а ответы на подзадачи содержатся в двумерном массиве целых чисел answers. В answers[i][j] находится ответ для подстроки с i-ого по j-й символ включительно. В функции main сначала вводится строка s. Далее ширина и глубина массива answers устанавливаются равными длине s. После этого он заполняется начальными значениями. Значение [latex]-1[/latex] означает, что ответ для этой ячейки ещё не был найден. Однако очевидно, что если строка состоит ровно из одного символа, согласно условию задачи, его придётся удалить, значит, главную диагональ можно сразу заполнить единицами. Затем происходит вызов рекурсивной функции calculate, принимающей индексы левой и правой границ целевой подстроки. Первый раз она вызывается для всей строки от первого до последнего символа. Работает эта функция следующим образом: если индекс левой границы отрезка больше индекса правой, что, в случае данной задачи, не имеет смысла, она возвращает ноль. Иначе она возвращает ответ на задачу для данной подстроки, а если этого не делалось ранее, то предварительно находит его. Происходит это так: сначала значение ответа устанавливается равным длине подстроки, поскольку в худшем случае необходимо будет удалить её всю целиком. Если символы на концах подстроки одинаковые, они, как сказано в условии, будут удалены в дальнейшем, потому нужно рассматривать минимум из текущего значения ответа и ответа для подстроки без крайних символов. Однако может оказаться, что выгоднее удалить символы из каких-то двух меньших подстрок, потому далее в цикле рассматриваются все возможные комбинации двух подстрок, из которых можно составить конкатенацией текущую. В итоге получаем ответ на задачу для данной подстроки.

Код на ideone.com. (C++)
Код на ideone.com. (Java)
Засчитанное решение на e-olymp.

Related Images:

e-olymp 1078. Степень строки

11/05/2017 by Вадим Гордийчук

Задача

Обозначим через [latex]a \cdot b[/latex] конкатенацию строк [latex]a[/latex] и [latex]b[/latex].

Например, если [latex]a =[/latex]«abc» и [latex]b =[/latex]«def» то [latex]a \cdot b =[/latex]«abcdef».

Если считать конкатенацию строк умножением, то можно определить операцию возведения в степень следующим образом:
[latex]a^{0} =[/latex]«» (пустая строка)
[latex]a^{n+1} = a \cdot a^{n}[/latex]

По заданной строке [latex]s[/latex] необходимо найти наибольшее значение [latex]n[/latex], для которого [latex]s = a^{n}[/latex] для некоторой строки [latex]a[/latex].

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

Каждый тест состоит из одной строки [latex]s[/latex], содержащей печатные (отображаемые) символы. Строка [latex]s[/latex] содержит не менее одного и не более миллиона символов.

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

Для каждой входной строки [latex]s[/latex] вывести в отдельной строке наибольшее значение [latex]n[/latex], для которого [latex]s[/latex] = [latex]a^{n}[/latex] для некоторой строки [latex]a[/latex].

Тесты

Входные данные	Выходные данные
abcabc gcdgcd gcgcgc gggggg hhhh	2 2 3 6 4
BbbbBbbbBbbb dogdogdog aaaaaaaa cstring	3 3 8 1

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

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

unsigned int cstringpow(const char *s)
{
    unsigned int answer = 1;
    const unsigned int size = strlen(s);
    for (unsigned int i = 1; i < size/2+1; ++i)
    {
        /*
        Ищем предполагаемую степень для ответа, которая
        обязательно является делителем длины строки.
        */
        if (size % i == 0)
        {
            bool not_broken = 1; //предполагаем, что выбранная степень строки максимальна
            for (int j = 0; j < size-i; j += i)
            {
                //сравниваем блоки строки
                if (strncmp(s+j, s+j+i, i) != 0)
                {
                    not_broken = 0;
                    break;
                }
            }
            if (not_broken)
            {
                //Если предполагаемая степень строки оказалась верной, возвращаем её.
                answer = size/i;
                break;
            }
        }
    }
    return answer;
}

int main()
{
    char s[1000010]; //Выделяем память для строк
    while (cin >> s)
        cout << cstringpow(s) << endl;
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

unsigned int cstringpow(const char *s)

{

unsigned int answer = 1;

const unsigned int size = strlen(s);

for (unsigned int i = 1; i < size/2+1; ++i)

{

Ищем предполагаемую степень для ответа, которая

обязательно является делителем длины строки.

if (size % i == 0)

{

bool not_broken = 1; //предполагаем, что выбранная степень строки максимальна

for (int j = 0; j < size-i; j += i)

{

//сравниваем блоки строки

if (strncmp(s+j, s+j+i, i) != 0)

{

not_broken = 0;

break;

}

if (not_broken)

{

//Если предполагаемая степень строки оказалась верной, возвращаем её.

answer = size/i;

break;

}

return answer;

}

int main()

{

char s[1000010]; //Выделяем память для строк

while (cin >> s)

cout << cstringpow(s) << endl;

return 0;

}

Решение задачи (c-string)

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

Для решения поставленной задачи используем функцию cstringpow, которая в качестве аргумента принимает строку, и возвращает её степень. Реализуем эту функцию следующим образом: вначале ищем делители значения переменной size (с использованием счётчика i в цикле), в которую было предварительно была сохранена длина строки, полученная функцией strlen. Числа, которые будут получатся из выражения size/i, будут предполагаемой максимальной степенью строки. Естественно, они будут находится в порядке убывания.
Найденные счётчиком делители будут представлять из себя длины подстрок, на которые можно полностью разбить данную строку. Затем, используя функцию strncmp, сравниваем каждую подстроку. В случае, если какие-то из подстрок не совпали, то предположенная максимальная степень строки не является верной, и необходимо искать следующую. Иначе (если несовпадающих подстрок не найдено, то) значение выражения size/i будет ответом на поставленную задачу. В крайнем случае, необходимое разбиение строки не будет найдено, и тогда совокупностью одинаковых подстрок будет сама строка, а следовательно её степень равна [latex]1[/latex].

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

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

unsigned int stringpow(const string &s)
{
    unsigned int answer = 1;
    const unsigned int size = s.size();
    for (unsigned int i = 1; i < size/2+1; ++i)
    {
        /*
        Ищем предполагаемую степень для ответа, которая
        обязательно является делителем длины строки.
        */
        if (size % i == 0)
        {
            bool not_broken = 1; //предполагаем, что выбранная степень строки максимальна
            for (int j = 0; j < size-i; j += i)
            {
                //сравниваем блоки строки
                if (s.compare(j, i, s, j+i, i) != 0)
                {
                    not_broken = 0;
                    break;
                }
            }
            
            if (not_broken)
            {
                //Если предполагаемая степень строки оказалась верной, возвращаем её.
                answer = size/i;
                break;
            }
        }
    }
    return answer;
}

int main()
{
    string s; //Выделяем переменную класса "строка"
    while (cin >> s)
        cout << stringpow(s) << endl;
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

unsigned int stringpow(const string &s)

{

unsigned int answer = 1;

const unsigned int size = s.size();

for (unsigned int i = 1; i < size/2+1; ++i)

{

Ищем предполагаемую степень для ответа, которая

обязательно является делителем длины строки.

if (size % i == 0)

{

bool not_broken = 1; //предполагаем, что выбранная степень строки максимальна

for (int j = 0; j < size-i; j += i)

{

//сравниваем блоки строки

if (s.compare(j, i, s, j+i, i) != 0)

{

not_broken = 0;

break;

}

if (not_broken)

{

//Если предполагаемая степень строки оказалась верной, возвращаем её.

answer = size/i;

break;

}

return answer;

}

int main()

{

string s; //Выделяем переменную класса "строка"

while (cin >> s)

cout << stringpow(s) << endl;

return 0;

}

import java.util.*;
import java.io.*;

public class Main
{
    public static int stringpow(String s)
    {
        int answer = 1;
        int size = s.length();
        for(int i = 1; i < size/2+1; ++i)
        {
            /*
            Ищем предполагаемую степень для ответа, которая
            обязательно является делителем длины строки.
            */
            if (size % i == 0)
            {
                boolean not_broken = true; //предполагаем, что выбранная степень строки максимальна
                String current = s.substring(0, i);
                for(int j = 0; j < size-i; j += i)
                {
                    //сравниваем блоки строки
                    if (!(current.equals(s.substring(j+i, j+2*i))))
                    {
                        not_broken = false;
                        break;
                    }
                }
            
                if (not_broken)
                {
                    answer = size/i;
                    break;
                }
            }
        }
        return answer;
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        PrintWriter out = new PrintWriter(System.out);

        String S; //Выделяем переменную класса "строка"
        while(in.hasNextLine())
        {
            S = in.nextLine();
            out.println(stringpow(S));
        }

        out.flush();
    }
}

import java.util.*;

import java.io.*;

public class Main

{

public static int stringpow(String s)

{

int answer = 1;

int size = s.length();

for(int i = 1; i < size/2+1; ++i)

{

Ищем предполагаемую степень для ответа, которая

обязательно является делителем длины строки.

if (size % i == 0)

{

boolean not_broken = true; //предполагаем, что выбранная степень строки максимальна

String current = s.substring(0, i);

for(int j = 0; j < size-i; j += i)

{

//сравниваем блоки строки

if (!(current.equals(s.substring(j+i, j+2*i))))

{

not_broken = false;

break;

}

if (not_broken)

{

answer = size/i;

break;

}

return answer;

}

public static void main (String[] args) throws java.lang.Exception

{

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

String S; //Выделяем переменную класса "строка"

while(in.hasNextLine())

{

S = in.nextLine();

out.println(stringpow(S));

}

out.flush();

}

Решение задачи (string)

Решение задачи с использованием класса string аналогично. Единственное отличие — замена функций strlen и strncmp, предназначенных для работы с c-string, на эквивалентные им методы класса string size и compare.

Ссылки

Related Images:

e-olymp 131. Слова

09/05/2017 by Иванна Ялымова

Задача
Из слова «молоко» можно составить слово «коло». Сколько слов из заданного словаря можно составить, используя буквы заданного слова, причем каждую букву можно использовать не более одного раза.

Тесты

Входные данные	Выходные данные
молоко 4 мило коло коліно око	2
приветствие 8 ветер треск спирт трепет перерыв север текст привести	5

Код программы на С++

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
int main() {
    string word; 
    vector <int> D(256), U;
    int n;
    for (int i = 0; i < D.size(); i++) D[i] = 0;
 
    cin >> word; // ввод заданного слова;
    for (int i = 0; i < word.size(); i++) 
    { 
        D[word[i]+127]++;
    }
 
    cin >> n; // ввод количества слов в словаре;
 
    int rez = 0;  
    for (int i = 0; i < n; i++) 
    {
        cin >> word; // ввод слов со словаря;
 
        U = D;
 
        bool words = true; 
        for (int j = 0; j < word.size(); j++)
        {
            U[word[j]+127]--;
            if (U[word[j]+127] < 0)
            {
                words = false;
                break;
            }
        }
 
        rez += words;
    }
    cout << rez << endl; // вывод количества слов, которые можно составить из заданного слова;
    return 0;
}

#include <iostream>

#include <vector>

#include <string>

using namespace std;

int main() {

string word;

vector <int> D(256), U;

int n;

for (int i = 0; i < D.size(); i++) D[i] = 0;

cin >> word; // ввод заданного слова;

for (int i = 0; i < word.size(); i++)

{

D[word[i]+127]++;

}

cin >> n; // ввод количества слов в словаре;

int rez = 0;

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

{

cin >> word; // ввод слов со словаря;

U = D;

bool words = true;

for (int j = 0; j < word.size(); j++)

{

U[word[j]+127]--;

if (U[word[j]+127] < 0)

{

words = false;

break;

}

rez += words;

}

cout << rez << endl; // вывод количества слов, которые можно составить из заданного слова;

return 0;

}

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

import java.util.*;
import java.lang.*;
import java.io.*;
class Ideone {
    public static void main (String[] args) throws java.lang.Exception {
            Scanner in = new Scanner(System.in);
            String word;
            String words[] = new String[256];
            char table[] = new char[256];
            int count[] = new int[256];
            int tempcount[] = new int[256];
            int templength,length,sum = 0,kilk,countwords = 0;
            int mem = 0, index = 0;
            word = in.nextLine();
            kilk = in.nextInt();
            for (int i = 0; i < kilk+1; i++) {
                    words[i] = in.nextLine();
            }
            length = word.length();
            table[0] = word.charAt(0);
            for (int i = 1; i < length; i++) {
                for (int j = 0; j < i; j++) {
                    if (word.charAt(i) == table[j]) 
                        mem = 1;
                } 
                if (mem == 0) {
                    index++;
                    table[index] = word.charAt(i);
                }
                mem = 0;
            }
            mem = 0;
            for (int i = 0; i <= index; i++) {
                    for (int j = 0; j < length; j++) {
                        if (table[i] == word.charAt(j)) {
                            mem++;
                        } 
                    }
                    count[i] = mem;
                    mem = 0;
            }
            int mem2 = 0;
            for (int a = 0; a < kilk; a++) {
                    templength = words[a].length();
                    mem = 0;
                    for (int i = 0; i <= index; i++) {
                        for (int j = 0; j < templength; j++) {
                            if (table[i] == words[a].charAt(j)) mem++;
                        }           
                        tempcount[i] = mem;
                        mem = 0;
                    }
                    for (int i = 0; i <= index; i++) sum = sum + tempcount[i];
                    mem2 = 0;
                    if (sum == templength) {
                        for (int i = 0; i <= index; i++) {
                            if (tempcount[i]>count[i])mem2++;
                        }
                        if (mem2 == 0) countwords++;
                    }
                    sum = 0;
            }
            System.out.println(countwords); 
        }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static void main (String[] args) throws java.lang.Exception {

Scanner in = new Scanner(System.in);

String word;

String words[] = new String[256];

char table[] = new char[256];

int count[] = new int[256];

int tempcount[] = new int[256];

int templength,length,sum = 0,kilk,countwords = 0;

int mem = 0, index = 0;

word = in.nextLine();

kilk = in.nextInt();

for (int i = 0; i < kilk+1; i++) {

words[i] = in.nextLine();

}

length = word.length();

table[0] = word.charAt(0);

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

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

if (word.charAt(i) == table[j])

mem = 1;

}

if (mem == 0) {

index++;

table[index] = word.charAt(i);

}

mem = 0;

}

mem = 0;

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

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

if (table[i] == word.charAt(j)) {

mem++;

}

count[i] = mem;

mem = 0;

}

int mem2 = 0;

for (int a = 0; a < kilk; a++) {

templength = words[a].length();

mem = 0;

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

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

if (table[i] == words[a].charAt(j)) mem++;

}

tempcount[i] = mem;

mem = 0;

}

for (int i = 0; i <= index; i++) sum = sum + tempcount[i];

mem2 = 0;

if (sum == templength) {

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

if (tempcount[i]>count[i])mem2++;

}

if (mem2 == 0) countwords++;

}

sum = 0;

}

System.out.println(countwords);

}

Решение
Создаем вектор [latex]D[/latex], в котором будем хранить количество каждого символа в слове, и обнуляем его. Тип [latex]char[/latex] вмещает максимум [latex]256[/latex] значений (в диапазоне от [latex]-127[/latex] до [latex]126[/latex]). Класс [latex]string[/latex] состоит из символов типа [latex]char[/latex], поэтому для того, чтобы «вернуть» значения этих символов к положительным (в чём возникает необходимость при обращении к элементам вектора), к ним прибавляется [latex]127[/latex].
Потом считаем число каждого символа в слове. Создаем переменную, в которой будем хранить число слов из словаря, которое можно составить, используя символ первого входного слова. Предполагаем, что слово [latex]words[/latex] составить можно ([latex]words=true[/latex]). Считаем использованные символы из первой входной строки и, если вдруг число стало отрицательным, то слово составить нельзя, обнуляем переменную [latex]words[/latex] и останавливаем цикл. К переменной [latex]rez[/latex] прибавляем переменную [latex]words[/latex] и выводим [latex]rez[/latex].

Ссылки
Код на ideone.com (C++)
Код на ideone.com (Java)
Задача с сайта e-olymp.com.
Засчитанное решение.