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 2322. Столбцы

28/04/2019 by Михаил Бутник

Столбцы

Дана таблица [latex]n × n[/latex], заполненная целыми числами. Петр Первый считает столбец хорошим, если тот содержит число [latex]x[/latex]. Требуется для каждого столбца выяснить, является ли тот хорошим.

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

В первой строке задано число [latex]x[/latex], не превышающее по модулю 2 [latex]\cdot[/latex] 10⁹. Во второй строке задано число [latex]n \left(1 \leqslant n \leqslant 100\right)[/latex]. Каждая из следующих [latex]n[/latex] строк содержит [latex]n[/latex] целых чисел, не превышающих по модулю 2 [latex]\cdot[/latex] 10⁹ — числа в ячейках таблицы.

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

Для каждого столбца в отдельной строке выведите YES, если в нем есть число [latex]x[/latex], и NO в противном случае.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1 2 0 1 0 0	NO YES
2	23 3 23 0 23 21 12 23 11 13 23	YES NO YES
3	7 1 0	NO
4	13 3 13 33 75 23 45 31 13 13 13	YES YES YES

Код

#include <iostream>
using namespace std; 
 
int arr[101];
int main() {
    long long x, c;
    cin >> x;
    int n, i = 0;
    cin >> n;
    while (cin >> c) {
        if (c == x) {
            arr[i % n]++;
        }
        i++;
    }
    for (int i = 0; i < n; i++) {
        if (arr[i] > 0) {
            cout << "YES" << endl;
        }
        else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

#include <iostream>

using namespace std;

int arr[101];

int main() {

long long x, c;

cin >> x;

int n, i = 0;

cin >> n;

while (cin >> c) {

if (c == x) {

arr[i % n]++;

}

i++;

}

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

if (arr[i] > 0) {

cout << "YES" << endl;

}

else {

cout << "NO" << endl;

}

return 0;

}

Решение

Для решения этой задачи заведём массив на [latex]n[/latex] элементов, в котором каждый элемент будет счётчиком соответствующего столбца. В цикле будем смотреть все элементы и, если нам встретится элемент [latex]x[/latex], увеличим соответствующий счётчик. Затем в другом цикле смотрим счётчик каждого столбца, если он больше нуля, то выводим YES, иначе — NO.

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

Related Images:

e-olymp 2507. Граница

08/01/2019 by Михаил Бутник

Задача

В международной политике важным понятием является граница между государствами. Нечеткое понимание сторонами того, где проходит граница, может привести к международным конфликтам и даже войнам. В этой задаче ситуация обстоит несколько проще, так как у двух рассматриваемых в задаче государств есть четкое понимание, какая территория принадлежит какому из них. Территория, занимаемая этими двумя государствами, представляет собой прямоугольник размером [latex]h[/latex] на [latex]w[/latex] километров, разбитый на квадраты со стороной в один километр. Каждый из этих квадратов полностью принадлежит либо первому государству, либо второму. Необходимо определить длину границы между двумя государствами. Сторона единичного квадрата считается принадлежащей границе, если по одну сторону от нее лежит квадрат, принадлежащий первому государству, а по другую — принадлежащий второму.

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

Первая строка содержит два целых числа: [latex]w[/latex] и [latex]h \left(1 \leqslant w, h \leqslant 100\right)[/latex] — размеры прямоугольника в километрах. Далее следуют [latex]h[/latex] строк, описывающих территорию. Каждая из них содержит [latex]w[/latex] символов. Если символ равен [latex]A[/latex], то соответствующий единичный квадрат принадлежит первому государству, а если он равен [latex]B[/latex], то второму. Гарантируется, что каждому государству принадлежит хотя бы один квадрат. Территории каждого из государств представляют собой связные области.

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

Выведите одно целое число — длину границы между государствами в километрах.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 6 AAABB ABBBB AAABB AAAAB AAAAB AABBB	13
2	4 3 AAAA AAAA AAAB	2
3	5 9 BBBBB ABBBB AABBB AAABB AAAAB AAABB AABBB ABBBB BBBBB	15
4	2 1 AB	1
5	6 5 AABBBB BBBBBB BBBAAA AAAAAA AAAAAA	10

Код

#include <iostream>
using namespace std;

int main() {
    int w, h, res = 0;
    cin >> w >> h;
    char **x = new char *[h];
    for (int i = 0; i < h; i++) x[i] = new char[w];
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            cin >> x[i][j];
        }
    }
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w - 1; j++) {
            if (x[i][j] != x[i][j + 1]) res++;
        }
    }
    for (int i = 0; i < h - 1; i++) {
        for (int j = 0; j < w; j++) {
            if (x[i][j] != x[i + 1][j]) res++;
        }
    }
    cout << res << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int w, h, res = 0;

cin >> w >> h;

char **x = new char *[h];

for (int i = 0; i < h; i++) x[i] = new char[w];

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

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

cin >> x[i][j];

}

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

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

if (x[i][j] != x[i][j + 1]) res++;

}

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

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

if (x[i][j] != x[i + 1][j]) res++;

}

cout << res << endl;

return 0;

}

Решение

Занесем прямоугольную область в многомерный массив символов. Рассмотрим символ x[i][j]. Если он не совпадает с x[i + 1][j], то между ними имеется граница длины 1 (снизу от x[i][j] проходит граница). Аналогично, если x[i][j] не совпадает с x[i][j + 1], то между ними имеется граница длины 1 (справа от x[i][j] проходит граница). Остается перебрать все символы и подсчитать для них количество нижних и правых границ.

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

