Category Archives: 8. Строки string

Задачи на использование методов класса string
Попробуйте решить задачи рубрики C-String используя возможности класса string.

Для приближения наших навыков к требованиям собеседований при приеме на работу выполните следующую короткую инструкцию:

Зарегистрируйтесь на сайте подготовки к собеседованиям или войдите в свой аккаунт. Будет лучше, если Вы сделаете это используя уже имеющийся аккаунт на Facebook. Для этого есть соответствующая кнопка внизу окна регистрации (sign up).
Перейдите по ссылке в раздел работы со строками. Если перейти не удалось, значит Вы ещё не выполнили предыдущий пункт инструкции.
Познакомьтесь со всеми материалами и решите все предлагаемые задачи.

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 2691. Проходной балл

27/12/2020 by Жук Світлана

Задача

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

Формат входных данных

В первой строке дано число $N$ ($1 \leqslant N \leqslant 10000$), количество учащихся в списке. Каждая из следующих $N$ строк имеет вид: фамилия и имя, затем число $M_i$ ($1 \leqslant M_i \leqslant 50$) — количество предметов, которые изучал ученик, а затем годовые оценки по каждому из этих предметов.
В последней строке дано единственное число $K$ — проходной балл. Фамилия и имя — строки, состоящие не более чем из $20$ латинских букв. Все числа во входном файле натуральные и не превышают $10^9$.

Формат выходных данных

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

Тесты

№	Входные данные	Выходные данные
1	3 Ivanov Ivan 2 7 9 Petrov Petr 1 7 Sidorov Sidor 2 10 8 4	Ivanov Ivan Petrov Petr Sidorov Sidor
2	1 Ivanov Ivan 1 6 5	Ivanov Ivan
3	4 Petrov Petr 10 1 2 3 4 5 6 7 8 9 10 Sidorov Sidor 5 8 8 8 4 4 Ivanov Ivan 0 Darienko Dasha 3 10 3 9 6	Sidorov Sidor Darienko Dasha
4	2 Petrov Petr 10 1 2 3 4 5 6 7 8 9 10 Darienko Dasha 3 10 3 9 11
5	5 Petrov Petr 10 100000000 200000000 300000000 400000000 500000000 600000000 700000000 800000000 900000000 1000000000 Darienko Dasha 5 500000000 500000000 500000000 700000000 800000000 Sidorov Sidor 20 100000000 200000000 300000000 400000000 500000000 600000000 700000000 800000000 900000000 1000000000 500000000 500000000 500000000 700000000 800000000 500000000 500000000 500000000 700000000 800000000 Ivanov Ivan 8 600000000 600000000 600000000 800000000 200000000 1000000000 300000000 300000000 Sergeev Alexandr 1 700000000 600000000	Darienko Dasha Sergeev Alexandr

Код

Оптимальное решение:

#include <iostream>
#include <string>
#define surname 0
#define name 1
#define column 2

using namespace std;

int main() {
    //количество учеников
    int n;
    cin >> n;
    //в первый столбец запишем фамилии, во второй - имена
    string names[column][n];
    //тут будут средние баллы соответствующих учеников 
    int average [n];
    
    //количество предметов и текущий балл данного ученика
    int subjects, mark;
    //сумма оценок данного ученика
    long sum;
    
    for (auto i = 0; i < n; i++){
        sum = 0;
        //последовательный ввод фамилии, имени и количества предметов
        cin >> names[surname][i] >> names[name][i] >> subjects;
        //ввод оценок в нужном количестве и подсчет суммы
        for (auto j = 0; j < subjects; j++){
            cin >> mark;
            sum += mark;
            
        }
        //вычисление среднего для данного ученика
        average[i] = sum / subjects;
    }
    //средний проходной балл
    int k;
    cin >> k;
    
    //если среднее не меньше проходного балла, 
    //выводим фамилию и имя данного ученика
    for (auto i = 0; i < n; i++){
        if (average[i] >= k) cout << names [surname][i] << 
        " " << names[name][i] << endl;
    }
    return 0;
}

#include <iostream>

#include <string>

#define surname 0

#define name 1

#define column 2

using namespace std;

int main() {

//количество учеников

int n;

cin >> n;

//в первый столбец запишем фамилии, во второй - имена

string names[column][n];

//тут будут средние баллы соответствующих учеников

int average [n];

//количество предметов и текущий балл данного ученика

int subjects, mark;

//сумма оценок данного ученика

long sum;

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

sum = 0;

//последовательный ввод фамилии, имени и количества предметов

cin >> names[surname][i] >> names[name][i] >> subjects;

//ввод оценок в нужном количестве и подсчет суммы

for (auto j = 0; j < subjects; j++){

cin >> mark;

sum += mark;

}

//вычисление среднего для данного ученика

average[i] = sum / subjects;

}

//средний проходной балл

int k;

cin >> k;

//если среднее не меньше проходного балла,

//выводим фамилию и имя данного ученика

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

if (average[i] >= k) cout << names [surname][i] <<

" " << names[name][i] << endl;

}

return 0;

}

Более структурированное решение:

#include <iostream>
#include <string>
 
using namespace std;
 
struct student {
    string name, surname;
    int average;
    void inputFullName() {
        cin >>surname >>name;
    }
    void printFullName() {
        cout <<surname <<" " <<name <<endl;
    }
    void inputMarks() {
        int subjects, mark;
        long sum = 0;
        cin>> subjects;
        //ввод оценок в нужном количестве и подсчет суммы
        for (auto j = 0; j < subjects; j++){
            cin >>mark;
            sum +=mark;
 
        }
        //вычисление среднего для данного ученика
        average = sum / subjects;
    }
    bool passCheck(int k) {
        return average >= k;
    }
};
 
