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

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

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

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

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

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

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

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

Задача

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

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

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

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

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

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

Тесты

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

Код

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

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

#include <iostream>

#include <cstring>

using namespace std;

int main() {

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

char b[100001], a[100001];

cin >> b >> a;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

}

Решение

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

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

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

Related Images:

e-olymp 8320. Заглавная строка

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

Условие

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

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

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

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

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

Тесты

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

Решение

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

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

#include <iostream>
using namespace std;

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

#include <iostream>

using namespace std;

int main() {

string s;

getline(cin, s);

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

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

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

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

}

cout << s;

return 0;

}

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

#include <iostream>
#include <cstring>

using namespace std;

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

#include <iostream>

#include <cstring>

using namespace std;

int main() {

char s[51];

cin.getline(s, 51);

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

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

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

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

}

cout << s;

return 0;

}

Ссылки

Related Images:

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

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

Задача

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

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

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

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

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

Тесты

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

Код 1

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

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

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

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

#include <iostream>

#include <string>

using namespace std;

struct student {

string name, surname;

char letter;

int Class;

string date;

};

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

bool res = false;

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

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

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

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

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

}

return res;

};

int main() {

int n;

cin >> n;

student *a = new student[n];

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

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

}

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

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

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

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

}

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

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

}

return 0;

}

Код 2

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

#include <iostream>

using namespace std;

struct student {

char name[21];

char surname[21];

char letter;

int Class;

char date[9];

};

bool operator > (const student & a,

const student & b) {

bool res = false;

bool tmp = true;

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

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

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

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

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

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

tmp = false;

break;

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

tmp = true;

break;

}

if (tmp) res = true;

}

return res;

};

int main() {

int n;

cin >> n;

student *a = new student[n];

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

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

}

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

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

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

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

}

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

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

}

return 0;

}

Решение

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

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

Related Images:

e-olymp 8367. Таксі

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

Задача

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

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

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

Завдання

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

Вхідні дані

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

Вихідні дані

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

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

Оцінювання

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

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

Тести

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

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

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

#include <iostream>

#include <string>

using namespace std;

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

while (b) {

a %= b;

swap (a, b);

}

return a;

}

int main() {

string str;

cin >> str;

int length = str.length();

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

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

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

}

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

gcd = GCD (numerator, denominator);

numerator /= gcd;

denominator /= gcd;

remainder = numerator % denominator;

numerator -= remainder;

fraction = numerator / denominator;

cout << denominator << endl;

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

if (i == fraction) {

i++;

cout << denominator - remainder << " ";

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

}

else cout << 0 << " ";

}

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

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

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

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

#include <iostream>

#include <cstring>

using namespace std;

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

if (b == 0) return a;

else return GCD (b, a % b);

}

int main() {

char str[20];

int length = 0;

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

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

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

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

}

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

gcd = GCD(numerator, denominator);

numerator /= gcd;

denominator /= gcd;

remainder = numerator % denominator;

numerator -= remainder;

fraction = numerator / denominator;

cout << denominator << endl;

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

if(i == fraction) {

i++;

cout << denominator - remainder << " ";

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

}

else cout << 0 << " ";

}

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

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

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

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

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

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

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

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

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

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

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

Посилання

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

Related Images:

e-olymp 8382. Пароль

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

Задача

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

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

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

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

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

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

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

Тесты

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

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

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

#include <iostream>

using namespace std;

bool isspecial (char c) {

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

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

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

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

}

int main() {

string password;

cin >> password;

bool test_lc, test_uc, test_dig, test_sp,

test_len = password.length() >= 8;

int length = password.length();

test_lc = test_uc = test_dig = test_sp = false;

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

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

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

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

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

}

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

return 0;

}

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

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

#include <iostream>

#include <cstring>

using namespace std;

bool isspecial (char c) {

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

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

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

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

}