Related Images:

e-olymp 137. НОД

25/12/2018 by Михаил Бутник

Задача

Найти НОД (наибольший общий делитель) [latex]n[/latex] чисел.

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

Первая строка содержит количество чисел [latex]n \left(1 \lt n \lt 101\right).[/latex] Во второй строке через пробел заданы [latex]n[/latex] натуральных чисел, каждое из которых не превышает 30000.

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

НОД заданных чисел.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	2 15 25	5
2	3 99 358 2	1
3	5 81 99 72 108 36	9
4	2 25 50	25
5	4 132 36 66 18	6

Код

#include <iostream>
using namespace std;
int gcd(int a, int b) {
    return (a == 0) ? b: gcd(b % a, a);
}

int main() {
    int n, m = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a;
        cin >> a;
        m = gcd(m, a);
    }
    cout << m;
    return 0;
}

#include <iostream>

using namespace std;

int gcd(int a, int b) {

return (a == 0) ? b: gcd(b % a, a);

}

int main() {

int n, m = 0;

cin >> n;

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

int a;

cin >> a;

m = gcd(m, a);

}

cout << m;

return 0;

}

Решение

Для решения этой задачи я воспользовался функцией gcd — рекурсивной функцией нахождения НОД 2-x чисел. В цикле читаем [latex]n[/latex] чисел и применяем к ним функцию gcd для нахождения их НОД. При первом проходе цикла находим НОД первого числа и нуля, так как это и будет само число.

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

Related Images:

e-olymp 273. Возведение в степень

22/12/2018 by Михаил Бутник

Задача

По трем натуральным числам [latex]a[/latex], [latex]b[/latex] и [latex]m[/latex] вычислить значение [latex]a^b\mod m[/latex].

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

Три натуральных числа [latex]a[/latex], [latex]b[/latex], [latex]m[/latex] [latex]\left(1 \leqslant a, m \leqslant 10^9, 2 \leqslant b \leqslant 10^7\right)[/latex].

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

Вывести [latex]a^b\mod m[/latex].

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1 2 100	1
2	100 2 1000000	10000
3	2 3 50	8
4	9 2 1	0
5	9 2 25	6

Код с циклом

#include <iostream>
using namespace std;
long binpow (long a, long n, long m) {
    long res = 1;
    while (n) {
        if (n & 1) {
            res *= a;
            res %= m;
        }
        a *= (a % m);
        a %= m;
        n >>= 1;
    }
    return res % m;
}
 
int main() {
    long a, b, m;
    cin >> a >> b >> m;
    cout << binpow (a, b, m);
    return 0;
}

#include <iostream>

using namespace std;

long binpow (long a, long n, long m) {

long res = 1;

while (n) {

if (n & 1) {

res *= a;

res %= m;

}

a *= (a % m);

a %= m;

n >>= 1;

}

return res % m;

}

int main() {

long a, b, m;

cin >> a >> b >> m;

cout << binpow (a, b, m);

return 0;

}

Код с ветвлением

#include <iostream>
using namespace std;
long binpow (long a, long n, long m) {
    if (n == 0)
        return 1 % m;
    if (n % 2 == 1)
        return (binpow (a, n - 1, m) * a) % m;
    else {
        return binpow ((a * a) % m, n/2, m);
    }
}
 
int main() {
    long a, b, m;
    cin >> a >> b >> m;
    cout << binpow (a, b, m);
    return 0;
}

#include <iostream>

using namespace std;

long binpow (long a, long n, long m) {

if (n == 0)

return 1 % m;

if (n % 2 == 1)

return (binpow (a, n - 1, m) * a) % m;

else {

return binpow ((a * a) % m, n/2, m);

}

int main() {

long a, b, m;

cin >> a >> b >> m;

cout << binpow (a, b, m);

return 0;

}

Решение

Для решения этой задачи я воспользовался функцией бинарного возведения в степень binpow () (рекурсивной для программы с ветвлением и нерекурсивной для программы с циклом). Это приём, позволяющий возводить любое число в [latex]n[/latex]-ую степень за [latex]O(\log n)[/latex] умножений. В этой функции при возведении я дополнительно применял операцию деление с остатком к результату res и возводимому числу a для того, чтобы получить решение.

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

Related Images:

e-olymp 4718. Привет, Гарри!

17/09/2018 by Михаил Бутник

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

Задача

Напишите программу, которая приветствует пользователя, выводя слово Hello, имя пользователя и знаки препинания в следующем виде: Hello, Harry

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

В единственной строке вводится имя пользователя.

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

В первой строке выведите приветствие.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	Harry	Hello, Harry
2	Peter	Hello, Peter
3	Emily	Hello, Emily
4	Anna-Maria	Hello, Anna-Maria
5	Zhao Yun	Hello, Zhao Yun

Код

#include <iostream>
#include <string>
using namespace std;
 
int main() {
    string name;
    getline (cin, name);
    cout << "Hello, " << name;
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

string name;

getline (cin, name);

cout << "Hello, " << name;

return 0;

}

Решение

Для того, чтобы задать переменную-строку, воспользуемся библиотекой string. Далее, введём переменную, к примеру name (имя). В строке вывода зададим неизменную часть фразы Hello, и саму переменную.

Ссылки

ideone
e-olymp