int main() {
    //количество учеников и средний проходной балл
    int n;
    cin >> n;
    //массив учеников
    student list[n];
 
    for (auto i = 0; i < n; i++){
        list[i].inputFullName();
        list[i].inputMarks();
    }
    //ввод среднего проходного балла
    int k;
    cin >> k;
 
    //если среднее не меньше проходного балла, 
    //выводим фамилию и имя данного ученика
    for (auto i = 0; i < n; i++){
        if (list[i].passCheck(k)) 
            list[i].printFullName();
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

struct student {

string name, surname;

int average;

void inputFullName() {

cin >>surname >>name;

}

void printFullName() {

cout <<surname <<" " <<name <<endl;

}

void inputMarks() {

int subjects, mark;

long sum = 0;

cin>> subjects;

//ввод оценок в нужном количестве и подсчет суммы

for (auto j = 0; j < subjects; j++){

cin >>mark;

sum +=mark;

}

//вычисление среднего для данного ученика

average = sum / subjects;

}

bool passCheck(int k) {

return average >= k;

}

};

int main() {

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

int n;

cin >> n;

//массив учеников

student list[n];

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

list[i].inputFullName();

list[i].inputMarks();

}

//ввод среднего проходного балла

int k;

cin >> k;

//если среднее не меньше проходного балла,

//выводим фамилию и имя данного ученика

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

if (list[i].passCheck(k))

list[i].printFullName();

}

return 0;

}

Решение

Введем данные в соответствующие структуры (см. комментарии в коде), вычислим средние баллы для каждого ученика и выведем фамилии и имена всех тех и только тех, чей средний балл выше проходного.
Т. к. все исходные данные натуральные и не превышают $10^9$ используем для их ввода тип int. При этом сумма оценок может выйти за пределы типа int ($50\cdot10^9 > 2 147 483 647$), поэтому для переменной sum используем тип long. Также заметим, что среднее арифметическое натуральных чисел может быть дробным числом, но в данном случаи средний проходной балл $K$ по условию являет натуральным числом, поэтому будет уместно отбросить дробную часть при сравнении, т. е. использовать целочисленных тип данных в вычислениях.

Ссылки

Задача на e-olymp

Код оптимального решения на ideone

Код решения со структурами на решения со структурами на ideone

Засчитанное оптимальное решение на e-olymp

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

Related Images:

e-olymp 7023. Тасование Ханафуда

11/12/2020 by Михайло Будіш

Задача

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

Имеется колода из $n$ карт. Начиная с $p$-ой карты сверху, $c$ карт вынимаются и кладутся на вершину колоды, как показано на рисунке. Такую операцию назовем операциею срезки.

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

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

Состоит из нескольких тестов. Каждый тест начинается со строки, содержащей два натуральных числа $n$ $(1 ≤ n ≤ 50)$ и $r$ $(1 ≤ r ≤ 50)$ — количество карт в колоде и количество операций срезания.

Каждая из следующих $r$ строк описывает операцию срезания. Они выполняются в перечисленном порядке. Каждая строка содержит два натуральных числа $p$ и $c$ $(p + c ≤ n + 1)$. Начиная с $p$-ой карты сверху, c карт вытаскиваются и кладутся наверх.

Последняя строка содержит два нуля.

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

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

Тесты

№	Входные данные	Выходные данные
1	5 2 3 1 3 1 10 3 1 10 10 1 8 3 0 0	4 4

Код

#include <iostream>
#include <string>
 
using namespace std;
 
struct Comma {
    int num, pos;
    Comma() {
        num = 0;
        pos = 0;
    }
};
 
int main() {
    int n, r;
    while(cin >> n >> r) {
        int p, c;
        string s;
        // Filling the array with cards' numbers separated by comma
        for (int i = n; i > 0; i--) s += (i == 1 ? to_string(1) : to_string(i) + ",");
        if (n > 0) {
            for (int i = 0; i < r; i++) {
                cin >> p >> c;
                // Create object with number of comma in string and its position
                Comma comma1, comma2;
                int s_len = s.length();
                if (p != 1) {
                    // -------- Looking for indexes of needed commas to pick 'c' cards
                    for (int j = 0; j < s_len; j++) {
                        if (comma1.num == p-1) {
                            comma1.pos = j;
                            comma1.num = 0;
                        }
                        if (comma2.num == p+c-1) {
                            comma2.pos = j;
                            comma2.num = 0;
                        }
                        if (comma1.pos == 0 && s[j] == ',') comma1.num += 1;
                        if (comma2.pos == 0 && s[j] == ',') comma2.num += 1;
                    }
                    // ---------------------------------------------------------------
 
 
                    // --------- Swapping cards ---------
                    string s1 = s.substr(comma1.pos, comma2.pos - comma1.pos);
                    s.erase(comma1.pos, comma2.pos - comma1.pos);
                    if (s1[s1.length()-1] != ',') s = s1 + ',' + s;
                    else s = s1 + s;
                    // ----------------------------------
                }
            }
            int k = 0;
            while (s[k] != ',') k++;
            string res = s.substr(0, k);
            cout << res << "\n";
        }
    }
}

#include <iostream>

#include <string>

using namespace std;

struct Comma {

int num, pos;

Comma() {

num = 0;

pos = 0;

}

};