int main() {

char password[101];

cin >> password;

bool test_lc, test_uc, test_dig, test_sp,

test_len = strlen(password) >= 8;

int length = strlen(password);

test_lc = test_uc = test_dig = test_sp = false;

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

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

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

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

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

}

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

return 0;

}

Решение

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

Ссылки

Для string:

Для c-string:

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

Related Images:

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

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

Задача

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

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

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

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

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

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

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

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

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

Тесты

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

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

#include <iostream>
using namespace std;

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

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

#include <iostream>

using namespace std;

void revers(string & str) {

char a;

cin.get(a);

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

else return;

str += a;

}

int main() {

string str = "";

char a;

while (cin.get(a))

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

else str += a;

cout << str;

return 0;

}

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

#include <iostream>
using namespace std;

const int N = 200;

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

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

#include <iostream>

using namespace std;

const int N = 200;

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

char a;

cin >> a;

if (a == ')') return;

else revers(res, n);

res[n++] = a;

}

int main() {

char res[N];

char a;

int n = 0;

while (cin >> a) {

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

else res[n++] = a;

}

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

cout << res[i];

return 0;

}

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

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

Ссылки

Related Images:

e-olymp 6901. Shuffling Strings

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

Task

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

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

Input

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

Output

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

Tests

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

Program code

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

#include <iostream>

using namespace std;

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

string s;

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

s += s2[i];

s += s1[i];

}

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

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

return s;

}

int main() {

string s1, s2, s;

int n;

while (cin >> n && n) {

cin >> s1 >> s2 >> s;

string s12 = s1; s12 += s2;

string fixS = s12;

bool flag = true;

int nofs = 0; // number of steps

do {

nofs++;

s12 = shuffle(s1, s2);

if (s == s12)

flag = false;

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

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

}

return 0;

}

Program code V2.

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

#include <iostream>

#include <cstring>

using namespace std;

int main() {

int n;

while( cin >> n && n){

int count = 0;

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

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

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

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

cin >> first;

cin >> second;

cin >> third;

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

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

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

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

}

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

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

count++;

}

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

}

return 0;

}

Solution

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

Related Images:

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

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

Задача

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

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

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

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

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

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

Тесты

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

Код (string)

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

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

#include <iostream>

#include <map>

using namespace std;

int main() {

string s;

map <char, int> m;

cin >> s;

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

long long fact[15];

fact[1] = 1;

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

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

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

++m[s[i]];

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

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

cout << fact[l] / count;

return 0;

}

Код (c-string)

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

#include <iostream>

#include <cstring>

#include <map>

using namespace std;

int main() {

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

map <char, int> m;

cin >> s;

int l, count = 1;

l = strlen(s);

long long fact[15];

fact[1] = 1;

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

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

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

++m[s[i]];

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

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

cout << fact[l] / count;

return 0;

}

Решение

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

Ссылки

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

Код на Ideone (string)

Код на Ideone (c-string)

Related Images:

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

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

Задача

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

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

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

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

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

Тесты

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

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

#include <iostream>
using namespace std;

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

#include <iostream>

using namespace std;

int main() {

string s;

int count = 0;

while (cin >> s) count++;

cout << count;

}

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

#include <iostream> 
using namespace std;

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

#include <iostream>

using namespace std;

int main() {

char *word = new char[251];

int count = 0;

while(cin >> word) count++;

cout << count;

return 0;

}

Решение

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

Ссылки

Related Images:

e-olymp 1124. Алфавитное граффити

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

Задача

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

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

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

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

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

Объяснение:

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

Тесты

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

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

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

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

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

char q='a';

int n,k,i,j;

cin >> n;

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

s=s+q;

q++;

cout << 'a';

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

cout << s << "\n";

}

return 0;

}

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

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

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

#include <iostream>

#include <cstring>

using namespace std;

int main() {

char s[30];

char q='a';

int n,k,i,j;

cin >> n;

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

s[i]=q;

q++;

cout << 'a';

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

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

cout << "\n";

}

