Category Archives: 7. Строки c-string

Задачи на использование char* — c-строк заканчивающихся символом с кодом 0 и/или массивов символов char[]

Попробуйте решить такую задачу:

Заяц-неудачник
Поле чудес
Реформа (Reform)
Кубики — 3 — используйте функцию сортировки, хоть это и не лучшее решение

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

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

e-olymp 1079. Удаление букв

25/06/2018 by Андрей Святозар Чернецкий

Задача

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

Найдите максимально возможную длину полученного слова.

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

Каждый тест состоит из одной строки, содержащей два заданных слова, разделенных пробелом. Длина каждого слова от $1$ до $200$ символов. Всего имеется не более $10$ тестов.

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

Для каждого теста выведите максимально возможную длину полученных одинаковых слов (длину максимального слова, которое можно получить путем удаления некоторых букв). Если одинаковые слова получить невозможно, то выведите $0$.

Тесты

Входные данные	Выходные данные
AAABBB ABABAB AXYAAZ CCCXCCCYCCCZCC	4 3
AAAAA BBBBB	0
ABABA BCACB	3
STRING GNIRTS	1

String

#include <iostream>
 
using namespace std;
 
int main() {
    string x, y;
    int A[2][1001];
    while (cin >> x  >> y ) 
    {
        for (int i = 0; i < 2; i++){
            for (int j = 0; j < 1001; j++){
                A[i][j] = 0;        
            }
        }
        for (int i = 0; i < x.size(); i++){
            for (int j = 0; j < y.size(); j++){
                if (x[i] == y[j]) A[i % 2][(j + 1)] = 1 + A[(i + 1) % 2][j];
                else A[i % 2][j + 1] = max(A[(i + 1) % 2][j + 1], A[i % 2][j]);
            }
        }
        cout <<  A[(x.size() + 1) % 2][y.size()] << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

string x, y;

int A[2][1001];

while (cin >> x >> y )

{

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

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

A[i][j] = 0;

}

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

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

if (x[i] == y[j]) A[i % 2][(j + 1)] = 1 + A[(i + 1) % 2][j];

else A[i % 2][j + 1] = max(A[(i + 1) % 2][j + 1], A[i % 2][j]);

}

cout << A[(x.size() + 1) % 2][y.size()] << endl;

}

return 0;

}

C-String

#include <iostream>
#include <cstring>
 
using namespace std;
 
int main() {
    string x, y;
    int A[2][1001];
    while (cin >> x  >> y ) 
    {
        for (int i = 0; i < 2; i++){
            for (int j = 0; j < 1001; j++){
                A[i][j] = 0;        
            }
        }
        for (int i = 0; i < x.length(); i++){
            for (int j = 0; j < y.length(); j++){
                if (x[i] == y[j]) A[i % 2][(j + 1)] = 1 + A[(i + 1) % 2][j];
                else A[i % 2][j + 1] = max(A[(i + 1) % 2][j + 1], A[i % 2][j]);
            }
        }
        cout <<  A[(x.length() + 1) % 2][y.length()] << endl;
    }
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

string x, y;

int A[2][1001];

while (cin >> x >> y )

{

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

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

A[i][j] = 0;

}

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

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

if (x[i] == y[j]) A[i % 2][(j + 1)] = 1 + A[(i + 1) % 2][j];

else A[i % 2][j + 1] = max(A[(i + 1) % 2][j + 1], A[i % 2][j]);

}

cout << A[(x.length() + 1) % 2][y.length()] << endl;

}

return 0;

}

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

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

Ссылки

Условие задачи на сайте E-Olymp
код задачи (string) на Ideone
код задачи (c-string) на Ideone
описание расстояния Левенштейна на Wikipedia

Related Images:

e-olymp 670. Поиск палиндромов

20/06/2018 by Костя Григорян

Задача

Строка символов называется палиндромом, если она одинаково читается в обоих направлениях, например, «madam», «bob».
Определите, сколько палиндромов заданной длины $K$ содержит заданная строка $S$.

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

В первой строке содержится целое число $K$ ($2 \leqslant K \leqslant 200$), а во второй – заданная строка $S$, состоящая только из латинских букв, причем большие и малые буквы различаются (т.е. «Bob» — не палиндром). Длина $S$ от $1$ до $30000$ символов.

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

В единственной строке должно находиться количество различных палиндромов длины $K$, содержащихся в $S$ (т.е. являющихся последовательностями подряд идущих символов в $S$) (различными считаются палиндромы, начинающиеся с разных позиций в $S$).

Тесты

Входные данные	Выходные данные
$3$	$3$
$babcbab$
$1$	$5$
$abcde$
$4$	$0$
$aarreeds$
$5$	$3$
$aaaaaaa$
$3$	$0$
$CaccaC$

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

String

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int k;
    cin >> k;
    string s;
    cin >> s;
    int l, r, flag=0, ans=0;
    for(int i=0; i<s.size()-k+1; i++)
    {
        flag=0;
        l=i;
        r=i+k-1;
        for(int j=0; j<k/2; j++)
        {
            if(s[l+j]!=s[r-j]){ 
                flag=1;
                break;
            }
        }
        if(flag==0){
            ans++;
        }
    }
    cout << ans;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

ios_base::sync_with_stdio(false);

cin.tie(0);

int k;

cin >> k;

string s;

cin >> s;

int l, r, flag=0, ans=0;

for(int i=0; i<s.size()-k+1; i++)