int main() {

int n, r;

while(cin >> n >> r) {

int p, c;

string s;

// Filling the array with cards' numbers separated by comma

for (int i = n; i > 0; i--) s += (i == 1 ? to_string(1) : to_string(i) + ",");

if (n > 0) {

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

cin >> p >> c;

// Create object with number of comma in string and its position

Comma comma1, comma2;

int s_len = s.length();

if (p != 1) {

// -------- Looking for indexes of needed commas to pick 'c' cards

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

if (comma1.num == p-1) {

comma1.pos = j;

comma1.num = 0;

}

if (comma2.num == p+c-1) {

comma2.pos = j;

comma2.num = 0;

}

if (comma1.pos == 0 && s[j] == ',') comma1.num += 1;

if (comma2.pos == 0 && s[j] == ',') comma2.num += 1;

}

// ---------------------------------------------------------------

// --------- Swapping cards ---------

string s1 = s.substr(comma1.pos, comma2.pos - comma1.pos);

s.erase(comma1.pos, comma2.pos - comma1.pos);

if (s1[s1.length()-1] != ',') s = s1 + ',' + s;

else s = s1 + s;

// ----------------------------------

}

int k = 0;

while (s[k] != ',') k++;

string res = s.substr(0, k);

cout << res << "\n";

}

Решение

Решить данную задачу можно несколькими способами. Первая мысль, которая мне пришла в голову — поместить все числа в строку и совершать тасование с помощью методов работы со строками, такими как $erase$ и $substr$. В течении решения стало понятно, что просто записывать числа в строку будет неправильно, так как возможны и двузначные числа. Так как неизвестно какое число будет следующим (однозначное или двузначное), особенно после нескольких перестановок, появляется идея хранить в строке числа, разделенные между собой запятыми. И в дальнейшем, если мне понадобится вытащить 5 карт из колоды начиная с 17, то я дойду до 16 запятой и возьму все, что хранится после нее, до 17+5 запятой и переставлю эти числа в начало строки (наверх колоды). Также в процессе поиска позиции необходимой запятой мне нужно получить ее позицию в строке, поэтому я решил создать структуру $Comma$, которая будет хранить номер запятой в строке и ее позицию относительно всех символов в данной строке, чтобы использовать ее во время каждой перестановки.

Таким образом, получаем рабочее решение данной задачи.

P.S. Новые решения согласно советам преподавателя

#include <iostream>
#include <string>

using namespace std;

int main() {
    int n, r;
    while(cin >> n >> r) {
        int p, c;
        string s;
        for (int i = n; i > 0; i--) s += (char)i;
        if (n > 0) {
            for (int i = 0; i < r; i++) {
                cin >> p >> c;
                if (p != 1) {
                    string s1 = s.substr(p-1, c);
                    s.erase(p-1, c);
                    s = s1 + s;
                }
            }
            cout << (int)s[0] << "\n";
        }
    }
}

#include <iostream>

#include <string>

using namespace std;

int main() {

int n, r;

while(cin >> n >> r) {

int p, c;

string s;

for (int i = n; i > 0; i--) s += (char)i;

if (n > 0) {

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

cin >> p >> c;

if (p != 1) {

string s1 = s.substr(p-1, c);

s.erase(p-1, c);

s = s1 + s;

}

cout << (int)s[0] << "\n";

}

#include <iostream>

using namespace std;

struct Card {
    int number;
    Card *next;
    Card(int num, Card *nxt = 0) {
        number = num;
        next = nxt;
    };
};

int main() {
    int n, r;
    Card *top_card = 0;
    while(cin >> n >> r) {
        int p, c;
        for (int i = 1; i <= n; i++) {
            top_card = new Card(i, top_card);
        };
        if (n > 0) {
            for (int i = 0; i < r; i++) {
                cin >> p >> c;
                if (p != 1) {
                    Card *first_moving = 0, *last_moving = 0, *last_before_moving = top_card;
                    for (int j = 1; j < p - 1; j++) {
                        last_before_moving = last_before_moving->next;
                    }
                    first_moving = last_before_moving->next;
                    last_moving = first_moving;

                    for (int j = 1; j < c; j++) {
                        last_moving = last_moving->next;
                    }
                    last_before_moving->next = last_moving->next;
                    last_moving->next = top_card;
                    top_card = first_moving;
                }
            }
            cout << top_card->number << "\n";
        }
    }
}

#include <iostream>

using namespace std;

struct Card {

int number;

Card *next;

Card(int num, Card *nxt = 0) {

number = num;

next = nxt;

};

int main() {

int n, r;

Card *top_card = 0;

while(cin >> n >> r) {

int p, c;

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

top_card = new Card(i, top_card);

};

if (n > 0) {

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

cin >> p >> c;

if (p != 1) {

Card *first_moving = 0, *last_moving = 0, *last_before_moving = top_card;

for (int j = 1; j < p - 1; j++) {

last_before_moving = last_before_moving->next;

}

first_moving = last_before_moving->next;

last_moving = first_moving;

for (int j = 1; j < c; j++) {

last_moving = last_moving->next;

}

last_before_moving->next = last_moving->next;

last_moving->next = top_card;

top_card = first_moving;

}

cout << top_card->number << "\n";

}

Ссылки

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 1290. Номерной знак

20/12/2019 by Таня Осипенко

Задача

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

Сколько существует различных таких номеров?

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

В единственной строке через пробел $2$ неотрицательных целых числа $B$ и $A$. Оба числа не превышают $26$.

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

Единственное число — ответ к задаче.

Тесты

№	Входные данные	Выходные данные
1	3 3	17576000
2	2 5	67600000
3	7 1	80318101760
4	1 1	260
5	26 26	615611958020715731079667428840020377600000000000000000000000000

Код

#include <iostream>
#include <string.h>

using namespace std;

void print(char * x, int n) { // функция вывода массива чисел 
  for (int i = n - 1; i >= 0; i--) {
    cout << (int) x[i];
  }
}
int MULT(char * x, char * y, char * z, int n, int m) { // функция для перемножения больших чисел
  memset(z, 0, n + m); // обнуляем массив
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      char w = x[j] * y[i] + z[i + j];
      z[i + j + 1] += w / 10;
      z[i + j] = w % 10;
    }
  }
  int res = (z[n + m - 1] == 0) ? (n + m - 1) : (n + m); //  кол-во разрядов
  return res;
}
const int N = 100; // кол-во элементов массивов с небольшим запасом
char acc[N] = {1};
int acc_size = 1;
char tmp[N] = {0};
char v_26[] = {6, 2}; // 26

int main() {
  int A, B; // входные данные
  cin >> B >> A;
  for (int i = 0; i < B; i++) { // возведение 26 в степень B
    memcpy(tmp, acc, acc_size);
    acc_size = MULT(tmp, v_26, acc, acc_size, 2); // 2 - число разрядов в 26
  }
  print(acc, acc_size); // вывод результата
  for (int i = 0; i < A; i++){ // домножение на 10 в степени A
    cout << "0";
  }
  return 0;
}

#include <iostream>

#include <string.h>

using namespace std;

void print(char * x, int n) { // функция вывода массива чисел

for (int i = n - 1; i >= 0; i--) {

cout << (int) x[i];

}

int MULT(char * x, char * y, char * z, int n, int m) { // функция для перемножения больших чисел

memset(z, 0, n + m); // обнуляем массив

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

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

char w = x[j] * y[i] + z[i + j];

z[i + j + 1] += w / 10;

z[i + j] = w % 10;

}

int res = (z[n + m - 1] == 0) ? (n + m - 1) : (n + m); // кол-во разрядов

return res;

}

const int N = 100; // кол-во элементов массивов с небольшим запасом

char acc[N] = {1};

int acc_size = 1;

char tmp[N] = {0};

char v_26[] = {6, 2}; // 26

int main() {

int A, B; // входные данные

cin >> B >> A;

for (int i = 0; i < B; i++) { // возведение 26 в степень B

memcpy(tmp, acc, acc_size);

acc_size = MULT(tmp, v_26, acc, acc_size, 2); // 2 - число разрядов в 26

}

print(acc, acc_size); // вывод результата

for (int i = 0; i < A; i++){ // домножение на 10 в степени A

cout << "0";

}

return 0;

}

Решение

Начнем с того, что к условию задачи прилагается картинка, на которой видно, что во всех номерных знаках буквы и цифры не перемешаны между собой произвольно, а имеют свои четко распределенные места, в примере это последовательность, в которой на первой позиции стоит буква, далее три цифры и на последних двух позициях снова буквы. Это важный момент, поскольку если бы действительно было разрешено использовать любую последовательность, возможных комбинаций было бы гораздо больше. Поскольку в латинском алфавите $26$ букв, для выбора буквы на первое место существует $26$ возможных вариантов, на второе тоже $26$, как и на третье, четвертое и т. д. То есть для того чтобы найти все комбинации из букв для $B$ мест, нужно умножить $26$ на $26$ $B$ раз. Точно так же это работает с арабскими цифрами. Их всего $10$, соответственно, умножаем $10$ на $10$ $A$ раз, где $A$ — количество мест в номерном знаке для цифр. Поэтому, чтобы найти количество возможных комбинаций букв и цифр, перемножаем полученные результаты. Отсюда получаем формулу $26^B\cdot 10^A$.

Сложность задачи заключается скорее не в формуле вычисления, а в реализации кода, поскольку большинство значений уже на этапе возведения в степень не помещаются даже в самые большие типы данных. Именно поэтому код состоит не из пяти строк и встроенной операции возведения в степень, а из более сложных операций, подходящих для работы с большими числами. По сути, у нас возникает проблема, связанная с перемножением больших чисел, которые не помещаются в стандартные типы данных С++. Для решения этой проблемы я выбрала модель представления, в которой числа записываются в виде массивов в десятичной системе, и каждая цифра числа является элементом массива. Младший разряд числа находится в нулевом элементе массива, а старший в $n-1$-ом соответственно. Далее была реализована функция «MULT», которая фактически осуществляет алгоритм умножения поэлементно с сохранением остатка от деления на $10$ в соответствующем элементе массива и добавлением частного от деления на $10$ к следующему элементу массива. Следует отметить, что данная функция принимает два числа, записанные в выше указанной модели представления (в виде массивов), и характеристиками этих чисел является пара: сам массив и количество разрядов в числе (размер массивов иными словами). На выходе функция возвращает количество разрядов полученного произведения. Сам же результат умножения сохраняется в виде массива, который является одним из параметров функции. В коде данная функция внесена в цикл для многократного перемножения чисел, то есть для возведения в нужную степень. Домножение на $10^A$ осуществляется в последнем цикле приписыванием A нулей к полученному результату.

Ссылки

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

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 8320. Заглавная строка

26/06/2019 by Лиза Севастьянова

Условие

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

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

Строка из слов, состоящих из прописных букв $’a’$ — $’z’$, разделенных одним или несколькими пробелами. Длина строки не более $50$ символов.

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

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

Тесты

№	Входные данные	Выходные данные
1	introduction to algorithms	Introduction To Algorithms
2	more than one space between words	More Than One Space Between Words
3	hello world	Hello World
4	string or c string	String Or C String

Решение

Для решения данной задачи необходимо, во-первых, прочитать строку. Используем для этого в первом решении getline(cin, s); и cin.getline(s, 51); во втором, так как есть необходимость читать несколько пробелов. Далее делаем первый символ заглавным с помощью toupper(s[0]), а затем проверяем все остальные символы, начиная с третьего и делаем первые символы в каждом слове заглавными с помощью упомянутой функции. В конце выводим строку.

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

#include <iostream>
using namespace std;

int main() {
    string s;
    getline(cin, s);
    s[0] = toupper(s[0]);
    for (int i = 2; i < s.length(); i++) {
        if (s[i-1] == ' ' and s[i] != ' ') { //если i-тый символ не является пробелом, а предыдущий - пробелом, то это первый символ в слове
            s[i] = toupper(s[i]);
        }
    }
    cout << s;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

string s;

getline(cin, s);

s[0] = toupper(s[0]);

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

if (s[i-1] == ' ' and s[i] != ' ') { //если i-тый символ не является пробелом, а предыдущий - пробелом, то это первый символ в слове

s[i] = toupper(s[i]);

}

cout << s;

return 0;

}

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

#include <iostream>
#include <cstring>

using namespace std;

int main() {
    char s[51];
    cin.getline(s, 51);
    s[0] = toupper(s[0]);
    for (int i = 2; i < strlen(s); i++) {
        if (s[i] != ' ' and s[i-1] == ' ') { //если i-тый символ не является пробелом, а предыдущий - пробелом, то это первый символ в слове
            s[i] = toupper(s[i]);
        }
    }
    cout << s;
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

char s[51];

cin.getline(s, 51);

s[0] = toupper(s[0]);

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

if (s[i] != ' ' and s[i-1] == ' ') { //если i-тый символ не является пробелом, а предыдущий - пробелом, то это первый символ в слове

s[i] = toupper(s[i]);

}

cout << s;

return 0;

}

Ссылки

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 8367. Таксі

17/06/2019 by Таисия Ткачева

Задача

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

Проте Аліна — дівчинка відповідальна, вона бажає поїхати із найдосвідченішим таксистом, тобто з тим, який вже здійснив найбільшу кількість перевезень. Але ось невдача — додаток не показує кількість перевезень, здійснених водієм. Єдина інформація, якою володіє Аліна — рейтинг водія.

Нагадаємо, що по завершенню кожного перевезення пасажир виставляє водієві оцінку — ціле число від $1$ до $5$ включно. Рейтинг таксиста $R$ рахується як середнє арифметичне усіх отриманих ним оцінок.

Завдання

Допоможіть Аліні – напишіть програму, яка визначить мінімально можливу кількість перевезень, які мав здійснити таксист щоб отримати рейтинг рівно $R$ (без округлень).

Вхідні дані

В єдиному рядку вхідного файлу знаходиться дійсне число $R$ $\left(1 \leqslant R \leqslant 5 \right)$ — рейтинг водія з точністю не більш ніж $18$ знаків після десяткової крапки.

Вихідні дані

В першому рядку вихідного файлу виведіть єдине натуральне число — відповідь на задачу, або $-1,$ якщо заданий рейтинг отримати неможливо.

Якщо рейтинг отримати можливо, у другому рядку необхідно вивести $5$ цілих невід’ємних чисел — кількість оцінок $1,$ $2,$ $3,$ $4$ і $5$ відповідно, отриманих водієм. У разі коли існує декілька варіантів оцінок, які призводять до оптимальної відповіді, дозволяється вивести будь-який з них.

Оцінювання

Пiдзадача. Бали. Додатковi обмеження. Необхідні підзадачі.

$0$ Тести з умови —
$41$ Точнiсть $R$ не бiльш нiж $1$ знак пiсля коми —
$33$ Точнiсть $R$ не бiльш нiж $6$ знаків пiсля коми $0,$ $1$
$26$ Точнiсть $R$ не бiльш нiж $18$ знаків пiсля коми $0,$ $1,$ $2$

Тести

#	Вхідні дані	Вихідні дані
1	3.0009	10000 0 0 9991 9 0
2	2.0805216	312500 0 287337 25163 0 0
3	4.999999999999999998	500000000000000000 0 0 0 1 499999999999999999
4	1.123581321345589144	125000000000000000 109552334831801357 15447665168198643 0 0 0
5	3.141592653585793236	250000000000000000 0 0 214601836603551691 35398163396448309 0

Код (cтроки string)

#include <iostream>
#include <string> 
using namespace std;
 
unsigned long long GCD (unsigned long long a, unsigned long long b) {
    while (b) {
        a %= b;
        swap (a, b);
    }
    return a;
}
 
int main() {
    string str;
    cin >> str;
    int length = str.length();
    unsigned long long numerator = 0, denominator = 1, gcd, fraction, remainder;
    for (int i = 0; i < length; i++) {
        if(str[i] != '.') numerator = numerator * 10 + (str[i] - '0');
    }
    while (--length > 1) denominator *= 10;
    gcd = GCD (numerator, denominator);
    numerator /= gcd;
    denominator /= gcd;
    remainder =  numerator % denominator;
    numerator -= remainder;
    fraction = numerator / denominator;
    cout << denominator << endl;
    for (int i = 1; i <= 5; i++) {
        if (i == fraction) {
            i++;
            cout << denominator - remainder << " ";
            if (fraction != 5) cout << remainder << " ";
        }
        else cout << 0 << " ";
    }
}

#include <iostream>

#include <string>

using namespace std;

unsigned long long GCD (unsigned long long a, unsigned long long b) {

while (b) {

a %= b;

swap (a, b);

}

return a;

}

int main() {

string str;

cin >> str;

int length = str.length();

unsigned long long numerator = 0, denominator = 1, gcd, fraction, remainder;

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

if(str[i] != '.') numerator = numerator * 10 + (str[i] - '0');

}

while (--length > 1) denominator *= 10;

gcd = GCD (numerator, denominator);

numerator /= gcd;

denominator /= gcd;

remainder = numerator % denominator;

numerator -= remainder;

fraction = numerator / denominator;

cout << denominator << endl;

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

if (i == fraction) {

i++;

cout << denominator - remainder << " ";

if (fraction != 5) cout << remainder << " ";

}

else cout << 0 << " ";

}

Код (cтроки c-string)

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

unsigned long long GCD (unsigned long long a, unsigned long long b) {
    if (b == 0) return a;
    else return GCD (b, a % b);
}

int main() {
    char str[20];
    int length = 0;
    while (cin >> str[length]) length++;
    unsigned long long numerator = 0, denominator = 1, gcd, fraction, remainder;
    for (int i = 0; i < length; i++) {
        if(str[i] != '.') numerator = numerator * 10 + (str[i] - '0');
    }
    while (--length > 1) denominator *= 10;
    gcd = GCD(numerator, denominator);
    numerator /= gcd;
    denominator /= gcd;
    remainder =  numerator % denominator;
    numerator -= remainder;
    fraction = numerator / denominator;
    cout << denominator << endl;
    for (int i = 1; i <= 5; i++) {
        if(i == fraction) {
            i++;
            cout << denominator - remainder << " ";
            if(fraction != 5) cout << remainder << " ";
        }
        else cout << 0 << " ";
    }
}

#include <iostream>

#include <cstring>

using namespace std;

unsigned long long GCD (unsigned long long a, unsigned long long b) {

if (b == 0) return a;

else return GCD (b, a % b);

}

int main() {

char str[20];

int length = 0;

while (cin >> str[length]) length++;

unsigned long long numerator = 0, denominator = 1, gcd, fraction, remainder;

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

if(str[i] != '.') numerator = numerator * 10 + (str[i] - '0');

}

while (--length > 1) denominator *= 10;

gcd = GCD(numerator, denominator);

numerator /= gcd;

denominator /= gcd;

remainder = numerator % denominator;

numerator -= remainder;

fraction = numerator / denominator;

cout << denominator << endl;

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

if(i == fraction) {

i++;

cout << denominator - remainder << " ";

if(fraction != 5) cout << remainder << " ";

}

else cout << 0 << " ";

}

Розв’язок задачі

Спочатку зазначимо, що для рейтингу з точністю $k$ знаків після десяткової коми оптимальна відповідь завжди $\leqslant 10^k$. Розглянемо це на прикладі. Нехай ми маємо рейтинг $3.xxx,$ де $xxx$ — $3$ будь-які цифри. Припустимо, що таксист отримав $10^3=1000$ оцінок $3.$ Тоді його рейтинг буде дорівнювати $\frac{3\cdot1000}{1000}=3.000,$ тобто рівно $3.$ Тепер спробуємо замінити одну оцінку $3$ на $4.$ Тоді його рейтинг дорівнюватиме $\frac{3\cdot 999+4\cdot 1}{999+1}=\frac{3001}{1000}.$ Тобто замінивши одну трійку на четвірку ми збільшили рейтинг на $\frac{1}{1000}.$ Таким чином якщо поступово змінювати усі $3$ на $4$ ми зможемо отримати будь-який рейтинг від $3.000$ до $4.000$ з трьома знаками після коми, а отже і заданий рейтинг $3.xxx.$

Підзадача $1$:

Виходячи з вищезазначеного відповідь $\leqslant 10.$ Тоді ЇЇ можна отримати просто перебравши усі можливі комбінації оцінок $5$-ма вкладеними циклами.

Підзадача $2$:

Доведемо, що оптимальну відповідь завжди можна отримати тільки за допомогою оцінок двох сусідніх типів $a$ та $\left(a+1\right),$ або одного типу (якщо рейтинг цілий). Припустимо, що існує оптимальна відповідь, у якій НЕ сусідні оцінки $x$ та $y,$ $x<y.$ У випадку, якщо $y-x=3,$ ми можемо замінити їх на $x+1$ та $y-1.$ Якщо $y-x=2$ або $y-x=4,$ можна замінити їх на дві оцінки по $x+1$ або $x+2$ відповідно. Ці дії жодним чином не впливають ні на суму, ні на кількість оцінок, а тому не впливають і на середнє арифметичне. Таким чином, будь-який набір оцінок можна звести до набору оцінок з щонайбільше двох типів. Очевидно, що ці два типи — рейтинг округлений вниз та вгору.

Тоді розв’язання полягає у тому щоб перебрати кількість оцінок першого типу, порахувати скільки потрібно оцінок другого типу, аби отримати заданий рейтинг і перевірити, чи кількість оцінок другого типу ціла (тобто такий розподіл оцінок можливий). Нехай рейтинг рівня $R,$ покладемо $a=\lfloor R\rfloor,$ кількість оцінок типу $a$ дорівнює $x,$ а кількість оцінок типу $a+1$ (якщо вони необхідні) дорівнює $y.$ Тоді, $x\cdot a+y\cdot\left(a+1\right)=R\cdot x+R\cdot y.$ З цього, щоб отримати точну відповідь, потрібно виконувати операції у цілих числах або у $64$-бітних числах з плавоючою комою.

Підзадача $3$:

Представимо рейтинг $R$ у вигляді звичайного дробу, домноживши чисельник та знаменник на $10^{18}$. Виходячи з визначення середнього арифметичного, знаменник цього дробу $10^{18}$ — кількість отриманих оцінок, а чисельник $\left( R \cdot 10^{18} \right)$ — їх сума. Якщо цей дріб можна скоротити, це зменшить кількість оцінок, тому що знаменник (тобто кількість оцінок) зменшиться, а відношення чисельника до знаменника (тобто рейтинг) не зміниться. Отже, чисельник і знаменник потрібно поділити на їх НСД. Припустимо, що після скорочення ми отримали дріб $\frac{a}{b}.$ Очевидно, що отримане у знаменнику число $\left( b \right)$ і є оптимальною відповіддю, адже дріб нескоротний і зменшити знаменник не вдасться. Тепер потрібно довести, що ця відповідь завжди досяжна, тобто існує набір з $b$ оцінок від $1$ до $5$, сума яких дорівнює $a.$

Доведення цього факту аналогічне доведенню у підзадачі $2.$ Зауважимо, що завжди $b \leqslant a \leqslant 5b,$ бо рейтинг за умовою від $1$ до $5$. Тепер припустимо, що усі оцінки дорівнюють $1.$ Тоді чисельник дорівнюватиме $1 \cdot b,$ тобто $b.$ Тепер змінемо будь-яку оцінку $\left( m \neq 5 \right)$ на $m+1.$ Тоді чисельник збільшиться на $1,$ а знаменник залишиться рівним $b.$ Поступово здійснюючи такі заміни, можемо припустити «пройти» через усі значення від $b$ до $5b,$ зокрема і через $a,$ яке нам потрібно отримати.

Аби відновити самі оцінки, згадаємо доведений у другій підзадачі факт про те, що оптимальну відповідь завжди можна отримати з оцінок $\lfloor R\rfloor$ та $\lceil R\rceil.$ Якщо б усі оцінки дорівнювали $\lfloor R\rfloor,$ чисельник був би $b \cdot \lfloor R\rfloor .$ Але чисельник дорівнює $a \geqslant b \cdot \lfloor R\rfloor ,$ тому кількість оцінок $\lceil R\rceil$ як раз дорівнює залишку, тобто $a-b \cdot \lfloor R\rfloor .$ Решта оцінок – оцінки $\lfloor R\rfloor .$ Також зауважимо, що через недостатню точність зберігання чисел з плаваючою комою у пам’яті комп’ютера, необхідно зчитувати рейтинг у вигляді рядка і конвертувати одразу у ціле число.

Посилання

Умова на e-olymp
Код (cтроки string)
Код (cтроки c-string)

Related Images:

e-olymp 8382. Пароль

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

Задача

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

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

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

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

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

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

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

Тесты

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

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

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

#include <iostream>

using namespace std;

bool isspecial (char c) {

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

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

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

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

}

int main() {

string password;

cin >> password;

bool test_lc, test_uc, test_dig, test_sp,

test_len = password.length() >= 8;

int length = password.length();

test_lc = test_uc = test_dig = test_sp = false;

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

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

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

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

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

}

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

return 0;

}

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

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