return 0;

}

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

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

Ссылки

Related Images:

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

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

Задача

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

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

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

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

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

Тесты

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

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

C-String

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

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

#include <iostream>

#include <cstring>

using namespace std;

int main() {

char s[101];

cin.getline(s,100);

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

return 0;

}

String

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

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

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

getline(cin, s);

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

return 0;

}

Решение

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

Ссылки

e-olymp

ideone(cstring)

ideone(string)

Related Images:

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

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

Задача

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

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

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

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

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

Тесты

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

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

#include <iostream>
#include <string>

using namespace std;

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

#include <iostream>

#include <string>

using namespace std;

int main() {

char S;

cin >> S;

int w, h, t;

cin >> w >> h >> t;

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

int times;

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

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

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

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

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

if(num < 0) num = 0;

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

cout << tmp;

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

else {

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

cout << S;

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

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

}

if (!flag) num--;

else num++;

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

if (num == 0) flag = true;

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

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

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

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

}

return 0;

}

Либо так:

#include <iostream>
using namespace std;

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

#include <iostream>

using namespace std;

int main() {

char S;

cin >> S;

int w, h, t;

cin >> w >> h >> t;

char *s1 = new char[w];

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

int times;

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

int num = 0;

bool flag = true;

char *tmp;

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

if(num < 0) num = 0;

tmp = new char [num];

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

cout << tmp;

if (i % 2) cout << s1;

else {

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

cout << S;

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

}

if (!flag) num--;

else num++;

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

if (num == 0) flag = true;

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

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

}

return 0;

}

Решение

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

Ссылки

Related Images:

e-olymp 8570. Длина слов

10/03/2019 by Иван Киреев

Задача. Длина слов

Задан текст — последовательность слов. Найдите длину каждого слова.

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

Текст содержит последовательность слов. Длина каждого слова не более $20$.

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

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

Тесты

№	Ввод	Вывод
1	Programming Principles 1	11 10 1
2	I like C very much	1 4 1 4 4
3	12345678901234567890	20
4	;-\ <cstring>	3 9
5	5^2-7*4/2 = 11	9 1 2
6	Veeeeeeery bIg LeTteR!	10 3 7
7	1, 25. 10!	2 3 3

Решение

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

Код через строки string

#include <iostream>
#include <string>
using namespace std;
 
int main() {
    string str;
    while (cin >> str) cout << str.length() << ' ';
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string str;

while (cin >> str) cout << str.length() << ' ';

return 0;

}

Код через строки c-string

#include <iostream>
#include <cstring>
using namespace std;
 
int main() {
    char str[20];
    while (cin >> str) cout << strlen(str) << ' ';
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

char str[20];

while (cin >> str) cout << strlen(str) << ' ';

return 0;

}

Related Images:

e-olymp 8571. Подсчитать буквы

24/02/2019 by Кирилл Веремйов

Задача

Задана строка s и буква c. Сколько раз буква встречается в строке?

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

Первая строка содержит строку s с не более чем $100$ символами. Вторая строка содержит прописную букву латинского алфавита c.

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

Выведите сколько раз буква c встречается в строке s. Одна и та же заглавная и прописная буква считаются одинаковыми. То есть «a» и «A» считаются одинаковыми буквами.

Тесты

Programming Principles 1 p	3
This is a cat sitting on a tablet	5
Some english text e	3
sSstring s	3
Another SoME eNGliSh tExT e	4
abcbcaacbcaacacabcbcaacbcaacacabcbcaacbcaacacabcbcaacbcaacacabcbcaacbcaacacabcbcaacbcaacac b	18
abcbcaacbcaacacabcbcaacbcaacacabcbcaacbcaacacabcbcaacbcaacacabcbcaacbcaacacabcbcaacbcaacac a	36
aAaAaBbAabaAaAaBbAabaAaAaBbAabaAaAaBbAabaAaAaBbAabaAaAaBbAabaAaAaBbAabaAaAaBbAabaAaAaBbAabaAaAaBbAab a	70

