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

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

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

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

e-olymp 1075. Умножение многочленов

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

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

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

Вводится в символьной форме два многочлена от [latex]x[/latex] с целыми коэффициентами. Вывести их произведение в порядке убывания степеней — также в символьной форме. Степень исходных многочленов не более [latex]10[/latex], коэффициенты исходных многочленов по модулю не более [latex]{ 10 }^{ 4 }[/latex].

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

В двух строках находятся многочлены.

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

В единственной строке выводится многочлен.

Тесты

№	Входные данные	Выходные данные
1	0 0	0
2	x+1 x-1	x^2-1
3	-5 x^2+x+x-2x^3	10x^3-5x^2-10x
3	x^10+2x^9+3x^8 -1	-x^10-2x^9-3x^8
4	x^10+2x^9+3x^8 0	0
5	x^10+5x^2 x^3-4x	x^13-4x^11+5x^5-20x^3

Решение с использованием класса string

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

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

int str_to_int(string &s, int begin, int end){ //Принимает строку и индексы первого и последнего символов, между которыми в ней (предположительно) записано число (последний не включительно).
    int val = 0;                //Возвращает объект типа int, значение которого равно этому числу.
    bool negative = 0;          //Является ли число отрицательным?
    if(s[begin] == '+') begin++;//Плюс игнорируется.
    else{
        if(s[begin] == '-'){    //Проверка на отрицательность.
            negative = 1;
            begin++;
        }
    }
    for(auto i = begin; i < end; ++i){   //Обработка самих цифр числа.
        val *= 10;
        val += s[i] - 48;
    }
    if(val == 0 && s[begin] != '0') val++; //Если значение получилось равным нулю, но в исходной строке не только ноль, значит, обрабатывается строка вида "+x", в которой при записи опускается единица
    if(negative == 1) val *= -1;
    return val;
}

string int_to_str(int val){ //Возвращает строку с записанным в ней числом val.
    string s, tmp;
    if(val > 0) s.push_back('+'); //Проверка на отрицательность.
    else{
        val *= -1;
        s.push_back('-');
    }
    while(val > 0){
        tmp.push_back(val%10 + 48);  //В tmp хранится запись числа в обратном порядке.
        val /= 10;
    }
    for(int i = tmp.size()-1; i >= 0; --i){ //Переписывание элементво из tmp в s в верном порядке.
        s.push_back(tmp[i]);
    }
    return s;
}

void erase_the_plus(string &s){  //Удаляет плюс, стоящий в начале строки.
    if(s[0] == '+') s.erase(s.begin());
}

void erase_the_one(string &s){   //Удаляет единицу из строк вида "+1", "-1".
    if((s[1] == '1') && (s.size() == 2)) s.erase(s.begin()+1);
}

void analyze(string &s, vector <int> &v){  //Анализирует строку и увеличивает соответствующие элементы вектора на коэфициенты при степенях х.
    if(s.find("x") == string::npos) v[0] += str_to_int(s, 0, s.size()); //Если в строке содержится запись константаы.
    else{
        if(s.find("^") == string::npos) v[1] += str_to_int(s, 0, s.find("x"));  //Строка вида "ax".
        else{
            int power = str_to_int(s, s.find("^") + 1, s.size()); //Строка вида "ax^y".
            v[power] += str_to_int(s, 0, s.find("x"));
        }
    }
}

vector <int> decompose(string &s){ //Разбивает многочлен на слагаемые и возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них.
    vector <int> v(11);
    string cur_s;
    int i = 0;
    while(i < s.size()){
        cur_s.clear();
        cur_s.push_back(s[i]);
        i++;
        while((s[i] != '+') && (s[i] != '-') && (i < s.size())){ //cur_s - анализируемое в данный момент слагаемое.
            cur_s.push_back(s[i]);
            i++;
        }
        analyze(cur_s, v);
    }
    return v;
}

vector <int> multiplicate (vector <int> &a, vector <int> &b){ //Умножение многочленов.
    vector <int> c(21);       //Возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них.
    for(int i = 0; i < c.size(); ++i) c[i] = 0;
    for(int i = 0; i < a.size(); ++i){
        for(int j = 0; j < b.size(); ++j){
            c[i + j] += a[i] * b[j];
        }
    }
    return c;
}

string compose(vector <int> &v){ //Из элементов вектора составляет строку, в которой записан многочлен.
    string s;
    for(int i = v.size() - 1; i >= 2; --i){
        if(v[i] != 0){
            string coef = int_to_str(v[i]); //Коэффициент.
            erase_the_one(coef);
            s = s + coef;
            s.push_back('x');
            s.push_back('^');
            string power = int_to_str(i);  //Степень х.
            erase_the_plus(power);
            s = s + power;
        }
    }
    if(v[1] != 0){   //Записи слагаемых с первой и нулевой степенями х отличаются.
        string coef = int_to_str(v[1]);
        erase_the_one(coef);
        s = s + coef;
        s.push_back('x');
    }
    if(v[0] != 0){
        s = s + int_to_str(v[0]);
    }
    return s;
}