#include <iostream>

#include <cstring>

using namespace std;

bool isspecial (char c) {

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

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

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

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

}

int main() {

char password[101];

cin >> password;

bool test_lc, test_uc, test_dig, test_sp,

test_len = strlen(password) >= 8;

int length = strlen(password);

test_lc = test_uc = test_dig = test_sp = false;

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

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

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

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

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

}

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

return 0;

}

Решение

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

Ссылки

Для string:

Для c-string:

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

Related Images:

e-olymp 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 6901. Shuffling Strings

12/05/2019 by Владислав Шеванов

Task

Suppose $S_1$ and $S_2$ are two strings of size $n$ consisting of characters $A$ through $H$ (capital letters). We plan to perform the following step several times to produce a given string $S$. In each step we shuffle $S_1$ and $S_2$ to get string $S_{12}$ Indeed, $S_{12}$ is obtained by scanning $S_1$ and $S_2$ from left to right and putting their characters alternatively in $S_{12}$from left to right.

The shuffling operation always starts with the leftmost character of $S_2$. After this operation, we set $S_1$ and $S_2$ to be the first half and the second half of $S_{12}$, respectively. For instance, if $S_1 = ABCHAD$ and $S_2 = DEFDAC$, then $S_12 = DAEBFCDHAACD$, and for the next step $S_1 = DAEBFC$ and $S_2 = DHAACD$. For the given string $S$ of size $2n$, the goal is to determine whether $S_{12} = S$ at some step.