Решение через string

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

int main() {
    string s;
    getline(cin, s);
    char c;
    cin >> c;
    int L = s.length(), k = 0;
    for(int i = 0; i < L; i++){
        if(s[i] == c || s[i] == c - 32)k++;
    }
    cout << k;
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

getline(cin, s);

char c;

cin >> c;

int L = s.length(), k = 0;

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

if(s[i] == c || s[i] == c - 32)k++;

}

cout << k;

return 0;

}

Решение через Null-terminated String

#include <iostream>
#include <cstring>
using namespace std;
 
int main() {
    char s[100], c;
    cin.getline(s,100);
    cin >> c;
    int k = 0, i = 0;
    while(s[i] != '\0'){
        if(s[i] == c || s[i] == c - ('a' - 'A')) k++;
        i++;
    }
    cout << k;
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

char s[100], c;

cin.getline(s,100);

cin >> c;

int k = 0, i = 0;

while(s[i] != '\0'){

if(s[i] == c || s[i] == c - ('a' - 'A')) k++;

i++;

}

cout << k;

return 0;

}

Объяснение

Сначала считывается строка, затем, интересующая буква. Потом посматриваем каждый символ строки, и если он совпадает с нужной буквой (Код символа «A» в ASCII— 65, «a»—97. Соответственно, разница между символами прописной и заглавной латинской буквы— $32$ (в ASCII буквы английского алфавита идут по порядку), и символ отличающийся на $32$ от искомого— его заглавная версия, и нужно его учитывать), увеличиваем счётчик $k$. Затем, выводим результат.

e-olymp

ideone (string)

ideone (null-terminated string)

Related Images:

e-olymp 4844. Поиск общей подстроки

24/02/2019 by Владимир Дроздин

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

Задача

Дана строка [latex] A = [/latex] [latex] a_1a_2…a_n [/latex] и строка [latex] B = [/latex] [latex] b_1b_2…b_m [/latex]. Также дано число [latex] L [/latex].

Нужно узнать, есть ли у строк [latex] A [/latex] и [latex] B [/latex] общая подстрока длиной [latex] L [/latex].

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

В первых двух строках записаны строки [latex]A[/latex] и [latex]B[/latex], состоящие из строчных латинских букв. Эти строки непустые и имеют длину не более [latex]100000[/latex] символов. В третьей строке записано целое число [latex]L (0 \leq L \leq 100000) [/latex] — длина общей подстроки.

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

В выходной файл выведите [latex]YES[/latex], если существует общая подстрока такой длины. В противном случае выведите [latex]NO[/latex].

Тесты

#	Входные данные	Выходные данные
1	saaa baaa 3	YES
2	raabc taaac 3	NO
3	aaaaaaaka akaa 3	YES
4	abcdfeg qwertycdfeg 10	NO

Код 1

#include <iostream>
#include <map>
using namespace std;
 
struct state {
    int len, link;
    map <char,int> next;
};
 
state st[2*100000]; 
int sz, last;
 
void sa_init() {
    sz = 0;
    last = 0;
    st[0].len = 0;
    st[0].link = -1;
    sz++;
}
 
void sa_extend (char c) {
    int cur = sz++;
    st[cur].len = st[last].len + 1;
    int p;
    for (p = last; p != -1 && !st[p].next.count(c); p = st[p].link) st[p].next[c] = cur;
    if (p == -1) st[cur].link = 0;
    else {
        int q = st[p].next[c];
        if (st[p].len + 1 == st[q].len) st[cur].link = q;
        else {
            int clone = sz++;
            st[clone].len = st[p].len + 1;
            st[clone].next = st[q].next;
            st[clone].link = st[q].link;
            st[q].link = st[cur].link = clone;
        }
    }
    last = cur;
}
 