{

flag=0;

l=i;

r=i+k-1;

for(int j=0; j<k/2; j++)

{

if(s[l+j]!=s[r-j]){

flag=1;

break;

}

if(flag==0){

ans++;

}

cout << ans;

return 0;

}

C-String

#include <iostream>
#include <cstring>

using namespace std;

const int max_length=30001; 
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int k;
    cin >> k;
    char s[max_length];
    cin >> s;
    int l, r, flag=0, ans=0;
    for(int i=0; i<strlen(s)-k+1; i++)
    {
        flag=0;
        l=i;
        r=i+k-1;
        for(int j=0; j<k/2; j++)
        {
            if(s[l+j]!=s[r-j]){ 
                flag=1;
                break;
            }
        }
        if(flag==0){
            ans++;
        }
    }
    cout << ans;
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

const int max_length=30001;

int main() {

ios_base::sync_with_stdio(false);

cin.tie(0);

int k;

cin >> k;

char s[max_length];

cin >> s;

int l, r, flag=0, ans=0;

for(int i=0; i<strlen(s)-k+1; i++)

{

flag=0;

l=i;

r=i+k-1;

for(int j=0; j<k/2; j++)

{

if(s[l+j]!=s[r-j]){

flag=1;

break;

}

if(flag==0){

ans++;

}

cout << ans;

return 0;

}

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

Мы рассматриваем все подстроки строки $s$ длины $k$ и проверяем, является ли каждая подстрока палиндромом. В случае положительного ответа, увеличиваем счетчик. Проверка, является ли каждая подстрока палиндромом, выполняется следующим образом: мы ставим указатели на противоположные концы подстроки, далее сравниваем элементы на которые указывают указатели и если они равны, одновременно сдвигаем указатели на один к центру этой подстроки. Продолжаем этот процесс до тех пор, пока указатели не «встретятся». Если на каком то этапе элементы не равны, прекращаем процесс с отрицательным ответом для этой подстроки. Если же указатели «встретились», то эта подстрока является палиндромом.

Ссылки

Условие задачи на e-olymp
Код решения. String
Код решения. C-String

Related Images:

e-olymp 1607. Число в обратном порядке

24/05/2018 by Андрей Лисовой

Задача

Запишите целое неотрицательное число $n$ в обратном порядке.

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

Одно целое неотрицательное $64$-х разрядное число.

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

Выведите число в обратном порядке.

Тесты

Входные данные	Выходные данные
$1234$	$4321$
$100$	$001$
$34567$	$76543$
$10983743$	$34738901$
$98352374234$	$43247325389$

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

#include <iostream>
using namespace std;

int main() {
    string s;
    cin>>s;
    for(int i=s.length()-1; i>=0; i--) {
        cout<<s[i];
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

string s;

cin>>s;

for(int i=s.length()-1; i>=0; i--) {

cout<<s[i];

}

return 0;

}

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

Для решения задачи вводим строку. Узнаем ее длину с помощью функции s.length(), затем циклом выводим строку в обратном порядке. Задача решена.

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

#include <iostream>
using namespace std;

int main() {
    char x[64];
    int length=0;
    while(cin>>x[length]) {
        length++;
    }
    for(int i=length-1; i>=0; i--) {
        cout<<x[i];
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

char x[64];

int length=0;

while(cin>>x[length]) {

length++;

}

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

cout<<x[i];

}

return 0;

}

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

Для решения задачи вводим входные данные в массив x[64]. При вводе считаем какое количество символов заполнилось в массив. Затем от этого числа( length) начинаем цикл, который выводит массив в обратном порядке. Задача решена.

Ссылки

Условие задачи на e-olymp
Код решения на ideone.com(String)
Код решения на ideone.com(C-string)

Related Images:

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

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

Задача

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

Вхідні дані

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

Вихідні дані

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

Тести

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

Код програми

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

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

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

int main() {

char s[101];

cin >> s;

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

int k = 1;

char c = s[0];

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

if( s[i] != c ){

c = s[i];

k++;

}

cout << k;

return 0;

}

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

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

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

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

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

#include <iostream>

#include <cstring>

using namespace std;

int main() {

string s;

cin >> s;

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

int i = j + 1;

while (i < s.size()) {

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

s.erase(i,1);

}

else i++;

}

cout << s.size();

return 0;

}

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

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

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

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

#include <iostream>

#include <set>

using namespace std;

int main() {

set<char> k;

set<char>::iterator iter;

char s[101];

cin >> s;

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

k.insert(s[i]);

}

cout << k.size();

return 0;

}

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

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

Посилання

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

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

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

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

Related Images:

e-olymp 3912. Реверс удавов

20/04/2018 by Мороз Дима

Задача

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

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

Первая строка содержит одно число $N (1 ≤ N ≤ 100000)$ – количество удавов. В следующих $N$ строках написаны имена удавов в том порядке, в котором они ползут. Имя удава – строчка, содержащая не более $10$ маленьких латинских букв.

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

Выведите единственную строку – название стаи после команды «Реверс».

Тесты

Входные данные	Выходные данные
3 abc def ghi	ghidefabc
3 zxcgh i db	dbizxcgh
4 mn kjl iu ghj	ghjiukjlmn
8 kdh jg lqwoc kfxvk iduhx nsh s kjwyv	kjwyvsnshiduhxkfxvklqwocjgkdh

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

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

int main () 
{
    int N;
    cin >> N;
    string flock[N];
    for (int i = 0; i < N; i++)
        cin >> flock[i];
    for (int i = N - 1; i >= 0; i--)
        cout << flock[i];
    
    return 0;
}

#include <iostream>

#include <string.h>

using namespace std;

int main ()

{

int N;

cin >> N;

string flock[N];

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

cin >> flock[i];

for (int i = N - 1; i >= 0; i--)

cout << flock[i];

return 0;

}

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

Записываем каждого удава в одномерный массив flock типа string размера N, а затем выводим его, начиная с конца.

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

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

#define boa_name_size 11

int main() 
{
    int N;
    cin >> N;
    char **flock = new char *[N]; // Создаем массив в N строк
    for (int i = 0; i <= N; i++)
        flock[i] = new char[boa_name_size]; // Под каждую строку выделяем массив в boa_name_size символов
    for (int i = 0; i <= N; i++)
        cin.getline(flock[i], boa_name_size);
    for (int i = N; i > 0; i--) 
        cout << flock[i];
    
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

#define boa_name_size 11

int main()

{

int N;

cin >> N;

char **flock = new char *[N]; // Создаем массив в N строк

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

flock[i] = new char[boa_name_size]; // Под каждую строку выделяем массив в boa_name_size символов

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

cin.getline(flock[i], boa_name_size);

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

cout << flock[i];

return 0;

}

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

Записываем каждого удава в динамический массив flock типа char размера $N$ $\times$ boa_name_size, где boa_name_size – это константа, размером в $11$ символов, которую определяем с помощью директивы #define в начале программы. Не $10$, а $11$ потому что в нуль-терминированных строках (c-string) последний символ – символ конца строки '\0'.
Далее выводим наш массив с последней строки до первой.

Ссылки

Условие задачи на e-olymp.com
Решение задачи на ideone.com (string)
Решение задачи на ideone.com (c-string)

Related Images:

e-olymp 440. Подделка чека

27/02/2018 by Кирилл Волков

Задача

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

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

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

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

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

Тесты

Входные данные	Выходные данные
$123321$	$332121$
$7888778888878888788878878777887$	$8888878888788878887778878777887$
$1091$	$9100$
$26364$	$64263$
$98765$	$98765$

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

String

#include <iostream>

using namespace std;

int main()
{
    string s;
    cin >> s;
    string maxS = s;
    int start = s.size() - 1;
    bool found = false;
    for(int i = 0; i < s.size() and !found; i++){
        for(int j = i; j < s.size() and !found; j++){
            if(s[j] > s[i]){
                start = i;
                found = true;
            }
        }
    }
    for(int j = start + 1; j < s.size(); j++){
        if(s[j] >= s[start]) {
            string curMax = s;
            for (int k = j; k < s.size(); k++) {
                curMax.insert(start + k - j, 1, s[k]);
                curMax.erase(k + 1, 1);
                maxS = max(curMax, maxS);
            }
        }
    }
    cout << maxS;
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

string s;

cin >> s;

string maxS = s;

int start = s.size() - 1;

bool found = false;

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

for(int j = i; j < s.size() and !found; j++){

if(s[j] > s[i]){

start = i;

found = true;

}

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

if(s[j] >= s[start]) {

string curMax = s;

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

curMax.insert(start + k - j, 1, s[k]);

curMax.erase(k + 1, 1);

maxS = max(curMax, maxS);

}

cout << maxS;

return 0;

}

C-String

#include <iostream>
#include <cstring>

using namespace std;

const int MAX_LENGTH = 101;

int main() {
    char s[MAX_LENGTH];
    cin >> s;
    char maxS[MAX_LENGTH];
    strcpy(maxS, s);
    int size = strlen(s);
    int start = size - 1;
    bool found = false;
    for(int i = 0; i < size and !found; i++){
        for(int j = i; j < size and !found; j++){
            if(s[j] > s[i]){
                start = i;
                found = true;
            }
        }
    }
    for(int j = start + 1; j < size; j++){
        if(s[j] >= s[start]) {
            char curMax[MAX_LENGTH];
            strcpy(curMax, s);
            for (int k = j; k < size; k++) {
                char temp = s[k];
                for(int i = k; i >  start + k - j; i--){
                    curMax[i] = curMax[i - 1];
                }
                curMax[start + k - j] = temp;
                if(strncmp(curMax, maxS, size) > 0){
                    strcpy(maxS, curMax);
                }
            }
        }
    }
    cout << maxS;
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

const int MAX_LENGTH = 101;

int main() {

char s[MAX_LENGTH];

cin >> s;

char maxS[MAX_LENGTH];

strcpy(maxS, s);

int size = strlen(s);

int start = size - 1;

bool found = false;

for(int i = 0; i < size and !found; i++){

for(int j = i; j < size and !found; j++){

if(s[j] > s[i]){

start = i;

found = true;

}

for(int j = start + 1; j < size; j++){

if(s[j] >= s[start]) {

char curMax[MAX_LENGTH];

strcpy(curMax, s);

for (int k = j; k < size; k++) {

char temp = s[k];

for(int i = k; i > start + k - j; i--){

curMax[i] = curMax[i - 1];

}

curMax[start + k - j] = temp;

if(strncmp(curMax, maxS, size) > 0){

strcpy(maxS, curMax);

}

cout << maxS;

return 0;

}

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

Пусть заданы два числа: $a = \overline{a_1a_2 \ldots a_k},\ b = \overline{b_1b_2 \ldots b_k}$. Тогда $a > b \Leftrightarrow \exists i: \ \forall j < i \ a_j = b_j \ \wedge \ a_i = b_i$. Отсюда получаем необходимое условие получения максимального числа при перестановке в записи числа $a$ групп цифр $\overline{a_ia_{i+1} \ldots a_l}$ и $\overline{a_ja_{j+1} \ldots a_m} \ l<j$ местами: $i = \min_{1 < s < k} s: \ \exists t>s: \ a_t \gt a_s$. Если такое $i$ существует, то далее мы делаем перебор по всем возможным перестановкам, таким что первая группа чисел начинается с индекса $i$ и таким образом находим максимально возможное число. В противном случае данное число уже является максимальным.

Ссылки

Условие задачи на e-olymp
Решение на e-olymp. String
Решение на e-olymp. C-String
Код решения на Ideone. String
Код решения на Ideone. C-String

Related Images:

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

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

Задача

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

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

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

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

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

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

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

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

Тесты

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

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

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

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

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

#include <iostream>

#include <cstring>

using namespace std;

unsigned int cstringpow(const char *s)

{

unsigned int answer = 1;

const unsigned int size = strlen(s);

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

{

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

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

if (size % i == 0)

{

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

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

{

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

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

{

not_broken = 0;

break;

}

if (not_broken)

{

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

answer = size/i;

break;

}

return answer;

}

int main()

{

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

while (cin >> s)

cout << cstringpow(s) << endl;

return 0;

}

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

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

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

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

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

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

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

#include <iostream>

#include <string>

using namespace std;

unsigned int stringpow(const string &s)

{

unsigned int answer = 1;

const unsigned int size = s.size();

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

{

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

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

if (size % i == 0)

{

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

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

{

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

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

{

not_broken = 0;

break;

}

if (not_broken)

{

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

answer = size/i;

break;

}

return answer;

}

int main()

{

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

while (cin >> s)

cout << stringpow(s) << endl;

return 0;

}

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

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

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

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

        out.flush();
    }
}

import java.util.*;

import java.io.*;

public class Main

{

public static int stringpow(String s)

{

int answer = 1;

int size = s.length();

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

{

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

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

if (size % i == 0)

{

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

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

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

{

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

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

{

not_broken = false;

break;

}

if (not_broken)

{

answer = size/i;

break;

}

return answer;

}

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

{

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

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

while(in.hasNextLine())

{

S = in.nextLine();

out.println(stringpow(S));

}

out.flush();

}

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

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

Ссылки

Related Images:

Chuck Norris

11/05/2017 by Антон Куперман

A task from codingame.com

Task

Binary with 0 and 1 is good, but binary with only 0, or almost, is even better! Originally, this is a concept designed by Chuck Norris to send so called unary messages.

Write a program that takes an incoming message as input and displays as output the message encoded using Chuck Norris’ method.

Here is the encoding principle:

The input message consists of ASCII characters (7-bit)
The encoded output message consists of blocks of 0
A block is separated from another block by a space
Two consecutive blocks are used to produce a series of same value bits (only 1 or 0 values):
— First block: it is always 0 or 00. If it is 0, then the series contains 1, if not, it contains 0
— Second block: the number of 0 in this block is the number of bits in the series

Input

Line 1: the message consisting of N ASCII characters (without carriage return)

Output

The encoded message

Tests

Input	Output
C	0 0 00 0000 0 00
CC	0 0 00 0000 0 000 00 0000 0 00
%	00 0 0 0 00 00 0 0 00 0 0 0
Hello	0 0 00 00 0 0 00 000 0 00 00 00 0 0 00 0 0 000 00 0 0 00 00 00 0 00 00 0 0 00 00 00 0 00 00 0 0 0000

Code

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


string binary(unsigned char x){
    unsigned char mask=64;
    string s;
    for(int i=0; i<7; i++) {
        s.push_back((x&mask)>0 ? '1':'0');
        mask=mask>>1;
    }
    return s;
}

int main() {
    string l;
    string a;
    unsigned char x;
    while(cin >> x){
        l+=binary(x);
    }
    for(int i=0;i<l.size();i++)
    {
        if(l.at(i)=='0')
        {
            if(i==0||l.at(i-1)=='1')
            {
                if(i!=0)
                {
            a+=" ";
            a.push_back('0');
            a.push_back('0');
            a+=" ";
                } else {
                    a.push_back('0');
                    a.push_back('0');
                    a+=" ";
                }
            } 
            a.push_back(l.at(i));
        } else if(l.at(i)=='1')
        {
            if(i==0||l.at(i-1)=='0')
            {
                if(i!=0)
                {
                a+=" ";
                a.push_back('0');
                a+=" ";
                } else{ 
                    a.push_back('0');
                    a+=" ";
                }
            } 
            a.push_back(l.at(i));
        }   
    }
    for(int i=0;i<a.size();i++)
    {
        if(a.at(i)=='1')
        {
            a.at(i)='0';
        }
    }
    cout<<a;
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

string binary(unsigned char x){

unsigned char mask=64;

string s;

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

s.push_back((x&mask)>0 ? '1':'0');

mask=mask>>1;

}

return s;

}

int main() {

string l;

string a;

unsigned char x;

while(cin >> x){

l+=binary(x);

}

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

{

if(l.at(i)=='0')

{

if(i==0||l.at(i-1)=='1')

{

if(i!=0)

{

a+=" ";

a.push_back('0');

a+=" ";

} else {

a.push_back('0');

a+=" ";

}

a.push_back(l.at(i));

} else if(l.at(i)=='1')

{

if(i==0||l.at(i-1)=='0')

{

if(i!=0)

{

a+=" ";

a.push_back('0');

a+=" ";

} else{

a.push_back('0');

a+=" ";

}

a.push_back(l.at(i));

}

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

{

if(a.at(i)=='1')

{

a.at(i)='0';

}

cout<<a;

return 0;

}

Solution

First, we create a so called mask, which takes the symbol, transform it to a binary 7-bit number and return string. Then we add this string to another one, while transforming every symbol in the cin. Then we create a loop, where we check either symbol is 0 or 1 and add them to another string in the right order according to the encoding principle. In order to escape mistakes with ‘1’ in the first loop, we create another loop, where we change all ‘1’ to ‘0’.

Related Images:

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:

e-olimp 1310. Наибольший блок

28/06/2016 by Аня Шохина

Задача

Блоком строки [latex]S[/latex] в позиции [latex]i[/latex] назовём наибольшую подстроку [latex]S[/latex], которая начинается в позиции [latex]i[/latex] и совпадает с префиксом [latex]S[/latex]. Длину блока в позиции 0 считать равной нулю. Вычислить длину наибольшего блока заданной строки [latex]S[/latex].

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

Единственная строка [latex]S[/latex] [latex]\left(\left|S\right|\leq{10}^{6}\right)[/latex].

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

Длина наибольшего блока строки [latex]S[/latex].

Тесты

Входные данные	Выходные данные
abaabaab	5
aaaaa	4
aaabaab	2

Реализация

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

int main() {
    string s;
    getline(cin,s); // используем данную функцию, так как это выгодно по времени
    int n =  s.length();
    vector<int> z (n);//вектор на n элеметов, в который будут записыватья значения блоков функции
    int l=0, r=0; //левая и правая граница "отрезка совпадения"
    for (int i=1; i<n; i++) { 
        if (i <= r)
            z[i] = min (r-i+1, z[i-l]);
        while (i+z[i] < n && s[z[i]] == s[i+z[i]])
            z[i]++;
        if (i+z[i]-1 > r){
            l = i;
            r = i+z[i]-1;
        }
    }
    int max=z[0];
    for (int i=1; i<z.size(); i++){
        if (max<z[i]){
            max=z[i];
        }
    }
    cout<<max<<endl;
    return 0;
}

#include <iostream>

#include <string>

#include <vector>

using namespace std;

int main() {

string s;

getline(cin,s); // используем данную функцию, так как это выгодно по времени

int n = s.length();

vector<int> z (n);//вектор на n элеметов, в который будут записыватья значения блоков функции

int l=0, r=0; //левая и правая граница "отрезка совпадения"

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

if (i <= r)

z[i] = min (r-i+1, z[i-l]);

while (i+z[i] < n && s[z[i]] == s[i+z[i]])

z[i]++;

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

l = i;

r = i+z[i]-1;

}

int max=z[0];

for (int i=1; i<z.size(); i++){

if (max<z[i]){

max=z[i];

}

cout<<max<<endl;

return 0;

}

Код на ideone.com

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

Решение

Для решения данной задачи необходимо рассмотреть алгоритм эффективного вычисления [latex]Z[/latex]-функции. Создадим массив [latex]z[/latex], где [latex]i[/latex]-ый элемент равен наибольшему числу символов, начиная с [latex]i[/latex]-ой позиции, совпадающих с первыми символами заданной строки [latex]s[/latex]. Эффективность алгоритма состоит в том, что при вычислении очередного элемента массива [latex]z[/latex] мы будем использовать уже вычисленные ранее значения. Назовем отрезком совпадения подстроку, совпадающую с префиксом заданной строки. Тогда искомое значение [latex]z\left [ i \right ][/latex] — это длина самого длинного отрезка совпадения, начинающегося в позиции [latex]i[/latex]. Из всех найденных отрезков совпадения будем хранить тот, который оканчивается правее всего. Положим, что [latex]l[/latex] и [latex]r[/latex] — индексы начала и конца данного отрезка соответственно. Тогда при вычислении [latex]z\left [ i \right ][/latex] возможны две ситуации: [latex]i>r[/latex] и [latex]i\leq r[/latex]. В первом случае позиция [latex]i[/latex] лежит за пределами проанализированной части строки . Тогда ищем значение [latex]Z[/latex]-функции перебором до тех пор, пока не дойдем до несовпадения или конца заданной строки. Стоит отметить, что если [latex]z\left [ i \right ]>0[/latex], следует изменить индексы отрезка совпадений. Во втором случае текущая позиция [latex]i[/latex] лежит внутри отрезка совпадений [latex]\left [ l,r \right ][/latex]. Так как подстроки [latex]s\left [ l\ldots r \right ][/latex] и [latex]s\left [ 0\ldots r-l \right ][/latex] совпадают, то в качестве значения [latex]z\left [ i \right ][/latex] можно взять значение [latex]z\left [ i-l \right ][/latex]. Однако, значение [latex]z\left [ i-l \right ][/latex] может быть слишком большим для данного блока (суффикс строки будет меньше, чем данное значение, чего быть не может). Следовательно, [latex]z\left [ i \right ][/latex]-ому элементу будем присваивать значение минимума из длины суффикса [latex]\left ( r-i+1 \right )[/latex] и [latex]z\left [ i-l \right ][/latex]. Далее используем вышеописанный перебор. В конечном итоге максимальный элемент массива — длина наибольшего блока заданной строки.

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 506. Новый компилятор

18/06/2016 by Аня Шохина

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

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

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

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

Входной файл содержит от 1 до 500 строк длиной не более 50 символов с ASCII-кодами от 32 до 127 – текст программы, которую нужно преобразовать.

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

В выходной файл вывести преобразованный текст программы.

Тесты

Исходный текст программы

Преобразованный текст программы

Test* t = new Test( );
t--> = 1;
t->b = 2
t->go() ; // a=1, b=2 -> a=2, b=3
t--> = 1;

Test* t = new Test( );

t--> = 1;

t->b = 2

t->go() ; // a=1, b=2 -> a=2, b=3

t--> = 1;

Test* t = new Test( );
t-. = 1;
t.b = 2
t.go() ; // a=1, b=2 -> a=2, b=3
t-. = 1;

Test* t = new Test( );

t-. = 1;

t.b = 2

t.go() ; // a=1, b=2 -> a=2, b=3

t-. = 1;

 Test* t = new Test();
t->a = 1;
t->b = 2;
t->go(); // a=1, b=2 -> a=2, b=3

Test* t = new Test();

t->a = 1;

t->b = 2;

t->go(); // a=1, b=2 -> a=2, b=3

 Test* t = new Test();
t.a = 1;
t.b = 2;
t.go(); // a=1, b=2 -> a=2, b=3

Test* t = new Test();

t.a = 1;

t.b = 2;

t.go(); // a=1, b=2 -> a=2, b=3

 Test* t = new Test( );
//t--> = 1;
t----->b = 2
t->-go() ;
t--> = 1;

Test* t = new Test( );

//t--> = 1;

t----->b = 2

t->-go() ;

t--> = 1;

 Test* t = new Test( );
//t--> = 1;
t----.b = 2
t.-go() ;
t-. = 1;

Test* t = new Test( );

//t--> = 1;

t----.b = 2

t.-go() ;

t-. = 1;

Реализация

#include <iostream>
#include <stdio.h>

using namespace std;

int main() {
    int c;
    int a;
    char b;
    c = getchar();
    while ((a = getchar()) != EOF) {
        if (c == '-') { //проверяем на наличие комбинации "->"
            if (a == '>') {
                cout << ".";
                a = getchar();
            } else {
                putchar(c);
            }
        } else if (c == '/') { //проверяем на наличие комбинации "//"
            putchar(c);
            if (a == '/') {
                putchar(a);
                while ((b = getchar()) != '\n') {
                    putchar(b); //печатаем комментарий не изменяя до конца строки
                }
                cout << endl;
                a = getchar();
            }
        } else putchar(c);
        c = a;
    }
}

#include <iostream>

#include <stdio.h>

using namespace std;

int main() {

int c;

int a;

char b;

c = getchar();

while ((a = getchar()) != EOF) {

if (c == '-') { //проверяем на наличие комбинации "->"

if (a == '>') {

cout << ".";

a = getchar();

} else {

putchar(c);

}

} else if (c == '/') { //проверяем на наличие комбинации "//"

putchar(c);

if (a == '/') {

putchar(a);

while ((b = getchar()) != '\n') {

putchar(b); //печатаем комментарий не изменяя до конца строки

}

cout << endl;

a = getchar();

}

} else putchar(c);

c = a;

}

Код на ideone.com

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

Ход решения

Для решения данной задачи используем функцию getchar, так как данная функция может работать с управляющими символами (когда программа находит комментарий, необходимо печатать без изменений до конца строки). Так как по условию задачи нам нужно найти такие комбинации символов, как «//» и «->» , мы при каждом проходе цикла, сравнивая символы входных данных с теми, что надо найти, запоминаем два соседних символа.

Related Images:

e-olymp 1342. Периодические строки

24/04/2016 by Кондратюк Настя

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

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

Будем говорить, что символьная строка имеет период [latex]k[/latex], если она может быть образована путем объединения одной или нескольких одинаковых строк длиной [latex]k[/latex]. Например, строка «[latex]abcabcabcabc[/latex]» имеет период [latex]3[/latex], так как она может быть образована путём объединения [latex]4[/latex]-х строк «[latex]abc[/latex]». Она также имеет период [latex]6[/latex] (объединение двух строк «[latex]abcabc[/latex]») и [latex]12[/latex] (сама строка «[latex]abcabcabcabc[/latex]»).

Напишите программу определяющую наименьший период заданной строки.

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

В первой строке задано количество тестовых случаев [latex]N[/latex] во входных данных. Каждый тестовый случай размещен в отдельной строке и содержит не более [latex]80[/latex] символов без пробелов.

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

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

Тесты

Входные данные	Выходные данные
2 HoHoHo mama	2 2
2 abcdefg abcabcabc	7 3
3 b bbb bbbbb	1 1 1

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

    #include <iostream>
    #include <cstring>
    using namespace std;
     
    int strPeriod(char *str){
        int period;
        period = strlen(str); // 
        for(int i=1; i<=(strlen(str)/2); i++){ /* разбиваем строку                    
                                                 на подстроки*/
                int j;
            for(j=0; j<strlen(str)-i; ){ /* ограничение номера символа,
                                              чтобы не выйти за границы строки*/
                if(str[j] == str[j+i]){
                    j++;
                }
                else{
                    break;
                }
            }
        if(j == (strlen(str) - i)){  /* если цикл дошел до конца 
                                        строки - период найден*/
                    period = i;
                    break;
            }
        }
     
        return period;
    }
     
    int main() {
        const int n = 81;
        int tests;
        cin >> tests;
        cin.ignore(1, ' '); /* пропуск символа перехода на новую строку*/
        char *str = new char[n];
        for(int j=0; j<tests; j++){
            cin.getline(str, n);
            cout << strPeriod(str);
            if(j != tests - 1){
                cout << endl << endl;
            }
        }
        return 0;
    }

#include <iostream>

#include <cstring>

using namespace std;

int strPeriod(char *str){

int period;

period = strlen(str); //

for(int i=1; i<=(strlen(str)/2); i++){ /* разбиваем строку

на подстроки*/

int j;

for(j=0; j<strlen(str)-i; ){ /* ограничение номера символа,

чтобы не выйти за границы строки*/

if(str[j] == str[j+i]){

j++;

}

else{

break;

}

if(j == (strlen(str) - i)){ /* если цикл дошел до конца

строки - период найден*/

period = i;

break;

}

return period;

}

int main() {

const int n = 81;

int tests;

cin >> tests;

cin.ignore(1, ' '); /* пропуск символа перехода на новую строку*/

char *str = new char[n];

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

cin.getline(str, n);

cout << strPeriod(str);

if(j != tests - 1){

cout << endl << endl;

}

return 0;

}

ideone.com

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

Решение

Строка длины [latex]s[/latex] может быть образована подстрокой, длина которой не превышает половины длины строки. Следовательно, период лежит в промежутке [latex]\left [ 1;s/2 \right ][/latex], либо равен длине строки. Последовательно разбивая строку на подстроки длиной от [latex]1[/latex] до [latex]s/2[/latex], проверяем равны ли они между собой. Если такие подстроки не нашлись, то период равен длине строки.

Related Images:

e-olymp 185. Орки будущего

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

Условие

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

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

В первой строке задано количество [latex]N[/latex] орков, участвующих в игрищах. Далее идет [latex]N[/latex] строк с речью соответствующего орка. Гарантируется, что речь каждого Орка находится в одной строке, и в игрищах принимает участие не менее одного и не более [latex]100[/latex] орков. Количество символов в каждой записанной речи орка не превышает [latex]1000[/latex] и не менее одного.

Из условия:

«…теперь в их алфавите в качестве гласных использовались только буквы «а», «o», «e», «u».»

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

«Самым «Годистым» орком считался тот из них, у кого это отношение было наименьшим, а в случае равенства этого показателя тот, у кого в произнесенной речи было больше сказано слов. Ваша задача – определить Орка года по заданному критерию.»

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

Единственное число – номер Орка, признанного Орком Года. В случае, если однозначно определить победителя невозможно, вывести "O-o-o-rks...".

Решение

Напишем 2 функции: int countSyllables(char* speech), которая будет считать гласные (т.к. кол-во слогов всегда равно кол-ву гласных), и int countWords(char* speech), считающую кол-во слов. Для написания первой воспользуемся стандартной функцией strpbrk(), для второй — функцией strtok(). Для каждой считанной строки будем по очереди вызывать эти 2 функции и заносить полученные значения в соответствующие массивы syllables и words (вызывать будем именно в таком порядке, т.к. функция strtok() делает строку непригодной к дальнейшему использованию).

Далее, чтобы избежать работы с вещественными числами (что может привести к потере точности) будем сравнивать полученные результаты согласно требованиям, но вместо деления воспользуемся соотношением пропорции. Заведем переменную-флаг ambiguous, показывающую, однозначен ли победитель. В зависимости от ее значения, выведем номер победителя (переменная winner, по умолчанию победитель — первый орк) или строку "O-o-o-rks..."

Тесты

№	Входные данные	Выходные данные
1	2 Hello, World! Ok.	2
2	3 Ooh, hey there 😀 Hello, World of me! Will be ambiguous???	O-o-o-rks…
3	4 Some people like C! Some say Java is better. Heh, or maybe Python? Who knows for sure?	O-o-o-rks…
4	5 A Lannister always pays his debts. Winter is coming… Hear me roar! King of the North! Sherlock?	1
5	8 O-o-o-rks… Is not the same as… O-o-o-rks! or O-o-orks… …trust me,… …when writing code, one must be extremely careful! …beware!	O-o-o-rks…

Код

#include <iostream>
#include <cstring>
#define SIZE 1001
using namespace std;

int countWords(char* speech)
{
    int wordCount = 0;
    char delim[] = " ,.!?:;-\"\'";
    char* pointer = strtok(speech, delim);
    while (pointer != NULL)
    {
        pointer = strtok(NULL, delim);
        wordCount++;
    }
    return wordCount;   
}

int countSyllables(char* speech)
{
    int syllableCount = 0;
    char vowels[] = "aoeuAOEU";
    char* pointer = strpbrk(speech, vowels);
    while (pointer != NULL)
    {
        pointer = strpbrk(pointer + 1, vowels);
        syllableCount++;
    }
    return syllableCount;
}

int main() 
{
    int n;
    cin >> n;
    char speech[SIZE];
    int words[n];
    int syllables[n];
    cin.ignore(); //пропустить перевод строки между числом и первой речью
    for (int i = 0; i < n; i++)
    {
        cin.getline(speech, SIZE);
        syllables[i] = countSyllables(speech);
        words[i] = countWords(speech);
    }
    bool many = false;
    int winner = 0;
    for (int i = 1; i < n; i++)
    {
        if (syllables[i] * words[winner] < syllables[winner] * words[i])
        {
            winner = i;
            many = false;
        }
        else if (syllables[i] * words[winner] == syllables[winner] * words[i])
        {
            if (words[winner] < words[i])
            {
                winner = i;
                many = false;
            }
            else if (words[winner] == words[i])
                many = true;
        }
    }
    if (many)
        cout << "O-o-o-rks...";
    else
        cout << winner + 1 << endl;
    return 0;
}

#include <iostream>

#include <cstring>

#define SIZE 1001

using namespace std;

int countWords(char* speech)

{

int wordCount = 0;

char delim[] = " ,.!?:;-\"\'";

char* pointer = strtok(speech, delim);

while (pointer != NULL)

{

pointer = strtok(NULL, delim);

wordCount++;

}

return wordCount;

}

int countSyllables(char* speech)

{

int syllableCount = 0;

char vowels[] = "aoeuAOEU";

char* pointer = strpbrk(speech, vowels);

while (pointer != NULL)

{

pointer = strpbrk(pointer + 1, vowels);

syllableCount++;

}

return syllableCount;

}

int main()

{

int n;

cin >> n;

char speech[SIZE];

int words[n];

int syllables[n];

cin.ignore(); //пропустить перевод строки между числом и первой речью

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

{

cin.getline(speech, SIZE);

syllables[i] = countSyllables(speech);

words[i] = countWords(speech);

}

bool many = false;

int winner = 0;

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

{

if (syllables[i] * words[winner] < syllables[winner] * words[i])

{

winner = i;

many = false;

}

else if (syllables[i] * words[winner] == syllables[winner] * words[i])

{

if (words[winner] < words[i])

{

winner = i;

many = false;

}

else if (words[winner] == words[i])

many = true;

}

if (many)

cout << "O-o-o-rks...";

else

cout << winner + 1 << endl;

return 0;

}

Ссылки

Код на ideaone.

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

Related Images:

e-olymp 1077. Java против C++

27/02/2016 by Женя Максимова

Задача. Сторонники языков Java и C++ часто спорят о том, какой язык лучше для решения олимпиадных задач. Одни говорят, что в Java есть масса полезных библиотек для работы со строками, хорошо реализованы механизмы чтения и вывода данных, а так же радует встроенные возможности для реализации длинной арифметики. С другой стороны, С++ является классическим языком, скорость выполнения программ благодаря существующим компиляторам (например, Intel Compiler 10.0) гораздо выше, чем у Java.

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

В языке Java принято первое слово, входящее в название переменной записывать с маленькой латинской буквы, следующее слово идет с большой буквы (только первая буква слова большая), слова не имеют разделителей и состоят только из латинских букв. Например, правильные записи переменных в Java могут выглядеть следующим образом: javaIdentifier, longAndMnemonicIdentifier, name,nEERC.

В языке C++ для описания переменных используются только маленькие латинские символы и символ «_», который отделяет непустые слова друг от друга. Примеры: java_identifier, long_and_mnemonic_identifier, name, n_e_e_r_c.

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

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

Во входном файле задано наименование переменной длиной не более [latex]100[/latex] символов.

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

В выходной файл требуется вывести аналог имени переменной в другом языке. Т.е. если переменная представлена в формате Java, то следует перевести в формат C++ и наоборот. В том случае, когда имя переменной не соответствует ни одному из вышеописанных языков, следует вывести «Error!«.

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

Тесты

Test	Input	Output
1	java_word	javaWord
2	cppWorD	cpp_wor_d
3	simpleword	simpleword
4	two__underscores	Error!
5	_underscore_in_the_beginning	Error!
6	underscore_in_the_end_	Error!
7	UppercaseInTheBeginning	Error!
8	mixed_Style	Error!

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

#include <iostream>
#include <cstring>
using namespace std;
const int START = 0; //start state
const int CONTINUE = 1; //common prefix identifier state
const int JAVAWORD = 2; //2-4 intermediate states
const int CPPWORD = 3;
const int CPPDEL = 4; //CPP-delimeter
const int JAVA = 5; //5-10 final states
const int CPP = 6;
const int UNIVERSAL = 7;
const int JAVAERR = 8; //Error in JAVA
const int CPPERR = 9; //Error in CPP
const int ERROR = 10;
char var[101];
char result[203] = {'\0'}; //fill the resulting string with zero code characters
int reslen = 0; //the length of the resulting string
int state;
bool is_small(char c) //supporting function
{
  return ('a'<= c && c <= 'z');
}
bool is_big(char c) //supporting function
{
  return ('A'<= c && c <= 'Z');
}
bool is_underscore(char c) //supporting function
{
  return (c == '_');
}
int selection_of_style(char * var, size_t len) //determines preliminary type of string
{
  char c=var[0];
  state = START;
  if(is_small(c))
    {
      state = CONTINUE;
    }
  if(is_big(c))
    {
      state = ERROR;
      return state;
    }
  if(is_underscore(c))
    {
      state = ERROR;
      return state;
    }
  for (int i=1; i<len; i++)
    {
      c=var[i];
      if(is_small(c)) state = state;
      if(is_big(c))
        {
          state = JAVAWORD;
          return state;
        }
      if(is_underscore(c))
        {
          state = CPPWORD;
          return state;
        }
    }
  //if(state == CONTINUE)
  //in the end os the word we are still in the state CONTINUE
  state = UNIVERSAL;
  return state;
}
int is_java(char * var, size_t len)//check if the word is a correct java variable
{
  for (int i=0; i<len; i++)
    {
      char c = var[i];
      if(is_small(c))
        {
          state = state;
        }
      if(is_big(c))
        {
          state = state;
        }
      if(is_underscore(c))
        {
          state = JAVAERR;
          return state;
        }
    }
  if(state == JAVAWORD)
    {
      state = JAVA;
    }
  return state;
}
int is_cpp(char * var, size_t len) //check if the word is a correct cpp variable
{
  for (int i=0; i<len; i++)
    {
      char c = var[i];
      if(is_small(c))
        {
          if(state == CPPDEL)
            {
              state = CPPWORD;
            }
          else
            state = state;
        }
      if(is_big(c))
        {
          state = JAVAERR;
          return state;
        }

      if(is_underscore(c))
        {
          if(state == CPPDEL)
            {
              state = CPPERR;
              return state;
            }
          state = CPPDEL;
        }
    }
  if(state == CPPWORD)
    {
      state = CPP;
    }
  if(state == CPPDEL) //underscore in the end is an error too
    {
      state = CPPERR;
    }
  return state;
}
void java_to_cpp(char * var, size_t len) //function-translator
{
  for(int i=0; i<len; i++)
    {
      char c = var[i];
      if(is_small(c))
        {
          result[reslen++] = var[i]; //append character to resulting string
        }
      if(is_big(c))
        {
          result[reslen++] = '_';
          result[reslen++] = var[i]+32;
        }
    }
}
void cpp_to_java(char * var, size_t len) //function-translator
{
  for(int i=0; i<len; i++)
    {
      char c = var[i];
      if(is_small(c))
        {
          result[reslen++] = var[i];
        }
      if(is_underscore(c))
        {
          result[reslen++]=var[++i]-32;
        }
    }
}
int main()
{
  cin >> var;
  size_t len = strlen(var);
  state = selection_of_style(var, len);
  if(state == ERROR)
    {
      cout << "Error!" << endl;
      return 0;
    }
  if(state == JAVAWORD)
    state = is_java(var,len);
  if(state == CPPWORD)
    state = is_cpp(var,len);
  if (state == UNIVERSAL)
    {
      cout << var << endl;
      return 0;
    }
  if(state == JAVAERR)
    {
      cout << "Error!" << endl;
      return 0;
    }
  if(state == CPPERR)
    {
      cout << "Error!" << endl;
      return 0;
    }
  if(state == JAVA)
    {
      java_to_cpp(var,len);
      cout << result;
      return 0;
    }
  if(state==CPP)
    {
      cpp_to_java(var,len);
      cout << result;
      return 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

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

198

199

200

201

202

203

204

205

206

207

#include <iostream>

#include <cstring>

using namespace std;

const int START = 0; //start state

const int CONTINUE = 1; //common prefix identifier state

const int JAVAWORD = 2; //2-4 intermediate states

const int CPPWORD = 3;

const int CPPDEL = 4; //CPP-delimeter

const int JAVA = 5; //5-10 final states

const int CPP = 6;

const int UNIVERSAL = 7;

const int JAVAERR = 8; //Error in JAVA

const int CPPERR = 9; //Error in CPP

const int ERROR = 10;

char var[101];

char result[203] = {'\0'}; //fill the resulting string with zero code characters

int reslen = 0; //the length of the resulting string

int state;

bool is_small(char c) //supporting function

{

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

}

bool is_big(char c) //supporting function

{

return ('A'<= c && c <= 'Z');

}

bool is_underscore(char c) //supporting function

{

return (c == '_');

}

int selection_of_style(char * var, size_t len) //determines preliminary type of string

{

char c=var[0];

state = START;

if(is_small(c))

{

state = CONTINUE;

}

if(is_big(c))

{

state = ERROR;

return state;

}

if(is_underscore(c))

{

state = ERROR;

return state;

}

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

{

c=var[i];

if(is_small(c)) state = state;

if(is_big(c))

{

state = JAVAWORD;

return state;

}

if(is_underscore(c))

{

state = CPPWORD;

return state;

}

//if(state == CONTINUE)

//in the end os the word we are still in the state CONTINUE

state = UNIVERSAL;

return state;

}

int is_java(char * var, size_t len)//check if the word is a correct java variable

{

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

{

char c = var[i];

if(is_small(c))

{

state = state;

}

if(is_big(c))

{

state = state;

}

if(is_underscore(c))

{

state = JAVAERR;

return state;

}

if(state == JAVAWORD)

{

state = JAVA;

}

return state;

}

int is_cpp(char * var, size_t len) //check if the word is a correct cpp variable

{

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

{

char c = var[i];

if(is_small(c))

{

if(state == CPPDEL)

{

state = CPPWORD;

}

else

state = state;

}

if(is_big(c))

{

state = JAVAERR;

return state;

}

if(is_underscore(c))

{

if(state == CPPDEL)

{

state = CPPERR;

return state;

}

state = CPPDEL;

}

if(state == CPPWORD)

{

state = CPP;

}

if(state == CPPDEL) //underscore in the end is an error too

{

state = CPPERR;

}

return state;

}

void java_to_cpp(char * var, size_t len) //function-translator

{

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

{

char c = var[i];

if(is_small(c))

{

result[reslen++] = var[i]; //append character to resulting string

}

if(is_big(c))

{

result[reslen++] = '_';

result[reslen++] = var[i]+32;

}

void cpp_to_java(char * var, size_t len) //function-translator

{

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

{

char c = var[i];

if(is_small(c))

{

result[reslen++] = var[i];

}

if(is_underscore(c))

{

result[reslen++]=var[++i]-32;

}

int main()

{

cin >> var;

size_t len = strlen(var);

state = selection_of_style(var, len);

if(state == ERROR)

{

cout << "Error!" << endl;

return 0;

}

if(state == JAVAWORD)

state = is_java(var,len);

if(state == CPPWORD)

state = is_cpp(var,len);

if (state == UNIVERSAL)

{

cout << var << endl;

return 0;

}

if(state == JAVAERR)

{

cout << "Error!" << endl;

return 0;

}

if(state == CPPERR)

{

cout << "Error!" << endl;

return 0;

}

if(state == JAVA)

{

java_to_cpp(var,len);

cout << result;

return 0;

}

if(state==CPP)

{

cpp_to_java(var,len);

cout << result;

return 0;

}

return 0;

}

Алгоритм

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

Для удобства я изобразила этот алгоритм в виде схемы:

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

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

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

Отдельно следует поговорить о состоянии CPP delimeter. Оно используется для контроля количества подчеркиваний. Если в нашей предполагаемой С++ переменной встречается подчеркивание, ей сразу же присваивается данное состояние, чтобы, при наличии второго подчеркивания сразу же перевести ее в состояние Error in CPP.

Финальные состояния отмечены зеленым цветом. В них мы переходим только после окончания строки непосредственно из предыдущего состояния. Переход в состояние Universal означает, что исходная строка состоит исключительно из маленьких букв и подходит как для языка Java, так и для C++.

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

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

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

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:

А808а

27/01/2016 by Сабиров Ильдар

Задача.
Дан текст. Группы символов, разделенные пробелами(одним или несколькими) и не содержащие пробелов внутри себя, будем называть, как и прежде, словами.

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

Тесты

Input	Output	Комментарий
123 321 1441 123 456 831 1441	123 — 2 1441 -2 321 — 1 456 — 1 831 — 1	Пройдено
iW@910 b10r l4e iW@910 10o b11 a mU611211a9	10o — 1 a — 1 b10r — 1 b11 — 1 iW@910 — 2 l4e — 1 mU611211a9 — 1	Пройдено
№!4%» ^&*() +\|\/., №!4%» _-=~`;?	+\|\/., — 1 ^&*() — 1 _-=~`;? — 1 №!4%» — 2	Пройдено
Hey Jude, don’t make it bad. Take a sad song and make it better.	Hey — 1 Jude, — 1 Take — 1 a — 1 and — 1 bad. — 1 better. — 1 don’t — 1 it — 2 make — 2 sad — 1 song — 1	Пройдено

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

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

int main() {
	map<string, int> m;
	string word;
	while( cin >> word )
		m[word]++;
	for(map<string, int>::iterator (it) = (m).begin(); (it) != (m).end() ; (it)++)
	{
		cout<<it->first<<" - "<<it->second<<endl;
	}
	return 0;
}

#include <iostream>

#include <map>

#include <cstring>

#include <cstdlib>

using namespace std;

int main() {

map<string, int> m;

string word;

while( cin >> word )

m[word]++;

for(map<string, int>::iterator (it) = (m).begin(); (it) != (m).end() ; (it)++)

{

cout<<it->first<<" - "<<it->second<<endl;

}

return 0;

}

Ход решения:

Применяя функцию [latex]map[/latex], запишем в индекс массива [latex]m[/latex] слово и увеличим элемент массива данного индекса на единицу. Используя цикл [latex]while[/latex] мы проделаем это для каждого слова введенного с клавиатуры. Если слово повторится , то элемент снова увеличится на единицу. Таким образом получаем количество слов в данном тексте.

С помощью цикла [latex]for[/latex] выводим индекс массива (т.е. слово) и значение (его количество в тексте).

Ссылка на код

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 1309. Блоки строки

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

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

Блоком строки S в позиции i назовём наибольшую подстроку S, которая начинается в позиции i и совпадает с префиксом S. Длину блока в позиции 0 считать равной нулю.

Вычислить длины блоков строки S для всех позиций.

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

Единственная строка S (|S| ≤ 10⁶).

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

В одной строке вывести длины блоков строки S для всех позиций, разделённые пробелом.

Тесты:

abaabaab
0 0 1 5 0 2 0

1 2	abaabaab 0 0 1 5 0 2 0

abaabaabbaaaaaaaaaaaabbbbbbbabaaaaaabababaaaaaaaabaaabaabaaaaaaaabaaabaaababababbab
0 0 1 5 0 1 2 0 0 1 1 1 1 1 1 1 1 1 1 1 2 0 0 0 0 0 0 0 4 0 1 1 1 1 1 3 0 3 0 4 0 1 1 1 1 1 1 1 4 0 1 1 7 0 1 4 0 1 1 1 1 1 1 1 4 0 1 1 4 0 1 1 3 0 3 0 3 0 2 0 0 2 0

1 2	abaabaabbaaaaaaaaaaaabbbbbbbabaaaaaabababaaaaaaaabaaabaabaaaaaaaabaaabaaababababbab 0 0 1 5 0 1 2 0 0 1 1 1 1 1 1 1 1 1 1 1 2 0 0 0 0 0 0 0 4 0 1 1 1 1 1 3 0 3 0 4 0 1 1 1 1 1 1 1 4 0 1 1 7 0 1 4 0 1 1 1 1 1 1 1 4 0 1 1 4 0 1 1 3 0 3 0 3 0 2 0 0 2 0

aaaaaaaaaaaaaaaaaaaaa
0 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

1 2	aaaaaaaaaaaaaaaaaaaaa 0 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

f2f
0 0 1

f2f

0 0 1

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

#include <iostream>
#include <cstring> 
using namespace std;
 
 
int main(){
	int zf[1000000];
	char s[1000000];
    scanf("%[^\n]%*c", s);
    int n = strlen(s);
    int right=0,left=0;
 
    for(int i=1; i < n; ++i){
           
            if(i<=right){
        		zf[i]=min(right-i+1,zf[i-left]);
            }
            while(s[zf[i]]==s[zf[i]+i]){
            	zf[i]++;
            }
            if(i+zf[i]-1>right){
    	        left=i;
                right=i+zf[i]-1;
            }
    }
 	
    for(int i=0; i < n; ++i){
    	cout << zf[i] << " ";	
    }
    
	return 0; 
}

#include <iostream>

#include <cstring>

using namespace std;

int main(){

int zf[1000000];

char s[1000000];

scanf("%[^\n]%*c", s);

int n = strlen(s);

int right=0,left=0;

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

if(i<=right){

zf[i]=min(right-i+1,zf[i-left]);

}

while(s[zf[i]]==s[zf[i]+i]){

zf[i]++;

}

if(i+zf[i]-1>right){

left=i;

right=i+zf[i]-1;

}

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

cout << zf[i] << " ";

}

return 0;

}

Алгоритм

В данной задаче из-за того, что наша строка может принимать длину до 10⁶ включительно, то необходим эффективный алгоритм. Я воспользовался алгоритмом вычисления Z-функции. Для начала мы заводим переменные left и right, в которых мы будем хранить координаты самого длинного отрезка, который совпадает с началом нашей строки. В начале цикла проверяем находится ли ячейчка, для которой ищется результат в отрезке между left и right. После прохождения цикла while, мы обновляем границы подстроки.

Код на ideone.com

Принятая задача на e-olymp.

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;
}