Input

There are multiple test cases in the input. Each test case starts with a line containing a non-negative integers [latex] 0 \le n \le 100 [/latex] which is the length of $S_1$ and $S_2$. The remainder of each test case consists of three lines. The first and the second lines contain strings $S_1$ and $S_2$ with size $n$, respectively, and the last line contains string $S$ with size $2n$. The input terminates with «$0$» which should not be processed.

Output

For each test case, output $-1$ if $S$ is not reachable. Otherwise, output the minimum number of steps to reach $S$ . To make your life easier, we inform you that the output is not greater than $50$ for the given input.

Tests

Input	Output
4 AHAH HAHA HHAAAAHH 3 CDE CDE EEDDCC 0	2 -1
3 DBC BCD CDBCBD 0	-1
3 DABC ABCD CADBCBAD 1 A B AB 0	-1 2
3 AAA AAA AAAAAA 0	1
5 ABACD ACABB AAAACCBBBD 0	-1

Program code

#include <iostream>
using namespace std;
 
string shuffle (string &s1, string &s2) {
    string s;
    for (int i = 0; i < s1.length(); i++) {
        s += s2[i];
        s += s1[i];
    }
    s1 = s.substr(0, s1.length());
    s2 = s.substr(s2.length(), s2.length());
    return s;
} 
 