int main() {
    string a,b;
    vector <int> a_decomposed(11, 0);
    vector <int> b_decomposed(11, 0);
    getline(cin, a);    //Ввод многочленов.
    getline(cin, b);
    a_decomposed = decompose(a);
    b_decomposed = decompose(b);
    vector <int> c_decomposed = multiplicate(a_decomposed, b_decomposed);
    string c = compose(c_decomposed);
    erase_the_plus(c);  //Удаляется первый плюс, если он есть.
    if(c.size() > 0) cout << c;
    else cout << 0;       //Если в ответе получаем константу 0.
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

#include <iostream>

#include <string>

#include <vector>

using namespace std;

int str_to_int(string &s, int begin, int end){ //Принимает строку и индексы первого и последнего символов, между которыми в ней (предположительно) записано число (последний не включительно).

int val = 0; //Возвращает объект типа int, значение которого равно этому числу.

bool negative = 0; //Является ли число отрицательным?

if(s[begin] == '+') begin++;//Плюс игнорируется.

else{

if(s[begin] == '-'){ //Проверка на отрицательность.

negative = 1;

begin++;

}

for(auto i = begin; i < end; ++i){ //Обработка самих цифр числа.

val *= 10;

val += s[i] - 48;

}

if(val == 0 && s[begin] != '0') val++; //Если значение получилось равным нулю, но в исходной строке не только ноль, значит, обрабатывается строка вида "+x", в которой при записи опускается единица

if(negative == 1) val *= -1;

return val;

}

string int_to_str(int val){ //Возвращает строку с записанным в ней числом val.

string s, tmp;

if(val > 0) s.push_back('+'); //Проверка на отрицательность.

else{

val *= -1;

s.push_back('-');

}

while(val > 0){

tmp.push_back(val%10 + 48); //В tmp хранится запись числа в обратном порядке.

val /= 10;

}

for(int i = tmp.size()-1; i >= 0; --i){ //Переписывание элементво из tmp в s в верном порядке.

s.push_back(tmp[i]);

}

return s;

}

void erase_the_plus(string &s){ //Удаляет плюс, стоящий в начале строки.

if(s[0] == '+') s.erase(s.begin());

}

void erase_the_one(string &s){ //Удаляет единицу из строк вида "+1", "-1".

if((s[1] == '1') && (s.size() == 2)) s.erase(s.begin()+1);

}

void analyze(string &s, vector <int> &v){ //Анализирует строку и увеличивает соответствующие элементы вектора на коэфициенты при степенях х.

if(s.find("x") == string::npos) v[0] += str_to_int(s, 0, s.size()); //Если в строке содержится запись константаы.

else{

if(s.find("^") == string::npos) v[1] += str_to_int(s, 0, s.find("x")); //Строка вида "ax".

else{

int power = str_to_int(s, s.find("^") + 1, s.size()); //Строка вида "ax^y".

v[power] += str_to_int(s, 0, s.find("x"));

}

vector <int> decompose(string &s){ //Разбивает многочлен на слагаемые и возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них.

vector <int> v(11);

string cur_s;

int i = 0;

while(i < s.size()){

cur_s.clear();

cur_s.push_back(s[i]);

i++;

while((s[i] != '+') && (s[i] != '-') && (i < s.size())){ //cur_s - анализируемое в данный момент слагаемое.

cur_s.push_back(s[i]);

i++;

}

analyze(cur_s, v);

}

return v;

}

vector <int> multiplicate (vector <int> &a, vector <int> &b){ //Умножение многочленов.

vector <int> c(21); //Возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них.

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

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

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

c[i + j] += a[i] * b[j];

}

return c;

}

string compose(vector <int> &v){ //Из элементов вектора составляет строку, в которой записан многочлен.

string s;

for(int i = v.size() - 1; i >= 2; --i){

if(v[i] != 0){

string coef = int_to_str(v[i]); //Коэффициент.

erase_the_one(coef);

s = s + coef;

s.push_back('x');

s.push_back('^');

string power = int_to_str(i); //Степень х.

erase_the_plus(power);

s = s + power;

}

if(v[1] != 0){ //Записи слагаемых с первой и нулевой степенями х отличаются.

string coef = int_to_str(v[1]);

erase_the_one(coef);

s = s + coef;

s.push_back('x');

}

if(v[0] != 0){

s = s + int_to_str(v[0]);

}

return s;

}

int main() {

string a,b;

vector <int> a_decomposed(11, 0);

vector <int> b_decomposed(11, 0);

getline(cin, a); //Ввод многочленов.

getline(cin, b);

a_decomposed = decompose(a);

b_decomposed = decompose(b);

vector <int> c_decomposed = multiplicate(a_decomposed, b_decomposed);

string c = compose(c_decomposed);

erase_the_plus(c); //Удаляется первый плюс, если он есть.

if(c.size() > 0) cout << c;

else cout << 0; //Если в ответе получаем константу 0.

return 0;

}

Нажмите, чтобы выполнить его на ideone.com.

Описание

Сначала в функции main объявляются две строки a и b. В них водятся исходные два многочлена. Но в форме строк, особенно учитывая, что подобные слагаемые не всегда приведены, умножать многочлены не удобно. Потому объявляются три вектора: a_decomposed, b_decomposed и c_decomposed. Первые два имеют размер [latex]11[/latex], поскольку в условии сказано, что многочлены могут быть от нулевой до десятой степени включительно. В них элемент с индексом [latex]i[/latex] равняется коэффициенту при слагаемом многочлена, в котором [latex]x[/latex] имеет степень [latex]i[/latex]. Они заполняются при помощи функции decompose. В ней при помощи функции analyze отдельно анализируется каждое слагаемое многочлена, и результат заносится в вектор. c_decomposed хранит коэффициенты многочлена, полученного умножением двух исходных. Значения его элементов вычисляются при помощи функции multiplicate. После в ходе работы функции compose многочлен в требуемой форме записывается в строку c. Далее, если её первым символом является [latex]+[/latex], он удаляется из строки. Наконец, если c — непустая строка, она выводится. Иначе выводится [latex]0[/latex].

Решение с использованием c-string

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

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

int str_to_int(char *s, int begin, int end){//Принимает адрес первого элемента строки и индексы первого и последнего символов, между которыми в ней (предположительно) записано число (последний не включительно).
    int val = 0;        //Возвращает объект типа int, значение которого равно этому числу.
    bool negative = 0;  //Является ли число отрицательным?
    if(s[begin] == '+') begin++;//Плюс игнорируется.
    else{
        if(s[begin] == '-'){    //Проверка на отрицательность.
            negative = 1;
            begin++;
        }
    }
    for(auto i = begin; i < end; ++i){   //Обработка самих цифр числа.
        val *= 10;
        val += s[i] - 48;
    }
    if(val == 0 && s[begin] != '0') val++; //Если значение получилось равным нулю, но в исходной строке не только ноль, значит, обрабатывается строка вида "+x", в которой при записи опускается единица
    if(negative == 1) val *= -1;
    return val;
}

void int_to_str(int val, char *s){ //Записывает в строку s число val.
    char tmp[5];
    if(val > 0) s[0] = '+';  //Проверка на отрицательность.
    else{
        val *= -1;
        s[0] = '-';
    }
    int i = 0;
    while(val > 0){
        tmp[i] = (val%10 + 48); //В tmp хранится запись числа в обратном порядке.
        val /= 10;
        i++;
    }
    tmp[i] = 0;
    int j = 1;
    for(i = strlen(tmp)-1; i >= 0; --i){ //Переписывание элементво из tmp в s в верном порядке.
        s[j] = tmp[i];
        j++;
    }
    s[j] = 0; //Если строка получилась короче пяти символов, нужно поставить после последнего нулевой символ.
}

void erase_the_plus(char *s){   //Удаляет плюс, стоящий в начале строки.
    if(s[0] == '+'){
        for(int i = 0; s[i] != 0; ++i){
            s[i] = s[i+1];
        }
    }
}

void erase_the_one(char *s){        //Удаляет единицу из строк вида "+1", "-1".
    if((s[1] == '1') && (strlen(s) == 2)){
        s[1] = 0;
    }
}

void analyze(char *s, vector <int> &v){       //Анализирует строку и увеличивает соответствующие элементы вектора на коэфициенты при степенях х.
    if(strchr(s, 'x') == NULL) v[0] += str_to_int(s, 0, strlen(s));     //Если в строке содержится запись константаы.
    else{
        if(strchr(s, '^') == NULL) v[1] += str_to_int(s, 0, strchr(s, 'x') - s);//Строка вида "ax".
        else{
            int power = str_to_int(s, strchr(s, '^') - s + 1, strlen(s));
            v[power] += str_to_int(s, 0, strchr(s, 'x') - s);
        }
    }
}
 
vector <int> decompose(char *s){//Разбивает многочлен на слагаемые и возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них.
    vector <int> v(11);
    char cur_s[10];
    int i = 0, j;
    while(s[i] != 0){
        //cur_s[0] = 0;
        cur_s[0] = s[i];
        i++;
        j = 1;
        while((s[i] != '+') && (s[i] != '-') && (s[i] != 0)){   //cur_s - анализируемое в данный момент слагаемое.
            cur_s[j] = s[i];
            i++;
            j++;
        }
        cur_s[j] = 0;
        analyze(cur_s, v);
    }
    return v;
}
 
vector <int> multiplicate (vector <int> &a, vector <int> &b){ //Умножение многочленов.
    vector <int> c(21);   //Возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них.
    for(int i = 0; i < c.size(); ++i) c[i] = 0;
    for(int i = 0; i < a.size(); ++i){
        for(int j = 0; j < b.size(); ++j){
            c[i + j] += a[i] * b[j];
        }
    }
    return c;
}
 
void compose(char *s, vector <int> &v){   //Из элементов вектора составляет строку, в которой записан многочлен.
    for(int i = v.size() - 1; i >= 2; --i){
        if(v[i] != 0){
            char coef[6];   //Коэффициент.
            int_to_str(v[i], coef);
            erase_the_one(coef);
            strcat(s, coef);
            strcat(s, "x");
            strcat(s, "^");
            char power[2];  //Степень х.
            int_to_str(i, power);
            erase_the_plus(power);
            strcat(s, power);
        }
    }
    if(v[1] != 0){  //Записи слагаемых с первой и нулевой степенями х отличаются.
        char coef[6];
        int_to_str(v[1], coef);
        erase_the_one(coef);
        strcat(s, coef);
        strcat(s, "x");
    }
    if(v[0] != 0){
        char coef[6];
        int_to_str(v[0], coef);
        strcat(s, coef);
    }
}
 
int main() {
    char *a, *b;
    int max_number_of_symbols = 100;
    a = new char[max_number_of_symbols];
    b = new char[max_number_of_symbols];
    vector <int> a_decomposed(11, 0);
    vector <int> b_decomposed(11, 0);
    
    cin.getline(a, max_number_of_symbols);  //Ввод многочленов.
    cin.getline(b, max_number_of_symbols);
    a_decomposed = decompose(a);
    b_decomposed = decompose(b);
    
    vector <int> c_decomposed = multiplicate(a_decomposed, b_decomposed);
    char *c;
    c = new char[max_number_of_symbols];
    compose(c, c_decomposed);
    erase_the_plus(c);  //Удаляется первый плюс, если он есть.
    if(strlen(c) > 0) cout << c;
    else cout << 0;       //Если в ответе получаем константу 0.
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

#include <iostream>

#include <cstring>

#include <vector>

using namespace std;

int str_to_int(char *s, int begin, int end){//Принимает адрес первого элемента строки и индексы первого и последнего символов, между которыми в ней (предположительно) записано число (последний не включительно).

int val = 0; //Возвращает объект типа int, значение которого равно этому числу.

bool negative = 0; //Является ли число отрицательным?

if(s[begin] == '+') begin++;//Плюс игнорируется.

else{

if(s[begin] == '-'){ //Проверка на отрицательность.

negative = 1;

begin++;

}

for(auto i = begin; i < end; ++i){ //Обработка самих цифр числа.

val *= 10;

val += s[i] - 48;

}

if(negative == 1) val *= -1;

return val;

}

void int_to_str(int val, char *s){ //Записывает в строку s число val.

char tmp[5];

if(val > 0) s[0] = '+'; //Проверка на отрицательность.

else{

val *= -1;

s[0] = '-';

}

int i = 0;

while(val > 0){

tmp[i] = (val%10 + 48); //В tmp хранится запись числа в обратном порядке.

val /= 10;

i++;

}

tmp[i] = 0;

int j = 1;

for(i = strlen(tmp)-1; i >= 0; --i){ //Переписывание элементво из tmp в s в верном порядке.

s[j] = tmp[i];

j++;

}

s[j] = 0; //Если строка получилась короче пяти символов, нужно поставить после последнего нулевой символ.

}

void erase_the_plus(char *s){ //Удаляет плюс, стоящий в начале строки.

if(s[0] == '+'){

for(int i = 0; s[i] != 0; ++i){

s[i] = s[i+1];

}

void erase_the_one(char *s){ //Удаляет единицу из строк вида "+1", "-1".

if((s[1] == '1') && (strlen(s) == 2)){

s[1] = 0;

}

void analyze(char *s, vector <int> &v){ //Анализирует строку и увеличивает соответствующие элементы вектора на коэфициенты при степенях х.

if(strchr(s, 'x') == NULL) v[0] += str_to_int(s, 0, strlen(s)); //Если в строке содержится запись константаы.

else{

if(strchr(s, '^') == NULL) v[1] += str_to_int(s, 0, strchr(s, 'x') - s);//Строка вида "ax".

else{

int power = str_to_int(s, strchr(s, '^') - s + 1, strlen(s));

v[power] += str_to_int(s, 0, strchr(s, 'x') - s);

}

vector <int> decompose(char *s){//Разбивает многочлен на слагаемые и возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них.

vector <int> v(11);

char cur_s[10];

int i = 0, j;

while(s[i] != 0){

//cur_s[0] = 0;

cur_s[0] = s[i];

i++;

j = 1;

while((s[i] != '+') && (s[i] != '-') && (s[i] != 0)){ //cur_s - анализируемое в данный момент слагаемое.

cur_s[j] = s[i];

i++;

j++;

}

cur_s[j] = 0;

analyze(cur_s, v);

}

return v;

}

vector <int> multiplicate (vector <int> &a, vector <int> &b){ //Умножение многочленов.

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

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

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

c[i + j] += a[i] * b[j];

}

return c;

}

void compose(char *s, vector <int> &v){ //Из элементов вектора составляет строку, в которой записан многочлен.

for(int i = v.size() - 1; i >= 2; --i){

if(v[i] != 0){

char coef[6]; //Коэффициент.

int_to_str(v[i], coef);

erase_the_one(coef);

strcat(s, coef);

strcat(s, "x");

strcat(s, "^");

char power[2]; //Степень х.

int_to_str(i, power);

erase_the_plus(power);

strcat(s, power);

}

if(v[1] != 0){ //Записи слагаемых с первой и нулевой степенями х отличаются.

char coef[6];

int_to_str(v[1], coef);

erase_the_one(coef);

strcat(s, coef);

strcat(s, "x");

}

if(v[0] != 0){

char coef[6];

int_to_str(v[0], coef);

strcat(s, coef);

}

int main() {

char *a, *b;

int max_number_of_symbols = 100;

a = new char[max_number_of_symbols];

b = new char[max_number_of_symbols];

vector <int> a_decomposed(11, 0);

vector <int> b_decomposed(11, 0);

cin.getline(a, max_number_of_symbols); //Ввод многочленов.

cin.getline(b, max_number_of_symbols);

a_decomposed = decompose(a);

b_decomposed = decompose(b);

vector <int> c_decomposed = multiplicate(a_decomposed, b_decomposed);

char *c;

c = new char[max_number_of_symbols];

compose(c, c_decomposed);

erase_the_plus(c); //Удаляется первый плюс, если он есть.

if(strlen(c) > 0) cout << c;

else cout << 0; //Если в ответе получаем константу 0.

return 0;

}

Нажмите, чтобы выполнить его на ideone.com.

Описание

Алгоритм решения тот же. Следует отметить: поскольку объекты типа char* «не знают» свою длину, и в силу других причин, в некоторых местах программы используются «магические числа». Однако они не взяты случайно, а продиктованы условием задачи (к примеру, тем, что максимальная степень исходных многочленов — [latex]10[/latex] и т.п.). Только подходящее значение переменной max_number_of_symbols было найдено эмпирически.

Решение на Java

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

import java.util.*;

class Main
{
    static int strToInt(String s, int begin, int end){ //Принимает строку и индексы первого и последнего символов, между которыми в ней (предположительно) записано число (последний не включительно).
        int val = 0;           //Возвращает объект типа int, значение которого равно этому числу.
        boolean negative = false;      //Является ли число отрицательным?
        if(s.charAt(begin) == '+') begin++;//Плюс игнорируется.
        else{
            if(s.charAt(begin) == '-'){   //Проверка на отрицательность.
                negative = true;
                begin++;
            }
        }
        for(int i = begin; i < end; ++i){  //Обработка самих цифр числа.
            val *= 10;
            val += s.charAt(i) - 48;
        }
        if(val == 0 && s.charAt(begin) != '0') val++; //Если значение получилось равным нулю, но в исходной строке не только ноль, значит, обрабатывается строка вида "+x", в которой при записи опускается единица
        if(negative == true) val *= -1;
        return val;
    }
    
    static String intToStr(int val){ //Возвращает строку с записанным в ней числом val.
        String s = "", tmp = "";
        if(val > 0) s = s + "+"; //Проверка на отрицательность.
        else{
            val *= -1;
            s = s + "-";
        }
        while(val > 0){
            tmp = tmp + Integer.toString(val%10); //В tmp хранится запись числа в обратном порядке.
            val /= 10;
        }
        for(int i = tmp.length()-1; i >= 0; --i){ //Переписывание элементво из tmp в s в верном порядке.
            s = s + tmp.charAt(i);
        }
        return s;
    }

    static String eraseThePlus(String s){  //Удаляет плюс, стоящий в начале строки.
        if(s.charAt(0) == '+') s = s.substring(1, s.length());
        return s;
    }
 
    static String eraseTheOne(String s){   //Удаляет единицу из строк вида "+1x", "-1x^y".
        if((s.charAt(1) == '1') && (s.length() == 2)) s = s.charAt(0) + s.substring(2, s.length());
        return s;
    }

    static void analyze(String s, Vector v){  //Анализирует строку и увеличивает соответствующие элементы вектора на коэфициенты при степенях х.
        for(int i = 0; i < 11; ++i) v.addElement(0);
        if(s.indexOf('x') == -1) v.set(0, (int)(v.elementAt(0)) + strToInt(s, 0, s.length())); 
        else{
            if(s.indexOf('^') == -1) v.set(1, (int)(v.elementAt(1)) + strToInt(s, 0, s.indexOf("x")));  //Строка вида "ax".
            else{
                int power = strToInt(s, s.indexOf("^") + 1, s.length()); //Строка вида "ax^y".
                v.set(power, (int)(v.elementAt(power)) + strToInt(s, 0, s.indexOf("x")));
            }
        }
    }
    
    static Vector decompose(String s){ //Разбивает многочлен на слогаемые и возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них.
        Vector v = new Vector();
        String cur_s = "";
        int i = 0;
        while(i < s.length()){
            cur_s  = "";
            cur_s = cur_s + s.charAt(i);
            i++;
            while((i < s.length()) && (s.charAt(i) != '+') && (s.charAt(i) != '-')){ //cur_s - анализируемое в данный момент слогаемое.
                cur_s = cur_s + s.charAt(i);
                i++;
            }
            analyze(cur_s, v);
        }
        return v;
    }

    static Vector multiplicate (Vector a, Vector b){ //Умножение многочленов.
        Vector c = new Vector();             //Возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них.
        for(int i = 0; i < 21; ++i) c.addElement(0);
        for(int i = 0; i < 11; ++i){
            for(int j = 0; j < 11; ++j){
                c.set(i+j, ((int)(c.elementAt(i+j)))+((int)(a.elementAt(i)))*((int)(b.elementAt(j))));
            }
        }
        return c;
    }

    static String compose(Vector v){ //Из элементов вектора составляет строку, в которой записан многочлен.
        String s = "";
        for(int i = v.size() - 1; i >= 2; --i){
            if((int)v.elementAt(i) != 0){
                String coef = intToStr((int)v.elementAt(i)); //Коэффициент.
                coef = eraseTheOne(coef);
                s = s + coef;
                s = s + "x";
                s = s + "^";
                String power = intToStr(i);  //Степень х.
                power = eraseThePlus(power);
                s = s + power;
            }
        }
        if((int)v.elementAt(1) != 0){   //Записи слогаемых с первой и нулевой степенями х отличаются.
            String coef = intToStr((int)v.elementAt(1));
            coef = eraseTheOne(coef);
            s = s + coef;
            s = s + "x";
        }
        if((int)v.elementAt(0) != 0){
            s = s + intToStr((int)v.elementAt(0));
        }
        return s;
    }

    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        String a = in.nextLine();
        String b = in.nextLine();
        String c = new String();
        Vector a_decomposed = new Vector(11);
        Vector b_decomposed = new Vector(11);
        a_decomposed = decompose(a);
        b_decomposed = decompose(b);
        Vector c_decomposed = multiplicate(a_decomposed, b_decomposed);
        c = compose(c_decomposed);
        if(c.length() > 0){
            c = eraseThePlus(c); //Удаляется первый плюс, если он есть.
            System.out.print(c);
        }
        else System.out.print(0); //Если в ответе получаем константу 0.
    }
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

import java.util.*;

class Main

{

static int strToInt(String s, int begin, int end){ //Принимает строку и индексы первого и последнего символов, между которыми в ней (предположительно) записано число (последний не включительно).

int val = 0; //Возвращает объект типа int, значение которого равно этому числу.

boolean negative = false; //Является ли число отрицательным?

if(s.charAt(begin) == '+') begin++;//Плюс игнорируется.

else{

if(s.charAt(begin) == '-'){ //Проверка на отрицательность.

negative = true;

begin++;

}

for(int i = begin; i < end; ++i){ //Обработка самих цифр числа.

val *= 10;

val += s.charAt(i) - 48;

}

if(val == 0 && s.charAt(begin) != '0') val++; //Если значение получилось равным нулю, но в исходной строке не только ноль, значит, обрабатывается строка вида "+x", в которой при записи опускается единица

if(negative == true) val *= -1;

return val;

}

static String intToStr(int val){ //Возвращает строку с записанным в ней числом val.

String s = "", tmp = "";

if(val > 0) s = s + "+"; //Проверка на отрицательность.

else{

val *= -1;

s = s + "-";

}

while(val > 0){

tmp = tmp + Integer.toString(val%10); //В tmp хранится запись числа в обратном порядке.

val /= 10;

}

for(int i = tmp.length()-1; i >= 0; --i){ //Переписывание элементво из tmp в s в верном порядке.

s = s + tmp.charAt(i);

}

return s;

}

static String eraseThePlus(String s){ //Удаляет плюс, стоящий в начале строки.

if(s.charAt(0) == '+') s = s.substring(1, s.length());

return s;

}

static String eraseTheOne(String s){ //Удаляет единицу из строк вида "+1x", "-1x^y".

if((s.charAt(1) == '1') && (s.length() == 2)) s = s.charAt(0) + s.substring(2, s.length());

return s;

}

static void analyze(String s, Vector v){ //Анализирует строку и увеличивает соответствующие элементы вектора на коэфициенты при степенях х.

for(int i = 0; i < 11; ++i) v.addElement(0);

if(s.indexOf('x') == -1) v.set(0, (int)(v.elementAt(0)) + strToInt(s, 0, s.length()));

else{

if(s.indexOf('^') == -1) v.set(1, (int)(v.elementAt(1)) + strToInt(s, 0, s.indexOf("x"))); //Строка вида "ax".

else{

int power = strToInt(s, s.indexOf("^") + 1, s.length()); //Строка вида "ax^y".

v.set(power, (int)(v.elementAt(power)) + strToInt(s, 0, s.indexOf("x")));

}

static Vector decompose(String s){ //Разбивает многочлен на слогаемые и возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них.

Vector v = new Vector();

String cur_s = "";

int i = 0;

while(i < s.length()){

cur_s = "";

cur_s = cur_s + s.charAt(i);

i++;

while((i < s.length()) && (s.charAt(i) != '+') && (s.charAt(i) != '-')){ //cur_s - анализируемое в данный момент слогаемое.

cur_s = cur_s + s.charAt(i);

i++;

}

analyze(cur_s, v);

}

return v;

}

static Vector multiplicate (Vector a, Vector b){ //Умножение многочленов.

Vector c = new Vector(); //Возвращает вектор, индексы элементов которого соответствуют степеням х, а сами элементы - коэффициентам при них.

for(int i = 0; i < 21; ++i) c.addElement(0);

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

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

c.set(i+j, ((int)(c.elementAt(i+j)))+((int)(a.elementAt(i)))*((int)(b.elementAt(j))));

}

return c;

}

static String compose(Vector v){ //Из элементов вектора составляет строку, в которой записан многочлен.

String s = "";

for(int i = v.size() - 1; i >= 2; --i){

if((int)v.elementAt(i) != 0){

String coef = intToStr((int)v.elementAt(i)); //Коэффициент.

coef = eraseTheOne(coef);

s = s + coef;

s = s + "x";

s = s + "^";

String power = intToStr(i); //Степень х.

power = eraseThePlus(power);

s = s + power;

}

if((int)v.elementAt(1) != 0){ //Записи слогаемых с первой и нулевой степенями х отличаются.

String coef = intToStr((int)v.elementAt(1));

coef = eraseTheOne(coef);

s = s + coef;

s = s + "x";

}

if((int)v.elementAt(0) != 0){

s = s + intToStr((int)v.elementAt(0));

}

return s;

}

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

{

Scanner in = new Scanner(System.in);

String a = in.nextLine();

String b = in.nextLine();

String c = new String();

Vector a_decomposed = new Vector(11);

Vector b_decomposed = new Vector(11);

a_decomposed = decompose(a);

b_decomposed = decompose(b);

Vector c_decomposed = multiplicate(a_decomposed, b_decomposed);

c = compose(c_decomposed);

if(c.length() > 0){

c = eraseThePlus(c); //Удаляется первый плюс, если он есть.

System.out.print(c);

}

else System.out.print(0); //Если в ответе получаем константу 0.

}

Нажмите, чтобы выполнить его на ideone.com.

Related Images:

Лабиринт

02/07/2016 by Маша Лукьянова

Условие:

Имя входного файла: стандартный поток ввода

Имя выходного файла: стандартный поток вывода

Ограничение по времени: 2 second

Ограничение по памяти: 64 мегабайт

Задан лабиринт [latex] N \times N [/latex], некоторые клетки которого могут быть заняты. Дан путь робота длины [latex] k [/latex] по этому лабиринту без указания его начального положения. Известно, что робот до начала движения стоит в одной из свободных клеток. Необходимо определить наименьшее количество передвижений по пути, после которого можно точно определить, где находится робот.

Задача взята из 1-го раунда KPI OPEN 2013 года.

Формат входного файла:

Первая строка входного файла содержит два целых числа через пробел $$ N (1 \leq N \leq 100) $$ и $$k (0 \leq k \leq 10^{5}) $$. В следующих [latex] N [/latex] строках задана карта лабиринта как совокупность 0 и 1 без пробелов: 1 – занятая клетка, 0 – свободная. В последней строке дана последовательность из $$ k (0 \leq k \leq 10^{5} ) $$ символов. Символы задают движение робота по лабиринту: символ [latex] U [/latex] — вверх, [latex] D [/latex] — вниз, [latex] R [/latex] —вправо, [latex] L [/latex] — влево. Других символов в строке передвижений нет, все символы в верхнем регистре латиницы.

Формат выходного файла:

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

Тесты:

№	Входные данные	Выходные данные
1	2 0 11 01	0
2	2 0 11 11	-1
3	2 1 11 01 R	-1
4	3 3 000 010 000 RDU	2
5	5 5 00010 10001 00100 10100 01101 RDUUU	4

Решение:

Если попробовать решить эту задачу «в лоб», то решение не будет удовлетворять пределу по времени, так как в худшем случае, нам надо перебрать $$ 10^{4} $$ возможных начальных позиций и совершить из них $$ 10^{5} $$ ходов, что в результате дает $$ 10^{9} $$ операций.

Решение «в лоб»:

Заведем список позиций в лабиринте, которым соответствуют элементы матрицы, в которые может попасть робот. В изначальном состоянии, без просмотра пути передвижения робота, это будут все позиции в лабиринте, где значение равно $$ 0 $$. После чего, проходя путь робота по шагам, будем для всех позиций в списке проверять:
- Если мы вышли за границу матрицы, или в клетке, в которую мы собираемся перейти стоит $$ 1 $$, тогда удаляем эту позицию, поскольку она для нас недостижима.
- Иначе ничего не делаем.
Если количество текущих вариантов пути стало равным $$ 1 $$, то мы запоминаем количество ходов при которой была достигнута данная ситуация.
Так будем делать до тех пор, пока робот закончил свой путь.
Если после всех проделанных нами операций остался один вариант полностью пройденного пути, тогда ответ найден. А именно это будет ход, после которого у нас кол-во удовлетворяющих позиций стало равным $$ 1 $$. В любом другом случае ответ нельзя определить однозначно.

Другая идея состоит в том, чтобы построить карту «переходов», в которой будет храниться номер хода, на котором робот впервые попал в эту клетку и ее координаты. Эта карта играет роль некоторого шаблона полного пути робота и «накладывая» его на каждый элемент матрицы в качестве начальной позиции, мы проверяем мог ли данный элемент матрицы служить «пунктом отправления» робота. Если такой элемент есть и он единственен, значит, можно однозначно определить начальное положение робота, но для того чтобы определить минимальное количество требуемых ходов-нужно последовательно удалять последние ходы из карты, «накладывая» изменившийся шаблон на каждый элемент, до тех пор, пока количество элементов удовлетворяющих шаблону не возрастет. Что значит, что мы получим номер решающего хода после которого судьба робота решится однозначно, значит ответом будет предыдущий ход. Стоит отметить, что если в карте останется всего лишь один элемент (соответствующий первому ходу), то расположение робота определялось однозначно первым ходом.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <stack>
#include <set>
#include <list>
#include <map>
 
#define ll long long int
#define X first
#define Y second
#include <iostream>

using namespace std;

int main() {
    int n, k;
    cin >> n >> k;
    char maze[n][n];//лабиринт
    for(int i = 0; i < n; ++i){
        getchar();
        for(int j = 0; j < n; ++j){
            maze[i][j] = getchar();
        }
    }
    getchar();
    char path[k+1]; //путь
    for(int i = 0; i < k; ++i){
        path[i + 1] = getchar();
    }
    set<pair<int, int> > visited; 
        //ячейки, в которых мы побывали
    map<int, pair<int, int> > nodes; 
        // узлы, которые должен пройти робот (номер хода, координаты)
    pair<int, int> cur = {0, 0};
    visited.insert(cur);
    nodes[0] = cur; 
    //проходим весь путь
    for(int i = 1; i <= k; ++i){
        if(path[i] == 'L'){
            --cur.X;
            if(!visited.count(cur)){
                nodes[i] = cur;
                visited.insert(cur);
            }
        }else if(path[i] == 'R'){
            ++cur.X;
            if(!visited.count(cur)){
                nodes[i] = cur;
                visited.insert(cur);
            }
        }else if(path[i] == 'U'){
            --cur.Y;
            if(!visited.count(cur)){
                nodes[i] = cur;
                visited.insert(cur);
            }
        }else if(path[i] == 'D'){
            ++cur.Y;
            if(!visited.count(cur)){
                nodes[i] = cur;
                visited.insert(cur);
            }
        }
    }
    int count = 0;
    map<int, int> ans; bool ok = false;
    for(; nodes.size();){
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                for(pair<int, pair<int, int> > a : nodes){
                    if(j + a.Y.X < 0 || j + a.Y.X >= n ||
                              // не вышли ли за пределы по строкам
                        i + a.Y.Y < 0 || i + a.Y.Y >= n || 
                              // не вышли ли за пределы по столбцам
                        maze[i + a.Y.Y][j + a.Y.X] == '1'){ 
                              //не попали ли на 1-цу
                        --count;
                        break;
                    }
                }
                ++count;
            }
        }
        auto t = --nodes.end();
        ans[count] = t->X;
        nodes.erase(t);
        count = 0;
        if(ans.size() == 2) break;
        if(!ok){
            ok = 1;
            if(ans.begin()->X != 1){
                cout << -1 << endl;
                return 0;
            }
        }
    }
    if(ans.size() == 1 && ans.begin()->X == 1){
        cout << ans.begin()->Y << endl;
    }else if(ans.size() == 2 && ans.begin()->X == 1){
        cout << ans.begin()->Y << endl;
    }else{
        cout << -1 << endl;
    }
}

100

101

102

103

104

105

106

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

#include <stack>

#include <set>

#include <list>

#include <map>

#define ll long long int

#define X first

#define Y second

#include <iostream>

using namespace std;

int main() {

int n, k;

cin >> n >> k;

char maze[n][n];//лабиринт

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

getchar();

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

maze[i][j] = getchar();

}

getchar();

char path[k+1]; //путь

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

path[i + 1] = getchar();

}

set<pair<int, int> > visited;

//ячейки, в которых мы побывали

map<int, pair<int, int> > nodes;

// узлы, которые должен пройти робот (номер хода, координаты)

pair<int, int> cur = {0, 0};

visited.insert(cur);

nodes[0] = cur;

//проходим весь путь

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

if(path[i] == 'L'){

--cur.X;

if(!visited.count(cur)){

nodes[i] = cur;

visited.insert(cur);

}

}else if(path[i] == 'R'){

++cur.X;

if(!visited.count(cur)){

nodes[i] = cur;

visited.insert(cur);

}

}else if(path[i] == 'U'){

--cur.Y;

if(!visited.count(cur)){

nodes[i] = cur;

visited.insert(cur);

}

}else if(path[i] == 'D'){

++cur.Y;

if(!visited.count(cur)){

nodes[i] = cur;

visited.insert(cur);

}

int count = 0;

map<int, int> ans; bool ok = false;

for(; nodes.size();){

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

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

for(pair<int, pair<int, int> > a : nodes){

if(j + a.Y.X < 0 || j + a.Y.X >= n ||

// не вышли ли за пределы по строкам

i + a.Y.Y < 0 || i + a.Y.Y >= n ||

// не вышли ли за пределы по столбцам

maze[i + a.Y.Y][j + a.Y.X] == '1'){

//не попали ли на 1-цу

--count;

break;

}

++count;

}

auto t = --nodes.end();

ans[count] = t->X;

nodes.erase(t);

count = 0;

if(ans.size() == 2) break;

if(!ok){

ok = 1;

if(ans.begin()->X != 1){

cout << -1 << endl;

return 0;

}

if(ans.size() == 1 && ans.begin()->X == 1){

cout << ans.begin()->Y << endl;

}else if(ans.size() == 2 && ans.begin()->X == 1){

cout << ans.begin()->Y << endl;

}else{

cout << -1 << endl;

}

Submission.

Related Images:

Функция Эйлера

01/07/2016 by Лена Наумова

Условие

В теории чисел известна функция Эйлера $latex \varphi(n)$ — количество чисел, меньших $latex n$ и взаимно простых с ним. Напомним, два числа взаимно просты, если у них нет общих делителей, кроме единицы.

Расширим понятие функции Эйлера на строки. Пусть $latex s$ — непустая строка над алфавитом {$latex a$ .. $latex z$}, а $latex k$ — целое положительное число. Тогда $latex s \cdot k$ по определению — строка $latex t = \underbrace{s \circ s \circ \ldots \circ s}_{\text{k}}$ (конкатенация $latex s$ самой с собой $latex k$ раз). В таком случае будем говорить, что строка $latex s$ — делитель строки $latex t$. Например, «ab» — делитель строки «ababab».

Две непустые строки $latex s$ и $latex t$ будем называть взаимно простыми, если не существует строки $latex u$ такой, что она — делитель и для $latex s$, и для $latex t$. Тогда функция Эйлера $latex \varphi(s)$ для строки $latex s$ по определению — количество непустых строк над тем же алфавитом {$latex a$ .. $latex z$}, меньших $latex s$ по длине, и взаимно простых с ней.

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

Во входном файле дана строка $latex s$ длиной от $latex 1$ до $latex 10^5$ символов включительно, состоящая из маленьких латинских букв.

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

Вычислите значение $latex \varphi(s)$ и выведите единственное число — остаток от его деления на $latex 1000000007 (10^9 + 7)$.

Решение

Очевидно, что когда строка $latex s$ длины $latex n$ не имеет делителей, кроме самой себя, любая строка длины меньшей, чем $latex n$, будет взаимно простой с $latex s$. Тогда достаточно посчитать количество всех возможных строк длины от $latex 1$ до $latex n-1$ включительно. Для некоторого $latex k$ количество строк этой длины будет равно $latex 26^k$. Тогда количество $latex m$ всех возможных строк длины от $latex 1$ до $latex n-1$ будет вычисляться по следующей формуле: $latex m=\sum\limits_{k=1}^{n-1} 26^k$.

Теперь рассмотрим случай, когда строка имеет делители. Поскольку строка $latex s$ в таком случае является конкатенацией некоторого количества одинаковых строк меньшей длины, найдём эту самую подстроку, кторая является минимальным (кратчайшим) делителем строки $latex s$. Для этого воспользуемся префикс-функцией. Она возвращает вектор $latex pi$ значений для всех подстрок строки $latex s$, которые являются префиксами $latex s$, где значение — максимальная длина префикса строки, совпадающего с её суффиксом. Тогда на $latex n-1$-ом месте вектора $latex pi$ будет стоять длина наибольшего префикса строки $latex s$, а оставшийся «кусочек» строки $latex s$ будет представлять собой минимальный делитель.

Осталось вычислить количество строк, которые не взаимно просты с $latex s$. Пусть k — длина минимального делителя $latex s$. Тогда все строки, являющиеся конкатенациями этого делителя, не будут взаимно простыми с $latex s$. Для подсчёта их количества достаточно поделить длину исходной строки на k, но ответ будет на единицу меньше, поскольку в этой формуле учитывается и сама строка $latex s$, как собственный делитель.

Для окончательного ответа на задачу остаётся вычесть из общего количества строк количество не взаимно простых с $latex s$.

Тесты

№	Входные данные	Выходные данные
1	aa	25
2	abab	18277
3	abcdefgh	353082526
4	aaaaaab	321272406
5	aaaaaaa	321272406

Программный код

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

const int MOD = 1e9+7;

vector<int> prefix_function(string s) {
    int n = s.length();
    vector<int> pi(n);
    pi[0] = 0;
    for(int i = 1; i < n; i++){
        int j = pi[i - 1];
        while(j > 0 && s[i] != s[j])
            j = pi[j - 1];
        if(s[i] == s[j])
            j++;
        pi[i] = j;  
    }
    return pi;
}

int main() {
    string s;
    cin >> s;
    int n = s.length();
    long long mul = 26, ans = 0;
    for(int i = 1; i < n; i++, mul *= 26, mul %= MOD)
        ans += mul;
    vector<int> pi = prefix_function(s);
    int k = n - pi[n - 1];
    if(n % k == 0){
        ans -= n / k - 1;   
    }
    cout << ans % MOD;
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

const int MOD = 1e9+7;

vector<int> prefix_function(string s) {

int n = s.length();

vector<int> pi(n);

pi[0] = 0;

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

int j = pi[i - 1];

while(j > 0 && s[i] != s[j])

j = pi[j - 1];

if(s[i] == s[j])

j++;

pi[i] = j;

}

return pi;

}

int main() {

string s;

cin >> s;

int n = s.length();

long long mul = 26, ans = 0;

for(int i = 1; i < n; i++, mul *= 26, mul %= MOD)

ans += mul;

vector<int> pi = prefix_function(s);

int k = n - pi[n - 1];

if(n % k == 0){

ans -= n / k - 1;

}

cout << ans % MOD;

return 0;

}

Related Images:

e-olymp 2163. Сообразим на троих!

26/06/2016 by Максим Носов

Задача

К Василию приехали два его друга с отличной новостью: они выиграли в лотерею [latex]n[/latex] рублей. Поскольку лотерейный билет был получен на сдачу во время общей закупки в магазине, то его принадлежность определить не удалось. Было решено разделить выигрыш поровну. Василий хотел бы узнать, можно ли честно разделить выигрыш.

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

Одно натуральное число [latex]n[/latex], количество знаков которого не превышает 255.

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

Вывести «YES», если входное число делится на 3, и «NO» если не делится.

Код string

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

int main() {
    string s;       
    cin>>s;           
    int a=0;        
    for(int i=0;i<s.size();i++){
        a+=s[i]-'0';
    }
    if(a%3==0)cout<<"YES";
    else cout<<"NO";
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

cin>>s;

int a=0;

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

a+=s[i]-'0';

}

if(a%3==0)cout<<"YES";

else cout<<"NO";

return 0;

}

Тесты

№	Входные данные	Выходные данные
1	33	YES
2	0	YES
3	1	NO
4	1234567890987654321	YES
5	12345678901	NO

Решение

Для начала вводим строку, где будет хранится наше число. Будем считать сумму цифр числа, т.к. число делится на 3, если сумма его цифр делится на 3. Для этого создаем переменную [latex]a[/latex] в которой будет хранится сумма цифр. Запускаем цикл от 0 до размера строки (количество цифр в числе). В цикле суммируем цифры числа, отнимая от него код символа 0, т.к. в [latex]string[/latex] записывается не число, а его код его символа. Далее проверяем — если сумма цифр делится по модулю на 3, то выводим «YES», если нет — то «NO».

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

Ссылка на решение e-olymp.

Код c-string

#include <iostream>
#include <cstring>
using namespace std;
 
int main() {
    const int MAX_SIZE = 256;
    char *c = new char [MAX_SIZE];     
    cin.getline (c,MAX_SIZE);
    int a=0;        
    for(int i=0;i<strlen(c);i++){
        a+=c[i]-'0';
    }
    if(a%3==0)cout<<"YES";
    else cout<<"NO";
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

const int MAX_SIZE = 256;

char *c = new char [MAX_SIZE];

cin.getline (c,MAX_SIZE);

int a=0;

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

a+=c[i]-'0';

}

if(a%3==0)cout<<"YES";

else cout<<"NO";

return 0;

}

Решение

Алгоритм решения такой же как и для [latex]string[/latex], только вместо библиотеки [latex]string[/latex] подключаем библиотеку [latex]cstring[/latex], немного изменяем ввод и используем функцию [latex]strlen()[/latex] вместо [latex]size()[/latex].

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

Ссылка на решение e-olymp.

Related Images:

e-olymp 2171. Поиск набора образцов

19/05/2016 by Женя Максимова

Задача. Напишите программу, которая для каждой строки из заданного набора [latex]S[/latex] проверяет, верно ли, что она содержит как подстроку одну из строк из набора [latex]T[/latex].

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

Первая строка содержит натуральное число [latex]n (n\leq100)[/latex] — количество строк в наборе [latex]T[/latex]. Каждая из следующих [latex]n[/latex] строк содержит непустую строку длины не более [latex]80[/latex]-ти символов.

Оставшаяся часть файла содержит строки из набора [latex]S[/latex]. Каждая строка состоит из ASCII символов с кодами от [latex]32[/latex] до [latex]126[/latex] включительно. Строка может быть пустой; гарантируется, что длины строк не превышают [latex]250[/latex]-ти символов.

Гарантируется, что размер входного файла не превышает [latex]1[/latex] Мбайт.

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

Выведите все строки из набора [latex]S[/latex] (в том порядке, в котором они находятся во входном файле), содержащие как подстроку по крайней мере одну строку из набора [latex]T[/latex].

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

Тесты

Test	Input	Output
1	3 gr sud abc lksh sudislavl kostroma summer group b	sudislavl group b
2	4 a b + + xxx ababa dfs c + + qwerty xxxx	ababa c + + xxxx
3	1 a a b a c a d	a a a
4	2 bab aba aabba w w w

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

#include <bits/stdc++.h>
using namespace std;

#define in_range(x,y,z) for (int x=y; x<z; x++)
typedef long long ll;

int find_subctr(string t, string s)
{
  const int p = 97;  // основание системы счисления для хеширования строк
  // вычисляем степени числа P, чтобы ускорить процесс хеширования
  vector<ll> p_pow (s.length());
  p_pow[0] = 1;
  for (size_t i=1; i<p_pow.size(); ++i)
    p_pow[i] = p_pow[i-1] * p;
  // вычисляем хеши всех префиксов строки S
  vector<ll> h (s.length());
  for (size_t i=0; i<s.length(); ++i)
    {
      h[i] = (s[i] - 't' + 1) * p_pow[i];
      if (i)  h[i] += h[i-1];
    }
  // посчитаем хеш строки Т
  ll h_t = 0;
  for (size_t i=0; i<t.length(); ++i)
    h_t += (t[i] - 't' + 1) * p_pow[i];
  // сравниваем хеши строки T и подстрок S длины |T|
  for (size_t i = 0; i + t.length() - 1 < s.length(); ++i)
    {
      ll cur_h = h[i+t.length()-1];
      if (i)  cur_h -= h[i-1];
      // если равенство выполняется хотя бы один раз, мы прекращаем поиск
      if (cur_h == h_t * p_pow[i])
        return int(i);
    }
  return -1;
}

int main()
{
  vector<string>T,S,C; // наборы строк T и S, а также набор образцов единичной длины C
  int n;
  cin >> n;
  string tmp;
  getline(cin,tmp);
  in_range(i,0,n)
    {
      getline(cin,tmp);
      if(tmp.length()==1) C.push_back(tmp);
      T.push_back(tmp);
    }
  while(getline(cin,tmp))
    {
      S.push_back(tmp);
    }
  in_range(i,0,S.size())
    {
      string s=S[i];
      if(s=="") continue; // отсекаем случай пустой строки
      if(s.length()==1) // в случае строки единичной длины ищем вхождения образцов из С простым перебором
        {
          in_range(j,0,C.size())
          {
            string c=C[j];
            if(s==c)
              {
                cout << s << "\n";
                break;
              }
          }
          continue;
        }
      in_range(j,0,n) // во всех остальных случаях ищем вхождения строк из Т, используя алгоритм Рабина-Карпа
      {
        string t=T[j];
        int pos = find_subctr(t,s);
        if(pos>=0)
          {
            cout << s << "\n";
            break;
          }
      }
    }
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

#define in_range(x,y,z) for (int x=y; x<z; x++)

typedef long long ll;

int find_subctr(string t, string s)

{

const int p = 97; // основание системы счисления для хеширования строк

// вычисляем степени числа P, чтобы ускорить процесс хеширования

vector<ll> p_pow (s.length());

p_pow[0] = 1;

for (size_t i=1; i<p_pow.size(); ++i)

p_pow[i] = p_pow[i-1] * p;

// вычисляем хеши всех префиксов строки S

vector<ll> h (s.length());

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

{

h[i] = (s[i] - 't' + 1) * p_pow[i];

if (i) h[i] += h[i-1];

}

// посчитаем хеш строки Т

ll h_t = 0;

for (size_t i=0; i<t.length(); ++i)

h_t += (t[i] - 't' + 1) * p_pow[i];

// сравниваем хеши строки T и подстрок S длины |T|

for (size_t i = 0; i + t.length() - 1 < s.length(); ++i)

{

ll cur_h = h[i+t.length()-1];

if (i) cur_h -= h[i-1];

// если равенство выполняется хотя бы один раз, мы прекращаем поиск

if (cur_h == h_t * p_pow[i])

return int(i);

}

return -1;

}

int main()

{

vector<string>T,S,C; // наборы строк T и S, а также набор образцов единичной длины C

int n;

cin >> n;

string tmp;

getline(cin,tmp);

in_range(i,0,n)

{

getline(cin,tmp);

if(tmp.length()==1) C.push_back(tmp);

T.push_back(tmp);

}

while(getline(cin,tmp))

{

S.push_back(tmp);

}

in_range(i,0,S.size())

{

string s=S[i];

if(s=="") continue; // отсекаем случай пустой строки

if(s.length()==1) // в случае строки единичной длины ищем вхождения образцов из С простым перебором

{

in_range(j,0,C.size())

{

string c=C[j];

if(s==c)

{

cout << s << "\n";

break;

}

continue;

}

in_range(j,0,n) // во всех остальных случаях ищем вхождения строк из Т, используя алгоритм Рабина-Карпа

{

string t=T[j];

int pos = find_subctr(t,s);

if(pos>=0)

{

cout << s << "\n";

break;

}

return 0;

}

Алгоритм

Мы последовательно перебираем все строки [latex]s[/latex] из набора [latex]S[/latex]. Для каждой из них найдем вхождение хотя бы одной строки [latex]t[/latex] из набора [latex]T[/latex]. Для этого мы воспользуемся алгоритмом Рабина-Карпа. Он заключается в следующем: мы сравниваем подстроки [latex]s[/latex] длины [latex]\left | t \right |[/latex] со строкой [latex]t[/latex], предварительно закодировав их с помощью хеша. Если после мы перебрали все подстроки, но так и не получили равенство, строка [latex]t[/latex] не является подстрокой [latex]s[/latex] и мы переходим к следующему образцу.

Однако данный алгоритм не целесообразно использовать для строк единичной длины. Про большом количестве таких строк неэффективность алгоритма становится очень заметной. Поэтому мы создаем отдельный набор образцов, состоящих ровно из одного символа. Если на вход поступает строка единичной длины, мы просто ищем ее в этом наборе за [latex]O(n)[/latex].

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

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

Related Images:

e-olymp 2034. WERTYU

19/05/2016 by Грешилов Константин

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

Обычная ошибка при наборе состоит в том, что вы помещаете ваши руки на клавиатуру на один ряд правее верной позиции. Тогда «Q» печатается как «W«, «J» печатается как «K» и т.д. Ваша задача состоит в расшифровке сообщения, напечатанного таким образом.

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

Входные данные состоят из нескольких строк текста. Каждая строка может содержать цифры, пробелы, прописные буквы (кроме Q, A, Z) и знаки препинания, показанные выше [кроме обратной кавычки (`)]. Клавиши, обозначенные словами [Tab, BackSp, Control и т.д.], не представлены во входных данных.

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

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

Тесты:

Входные данные	Выходные данные
O S, GOMR YPFSU/	I AM FINE TODAY.
JS;=0—	HAL-9000
OY OD S MOVR MOHJY GPT VPFOMH	IT IS A NICE NIGHT FOR CODING

Решение:

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

int main() {
    string x;
    string y="`1234567890-=QWERTYUIOP[]\ASDFGHJKL;'ZXCVBNM,./";
    while(getline(cin,x)) {
        size_t found;
        for (int i=0; i<x.length(); i++) {
            if (x[i]==' ') {
                cout<<" ";
            } else {
                found=y.find_first_of(x[i]);
                cout<<y[found-1];
            }
        }
        cout<<endl;
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string x;

string y="`1234567890-=QWERTYUIOP[]\ASDFGHJKL;'ZXCVBNM,./";

while(getline(cin,x)) {

size_t found;

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

if (x[i]==' ') {

cout<<" ";

} else {

found=y.find_first_of(x[i]);

cout<<y[found-1];

}

cout<<endl;

}

return 0;

}

Описание решения:

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

while(getline(cin,x))

8	while(getline(cin,x))

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

Если данный символ пробел — то выведем его на экран.
Иначе, с помощью функции [latex]find[/latex]_[latex]first[/latex]_[latex]of()[/latex] найдем номер вхождения данного символа в проверочном массиве [latex]y[/latex], и выведем предыдущий элемент из этого массива.
Повторяем пункты 1, 2 до тех пор, пока не дойдем до конца строки [latex]x[/latex]. После этого перейдем на новую строку с помощью команды [latex]endl[/latex].

Условие задачи на сайте e-olymp.com можно найти здесь.

Решение, что зашло на 100%.

Код решения можно проверить здесь.

Related Images:

e-olymp 6127. Очередь неограниченного размера

15/04/2016 by Катя Писова

Задача

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

push n

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

pop

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

front

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

size

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

clear

Программа должна очистить очередь и вывести ok.

exit

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

Размер очереди должен быть ограничен только размером доступной оперативной памяти. Перед исполнением операций front и popпрограмма должна проверять, содержится ли в очереди хотя бы один элемент. Если во входных данных встречается операция frontилиpop, и при этом очередь пуста, то программа должна вместо числового значения вывести строку error.

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

Описаны в условии. См. также пример входных данных.

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

Описаны в условии. См. также пример выходных данных.

Тесты

№	Входные данные	Выходные данные:
1	push 1 front exit	ok 1 bye
2	size push 1 size push 2 size push 3 size exit	0 ok 1 ok 2 ok 3 bye

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

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

struct node{
    int value;
    node *next;
    node():value(0), next(NULL){}
    node(int value, node *next)
    :value(value), next(next){}
};

struct _queue{
    int _size;
    node *first;
    node *last;
    _queue():_size(0), first(NULL), last(NULL){}

    void push (int v){
        node *new_node = new node(v, last);
        if(_size == 0){
            first = last = new_node;
        }
        else{
            last->next = new_node;
            last = new_node;
        }
        _size++;
    }

    void pop(){
        if (_size > 0){
            int val = first->value;
            first = first->next;
            _size--;
            cout << val;
        }
        else throw 0;
    }

    void front(){
        if (_size > 0) cout << first->value;
        else throw 0;
    }
    
    int size(){
        return _size;
    }

    void clear(){
        while (_size > 0){
            node *new_node = first->next;
            delete first;
            first = new_node;
            _size--;
        }
        first = NULL;
        last = NULL;
    }
};


int main()
{
    _queue q;
    string s;
    int n;
    while (cin >> s){
        if (s == "size"){
            cout << q.size() << endl;
        }
        if (s == "push"){
            cin >> n;
            q.push(n);
            cout << "ok" << endl;
        }
        if (s == "pop"){
            try{
                q.pop();
            }
            catch(int e){cout << "error";}
            cout << endl;
        }
        if (s == "front"){
            try {
                q.front();
            }
            catch(int e){cout << "error";}
            cout<<endl;
        }
        if (s == "clear"){
            q.clear();
            cout << "ok" << endl;
        }
        if (s == "exit"){
            cout << "bye" <<endl;
            return 0;
        }
    }
    return 0;
}

100

101

102

#include <iostream>

#include <string>

#include <exception>

using namespace std;

struct node{

int value;

node *next;

node():value(0), next(NULL){}

node(int value, node *next)

:value(value), next(next){}

};

struct _queue{

int _size;

node *first;

node *last;

_queue():_size(0), first(NULL), last(NULL){}

void push (int v){

node *new_node = new node(v, last);

if(_size == 0){

first = last = new_node;

}

else{

last->next = new_node;

last = new_node;

}

_size++;

}

void pop(){

if (_size > 0){

int val = first->value;

first = first->next;

_size--;

cout << val;

}

else throw 0;

}

void front(){

if (_size > 0) cout << first->value;

else throw 0;

}

int size(){

return _size;

}

void clear(){

while (_size > 0){

node *new_node = first->next;

delete first;

first = new_node;

_size--;

}

first = NULL;

last = NULL;

}

};

int main()

{

_queue q;

string s;

int n;

while (cin >> s){

if (s == "size"){

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

}

if (s == "push"){

cin >> n;

q.push(n);

cout << "ok" << endl;

}

if (s == "pop"){

try{

q.pop();

}

catch(int e){cout << "error";}

cout << endl;

}

if (s == "front"){

try {

q.front();

}

catch(int e){cout << "error";}

cout<<endl;

}

if (s == "clear"){

q.clear();

cout << "ok" << endl;

}

if (s == "exit"){

cout << "bye" <<endl;

return 0;

}

return 0;

}

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

Каждый элемент (узел) очереди состоит из информационной части (его значение) и адресной. В адресную часть первого элемента записываем адрес следующего элемента и т.д., тем самым мы создаем порядок следования элементов в очереди, связывая их между собой. При добавлении или удалении элемента мы соответственно изменяем размер очереди, который изначально равен нулю, а также меняем позиции указателей на начало и конец очереди. В условии задачи сказано, что если во входных данных встречается операция front или pop, и при этом очередь пуста, то программа должна вместо числового значения вывести строку error. Поэтому создаем исключительную ситуацию для проверки наличия в очереди хотя бы одного элемента.

Ссылка на засчитанное решение на e-olymp
Ссылка на условие задачи
Ссылка на решение задачи на ideone.com

Related Images:

e-olymp 1073. Статическая сложность

05/03/2016 by Сплошнов Кирилл

Условие

Задача взята с сайта e-olymp, полное условие можно прочитать здесь.

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

В первой строке находится целое число [latex]k[/latex] — число программ во входном файле. Затем идут [latex]k[/latex] программ, удовлетворяющих приведенной грамматике. Пробелы и переводы строк могут встречаться везде в программе, но не в ключевых словах [latex]BEGIN[/latex], [latex]END[/latex], [latex]LOOP[/latex] и [latex]OP[/latex], нет их и в целых числах.

Вложенность операторов [latex]LOOP[/latex] не превышает [latex]10[/latex], размер входного файла не более [latex]2[/latex] Кбайт, коэффициенты многочлена в ответе не превышают [latex]50000[/latex].

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

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

Для каждой программы сначала идет строка с номером программы. В следующей строке записывается время работы программы в терминах [latex]n[/latex] — многочлен степени не более [latex]10[/latex]. Многочлен должен быть записан обычным способом, то есть подобные слагаемые должны быть приведены, слагаемое большей степени должно предшествовать слагаемому меньшей степени, слагаемые с коэффициентом [latex]0[/latex] не записываются, множители [latex]1[/latex] не записываются. Общий вид второй строки [latex]Runtime = a*n^{10}+b*n^9+\ldots+i*n^2+j*n+k[/latex]. Если время выполнения нулевое, нужно вывести [latex]Runtime = 0[/latex]. За строкой с многочленом должна следовать пустая строка, кроме последнего тестового случая.

Решение

Создадим массив коэффициентов [latex]coefficients[/latex] на 11 элементов (нулевой элемент — свободный член, 10-й — десятая (максимальная) степень). В цикле для каждой программы будем:

Обнулять массив [latex]coefficients[/latex].
Заполнять его новыми данными с помощью функции void getCoefficients(int* coefficients);
Строить на основании полученных коэффициентов требуемую строку-многочлен, за это отвечает функция string toString(int* coefficients);
Выводить требуемую информацию.

Рассмотрим процесс заполнения массива. Создадим вектор для строк [latex]params[/latex], где будем хранить кол-ва повторений для всех открытых циклах, от внешнего к внутреннему, и переменную-счетчик [latex]keywords[/latex]. Функция будет завершать свою работу при значении [latex]keywords[/latex] равном [latex]0[/latex]. Изначально присвоим [latex]keywords = 1[/latex] (оператор [latex]BEGIN[/latex]). Далее, в цикле будем, в зависимости от прочитанного оператора:

[latex]END[/latex]: уменьшаем значение [latex]keywords[/latex] на [latex]1[/latex], удаляем последний элемент из [latex]params[/latex] (чтобы не было проблем с последним оператором [latex]END[/latex] (пустой вектор), положим в него перед циклом строку «[latex]1[/latex]»). Если [latex]keywords[/latex] равно нулю — завершаем работу.
[latex]LOOP[/latex]: увеличиваем значение [latex]keywords[/latex] на [latex]1[/latex], считываем следующую строку и добавляем ее в конец [latex]params[/latex].
[latex]OP[/latex]: Считываем следующую строку, преобразовываем ее к числу (кол-ву операций) стандартной функцией stoi(). Далее, проходя по строкам из [latex]params[/latex], если строка равна [latex]n[/latex], увеличиваем степень (номер ячейки массива, куда прибавим результат) на [latex]1[/latex], иначе — преобразовываем к числу и домножаем на кол-во операций. Прибавляем полученный результат к числу в соответствующей ячейке массива.

Функция toString() реализована достаточно просто (см. код). Пробегаем по элементам массива с конца, и если элемент [latex]n[/latex] не равен нулю, прибавляем к строке-многочлену соответствующий набор символов (отдельно учитывая случаи при [latex]n = 1[/latex], [latex]n=-1[/latex], первой и нулевой степени и т.д.). Если в итоге строка пустая, возвращаем «[latex]0[/latex]».

Тесты

№

Ввод

Вывод

2
BEGIN
LOOP n
OP 4
LOOP 3
LOOP n
OP 1
END
OP 2
END
OP 1
END
OP 17
END

BEGIN
OP 1997 LOOP n LOOP n OP 1 END END
END

Program #1
Runtime = 3*n^2+11*n+17

Program #2
Runtime = n^2+1997

3
BEGIN
END

BEGIN
LOOP n LOOP n LOOP n OP 1
LOOP n LOOP n LOOP n OP 1
LOOP n LOOP n LOOP n OP 1
END END END OP 3
END END END OP 3
END END END OP 3
END

BEGIN OP 42
LOOP n LOOP 5 LOOP n
OP 7 END OP 2 END OP 1 END
OP 1 END

Program #1
Runtime = 0

Program #2
Runtime = n^9+4*n^6+4*n^3+3

Program #3
Runtime = 35*n^2+11*n+43

Код

#include <iostream>
#include <string>
#include <vector>
#define MAX_POWER 10
using namespace std;

void getCoefficients(int* coefficients)
{
	int keywords = 1;
	vector<string> params;
	string begin;
	cin >> begin;
	params.push_back(((string) "1")); //чтобы вектор не был пустой на последнем END (который соответствует BEGIN)
	while (true)
	{
		string keyword;
		cin >> keyword;
		if (keyword == (string)"END")
        {
            keywords--;
            params.pop_back();
            if (keywords == 0) 
            {
            	break;
            }
        }
        else if (keyword == (string)"LOOP")
        {
            keywords++;
            string param;
            cin >> param;
            params.push_back(param);
        }
        else if (keyword == (string)"OP")
        {
        	string num;
        	cin >> num;
            int coefficient = stoi(num);
            int multiplier = 1, pow = 0;
            for (string param : params)
            {
                if (param == (string)"n") 
                {
                	pow++;
                }
                else 
                {
                	multiplier *= stoi(param);
                }
            }
            coefficients[pow] += coefficient * multiplier;
        }
	}
}

string toString(int* coefficients)
{
	string result;
    for (int i = MAX_POWER; i > 0; i--)
    {
        if (coefficients[i] != 0)
            {
                if (coefficients[i] == 1) 
                {
                	result += "n";
                }
                else if (coefficients[i] == -1) 
                {
                	result += "-n";
                }
                else
                {
                	result += to_string(coefficients[i]); //стандартная функция, преобразовывает число в строку
                	result += "*n";
                }
                if (i != 1) //если степень не первая, добавляем "^[степень]"
                {
                	result += "^";
                	result += to_string(i);
                }
            }
            if (coefficients[i-1] > 0 && result.length() != 0) //проверка, чтобы + не стоял в начале строки и между членами не было "+-"
            {
            	result += "+";
            }
        }
        if (result.length() == 0 || coefficients[0] != 0) //прибавляем последний коэффициент, если он не равен нулю или строка пустая
        {
        	result += to_string(coefficients[0]);
        }
        return result;
}

int main() 
{
	int n;
	cin >> n;
	int coefficients[MAX_POWER + 1];
	for (int i = 1; i <= n; i++)
	{
		cout << "Program #" << i << endl;
		fill(coefficients, coefficients + MAX_POWER + 1, 0); //обнуляем массив коэффициентов
		getCoefficients(coefficients);
		cout << "Runtime = " << toString(coefficients) << endl;
		if (i != n)
		{
			cout << endl; 
		}
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

#include <iostream>

#include <string>

#include <vector>

#define MAX_POWER 10

using namespace std;

void getCoefficients(int* coefficients)

{

int keywords = 1;

vector<string> params;

string begin;

cin >> begin;

params.push_back(((string) "1")); //чтобы вектор не был пустой на последнем END (который соответствует BEGIN)

while (true)

{

string keyword;

cin >> keyword;

if (keyword == (string)"END")

{

keywords--;

params.pop_back();

if (keywords == 0)

{

break;

}

else if (keyword == (string)"LOOP")

{

keywords++;

string param;

cin >> param;

params.push_back(param);

}

else if (keyword == (string)"OP")

{

string num;

cin >> num;

int coefficient = stoi(num);

int multiplier = 1, pow = 0;

for (string param : params)

{

if (param == (string)"n")

{

pow++;

}

else

{

multiplier *= stoi(param);

}

coefficients[pow] += coefficient * multiplier;

}

string toString(int* coefficients)

{

string result;

for (int i = MAX_POWER; i > 0; i--)

{

if (coefficients[i] != 0)

{

if (coefficients[i] == 1)

{

result += "n";

}

else if (coefficients[i] == -1)

{

result += "-n";

}

else

{

result += to_string(coefficients[i]); //стандартная функция, преобразовывает число в строку

result += "*n";

}

if (i != 1) //если степень не первая, добавляем "^[степень]"

{

result += "^";

result += to_string(i);

}

if (coefficients[i-1] > 0 && result.length() != 0) //проверка, чтобы + не стоял в начале строки и между членами не было "+-"

{

result += "+";

}

if (result.length() == 0 || coefficients[0] != 0) //прибавляем последний коэффициент, если он не равен нулю или строка пустая

{

result += to_string(coefficients[0]);

}

return result;

}

int main()

{

int n;

cin >> n;

int coefficients[MAX_POWER + 1];

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

{

cout << "Program #" << i << endl;

fill(coefficients, coefficients + MAX_POWER + 1, 0); //обнуляем массив коэффициентов

getCoefficients(coefficients);

cout << "Runtime = " << toString(coefficients) << endl;

if (i != n)

{

cout << endl;

}

return 0;

}

Ссылки

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

Рабочий код на ideaone.

Related Images:

e-olymp 1072. Химические реакции

04/03/2016 by Сплошнов Кирилл

Условие

Задача взята с сайта e-olymp, полное условие можно прочитать здесь.

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

В первой строке находится формула — левая часть уравнения, во второй- одно число [latex]N (1 \leq N \leq 10)[/latex] — количество рассматриваемых правых частей, в каждой из последующих [latex]N[/latex] строк — одна формула — предполагаемая правая часть уравнения.

Длина формулы не превосходит [latex]100[/latex] символов, каждый отдельный химический элемент встречается всего не более [latex]10000[/latex] раз в каждой формуле.

(Примечание: понятие формулы в данном алфавите можно прочитать по ссылке выше.)

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

Для каждой из [latex]N[/latex] заданных строк вывести одну строку вида

формула левой части==формула правой части

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

формула левой части!=формула правой части

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

Решение (вспомогательные функции)

Так как задача достаточно объемная, напишем ряд вспомогательных функций:

Определяет, является ли символ цифрой.

bool isDigit(char c);

1

bool isDigit(char c);
Определяет, является ли символ буквой в верхнем регистре.

bool isUpperCaseLetter(char c);

1

bool isUpperCaseLetter(char c);
Определяет, является ли символ буквой в нижнем регистре.

bool isLowerCaseLetter(char c);

1

bool isLowerCaseLetter(char c);
Будем хранить содержимое формулы используя структуру map (карта), ключами будут выступать названия элементов (строки), значениями — количества их вхождений. Если элемента в карте нет, добавляем пару <элемент, кол-во>, иначе — прибавляем к старом числу вхождений новое. За это отвечает следующая функция.

void update(map<string, int> &map, string key, int value);

1

void update(map<string, int> &map, string key, int value);
Для простоты разобьем формулу на подформулы (по знаку [latex]+[/latex], если он встречается), и будем работать с каждой формулой по отдельности. Функция разбивает строку на подстроки по знаку [latex]+[/latex] и заполняет ими вектор [latex]storage[/latex] (так как мы не знаем кол-во подформул заранее, вектор предпочтительнее массива).

void split(string formula, vector<string> &storage);

1

void split(string formula, vector<string> &storage);
По условию, перед каждой подформулой может идти множитель, относящейся ко всей подформуле. Функция возвращает множитель ( [latex]1[/latex], если множитель не записан явно).

int getMultiplier(string formula);

1

int getMultiplier(string formula);
Основная функция. Добавляет в карту [latex]content[/latex] содержимое подформулы.

void getContent(string formula, int multiplier, map<string, int> &content);

1

void getContent(string formula, int multiplier, map<string, int> &content);
Обрабатывает формулу. Просто вызывает функции №[latex]6[/latex] и №[latex]7[/latex] по очереди для каждой из подформул (элементов из [latex]subformulas[/latex]).

void process(vector<string> subformulas, map<string, int> &content);

1

void process(vector<string> subformulas, map<string, int> &content);

Решение (основной алгоритм)

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

void getContent(string formula, int multiplier, map<string, int> &content);

1	void getContent(string formula, int multiplier, map<string, int> &content);

Тут:

[latex]formula[/latex] — подформула обрабатываемой формулы (без общего множителя);
[latex]multiplier[/latex] — множитель, определяется предыдущей функцией, перед вызовом данной;
[latex]content[/latex] — карта, куда записываются элементы всех подформул текущей формулы (доступ осуществляется по адресу).

Алгоритм разделяется на 2 случая, в зависимости от наличия скобок. Предположим, скобок в подформуле (далее — просто формуле) нет. Заведем переменные [latex]name[/latex] (название элемента. тип string) и [latex]coefficient[/latex] (задний коэффициент, тип string). Тогда, проходя по порядку по символам формулы, будем выполнять следующие действия в зависимости от текущего символа([latex]c[/latex]):

[latex]c[/latex] — цифра: добавляем его в конец строки [latex]coefficient[/latex];
[latex]c[/latex] — буква в нижнем регистре: добавляем его в конец строки [latex]name[/latex];
[latex]c[/latex] — буква в верхнем регистре: если строка [latex]name[/latex] — пустая (первый элемент в формуле), то добавляем его в конец строки [latex]name[/latex]. Иначе, сперва обнуляем [latex]name[/latex], потом добавляем. Тогда, если строка [latex]coefficient[/latex] — пустая, присваиваем [latex]coefficient=[/latex]»[latex]1[/latex]». Получаем количество вхождений элемента как [latex]multiplier*stoi(coefficient)[/latex], где stoi() — стандартная функция, преобразующая число к строке. Затем добавляем в карту элемент и полученное кол-во вхождений.

update(content, name, multiplier * stoi(coefficient));

140

update(content, name, multiplier * stoi(coefficient));

(Примечание: пункт [latex]3[/latex] для последнего элемента (кроме обновления значения [latex]name[/latex]) придется повторить отдельно.)

update(content, name, multiplier * stoi(coefficient));

153	update(content, name, multiplier * stoi(coefficient));

Если же в формуле имеются скобки, то:

Находим первую открывающую скобку.
Находим соответствующую ей закрывающую скобку.
Для выражения в скобках вычисляем задний коэффициент (см. код), заносим в переменную [latex]newMultiplier[/latex] значение множителя для выражения внутри скобок.
Рекурсивно вызываем функцию getContent() для:
1. Выражения перед открывающей скобкой, если формула не начинается с нее.
  
  getContent(formula.substr(0, begin - 1), multiplier, content);
  
  106
  
  getContent(formula.substr(0, begin - 1), multiplier, content);
  
  ([latex]begin[/latex] — номер первого символа внутри скобок.)
2. Выражения внутри скобок.
  
  getContent(formula.substr(begin, end - begin), newMultiplier, content);
  
  108
  
  getContent(formula.substr(begin, end - begin), newMultiplier, content);
  
  ([latex]end[/latex] — номер закрывающей скобки.)
3. Выражения после закрывающей скобки или заднего коэффициента, если присутствует (если только скобка/коэффициент не является концом формулы).
  
  getContent(formula.substr(afterEnd), multiplier, content);
  
  111
  
  getContent(formula.substr(afterEnd), multiplier, content);
  
  ([latex]afterEnd[/latex] — следующий после скобки/коэффициента символ.)

Этот алгоритм фактически является решением задачи. Теперь в методе [latex]main[/latex] надо всего лишь обработать главную формулу, а затем для каждого случая в цикле — сравниваемую с ней формулу, сравнив после содержимое их карт (сравнение осуществляется просто используя оператор сравнения ==). Обработка подразумевает последовательный вызов функций split() и process().

Тесты

№	Ввод	Вывод
1	C2H5OH+3O2+3(SiO2) 6 2CO2+3H2O+3SiO2 2C+6H+13O+3Si 99C2H5OH+3SiO2 3SiO4+C2H5OH C2H5OH+3O2+3(SiO2)+Ge 3(Si(O)2)+2CO+3H2O+O2	C2H5OH+3O2+3(SiO2)==2CO2+3H2O+3SiO2 C2H5OH+3O2+3(SiO2)==2C+6H+13O+3Si C2H5OH+3O2+3(SiO2)!=99C2H5OH+3SiO2 C2H5OH+3O2+3(SiO2)==3SiO4+C2H5OH C2H5OH+3O2+3(SiO2)!=C2H5OH+3O2+3(SiO2)+Ge C2H5OH+3O2+3(SiO2)==3(Si(O)2)+2CO+3H2O+O2
2	2H2O 5 HHOHHO 2H+H2+(O(O)) 2((H2)O) HOHHOHe H4O	2H2O==HHOHHO 2H2O==2H+H2+(O(O)) 2H2O==2((H2)O) 2H2O!=HOHHOHe 2H2O!=H4O
3	8Zn+Ar4+Ne 3 Ne(Ar2(Zn)4)2 2Ne(Ar2(Zn)4) Ne+2Zn2(((((Ar)))))2Zn2	8Zn+Ar4+Ne==Ne(Ar2(Zn)4)2 8Zn+Ar4+Ne!=2Ne(Ar2(Zn)4) 8Zn+Ar4+Ne==Ne+2Zn2(((((Ar)))))2Zn2

Код

#include <iostream>
#include <cmath>
#include <string>
#include <vector>
#include <map>
using namespace std;

bool isDigit(char c) { return  c >= '0' && c <= '9'; }

bool isUpperCaseLetter(char c) { return  c >= 'A' && c <= 'Z'; }

bool isLowerCaseLetter(char c) { return  c >= 'a' && c <= 'z'; }

void update(map<string, int> &map, string key, int value)
{
    if (map.count(key)) //вернет 0 (false) если элемент не найден, иначе - 1 (true)
    {
        map.at(key) = map.at(key) + value; //обновляем значение элемента в карте
    }
    else
    {
        map.insert(make_pair(key, value)); //добавляем элемент в карту
    }
}

void split(string formula, vector<string> &storage)
{
    int begin = 0, length = 0;
    for (int i = 0; i < formula.length(); i++)
    {
        if (formula.at(i) == '+')
        {
            storage.push_back(formula.substr(begin, length));
            length = 1;
            begin = ++i;
        }
        else
        {
            length++;
        }
    }
    storage.push_back(formula.substr(begin, length));
}

int getMultiplier(string formula)
{
    int res = 0;
    for (int i = 0; i < formula.length(); i++)
    {
        if (isDigit(formula.at(i))) 
        {
            res *= 10;
            res += (formula.at(i) - '0'); //получаем из символа соответствующую цифру
        }
        else break;
    }
    return res == 0 ? 1 : res; //0 - если перед формулой нет множителя, тогда он должен быть 1
}

void getContent(string formula, int multiplier, map<string, int> &content)
{ 
    if (formula.find('(') != string::npos) //если есть скобки
    {
        int begin = formula.find('(') + 1; //первый символ внутри скобок
        int end;
        int bracketCounter = 1;
        for (int i = begin; true; i++)
        {
            if (formula.at(i) == '(')
            {
                bracketCounter ++;
            }
            else if (formula.at(i) == ')')
            {
                bracketCounter--;
                if (bracketCounter == 0)
                {
                    end = i; //находим соответствующую закрывающую скобку
                    break;
                }
            }
        }
        int newMultiplier = multiplier;
        int afterEnd = end + 1;
        int backCoefficient = 0; //вычисляем коэффициент за скобочным выражением
        for (int i = 1; true; i++)
        {
            if (end + i != formula.length() && isDigit(formula.at(end + i))) //пока есть числа за закрывающей скобкой, обновляем значение заднего коэффициента
            {
                backCoefficient *= 10;
                backCoefficient += (formula.at(end + i) - '0');
                afterEnd++;
            }
            else
            {
                if (backCoefficient == 0) //если чисел после закрывающей скобки нет, коэффициент равен 1
                {
                    backCoefficient++;
                }
                newMultiplier *= backCoefficient; //вычисляем новое значение множителя для выражения внутри скобок
                break;
            }
        }
        if (begin != 1)
        {
            getContent(formula.substr(0, begin - 1), multiplier, content); 
        }
        getContent(formula.substr(begin, end - begin), newMultiplier, content); 
        if (afterEnd < formula.length())
        {
            getContent(formula.substr(afterEnd), multiplier, content);
        }
    }
    else //если скобок нет
    {
        string name = "";
        string coefficient = "";
        for (char c : formula)
        {
            if (isDigit(c)) 
            {
                coefficient += c;
            }
            else if (isLowerCaseLetter(c)) 
            {
                name += c;
            }
            else if (isUpperCaseLetter(c))
            {
                if (name.empty()) 
                {
                    name += c;
                }
                else
                {
                    if (coefficient.empty()) 
                    {
                        coefficient = "1";
                    }
                    update(content, name, multiplier * stoi(coefficient));
                    name.clear();
                    name += c;
                    coefficient = "";
                }
            }
        }
        if (!name.empty())
        {
            if (coefficient.empty()) 
            {
                coefficient = "1";
            }
            update(content, name, multiplier * stoi(coefficient));
        }
    }
}

void process(vector<string> subformulas, map<string, int> &content)
{
    for (string subformula : subformulas) //для каждой подформулы:
    {
        int multiplier = getMultiplier(subformula); //вычисляем множитель перед ней
        if (multiplier != 1) //если множитель записан явно
        {
            getContent(subformula.substr(floor(log10(multiplier)+1)), multiplier, content); //передаем в функцию подформулу, начиная с первого символа, не относящегося к переднему множителю
        }
        else
        {
            getContent(subformula, multiplier, content); //иначе передаем подформулу целиком
        }
    }
}

int main() 
{
    string mainFormula;
    vector<string> mainSubformulas;
    map<string, int> mainContent;
    cin >> mainFormula;
    split(mainFormula, mainSubformulas);
    process(mainSubformulas, mainContent);
    int n;
    cin >> n;
    string formulaToCompare;
    vector<string> subformulasToCompare;
    map<string, int> contentToCompare;
    for (int i = 0; i < n; i++)
    {
        subformulasToCompare.clear(); //
        contentToCompare.clear();
        cin >> formulaToCompare;
        split(formulaToCompare, subformulasToCompare);
        process(subformulasToCompare, contentToCompare);
        cout << mainFormula << (mainContent == contentToCompare ? "==" : "!=") << formulaToCompare << endl;
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

#include <iostream>

#include <cmath>

#include <string>

#include <vector>

#include <map>

using namespace std;

bool isDigit(char c) { return c >= '0' && c <= '9'; }

bool isUpperCaseLetter(char c) { return c >= 'A' && c <= 'Z'; }

bool isLowerCaseLetter(char c) { return c >= 'a' && c <= 'z'; }

void update(map<string, int> &map, string key, int value)

{

if (map.count(key)) //вернет 0 (false) если элемент не найден, иначе - 1 (true)

{

map.at(key) = map.at(key) + value; //обновляем значение элемента в карте

}

else

{

map.insert(make_pair(key, value)); //добавляем элемент в карту

}

void split(string formula, vector<string> &storage)

{

int begin = 0, length = 0;

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

{

if (formula.at(i) == '+')

{

storage.push_back(formula.substr(begin, length));

length = 1;

begin = ++i;

}

else

{

length++;

}

storage.push_back(formula.substr(begin, length));

}

int getMultiplier(string formula)

{

int res = 0;

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

{

if (isDigit(formula.at(i)))

{

res *= 10;

res += (formula.at(i) - '0'); //получаем из символа соответствующую цифру

}

else break;

}

return res == 0 ? 1 : res; //0 - если перед формулой нет множителя, тогда он должен быть 1

}

void getContent(string formula, int multiplier, map<string, int> &content)

{

if (formula.find('(') != string::npos) //если есть скобки

{

int begin = formula.find('(') + 1; //первый символ внутри скобок

int end;

int bracketCounter = 1;

for (int i = begin; true; i++)

{

if (formula.at(i) == '(')

{

bracketCounter ++;

}

else if (formula.at(i) == ')')

{

bracketCounter--;

if (bracketCounter == 0)

{

end = i; //находим соответствующую закрывающую скобку

break;

}

int newMultiplier = multiplier;

int afterEnd = end + 1;

int backCoefficient = 0; //вычисляем коэффициент за скобочным выражением

for (int i = 1; true; i++)

{

if (end + i != formula.length() && isDigit(formula.at(end + i))) //пока есть числа за закрывающей скобкой, обновляем значение заднего коэффициента

{

backCoefficient *= 10;

backCoefficient += (formula.at(end + i) - '0');

afterEnd++;

}

else

{

if (backCoefficient == 0) //если чисел после закрывающей скобки нет, коэффициент равен 1

{

backCoefficient++;

}

newMultiplier *= backCoefficient; //вычисляем новое значение множителя для выражения внутри скобок

break;

}

if (begin != 1)

{

getContent(formula.substr(0, begin - 1), multiplier, content);

}

getContent(formula.substr(begin, end - begin), newMultiplier, content);

if (afterEnd < formula.length())

{

getContent(formula.substr(afterEnd), multiplier, content);

}

else //если скобок нет

{

string name = "";

string coefficient = "";

for (char c : formula)

{

if (isDigit(c))

{

coefficient += c;

}

else if (isLowerCaseLetter(c))

{

name += c;

}

else if (isUpperCaseLetter(c))

{

if (name.empty())

{

name += c;

}

else

{

if (coefficient.empty())

{

coefficient = "1";

}

update(content, name, multiplier * stoi(coefficient));

name.clear();

name += c;

coefficient = "";

}

if (!name.empty())

{

if (coefficient.empty())

{

coefficient = "1";

}

update(content, name, multiplier * stoi(coefficient));

}

void process(vector<string> subformulas, map<string, int> &content)

{

for (string subformula : subformulas) //для каждой подформулы:

{

int multiplier = getMultiplier(subformula); //вычисляем множитель перед ней

if (multiplier != 1) //если множитель записан явно

{

getContent(subformula.substr(floor(log10(multiplier)+1)), multiplier, content); //передаем в функцию подформулу, начиная с первого символа, не относящегося к переднему множителю

}

else

{

getContent(subformula, multiplier, content); //иначе передаем подформулу целиком

}

int main()

{

string mainFormula;

vector<string> mainSubformulas;

map<string, int> mainContent;

cin >> mainFormula;

split(mainFormula, mainSubformulas);

process(mainSubformulas, mainContent);

int n;

cin >> n;

string formulaToCompare;

vector<string> subformulasToCompare;

map<string, int> contentToCompare;

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

{

subformulasToCompare.clear(); //

contentToCompare.clear();

cin >> formulaToCompare;

split(formulaToCompare, subformulasToCompare);

process(subformulasToCompare, contentToCompare);

cout << mainFormula << (mainContent == contentToCompare ? "==" : "!=") << formulaToCompare << endl;

}

return 0;

}

Ссылки

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

Код на ideaone.

Related Images:

e-olymp 2165. Лишние пробелы

21/02/2016 by Настя Панько

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

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

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

Дана строка [latex]s[/latex] (0 ≤ |S| ≤ 255). Строка содержит только латинские буквы и пробелы.

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

Требуется вывести строку без лишних пробелов.

Код

#include <iostream>
#include <string>
     
using namespace std;
     
int main(){
    string s;
    getline(cin, s);
    for (int i = 0; i < s.length(); i++)
         if (s[i] == ' ' && s[i + 1] == ' ') {s.erase(i, 1); i = (i - 1);}
    cout << s << endl;
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main(){

string s;

getline(cin, s);

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

if (s[i] == ' ' && s[i + 1] == ' ') {s.erase(i, 1); i = (i - 1);}

cout << s << endl;

return 0;

}

Код

#include <iostream>
#include <cstring>
     
using namespace std;
     
const short SIZE = 257;     
int main(){
    int j = 0;
    char * str1 = new char[SIZE];
    char * str2 = new char[SIZE];
    cin.getline(str1, SIZE);
    int space = 0;
    for (int i = 0; i < strlen(str1); i++) {
         if (str1[i] == ' '){
            while (!space){ // space != 0
                  str2[j] = ' ';
                  j++;
                  space = 1;
            }
         }
         else {
             str2[j] = str1[i];
             j++;
             space = 0;
        }
    }
    str2[j] = 0;
    printf("%s", str2);
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

const short SIZE = 257;

int main(){

int j = 0;

char * str1 = new char[SIZE];

char * str2 = new char[SIZE];

cin.getline(str1, SIZE);

int space = 0;

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

if (str1[i] == ' '){

while (!space){ // space != 0

str2[j] = ' ';

j++;

space = 1;

}

else {

str2[j] = str1[i];

j++;

space = 0;

}

str2[j] = 0;

printf("%s", str2);

return 0;

}

Тесты

Alexandr      Sergeevich   Pushkin

1	Alexandr Sergeevich Pushkin

Alexandr Sergeevich Pushkin

1	Alexandr Sergeevich Pushkin

Ivanov Maxim

Ivanov Maxim

1	Ivanov Maxim

Scott Fitzgerald

Scott Fitzgerald

1	Scott Fitzgerald

Gertruda Stal

Gertruda Stal

1	Gertruda Stal

John Green

John Green

1	John Green

Решение

Первый код написан на string. Вводим строку [latex]s[/latex], которая содержит латинские буквы и пробелы. В цикле рассматриваем все символы строки от начала до конца. В условии после каждого следующего символа ставим пробелы, используем функцию erase, которая удаляет из строки лишние пробелы. Выводим строку.

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

Ideone.com

Related Images:

e-olymp 1080. Анаграмматическое расстояние

21/12/2015 by Антон Локтев

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

Два слова называются анаграмматически одинаковыми, если из букв одного слова можно получить другое слово. Например, occurs является анаграммой для слова succor; и наоборот, dear не является анаграммой слова dared (так как буква d встречается дважды в dared, и только один раз в dear). Наиболее известной английской анаграммой являются слова dog и god.

Анаграмматическим расстоянием двух слов называется минимальное количество букв, которые нужно удалить, чтобы в результате два слова стали анаграмматически одинаковыми. Например, для слов sleep и leap, нужно удалить как минимум три буквы — две из sleep и одну из leap — чтобы остались анаграмматически одинаковые слова (в указанном случае lep). А для слов dog и cat, в которых нет одинаковых букв, анаграмматическое расстояние равно [latex]6[/latex], так как нужно удалить все буквы (любое слово, в том числе и пустая строка, являются анаграммой само к себе).

Ваша задача найти анаграмматическое расстояние для заданных двух слов.

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

В первой строке задано положительное целое число [latex]N[/latex] (не превышающее [latex]60000[/latex]), указывающее количество тестовых примеров. Каждый тестовый пример состоит из двух слов, возможно пустых, каждое из которых записано в отдельной строке (всего [latex]2N[/latex]последующих строк).

Все слова, имеющие не нулевую длину, сформированы из строчных букв английского алфавита (abcdefghijklmnopqrstuvwxyz). Самым длинным словом является pneumonoultramicroscopicsilicovolcanoconiosis.

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

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

Ссылка на задачу находится здесь.

Тесты

№	Входные данные	Выходные данные
1	4 crocus succor dares seared empty smell lemon	Case #1: 0 Case #2: 1 Case #3: 5 Case #4: 4
2	1	Case #1: 0
3	5 lol lolipop primate mathematics kangaroo kilimanjaro sister sisters android andromeda	Case #1: 4 Case #2: 8 Case #3: 7 Case #4: 1 Case #5: 4

Код (cstring)

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

const short maxSize = 46;

int main() {
	int n, matchingLetters;
	cin >> n;
	cin.ignore();
	char *word_1 = new char[maxSize]; 
	char *word_2 = new char[maxSize];
	for (int i = 0; i < n; i++) {
		 matchingLetters = 0;
		 cin.getline(word_1, maxSize);
		 cin.getline(word_2, maxSize);
		 for (int j = 0; j < strlen(word_1); j++) {
		 	  for (int k = 0; k < strlen(word_2); k++)  {
		 	  	   if (word_1[j] == word_2[k]) {
		 	  	   	   word_2[k] = '#';
		 	  	       matchingLetters++;
		 	  	       break;
		 	  	   }
		 	  }
		 }
		 cout << "Case #" << i + 1 << ":  " << strlen(word_1) + strlen(word_2) - 2 * matchingLetters << endl;
	}
	return 0;
}

#include <cstring>

#include <iostream>

using namespace std;

const short maxSize = 46;

int main() {

int n, matchingLetters;

cin >> n;

cin.ignore();

char *word_1 = new char[maxSize];

char *word_2 = new char[maxSize];

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

matchingLetters = 0;

cin.getline(word_1, maxSize);

cin.getline(word_2, maxSize);

for (int j = 0; j < strlen(word_1); j++) {

for (int k = 0; k < strlen(word_2); k++) {

if (word_1[j] == word_2[k]) {

word_2[k] = '#';

matchingLetters++;

break;

}

cout << "Case #" << i + 1 << ": " << strlen(word_1) + strlen(word_2) - 2 * matchingLetters << endl;

}

return 0;

}

Код на ideone можно найти здесь.

Ход решения

Наша задача состоит в определении количества символов в двух строках, которые необходимо удалить для того, чтобы слова считались анаграммами. Используем после ввода числа примеров [latex]n[/latex] функцию cin.ignore(), для игнорирования перехода на новую строку, а затем считываем по парам слова. Последовательно проходим все буквы слова в первой строке с помощью цикла for. Если находим эту букву в слове второй строки, увеличиваем счётчик совпадающих букв. Совпадающую букву во второй строке заменяем на символ #, дабы избежать повторных проверок одной и той же буквы в случае её неоднократного появления в первой строке. Общее количество букв в двух строках равняется сумме длин первой и второй строк. Таким образом, чтобы получить анаграмматическое расстояние необходимо вывести:

strlen(word_1) + strlen(word_2) - 2 * matchingLetters

26	strlen(word_1) + strlen(word_2) - 2 * matchingLetters

Умножение matchingLetters на [latex]2[/latex] возникает вследствие того, что (по факту) нужно зачёркивать символы в двух строках.

Стоит отметить, что в задаче не требуется реализовывать поиск символа самостоятельно. Можно воспользоваться уже встроенной функцией для работы со строками strchr(), которая вернёт нам указатель на искомый символ. Если символ не будет найден, функция вернёт NULL. Тогда наш код приобретает следующий вид:

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

const short maxSize = 46;

int main() {
	int n, matchingLetters;
	cin >> n;
	cin.ignore();
	char *word_1 = new char[maxSize]; 
	char *word_2 = new char[maxSize];
	for (int i = 0; i < n; i++) {
		 matchingLetters = 0;
		 cin.getline(word_1, maxSize);
		 cin.getline(word_2, maxSize);
		 for (int j = 0; j < strlen(word_1); j++) {
		 	  if (strchr(word_2, word_1[j])) {
		 	  	   *strchr(word_2, word_1[j]) = '#';
		 	  	   matchingLetters++;
		 	  }
		 }
		 cout << "Case #" << i + 1 << ":  " << strlen(word_1) + strlen(word_2) - 2 * matchingLetters << endl;
	}
	return 0;
}

#include <cstring>

#include <iostream>

using namespace std;

const short maxSize = 46;

int main() {

int n, matchingLetters;

cin >> n;

cin.ignore();

char *word_1 = new char[maxSize];

char *word_2 = new char[maxSize];

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

matchingLetters = 0;

cin.getline(word_1, maxSize);

cin.getline(word_2, maxSize);

for (int j = 0; j < strlen(word_1); j++) {

if (strchr(word_2, word_1[j])) {

*strchr(word_2, word_1[j]) = '#';

matchingLetters++;

}

cout << "Case #" << i + 1 << ": " << strlen(word_1) + strlen(word_2) - 2 * matchingLetters << endl;

}

return 0;

}

Код на ideone можно найти здесь.

Код (string)

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

int main() {
	int n, matchingLetters;
	cin >> n;
	cin.ignore();
	string word_1, word_2;
	for (int i = 0; i < n; i++) {
		 matchingLetters = 0;
		 getline(cin, word_1);
		 getline(cin, word_2);
		 for (int j = 0; j < word_1.size(); j++) {
		 	  if (word_2.find(word_1[j]) != string::npos) {
		 	  	  word_2[word_2.find(word_1[j])] = '#';
		 	  	  matchingLetters++;
		 	  }
		 }
		 cout << "Case #" << i + 1 << ":  " << word_1.size() + word_2.size() - 2 * matchingLetters << endl;
	}
	return 0;
}

#include <string>

#include <iostream>

using namespace std;

int main() {

int n, matchingLetters;

cin >> n;

cin.ignore();

string word_1, word_2;

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

matchingLetters = 0;

getline(cin, word_1);

getline(cin, word_2);

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

if (word_2.find(word_1[j]) != string::npos) {

word_2[word_2.find(word_1[j])] = '#';

matchingLetters++;

}

cout << "Case #" << i + 1 << ": " << word_1.size() + word_2.size() - 2 * matchingLetters << endl;

}

return 0;

}

В случае решения данной задачи с помощью класса string используем функцию find() для поиска заданного символа в строке.

Код на ideone можно найти здесь.

Ссылка на засчитанное решение.

Related Images:

e-olymp 2459. Юбилей Винни-Пуха

20/12/2015 by Павел Загинайло

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

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

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

Входной файл содержит дату Юбилея Винни-Пуха в формате dd.mm.gggg. Гарантируется, что дата корректна.

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

В выходной файл нужно вывести YES, если дата, читающаяся справа налево корректна, и NO в противном случае.

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

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

string reverse(string s){
	string y;
	for (int i = 0; !s.empty(); i++){
		if (s.back() != '.'){
			y.push_back(s.back());
			s.pop_back();
		}
		if (s.back() == '.') s.pop_back();
	}
	return y;
}

bool is_leap(int year){
	bool leap;
	if ((year % 400) == 0) leap = true;
	else if ((year % 100) == 0) leap = false;
	else if ((year % 4) == 0) leap = true;
	else leap = false;
	return leap;
}

int get_days (int month, int year){
	int days;
	switch (month) {
		case 1:
		case 3:
		case 5:
		case 7:
		case 8:
		case 10:
		case 12:
		    days = 31;
		    break;
		case 4:
		case 6:
		case 9:
		case 11:
		    days = 30;
		    break;
		case 2:
			is_leap(year)?days = 29:days=28;
		    break;
		default:
		    days = -1;
    }
    return days;
}

int main() {
	string s,y;
	getline(cin, s);
	y = reverse(s);
	int day = stoi(y.substr(0,2));
	int month = stoi(y.substr(2,2));
	int year = stoi(y.substr(4,4));
	cout << (((month>=1)&&(month<=12)&&(day >= 1)&&(day <= (get_days(month, year))))?"YES":"NO");

	return 0;
}

#include <iostream>

#include <string>

using namespace std;

string reverse(string s){

string y;

for (int i = 0; !s.empty(); i++){

if (s.back() != '.'){

y.push_back(s.back());

s.pop_back();

}

if (s.back() == '.') s.pop_back();

}

return y;

}

bool is_leap(int year){

bool leap;

if ((year % 400) == 0) leap = true;

else if ((year % 100) == 0) leap = false;

else if ((year % 4) == 0) leap = true;

else leap = false;

return leap;

}

int get_days (int month, int year){

int days;

switch (month) {

case 1:

case 3:

case 5:

case 7:

case 8:

case 10:

case 12:

days = 31;

break;

case 4:

case 6:

case 9:

case 11:

days = 30;

break;

case 2:

is_leap(year)?days = 29:days=28;

break;

default:

days = -1;

}

return days;

}

int main() {

string s,y;

getline(cin, s);

y = reverse(s);

int day = stoi(y.substr(0,2));

int month = stoi(y.substr(2,2));

int year = stoi(y.substr(4,4));

cout << (((month>=1)&&(month<=12)&&(day >= 1)&&(day <= (get_days(month, year))))?"YES":"NO");

return 0;

}

Тесты

Входные данные	Выходные данные
23.02.2002	YES
20.02.2023	NO
20.12.2015	NO
20.12.2051	YES

Решение

Как только получили строку из стандартного ввода, воспользуемся функцией reverse(). Эта функция записывает нашу строку «задом наперед», в это же время удаляя символ ‘.’ из строки. Так как я точно знаю, что строка из ввода записана верно, то я могу не проверять остальные символы. Пользуясь этим же фактом я завел три переменные целочисленного типа: day, month, year. В новой строке присутствуют только цифры, поэтому я присваиваю каждой новой переменной соответствующие подстроки, после приведения типа string к типу int с помощью функции stoi(). В выводе проверяется соответствуют ли значения дня и месяца требованиям. День проверяется с помощью функции get_days(). Она позволяет получить количество дней в зависимости от месяца и года. В самой функции get_days() используется функция is_leap(), которая проверяет год на високосность и возвращается булевское значение. В зависимости от этого значения, изменяется значение количества дней в феврале — 28 или 29 соответственно. Когда наши числа прошли все проверки, то мы получаем на вывод «YES», если новая дата является корректной или «NO» в ином случае.

Код на ideone.com

Засчитанная задача на e-olymp.com

Related Images:

e-olymp 2040. Обычная перестановка.

20/12/2015 by Кондратюк Настя

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

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

По заданным двум строкам a и b следует вывести такую строку x наибольшей длины, которая одновременно является подстрокой перестановки a и подстрокой перестановки b.

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

Состоит из нескольких тестов, каждый их которых содержит две строки. То есть строки 1 и 2 — это первый тест, строки 3 и 4 — второй тест и т.д. Каждая строка состоит из символов нижнего регистра, причём первой строкой в паре является a, а второй строкой b. Максимальная длина каждой строки 1000 символов.

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

Для каждого теста следует в отдельной строке вывести строку x. Если таких строк несколько, то вывести наименьшую в алфавитном порядке.

Тесты

Входные данные	Выходные данные
walking down	nw
the street	et
abcd efg
abbcdd badbc	abbcd

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

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

int main() {
	string a, b;
	while(getline(cin, a) && getline(cin, b)){
		for(char letter ='a'; letter <= 'z'; ){
			if((a.find(letter)!=string::npos) && 
			   (b.find(letter)!=string::npos)){ /* если буква есть в 
                            обеих строках */
				cout << letter;
				a.erase(a.find(letter),1); /* стираем найденную 
				букву в первой строке */
				b.erase(b.find(letter),1); /* стираем найденную 
				букву во второй строке */
			}
			else letter++; /* если буквы нет в обеих строках,
                        переходим к следующей букве алфавита */
		}
	    cout << endl;
	}

	return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string a, b;

while(getline(cin, a) && getline(cin, b)){

for(char letter ='a'; letter <= 'z'; ){

if((a.find(letter)!=string::npos) &&

(b.find(letter)!=string::npos)){ /* если буква есть в

обеих строках */

cout << letter;

a.erase(a.find(letter),1); /* стираем найденную

букву в первой строке */

b.erase(b.find(letter),1); /* стираем найденную

букву во второй строке */

}

else letter++; /* если буквы нет в обеих строках,

переходим к следующей букве алфавита */

}

cout << endl;

}

return 0;

}

ideone.com

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

Решение

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

Related Images:

e-olymp 2166: Анаграммы

20/12/2015 by Алина Гончарова

Задача

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

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

Два слова заданы в отдельных строках. Слова состоят из строчных латинских букв и цифр. Длины слов не превышают 255.

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

Следует вывести «YES«, если введенные слова являются анаграммами друг друга и «NO» если нет.

Решение 1

В данной задаче требуется определить являются ли два введенных слова анаграммами. Для этого заведем две отдельные строки и считаем их.
Основная проблема состоит в том, что буквы находятся в словах на различных позициях и это мешает нам просто сравнить строки. Поэтому упорядочим символы в строке, например, по возрастанию с помощью встроенной функции sort().
Теперь мы можем выполнить сравнение строк с помощью функции strcmp(), которая вернет нам 0 только в том случае, если строки идентичны. В таком случае и выводим «YES», а в противном случае «NO».

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

#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
 
const short SIZE = 256;
 
int main() {
	char *a = new char[SIZE]; 
	char *b = new char[SIZE];
	cin.getline(a, SIZE);
	cin.getline(b, SIZE);
	sort(a, a + strlen(a));	
	sort(b, b + strlen(b));
	cout << (strcmp(a, b) == 0 ? "YES" : "NO");
	return 0;
}

#include <algorithm>

#include <iostream>

#include <cstring>

using namespace std;

const short SIZE = 256;

int main() {

char *a = new char[SIZE];

char *b = new char[SIZE];

cin.getline(a, SIZE);

cin.getline(b, SIZE);

sort(a, a + strlen(a));

sort(b, b + strlen(b));

cout << (strcmp(a, b) == 0 ? "YES" : "NO");

return 0;

}

Решение 2

Решение аналогично, но нам не нужно теперь использовать функцию strcmp(), а мы просто сравниваем получившиеся строки, смотрим равны ли они, если да, то выводим «YES», а в противном случае «NO».

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

#include <algorithm>
#include <iostream>
#include <string>
using namespace std;
 
int main() {
	string a, b;
	cin >> a >> b;
	sort(a.begin(), a.end());	
	sort(b.begin(), b.end());
	cout << (a == b ? "YES" : "NO");
	return 0;
}

#include <algorithm>

#include <iostream>

#include <string>

using namespace std;

int main() {

string a, b;

cin >> a >> b;

sort(a.begin(), a.end());

sort(b.begin(), b.end());

cout << (a == b ? "YES" : "NO");

return 0;

}

Тесты

Входные данные	Выходные данные
sharm marsh	YES
ananas nnaass	NO
tommarvoloriddle iamlordvoldemort	YES

Задача взята отсюда.

Решенная задача на e-olymp.

Код на Ideone.com: c-string, string.

Related Images:

e-olymp 912. Количество предложений

20/12/2015 by Александр Коломеец

Постановка задачи

e-olymp 912. Количество предложений

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

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

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

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

Единственное число — количество предложений в фрагменте.

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

Нужно заметить, что каждое предложение может заканчиваться точкой, восклицательным знаком или вопросительным знаком. Значит, если в тексте мы нашли какой-то из этих символов, то мы нашли и предложение. Но возникает проблема. Предложение может заканчиватся несколькими знаками препинания (к примеру, многоточием). Так как многоточие — это три поставленых рядом точки, то, если считать количество предложений как количество знаков препинания, которыми может заканчиваться предложение, мы, вероятнее всего, допустим ошибку. Это решается легким путем: при встрече таких знаков, идущих подряд, мы берем во внимание только один из них, игнорируя остальные. Таким образом мы можем подсчитать количество предложений.

Тесты

Входные данные	Выходные данные
Hello, World!	1
Those lips that Love’s own hand did make Breathed forth the sound that said ‘I hate,’ To me that languish’d for her sake: But when she saw my woeful state, Straight in her heart did mercy come, Chiding that tongue that ever sweet Was used in giving gentle doom, And taught it thus anew to greet: ‘I hate’ she alter’d with an end, That follow’d it as gentle day Doth follow night, who like a fiend From heaven to hell is flown away; ‘I hate’ from hate away she threw, And saved my life, saying — ‘not you.’	1
Winter…	1
Winter	0

Реализация

ideone: ссылка
Засчитаное решение: ссылка

#include <iostream>
using namespace std;

bool isNeededChar(char c) {
	switch(c) {
		case '.':
		case '!':
		case '?':
			return true;
		default:
			return false;
	}
}

int main() {
	int counter = 0;
	string text;
	getline(cin, text);
	for(int i = 1; i < text.length(); i++) {
		if(isNeededChar(text.at(i))) {
			if(!isNeededChar(text.at(i - 1))) {
				counter++;
			}
		}
	}
	cout << counter << endl;
	return 0;
}

#include <iostream>

using namespace std;

bool isNeededChar(char c) {

switch(c) {

case '.':

case '!':

case '?':

return true;

default:

return false;

}

int main() {

int counter = 0;

string text;

getline(cin, text);

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

if(isNeededChar(text.at(i))) {

if(!isNeededChar(text.at(i - 1))) {

counter++;

}

cout << counter << endl;

return 0;

}

Related Images:

e-olymp 2162. Палиндром

19/12/2015 by Кудымовская Вика

Задача. Палиндром

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

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

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

Дана строка [latex]S[/latex], [latex]|S| \leq 255[/latex], состоящая из строчных латинских букв и пробелов. Под [latex]|S|[/latex] подразумевается длина строки.

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

Требуется вывести «YES«, если текст является палиндромом, «NO» если не является.

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

Тестирование

№	Входные данные	Выходные данные
1.	palindrom	NO
2.	a roza upala na lapu azora	YES
3.	my gym	YES
4.	character	NO

Реализация (с использованием c-string)

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

int main()
{
	const int startSize = 256;
	char s[startSize];
	char s_1[startSize];
	cin.getline(s, 256);
	int j = 0;
	for (int i = 0; i < startSize; i++)
	{
		if (s[i] == ' ') continue; 
		//учитываем, что пробел при чтении никак не произносится
		s_1[j] = s[i];
		j++;
	}
	int resSize = strlen(s_1);
	char * s_2 = new char[resSize + 1];
	for (int i = 0; i < resSize; i++)
	{
		s_2[i] = s_1[resSize - 1 - i];
	}
	s_2[resSize] = '\0';
	if (!strcmp(s_1, s_2))
	{
		cout << "YES\n";
	}
	else
	{
		cout << "NO\n";
	}
	return 0;
}

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

int main()

{

const int startSize = 256;

char s[startSize];

char s_1[startSize];

cin.getline(s, 256);

int j = 0;

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

{

if (s[i] == ' ') continue;

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

s_1[j] = s[i];

j++;

}

int resSize = strlen(s_1);

char * s_2 = new char[resSize + 1];

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

{

s_2[i] = s_1[resSize - 1 - i];

}

s_2[resSize] = '\0';

if (!strcmp(s_1, s_2))

{

cout << "YES\n";

}

else

{

cout << "NO\n";

}

return 0;

}

Алгоритм решения (c-string)

С помощью функции [latex]strcmp()[/latex] сравниваем символы строк [latex] s_1[/latex] и [latex]s_2[/latex], предварительно учтя тот факт, что пробел при чтении никак не произносится. Если они идентичны, введенный текст одинаково читается слева направо и справа налево, то есть является палиндромом. В противном случае, текст палиндромом не является. Важно отметить, что функция [latex]strcmp()[/latex] учитывает регистр введенных символов, согласно условию мы должны использовать строчные латинские буквы.

Для запроса на выполнение следует перейти по ссылке.

Ссылка на засчитанное решение на e-olymp.com.

Реализация (с использованием string)

#include <iostream>
#include <string>
using namespace std;
 
int main() {
	string s;
    char c;
    while (cin >> c)
    {
        if (c != ' ') 
        	s.push_back(c);
    }
    if (s.empty())
    {
        cout << "YES";
        return 0;
    }
    bool palindrom = true;
    for (int i = 0; i <= s.length()/2; i++)
    {
        if (s.at(i) != s.at(s.length()-1-i))
        {
            palindrom = false;
            break;
        }
    }
    cout << (palindrom ? "YES" : "NO");
	return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

char c;

while (cin >> c)

{

if (c != ' ')

s.push_back(c);

}

if (s.empty())

{

cout << "YES";

return 0;

}

bool palindrom = true;

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

{

if (s.at(i) != s.at(s.length()-1-i))

{

palindrom = false;

break;

}

cout << (palindrom ? "YES" : "NO");

return 0;

}

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

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

Для запроса на выполнение следует перейти по ссылке.

Ссылка на засчитанное решение на e-olymp.com.

Related Images:

e-olymp 901.Количество операций

03/12/2015 by Станислав Коциевский

Задача.

Определить общее количество операций сложения (+), вычитания (—) и умножения (*) в заданном арифметическом выражении.

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

В единственной строке задано арифметическое выражение, не содержащее скобок и пробелов. Количество символов в выражении не превышает 250.

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

Единственное число — количество указанных операций.

Тесты:

входящая строка	результат первой программы	результат второй программы	результат третей программы
-5+20-a+2*c	4	4	4
20+40-a	2	2	2
-2+2+2+2-a46-2*5-	8	8	8
2+6*6	2	2	2

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

Первый способ. Потоковая обработка символов.

#include 
using namespace std;
 
bool f (char x)
{
	return ((x<='9') || (x>='a' && x<='z') || (x>='A' && x<='Z')); //Проверяем является ли символ частью числа или переменной.
}
 
int main()
{
	char a,b,c;
	int n=0;
	a=getchar();
	b=getchar();
	while (EOF!=(c=getchar()))
	{
		if (f(a)&&f(c)&&(b=='*' || b=='-' || b=='+'))
		{
			n++;
		}
		a=b;
		b=c;
	}
	cout<<n;
	return 0;
}

#include

using namespace std;

bool f (char x)

{

return ((x<='9') || (x>='a' && x<='z') || (x>='A' && x<='Z')); //Проверяем является ли символ частью числа или переменной.

}

int main()

{

char a,b,c;

int n=0;

a=getchar();

b=getchar();

while (EOF!=(c=getchar()))

{

if (f(a)&&f(c)&&(b=='*' || b=='-' || b=='+'))

{

n++;

}

a=b;

b=c;

}

cout<<n;

return 0;

}

Второй способ. c-string.

#include <iostream>
#include <cstring>
using namespace std;
 
bool f (char x)
{
	return ((x<='9') || (x>='a' && x<='z') || (x>='A' && x<='Z')); //Проверяем является ли символ частью числа или переменной.
}
 
int main()
{
	short int k = 0;
	char s[250];
	while (cin>>s[k])
	{
		k++;
	}
	
	char * c = strpbrk (s+1, "+-*");
	short int n = 0;
	while (c!=NULL)
	{
		if (f(s[c-1 - s]) && f(s[c+1-s])&&(c-s!=k-1))
		{
			n++;
		}
		s[c-s] = ' ';
		c = strpbrk (s+1, "+-*");
	}
	cout<<n;
	return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

bool f (char x)

{

return ((x<='9') || (x>='a' && x<='z') || (x>='A' && x<='Z')); //Проверяем является ли символ частью числа или переменной.

}

int main()

{

short int k = 0;

char s[250];

while (cin>>s[k])

{

k++;

}

char * c = strpbrk (s+1, "+-*");

short int n = 0;

while (c!=NULL)

{

if (f(s[c-1 - s]) && f(s[c+1-s])&&(c-s!=k-1))

{

n++;

}

s[c-s] = ' ';

c = strpbrk (s+1, "+-*");

}

cout<<n;

return 0;

}

Третий способ. Класс string.

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

bool f (char x)
{
	return ((x<='9') || (x>='a' && x<='z') || (x>='A' && x<='Z')); //Проверяем является ли символ частью числа или переменной.
}
int NOP (string s, char c) //функция, читающая, сколько раз символ c встречается в строке s
{
	int n=0;
	
	if (s.find_first_of(c) == s.find_last_of(c)) // проверяем, больше ли вхождений символа с в троку, чем 1
	{
		if (s.find_first_of(c)<s.size() && s.find_first_of(c)>0)
			return 1;
		else
			return 0;
	}
	
	size_t i=s.find_first_of(c); //находим первое вхождение символа с и проверяем, не в наале ли он строки. Это делается отдельно, чтобы не выходить за пределы строки.
	if (i!=0)
		if (f(s[i-1])&&f(s[i+1]))
			n++;
	s.at(i) = '_';
	
	size_t q=s.find_last_of(c); //Аналогично, находим последнее вхождение символа с
	if (q == s.size()-1)
		if (f(s[i-1])&&f(s[i+1]))
			n--;
	
	while (i<q)
	{
		i=s.find_first_of(c);
		s.at(i) = '_';
		if (f(s[i-1])&&f(s[i+1]))
			n++;
	}
	return n;
}

int main()
{
	string s;
	getline(cin,s);
	cout<<NOP(s,'+')+NOP(s,'-')+NOP(s,'*');
	return 0;
}

#include <iostream>

#include <string>

using namespace std;

bool f (char x)

{

return ((x<='9') || (x>='a' && x<='z') || (x>='A' && x<='Z')); //Проверяем является ли символ частью числа или переменной.

}

int NOP (string s, char c) //функция, читающая, сколько раз символ c встречается в строке s

{

int n=0;

if (s.find_first_of(c) == s.find_last_of(c)) // проверяем, больше ли вхождений символа с в троку, чем 1

{

if (s.find_first_of(c)<s.size() && s.find_first_of(c)>0)

return 1;

else

return 0;

}

size_t i=s.find_first_of(c); //находим первое вхождение символа с и проверяем, не в наале ли он строки. Это делается отдельно, чтобы не выходить за пределы строки.

if (i!=0)

if (f(s[i-1])&&f(s[i+1]))

n++;

s.at(i) = '_';

size_t q=s.find_last_of(c); //Аналогично, находим последнее вхождение символа с

if (q == s.size()-1)

if (f(s[i-1])&&f(s[i+1]))

n--;

while (i<q)

{

i=s.find_first_of(c);

s.at(i) = '_';

if (f(s[i-1])&&f(s[i+1]))

n++;

}

return n;

}

int main()

{

string s;

getline(cin,s);

cout<<NOP(s,'+')+NOP(s,'-')+NOP(s,'*');

return 0;

}

Решение.

Чтобы подсчитать количество операций, указанных в условии, необходимо подсчитать символы которые соответствуют этим операциям и находятся между переменными или числами. проверять только предыдущий и следующий символ на то, является ли он буквой (значит, он является частью переменной или переменная) или цифрой (значит, он является частью числа или числом). В первой программе это осуществляется потоковой обработкой символов с запоминанием последующего и предыдущего, во второй — созданием массива символов c-string и использованием функции strpbrk, в третей — созданием объекта класса string и использованием функций find_first_of, find_last_of.

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

Ссылка на условие задачи

Ссылки на зачитанные решения:

Первый способ

Второй способ

третий способ

Ссылки на код на ideone:

Первый способ

Второй способ

третий способ

Related Images:

e-olymp 1308. Наибольшая грань подстроки

30/11/2015 by Молоканов Юрий

Условие

Гранью (border, verge, brink) [latex]br[/latex] строки [latex]S[/latex] называется любой собственный префикс этой строки, равный суффиксу [latex]S[/latex].

Строка [latex]S = abaababaabaab[/latex] имеет две грани (не пустые): [latex]ab[/latex] и [latex]abaab[/latex]. Строка [latex]S = abaabaab[/latex] также имеет две грани: [latex]ab[/latex] и [latex]abaab[/latex], но вторая грань — перекрывающаяся. Строка длины [latex]n[/latex] из повторяющегося символа, например [latex]aaaaaaaa[/latex] (или [latex]a^8[/latex]), имеет [latex]n — 1[/latex] грань. Для [latex]S = a^8[/latex] это грани: [latex]a[/latex], [latex]aa[/latex], [latex]aaa[/latex], [latex]aaaa[/latex], [latex]aaaaa[/latex], [latex]aaaaaa[/latex], [latex]aaaaaaa[/latex].

Понятие «собственный префикс» исключает грань, совпадающую с самой строкой.

Длина грани — это количество символов в ней.

Сделаем обобщение задачи. Пусть необходимо вычислить значения наибольших граней для всех подстрок [latex]S[1..i][/latex] ([latex]i = 1..n[/latex]) и сохранить их в массиве [latex]br[1..n][/latex].

Найдите наибольшее значение грани в массиве наибольших граней [latex]br[/latex] для всех подстрок [latex]S[/latex].

Тестирование

№	Входные данные	Выходные данные	Комментарий
1	abaabaab	5	abaab в исходной строке
2	abaababaabaab	6	abaaba в подстроке abaababaabaab
3	aaaaaaaa	7	aaaaaaa в исходной строке
4	YM	0	Грань отсутствует, т.к. префикс и суффикс не могут совпадать с самой строкой, а кроме Y в качестве префикса и M в качестве суффикса вариантов выбора нет
5	&#%*%#&	1	& в исходной строке
6	15015105	2	15 в подстроке 15015105
7	f0A+.f0A+.f0A.+.A0f	8	f0A+.f0A в подстроке f0A+.f0A+.f0A.+.A0f

Код

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

int main() {
    string s;
    getline(cin, s);
    int max = 0;    // Длина наибольшей грани
    for(int i = 1; i < s.length() && s.length() - i > max; i++) { 
        int j = 0;
        /*
        Перебираем различные длины префиксов (суффиксов), пока не дойдем до длины 1 и пока можем встретить грань, длиннее хранящейся.
        i - первый символ очередного суффикса
        j - длина текущей грани и первый символ очередного префикса
        */
        while(j < s.length() - i && s.at(j) == s.at(i + j))  // Накапливаем длину, пока символы префикса и суффикса совпадают
            j++;
        if(j > max)  // Если длина текущей грани больше хранящейся, обновляем максимум
            max = j;
    }
    cout << max;
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

getline(cin, s);

int max = 0; // Длина наибольшей грани

for(int i = 1; i < s.length() && s.length() - i > max; i++) {

int j = 0;

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

i - первый символ очередного суффикса

j - длина текущей грани и первый символ очередного префикса

while(j < s.length() - i && s.at(j) == s.at(i + j)) // Накапливаем длину, пока символы префикса и суффикса совпадают

j++;

if(j > max) // Если длина текущей грани больше хранящейся, обновляем максимум

max = j;

}

cout << max;

return 0;

}

Решение

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

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

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

for(int i = 1; i < s.length() && s.length() - i > max; i++) {   
    int j = 0;
/*
Перебираем различные длины префиксов (суффиксов), пока не дойдем до длины 1 и пока можем встретить грань, длиннее хранящейся.
i - первый символ очередного суффикса
j - длина текущей грани и первый символ очередного префикса
*/

for(int i = 1; i < s.length() && s.length() - i > max; i++) {

int j = 0;

i - первый символ очередного суффикса

j - длина текущей грани и первый символ очередного префикса

Начнем параллельно «двигаться» вправо по строке, проверяя на совпадение соответствующие символы префикса и суффикса и продолжая до тех пор, пока не наткнемся на различные символы или пока не дойдем до конца строки. При этом будем попутно накапливать значение длины текущей грани, пока пары символов совпадают. К примеру, если в очередной итерации первые символы префикса и суффикса — это первый и третий символы строки соответственно, то сначала проверим на совпадение символы на позициях 1 и 3, затем 2 и 4, 3 и 5 и т. д.

C++

while(j < s.length() - i && s.at(j) == s.at(i + j)) j++;

1
2

while(j < s.length() - i && s.at(j) == s.at(i + j))
j++;

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

Отметим, что значение переменной j, получаемое в каждой итерации, представляет собой максимально возможную длину грани либо исходной строки (если проверки на совпадение пар символов закончились из-за достижения конца строки), либо подстроки, получаемой путем отбрасывания правой части исходной до того символа, на котором обнаружилось несовпадение.

Ссылки

Условие задачи на E-Olymp;

Код программы на Ideone.com;

Подтверждение решения на E-Olymp.

Related Images:

e-olymp 331. Предложение — чемпион

30/11/2015 by Сплошнов Кирилл

Условие

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

Замечание

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

Тесты

Входные данные	Номер предложения
No palindrom here. Here it is: abcba! Seriously, I just hate orks…	2
Some random text ahead: AaA o-O-o I. 1 22 333. Result will be 1.	1
Some random text ahead: AaA o-O-o I. 1 22 333 4444. Now result will be 2!	2
Some random text ahead: AaA o-O-o I. 1 — 22 — 333. Result will be 1.	1
No. Palindrom. at. ALL?!	0

Решение

Заведем переменную [latex]currentSentence[/latex], хранящую номер текущего предложения, будем считывать по слову и увеличивать ее значение на 1, если текущее слово заканчивается на точку, восклицательный или вопросительный знак. Далее, поочередно удаляем с конца лишние символы, заменяя их терминальным, пока не встретится первая буква. Затем переводим слово в нижний регистр и проверяем его на палиндромность, если да — увеличиваем на 1 переменную-счетчик кол-ва палиндромов в текущем предложении [latex]palCount[/latex]. Если слово было последним в предложении (за это отвечает флаг [latex]endOfSentence[/latex]) — сравниваем предложение с предыдущим чемпионом, после обнуляем значение [latex]palCount[/latex].

Код

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

int main() 
{
	char s[256];
	int maxPalNum = 0;
	int champion = 0;
	int currentSentence = 1; 
	int palCount = 0;
	while (cin >> s)
	{
		if (s[0] == '-' && strlen(s) == 1) 
			continue; //если тире, то просто считываем следующее слово
		bool endOfSentence = false;
		if (s[strlen(s)-1] == '.' || s[strlen(s)-1] == '!' || s[strlen(s)-1] == '?')
			endOfSentence = true; //слово - последнее в предложении
		for (int i = strlen(s) - 1; i >= 0; i--)
		{
			if (!(s[i] >= 'a' && s[i] <= 'z' || s[i] >= 'A' && s[i] <= 'Z' || s[i] >= '1' && s[i] <= '9' || s[i] == '-'))
				s[i] = '\0';
			else
				break;
		}
		for (int i = 0; i < strlen(s); i++)//перевод в нижний регистр
		{
			if (s[i] >= 'A' && s[i] <= 'Z')
				s[i] += 32;
		}
		bool pal = true;
		for (int i = 0; i < strlen(s) / 2; i++)
		{
			if (s[i] != s[strlen(s)-i-1])
			{
				pal = false;
				break;
			}
		}
		if (pal)
			palCount ++;
		if (endOfSentence) //если слово было последним - сравниваем предложения
		{
			if (palCount > maxPalNum)
			{
				maxPalNum = palCount;
				champion = currentSentence;
			}
			currentSentence++;
			palCount = 0;
		}
	}
	cout << champion;
	return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main()

{

char s[256];

int maxPalNum = 0;

int champion = 0;

int currentSentence = 1;

int palCount = 0;

while (cin >> s)

{

if (s[0] == '-' && strlen(s) == 1)

continue; //если тире, то просто считываем следующее слово

bool endOfSentence = false;

if (s[strlen(s)-1] == '.' || s[strlen(s)-1] == '!' || s[strlen(s)-1] == '?')

endOfSentence = true; //слово - последнее в предложении

for (int i = strlen(s) - 1; i >= 0; i--)

{

if (!(s[i] >= 'a' && s[i] <= 'z' || s[i] >= 'A' && s[i] <= 'Z' || s[i] >= '1' && s[i] <= '9' || s[i] == '-'))

s[i] = '\0';

else

break;

}

for (int i = 0; i < strlen(s); i++)//перевод в нижний регистр

{

if (s[i] >= 'A' && s[i] <= 'Z')

s[i] += 32;

}

bool pal = true;

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

{

if (s[i] != s[strlen(s)-i-1])

{

pal = false;

break;

}

if (pal)

palCount ++;

if (endOfSentence) //если слово было последним - сравниваем предложения

{

if (palCount > maxPalNum)

{

maxPalNum = palCount;

champion = currentSentence;

}

currentSentence++;

palCount = 0;

}

cout << champion;

return 0;

}

Ссылки

Рабочий код на Ideaone.

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

Related Images:

e-olymp 332. Детская железная дорога

28/11/2015 by Таран Таня

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

Какое слово получится у Витэка?

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

Первая и единственная строка содержит исходное слово. Кубики у Витэка только из заглавных букв латинского алфавита и их количество не превышает [latex]500000[/latex].

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

Слово, которое образовал Витэк.

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

Тесты

Входные данные	Выходные данные
CBABC	ABCCB
XXXXX	XXXXX
ABEABFABBABC	ABBABCABEABF
RATOBCQATOBC	ATOBCQATOBCR
OROOXOOSTO	OOROOXOOST
LBDEAFAARDEABBAF	AARDEABBAFLBDEAF

Алгоритм

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

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

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

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

Рассмотрим на произвольно выбранном примере:

LBDEAFAARDEABBAF

Тогда следует сравнить такие подслова:

AFAARDEABBAF
AARDEABBAF
ARDEABBAF
ABBAF
AF

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

Реализуем описанный выше алгоритм на практике с некоторыми особенностями.

Прочитаем слово.
Найдем минимальный символ в данном слове.
Создадим вектор для хранения индексов вхождения минимального символа (indicesOfMinSymbol) и будем добавлять в него значение только в том случае, если текущий символ является минимальным, а предыдущий нет. (Обратившись к предоставленному примеру, можно заметить, что не имеет смысла отдельно проводить сравнение подслов AARDEABBAF и ARDEABBAF, так как первое из них явно «выгоднее». Также мы сможем упростить ситуацию и избавиться от большого количества лишних проверок, когда на вход поступает слово состоящее из всех одинаковых символов (например, XXXXX), в котором не нужно выполнять ни единого сравнения и как-либо изменять слово).
Объявим индекс начала текущего наименьшего лексикографического подслова (indexOfMinLexicSubstr) и для каждого значения из заполненного ранее вектора будем сравнивать от иднекса начала текущего наименьшего лексикографического подслова столько символов, сколько осталось до конца строки от текущего индекса вхождения минимального символа, с подстрокой, начинающейся с этого индекса и заканчивающейся в конце слова, с помощью функции compare. (Рассмотрим произвольные подслова из заданного примера: AFAARDEABBAF и AARDEABBAF. Тогда исходя из пункта 4 следует сравнить подслова AFААRDEABB и AARDEABBAF. Мы имеем полное право выполнить такое упрощение, так как отсутствие следующего символа меньше, чем наличие любого другого символа, и если будет выбрано первое подслово, то второе подслово, стоящее справа от него, автоматически также будет сдвинуто в начало.
Однако существует немаловажное исключение при построении такого алгоритма. Его удобно рассмотреть на каком-либо конкретном случае, например, OROOXOOSTO. Когда мы дойдем до сравнения подслов OOSTO (на данный момент будет являться минимальным) и О, исходя из выше описанного алгоритма, мы получим равенство подстрок и не изменим индекс начала минимальной строки, тогда ложно будет построена как наименьшая лексикографическая строка из данной OOSTOOROOX. Исправить эту проблему можно дополнительной проверкой того, что выйдет при сдвиге второй (более короткой) подстроки в начало заданного слова. То есть для данного примера, можно заметить, что подслово OROO лексикографически меньше чем OSTO (сравниваем такое же количество символов в начале строки, сколько оставалось до конца у текущей наименьшей лексикографической подстроки).
Примечание: следует отметить, что даже без выполнения второй проверки алгоритм проходил все тесты к данной задаче на сайте e-olymp, что может говорить лишь о неполноте тестов.).
И только в том случае, если функция compare в пункте 4 вернула значение больше чем [latex]0[/latex], то есть правое подслово меньше, или же меньше подслово получаемое при сдвиге правой строки в сравнении с текущим наименьшим лексикографическим, тогда изменяем значение индекса минимального лексикографического подслова на текущий индекс вхождения минимального символа.
После прохождения всего вектора, выполняем сдвиг найденного минимального лексикографического подслова в начало, благодаря встроенной функции rotate, и выполняем вывод полученного слова.

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

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

int main() {
	string word;
	cin >> word;
	char minSymbol = word[0]; 
	vector <int> indicesOfMinSymbol; // Вектор для хранения индексов вхождения "минимального" символа
	for (int i = 1; i < word.size(); i++) {
		 if (word[i] < minSymbol) {
		     minSymbol = word[i];
		 }
	} // Поиск "минимального" символа в данном слове
	for (int i = 0; i < word.size(); i++) {
		 if (word[i] == minSymbol && word[i - 1] != minSymbol) {
		     indicesOfMinSymbol.push_back(i);
		 } // Добавляем индекс, если текущий является "минимальным", а предыдущий таковым не был
	} // Заполняем вектор индексами вхождения "минимального" символа
	int indexOfMinLexicSubstr = indicesOfMinSymbol[0]; // Индекс начала текущего минимального лексикографического подслова
	for (int i = 1; i < indicesOfMinSymbol.size(); i++) {
		 if (word.compare(indexOfMinLexicSubstr, word.size() - indicesOfMinSymbol[i], word, indicesOfMinSymbol[i], string::npos) > 0
		 	 || (word.compare(indexOfMinLexicSubstr, word.size() - indicesOfMinSymbol[i], word, indicesOfMinSymbol[i], string::npos) == 0
		 	     &&  word.compare(0, indicesOfMinSymbol[i] - indexOfMinLexicSubstr, word, indexOfMinLexicSubstr + word.size() - indicesOfMinSymbol[i], string::npos) < 0)) {
			 indexOfMinLexicSubstr = indicesOfMinSymbol[i]; 
		 } // Сравниваем текущее минимальное подслово и подслово начинающееся со следующего вхождения "минимального" символа, если они равны, то следует проверить, что выйдет, благодаря задействованию символов из начала строки
    } // Поиск наименьшего лексикографического подслова
	rotate(word.begin(), word.begin() + indexOfMinLexicSubstr, word.end()); // Cдвигаем наименьшее лексикографическое подслово в начало
	cout << word;
	return 0;
}

#include <string>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

string word;

cin >> word;

char minSymbol = word[0];

vector <int> indicesOfMinSymbol; // Вектор для хранения индексов вхождения "минимального" символа

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

if (word[i] < minSymbol) {

minSymbol = word[i];

}

} // Поиск "минимального" символа в данном слове

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

if (word[i] == minSymbol && word[i - 1] != minSymbol) {

indicesOfMinSymbol.push_back(i);

} // Добавляем индекс, если текущий является "минимальным", а предыдущий таковым не был

} // Заполняем вектор индексами вхождения "минимального" символа

int indexOfMinLexicSubstr = indicesOfMinSymbol[0]; // Индекс начала текущего минимального лексикографического подслова

for (int i = 1; i < indicesOfMinSymbol.size(); i++) {

if (word.compare(indexOfMinLexicSubstr, word.size() - indicesOfMinSymbol[i], word, indicesOfMinSymbol[i], string::npos) > 0

|| (word.compare(indexOfMinLexicSubstr, word.size() - indicesOfMinSymbol[i], word, indicesOfMinSymbol[i], string::npos) == 0

&& word.compare(0, indicesOfMinSymbol[i] - indexOfMinLexicSubstr, word, indexOfMinLexicSubstr + word.size() - indicesOfMinSymbol[i], string::npos) < 0)) {

indexOfMinLexicSubstr = indicesOfMinSymbol[i];

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

} // Поиск наименьшего лексикографического подслова

rotate(word.begin(), word.begin() + indexOfMinLexicSubstr, word.end()); // Cдвигаем наименьшее лексикографическое подслово в начало

cout << word;

return 0;

}

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

Засчитанное решение