int longest_common_string (string a, string b) {
    sa_init();
    for (int i = 0; i < a.length(); i++) sa_extend (a[i]);
    int v = 0, l = 0, best = 0, bestpos = 0;
    for (int i = 0; i < b.length(); i++) {
        while (v != 0 && ! st[v].next.count(b[i])) {
            v = st[v].link;
            l = st[v].len;
        }
        if (st[v].next.count(b[i])) {
            v = st[v].next[b[i]];
            l++;
        }
        if (l > best){
            best = l;
            bestpos = i;
        }
    }
    return best;
}
 
int main() {
    string a, b;
    int n;
    cin >> a >> b >> n;
    if (longest_common_string(a, b) >= n) cout << "YES";
    else cout << "NO";
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

struct state {

int len, link;

map <char,int> next;

};

state st[2*100000];

int sz, last;

void sa_init() {

sz = 0;

last = 0;

st[0].len = 0;

st[0].link = -1;

sz++;

}

void sa_extend (char c) {

int cur = sz++;

st[cur].len = st[last].len + 1;

int p;

for (p = last; p != -1 && !st[p].next.count(c); p = st[p].link) st[p].next[c] = cur;

if (p == -1) st[cur].link = 0;

else {

int q = st[p].next[c];

if (st[p].len + 1 == st[q].len) st[cur].link = q;

else {

int clone = sz++;

st[clone].len = st[p].len + 1;

st[clone].next = st[q].next;

st[clone].link = st[q].link;

st[q].link = st[cur].link = clone;

}

last = cur;

}

int longest_common_string (string a, string b) {

sa_init();

for (int i = 0; i < a.length(); i++) sa_extend (a[i]);

int v = 0, l = 0, best = 0, bestpos = 0;

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

while (v != 0 && ! st[v].next.count(b[i])) {

v = st[v].link;

l = st[v].len;

}

if (st[v].next.count(b[i])) {

v = st[v].next[b[i]];

l++;

}

if (l > best){

best = l;

bestpos = i;

}

return best;

}

int main() {

string a, b;

int n;

cin >> a >> b >> n;

if (longest_common_string(a, b) >= n) cout << "YES";

else cout << "NO";

return 0;

}

Решение 1

Суффиксный автомат

Создадим структуру struct state, которая будет хранить информацию о переходах. len — это длина строки (далее будем использовать, как длину строки в каком-то состоянии), link — это суффиксальная ссылка, список переходов будем хранить в контейнере map <char, int> next, где ключом будет выступать символ, а значением — номер состояния.. Сам суффиксный автомат будем хранить в массиве этой структуры. Заведем переменные last и sz, отвечающие за последнее состояние и номер нового состояния соответственно.

Нам потребуется функция инициализирующая суффиксный автомат sa_init(). Так как вначале состояние лишь одно, то его длина равна [latex]0[/latex], а суффиксную ссылку приравняем к [latex]-1[/latex].

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

Поиск наибольшей общей подстроки

Сначала для строки a построим суффиксный автомат. Заведем две переменные, благодаря которым найдем совпадающую часть двух строк. Для этого нужна переменная, отвечающая за состояние v и переменная, отвечающая за длину совпадающей части l. Если есть переход, то переходим и увеличиваем длину на 1. Если нету, то уменьшаем длину совпадающей подстроки и переходим в новое состояние, меняя l. Цикл будет работать до тех пор, пока не найдем переход. Однако, если по суффиксным ссылкам мы дошли до состояния, в которое ведет ссылка изначальной вершины, то символ не встретился. Теперь длина наибольшей общей подстроки bestpos — это максимум из всех значений l.

Код 2

#include <iostream>
#include <cstring>
using namespace std;
 
int main() {
    char a[100001], b[100001]; 
    int l1, l2, l, k = 0;
    cin >> a >> b >> l;
    l1 = strlen(a);
    l2 = strlen(b);
    if (l1 < l || l2 < l) cout << "NO";
    else {
        for (int i = 0; i < l1; i ++) {
            for (int j = i; j <= l ; j ++) {
                if (a[j] == b[j]) k ++;
                else i ++;
                if (k == l) {
                    cout << "YES";
                    return 0;
                }
            }
            k = 0;
        }
        cout << "NO";
    }
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

char a[100001], b[100001];

int l1, l2, l, k = 0;

cin >> a >> b >> l;

l1 = strlen(a);

l2 = strlen(b);

if (l1 < l || l2 < l) cout << "NO";

else {

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

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

if (a[j] == b[j]) k ++;

else i ++;

if (k == l) {

cout << "YES";

return 0;

}

k = 0;

}

cout << "NO";

}

return 0;

}

Решение 2

Стоит отметить сразу, что данный код, по сути не работает на некоторых тестах, например когда символы, которые должны входить в искомую наибольшую подстроку, стоят в начале или конце обоих строк или хотя бы одной из них. Однако, как показывает практика, тесты на e-olymp данный способ посимвольного сравнения проходит. В данном варианте решения будем использовать c-string. Сами строки объявлены так: char a[100001], b[100001];, где [latex]100001[/latex] — это максимальная длина строки, которая может быть по условию задачи, и еще [latex]+1[/latex]. Объявить можно было еще и так: char * a = new char [100001];

Ссылки

Related Images:

e-olymp 1488. Шахматная головоломка

22/02/2019 by Инна Литвиненко

Задача

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

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

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

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

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

Первая строка входного файла содержит положение коня в следующем формате. Сначала буква от $a$ до $h$, обозначающая номер столбца в котором находится конь, потом цифра от $1$ до $8$, обозначающая номер строки.

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

В первую строку выведите положение ладьи в аналогичном формате, во вторую строку выведите положение слона.

Гарантируется, что требуемая расстановка всегда существует.

Тесты

№	Ввод	Вывод
1	a1	d1 b2
2	h8	e8 g7
3	e5	b5 d4
4	c8	f8 d7
5	h6	e6 g5

Код

#include <iostream>
using namespace std;

int main() {
    int k1;
    char k0;
    cin >> k0 >> k1;
    int n = 8; //Вводим n, чтобы иметь возможность изменить размер доски 
    char mid = char (('a' + n) - n / 2); //Находим середину доски
    if ( k1 != 1) {
        if (k0 < mid) cout << char(k0 + 3) << k1 << "\n" << char(k0 + 1) << k1 - 1;
        else cout << char(k0 - 3) << k1 << "\n" << char(k0 - 1) << k1-1;
    }
    else {
        if (k0 < mid) cout << char(k0 + 3) << k1 << "\n" << char(k0 + 1) << k1 + 1;
        else cout << char(k0 - 3) << k1 << "\n" << char(k0 - 1) << k1 + 1;
    } 
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int k1;

char k0;

cin >> k0 >> k1;

int n = 8; //Вводим n, чтобы иметь возможность изменить размер доски

char mid = char (('a' + n) - n / 2); //Находим середину доски

if ( k1 != 1) {

if (k0 < mid) cout << char(k0 + 3) << k1 << "\n" << char(k0 + 1) << k1 - 1;

else cout << char(k0 - 3) << k1 << "\n" << char(k0 - 1) << k1-1;

}

else {

if (k0 < mid) cout << char(k0 + 3) << k1 << "\n" << char(k0 + 1) << k1 + 1;

else cout << char(k0 - 3) << k1 << "\n" << char(k0 - 1) << k1 + 1;

}

return 0;

}

Решение

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

Ссылки

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

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

Related Images:

e-olymp 8377. Стойкое число

21/02/2019 by Дмитрий Калинин

Задача

По числу $x$ определим $p(x)$ как произведение его цифр. Рассмотрим последовательность $x$, $p(x)$, $p(p(x))$… Стойкостью $x$ назовем индекс (начиная с $0$) первого однозначного числа в этой последовательности. Например, из $99$ получим последовательность $99$, $9 · 9 = 81$, $8 · 1 = 8$. Стойкость числа $99$ равна $2$. По заданному числу $n$ определите его стойкость.

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

Каждая строка содержит одно целое число $n (0 \leqslant n \leqslant 2 · 10^9)$.

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

Для каждого значения $n$ выведите в отдельной строке его стойкость.

Решение

Опишем функцию $p(x)$, которая будет считать произведение цифр числа $x$. Для этого в функции заводим дополнительную переменную, например, $t$, равную единице, которую будем циклично домножать на остаток от деления $x$ на $10$, а $x$ уменьшать на разряд до тех пор, пока $x$ не попадёт в разряд единиц. Получившееся значение $t$ снова передаём в функцию $p(x)$ в качестве аргумента. Продолжим действия, описанные выше, до тех пор пока значение $t$ не будет находиться в разряде единиц. Индекс последней итерации функции и будет искомой стойкостью числа $x$.

Тесты

№	Ввод	Вывод
1	99 268 6	2 4 0
2	796 1 100	5 0 1
3	2356951 53 9892	2 2 3

Код

#include <iostream>
using namespace std;
 
int p(int x) {
    int t = 1;
    while (x != 0) {
        t *= x % 10;
        x = x / 10;
    }
    return t;
}
 
int main() {
    int x;
    while (cin >> x) {
        int i = 0;
        while (x / 10 != 0) {
            x = p(x);
            i++;
        }
        cout << i << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int p(int x) {

int t = 1;

while (x != 0) {

t *= x % 10;

x = x / 10;

}

return t;

}

int main() {

int x;

while (cin >> x) {

int i = 0;

while (x / 10 != 0) {

x = p(x);

i++;

}

cout << i << endl;

}

return 0;

}

Код для считывания строками

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

string f(string x) {
    int mult = 1;
    for (int i = 0; i < x.length(); i++) {
        mult *= int(x.at(i)) - int('0');
    }
    string result = to_string(mult);
    return result;
}

int main() {
    string inp;
    while (cin >> inp) {
        int count = 0;
        while (inp.length() > 1) {
            inp = f(inp);
            count++;
        }
        cout << count << endl;
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

string f(string x) {

int mult = 1;

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

mult *= int(x.at(i)) - int('0');

}

string result = to_string(mult);

return result;

}

int main() {

string inp;

while (cin >> inp) {

int count = 0;

while (inp.length() > 1) {

inp = f(inp);

count++;

}

cout << count << endl;

}

return 0;

}

Код c-string

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

int f(char* str, int i) {
    if (i == 0)
        return int(str[i]) - int('0');
    else
        return (int(str[i]) - int('0')) * f(str, i - 1);
}

int main() {
    char str[10];
    int t;
    while (cin >> str) {
        int count = 0;
        while (strlen(str) > 1) {
            int k = strlen(str) - 1;
            t = f(str, k);
            memset(str, 0, sizeof(str) / sizeof(str[0]));
            sprintf(str, "%d", t);
            count++;
        }
        cout << count << endl;
    }
    return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int f(char* str, int i) {

if (i == 0)

return int(str[i]) - int('0');

else

return (int(str[i]) - int('0')) * f(str, i - 1);

}

int main() {

char str[10];

int t;

while (cin >> str) {

int count = 0;

while (strlen(str) > 1) {

int k = strlen(str) - 1;

t = f(str, k);

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

sprintf(str, "%d", t);

count++;

}

cout << count << endl;

}

return 0;

}

Ссылки

Continue reading →

Related Images:

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

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

Задача

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

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

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

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

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

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

Тесты

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

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

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

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

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

int q, begin1, end1, begin2, end2;

getline(cin, s);

cin >> q;

while (q--) {

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

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

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

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

}

return 0;

}

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

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

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

#include <iostream>

#include <cstring>

using namespace std;

int main() {

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

cin >> str;

int q, l1, r1, l2, r2;

cin >> q;

while (q--) {

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

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

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

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

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

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

}

return 0;

}

Решение

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

Ссылки

string

c-string

Related Images:

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

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

Задача

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

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

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

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

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

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

Тесты

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

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

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

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

#include <iostream>

#include <string>

using namespace std;

int main() {

string s;

char a;

cin >> a;

float b;

s = a;

cin >> b;

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

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

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

cout << " ";

cout << s;

s = a + s + a;

cout<<endl;

}

return 0;

}

Решение

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

Ссылки

e-olymp
Ideone

Related Images:

e-olymp 1611. Реверс подстроки

26/06/2018 by Карина Миловская

Задача

Дана строка $s$, в которой выделили подстроку, состоящую из символов с $i$-го по $j$-ый включительно (символы строки $s$ нумеруются с единицы) и поменяли местами $i$-ый символ с $j%-ым, %(i + 1)%-ый с %(j — 1)$-ым и так далее (конвертировали подстроку). Выведите строку $s$ после внесенных изменений.

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

В первой строке содержится строка $s$ длиной не более $1000$ символов, во второй — два числа $i$ и $j$ $\left (i \leqslant j \right).$

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

Выведите строку $s$ после внесенных изменений.

Тесты

Входные данные	Выходные данные
$zbbg \\ 2 \; 3$	$zbbg$
$gaqipkajibk \\ 5 \; 6$	$gaqikpajibk$
$helloworld \\ 5 \; 7 $	$helloworld$
$rkdobnjfyy \\ 6 \; 3 $	$rkdobnjfyy$

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

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

int main() {
    char s[1001];
    cin >> s;
    int i, j;
    cin >> i >> j;
    for (int b = i - 1, c = j - 1; b < c; b++,c--) {
        int k = s[b];
        s[b] = s[c];
        s[c] = k;
    }
    cout << s;
    
    return 0;
    
}

#include <iostream>

#include <cstring>

using namespace std;

int main() {

char s[1001];

cin >> s;

int i, j;

cin >> i >> j;

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

int k = s[b];

s[b] = s[c];

s[c] = k;

}

cout << s;

return 0;

}

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

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

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

#include <iostream>
using namespace std;
 
int main() {
    string s;
    cin >> s;
    int i, j;
    cin >> i >> j;
    for (int b = i - 1, c = j - 1; b < c; b++,c--) {
        int k = s[b];
        s[b] = s[c];
        s[c] = k;
 
    }
    cout << s;
 
    return 0;
}

#include <iostream>

using namespace std;

int main() {

string s;

cin >> s;

int i, j;

cin >> i >> j;

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

int k = s[b];

s[b] = s[c];

s[c] = k;

}

cout << s;

return 0;

}

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

Для решения задачи вводим строку $s$. Далее в цикле конвертируем подстроку и выводим строку $s$ после внесенных изменений.

Ссылки

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

Задача

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

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

Тесты

Код

Решение

Related Images:

Условие

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

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

Тесты

Решение

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

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

Ссылки

Related Images:

Задача

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

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

Тесты

Код 1

Код 2

Решение

Related Images:

Задача

Завдання

Вхідні дані

Вихідні дані

Оцінювання

Тести

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

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

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

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

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

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

Посилання

Related Images:

Задача

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

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

Тесты

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

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

Решение

Ссылки

Для string:

Для c-string:

Related Images:

Задача

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

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

Тесты

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

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

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

Ссылки

Related Images:

Task

Input

Output

Tests

Program code

Program code V2.

Solution

Links

Related Images:

Задача

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

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

Тесты

Код (string)

Код (c-string)

Решение

Ссылки

Related Images:

Задача

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

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

Тесты