int main() {
    string s1, s2, s;
    int n;
    while (cin >> n && n) {
        cin >> s1 >> s2 >> s;
        string s12 = s1; s12 += s2;
        string fixS = s12;
        bool flag = true;
        int nofs = 0;           // number of steps
        do {
            nofs++;
            s12 = shuffle(s1, s2);
            if (s == s12)
                flag = false;
        } while (s12 != fixS && flag && nofs <= 50);
        cout << (flag ? -1 : nofs) << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

string shuffle (string &s1, string &s2) {

string s;

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

s += s2[i];

s += s1[i];

}

s1 = s.substr(0, s1.length());

s2 = s.substr(s2.length(), s2.length());

return s;

}

int main() {

string s1, s2, s;

int n;

while (cin >> n && n) {

cin >> s1 >> s2 >> s;

string s12 = s1; s12 += s2;

string fixS = s12;

bool flag = true;

int nofs = 0; // number of steps

do {

nofs++;

s12 = shuffle(s1, s2);

if (s == s12)

flag = false;

} while (s12 != fixS && flag && nofs <= 50);

cout << (flag ? -1 : nofs) << endl;

}

return 0;

}

Program code V2.

#include <iostream>
#include <cstring>
using namespace std;
 
int main() {
    int n;
    while( cin >> n && n){
        int count = 0;
        char *first = new char[n+1];
        char *second = new char[n+1];
        char *third = new char[2 * n+1];
        char *result = new char[2 * n+1];
        cin >> first;
        cin >> second;
        cin >> third;
        while(strcmp(result, third) && (count < 51)){
            for(int i = 0; i < n; i++){
                result[2 * i] = second[i];
                result[2 * i + 1] = first[i];
            }
            strncpy(first, &result[0], n);
            strncpy(second, &result[n], n);
            count++;
        }
        cout << ((count < 51) ? count : -1) << endl;
    }
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

int n;

while( cin >> n && n){

int count = 0;

char *first = new char[n+1];

char *second = new char[n+1];

char *third = new char[2 * n+1];

char *result = new char[2 * n+1];

cin >> first;

cin >> second;

cin >> third;

while(strcmp(result, third) && (count < 51)){

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

result[2 * i] = second[i];

result[2 * i + 1] = first[i];

}

strncpy(first, &result[0], n);

strncpy(second, &result[n], n);

count++;

}

cout << ((count < 51) ? count : -1) << endl;

}

return 0;

}

Solution

Repeating the shuffling of the two strings a sufficient number of times, it becomes clear that the variations of the lines repeat with a certain periodicity. In order not to continue the cycle of shuffling if strings began to repeat, we fix the first concatenation of the strings $S_1$ and $S_2$, and if we meet it again, we assume that the string $S$ cannot be obtained. Also a sign of this is that the number of steps exceeded $50$ — from the condition of the problem.

Related Images:

e-olymp 390. Анаграммы

01/05/2019 by Инна Литвиненко

Задача

Анаграммой слова называется любая перестановка всех букв слова. Например, из слова SOLO можно получить 12 анаграмм: SOLO, LOSO, OSLO, OLSO, OSOL, OLOS, SLOO, LSOO, OOLS, OOSL, LOOS, SOOL.

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

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

Слово, количество букв в котором не превышает 14.

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

Количество различных анаграмм.

Тесты

№	Ввод	Вывод
1	SOLO	12
2	ANAGRAM	840
3	PERMUTATION	19958400
4	AAAAA	1
5	AABBBCCC	560

Код (string)

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

int main() {
    string s;
    map <char, int> m;
    cin >> s;
    int l = s.size(), count = 1;
    long long fact[15];
    fact[1] = 1;
    for (int i = 2; i <= l; i++) //заполняем массив факториалов
        fact[i] = fact[i - 1] * i;
    for (int i = 0; i < l; i++) //подсчитываем повторения
        ++m[s[i]];
    for (auto it = m.begin(); it != m.end(); it++) 
        if (it -> second > 1) count *= fact[it -> second];
    cout << fact[l] / count; 
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

string s;

map <char, int> m;

cin >> s;

int l = s.size(), count = 1;

long long fact[15];

fact[1] = 1;

for (int i = 2; i <= l; i++) //заполняем массив факториалов

fact[i] = fact[i - 1] * i;

for (int i = 0; i < l; i++) //подсчитываем повторения

++m[s[i]];

for (auto it = m.begin(); it != m.end(); it++)

if (it -> second > 1) count *= fact[it -> second];

cout << fact[l] / count;

return 0;

}

Код (c-string)

#include <iostream>
#include <cstring>
#include <map>
using namespace std;
 
int main() {
    char s[15]; //равносильно char * s = new char [15], где 15 - максимальный размер строки
    map <char, int> m;
    cin >> s;
    int l, count = 1;
    l = strlen(s);
    long long fact[15];
    fact[1] = 1;
    for (int i = 2; i <= l; i++) //заполняем массив факториалов
        fact[i] = fact[i - 1] * i;
    for (int i = 0; i < l; i++) //подсчитываем повторения
        ++m[s[i]];
    for (auto it = m.begin(); it != m.end(); it++) 
        if (it -> second > 1) count *= fact[it -> second];
    cout << fact[l] / count; 
    return 0;
}

#include <iostream>

#include <cstring>

#include <map>

using namespace std;

int main() {

char s[15]; //равносильно char * s = new char [15], где 15 - максимальный размер строки

map <char, int> m;

cin >> s;

int l, count = 1;

l = strlen(s);

long long fact[15];

fact[1] = 1;

for (int i = 2; i <= l; i++) //заполняем массив факториалов

fact[i] = fact[i - 1] * i;

for (int i = 0; i < l; i++) //подсчитываем повторения

++m[s[i]];

for (auto it = m.begin(); it != m.end(); it++)

if (it -> second > 1) count *= fact[it -> second];

cout << fact[l] / count;

return 0;

}

Решение

Данная задача решается с помощью единой формулы \begin{equation} N_s =\frac {length!}{p_1! × p_2! × \ldots\ × p_n!}\end{equation} где $ length$ — длина строки, а $p_i$ — количество повторений одной буквы $(i = 1, 2, \ldots\ , n$, $ n$ — количество различных букв). Буквы, повторяющиеся один раз, можем опустить, так как их факториал даст единицу, что никак не повлияет на результат.
Длину строки найдем с помощью метода size()(или strlen()), а количество повторений для удобства будем подсчитывать в контейнере map.

Ссылки

Задача 390 на e-olymp

Код на Ideone (string)

Код на Ideone (c-string)

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 1124. Алфавитное граффити

07/04/2019 by Владислав Бебик

Задача

Граффити — один из видов современной варварской живописи. Вася, как и надлежит достойному потомку варваров, решил также заняться этим довольно перспективным с его точки зрения делом и увековечить свое пребывание в школе надписями в стиле граффити.
Так как по рисованию у Васи была твердая «двойка», а он начал еще и изучать английский, после изучения довольно тяжело давшейся ему в произношении третьей буквы английского алфавита он решил увековечивать свои муки в изучении этого опять трудного для него предмета отображением каждого этапа, связанного с изучением очередной буквы, соответствующей надписью на школьной стене.
Художественные изыскания Васи после изучения $3$-й и $7$-й букв приведены в примере выходных данных.
Так как с каждым этапом сделать правильную надпись Васе становилось всё трудней и трудней, напишите программу, которая поможет ему сделать шпаргалку для нанесения очередного узора.

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

Единственное число $N (3 ≤ N ≤ 26) -$ количество изученных букв английского алфавита.

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

Надпись на стене, сделанная Васей после изучения $N$ букв английского алфавита.

Объяснение:

Точками в примере обозначены пробелы для удобства подсчета, так как и с математикой, соответственно, у Васи тоже были проблемы… 🙂

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	3	a..a a.ab aabc
2	7	a……a a…..ab a….abc a…abcd a..abcde a.abcdef aabcdefg

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

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

int main() {
    string s;
    char q='a';
    int n,k,i,j;
    cin >> n;
    for (i=0, k=n-1; i<n; i++, k--) {
        s=s+q;
        q++;
        cout << 'a';
        for (j=0; j<k; j++) cout << " ";
        cout << s << "\n";
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

char q='a';

int n,k,i,j;

cin >> n;

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

s=s+q;

q++;

cout << 'a';

for (j=0; j<k; j++) cout << " ";

cout << s << "\n";

}

return 0;

}

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

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

int main() {
    char s[30];
    char q='a';
    int n,k,i,j;
    cin >> n;
    for (i=0, k=n-1; i<n; i++, k--) {
        s[i]=q;
        q++;
        cout << 'a';
        for (j=0; j<k; j++) cout << " ";
        for (j=0; j<i+1; j++) cout << s[j];
        cout << "\n";
    }
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

char s[30];

char q='a';

int n,k,i,j;

cin >> n;

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

s[i]=q;

q++;

cout << 'a';

for (j=0; j<k; j++) cout << " ";

for (j=0; j<i+1; j++) cout << s[j];

cout << "\n";

}

return 0;

}

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

В каждой строке сначала выводим букву $a$. В первой строке выводим $n-1$ количество пробелов и строку $s$, которая содержит изначально
букву $a$. При переходе на новые строки к строке $s$ будем добавлять новую букву, которая идёт следующей в алфавите от последней буквы данной строки. В каждых последующих строках выводим на один пробел меньше и строку $s$. Выводим новые строки, чтобы в итоге вывести последнюю букву под номером $n$ в алфавите.

Ссылки

Related Images:

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

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

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

Задача

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

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

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

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

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

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

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

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

Тесты

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

Решение

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

#include <iostream>

#include <map>

using namespace std;

int main() {

map <string,int> s;

map <string,int> w;

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

cin >> n >> m;

string word, sent;

while(cin >> word){

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

sent = sent + word;

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

word.pop_back();

sent.pop_back();

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

sent = "";

}

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

}

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

}

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

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

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

Related Images:

e-olymp 8569. Длина строки

27/03/2019 by Александр Мога

Задача

Задана строка. Найдите ее длину.

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

Одна строка, содержащая не более 100 символов.

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

В первой строке выведите входную строку. Во второй строке выведите ее длину.

Тесты

Вход	Выход
Deus Vult! Ave Nikita!	Deus Vult! Ave Nikita! 22
Vive La France	Vive La France 14
Benjamin Franklin could not read.	Benjamin Franklin could not read. 33
Evolution Theory False!	Evolution Theory False! 39
Programming Principles 1	Programming Principles 1 24

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

C-String

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

int main() {
    char s[101];
    cin.getline(s,100);
    cout << s << endl << strlen(s);
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

char s[101];

cin.getline(s,100);

cout << s << endl << strlen(s);

return 0;

}

String

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

int main() {
    string s;
    getline(cin, s);
    cout << s << endl << s.size();
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

getline(cin, s);

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

return 0;

}

Решение

Формулировка задачи сама по себе диктует решение. Вводим строку, а после считаем длину.

Ссылки

e-olymp

ideone(cstring)

ideone(string)

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 увеличивается с каждым проходом цикла на единицу, с середины до нуля — наоборот. При этом для того, чтобы узор с чётной высотой не шел полностью «ёлочкой» создаём условие, при котором по достижению середины количество дважды уменьшится.