e-olymp 2099. Два массива

26/05/2019 by Даниил Мозгунов

Задача

Даны два массива чисел. Требуется вывести те элементы первого массива (в том порядке, в каком они идут в первом массиве), которых нет во втором массиве.

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

Сначала подаётся количество [latex]n[/latex] элементов в первом массиве, затем [latex]n[/latex] чисел — элементы массива. Затем записано количество [latex]m[/latex] элементов во втором массиве. Далее заданы элементы второго массива. Количество элементов каждого массива не превышает [latex]100[/latex]. Все элементы — целые числа.

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

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

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	7 3 1 3 4 2 4 12 6 4 15 43 1 15 1	4 3 3 2 12
2	5 12 16 17 45 68 6 1 93 45 68 34 38	3 12 16 17
3	10 15 47 68 59 75 25 35 61 21 86 10 15 47 69 58 75 26 36 61 21 89	5 68 59 25 35 86
4	10 15 47 68 59 75 25 35 61 21 86 10 15 47 68 59 75 25 35 61 21 86	0 0

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

#include <iostream>
using namespace std;
 
int main() {
  bool q;
  int n, m, c = 0;
  int arr1[101], arr2[101], arr3[101];
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> arr1[i];
  }
  cin >> m;
  for (int i = 0; i < m; i++) {
    cin >> arr2[i];
  }
  for (int i = 0; i < n; i++) {
    q = false;
    for (int j = 0; j < m; j++)
      if (arr1[i] == arr2[j]) q = true;
    if (q == false) {
      arr3[c] = arr1[i];
      c++;
    }
  }
  cout << c << endl;
  for (int i = 0; i < c - 1; i++) {
    cout << arr3[i] << " ";
  }
  cout << arr3[c - 1];
  return 0;
}

#include <iostream>

using namespace std;

int main() {

bool q;

int n, m, c = 0;

int arr1[101], arr2[101], arr3[101];

cin >> n;

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

cin >> arr1[i];

}

cin >> m;

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

cin >> arr2[i];

}

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

q = false;

for (int j = 0; j < m; j++)

if (arr1[i] == arr2[j]) q = true;

if (q == false) {

arr3[c] = arr1[i];

c++;

}

cout << c << endl;

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

cout << arr3[i] << " ";

}

cout << arr3[c - 1];

return 0;

}

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

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

Ссылки

Related Images:

e-olymp 928. Сумма наибольшего и наименьшего

14/05/2019 by Даниил Мозгунов

Задача

Задан массив целых чисел. Определить сумму наименьшего и наибольшего элементов массива.

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

В первой строке задано количество элементов массива [latex]n[/latex] ([latex]n \leq 100[/latex]). Во второй строке заданы [latex]n[/latex] элементов массива, значение каждого из которых по модулю не превышает [latex]100[/latex].

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

Вывести сумму наименьшего и наибольшего элементов массива.

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	4 1 2 3 4	5
2	5 2 4 6 8 5	10
3	6 6 2 4 5 7 9	11
4	7 7 5 4 6 8 16 1	17
5	5 16 20 65 34 86	102

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

#include <iostream>
using namespace std;
 
int main() {
    int n, p;
    cin>>p; 
    int min = 100;
    int max = -100;
    for (int i = 0; i < p; i++){
        cin>>n;
        if(n < min){
            min = n;
        }
        if(n > max){
            max = n;
        }
    }
    cout<<min + max;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, p;

cin>>p;

int min = 100;

int max = -100;

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

cin>>n;

if(n < min){

min = n;

}

if(n > max){

max = n;

}

cout<<min + max;

return 0;

}

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

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

Ссылки

Related Images:

e-olymp 75. Пираты и монеты

24/12/2018 by Даниил Мозгунов

Задача

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

Сколько было пиратов вместе с капитаном, если известны [latex]a[/latex] и [latex]m[/latex]. Так как капитан без команды просто пират, то [latex]n > 1[/latex].

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

Два натуральных числа [latex]a[/latex] и [latex]m[/latex] ([latex]1 \leq a \leq 100, m < 15150[/latex]). Входные данные корректны.

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

Количество пиратов [latex]n[/latex].

Тесты

#	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	5 25	3
2	3 24	4
3	4 38	5
4	5 55	6
5	6 75	7

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

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
    double a, m, n, b, c, d;
    cin>>a>>m; 
    b = 2 * a + 1;
    c = 2 * a - 2 - 2 * m;
    d = b * b - 4 * c;
    n = ( -b + sqrt(d) ) / 2;
    cout<<n;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double a, m, n, b, c, d;

cin>>a>>m;

b = 2 * a + 1;

c = 2 * a - 2 - 2 * m;

d = b * b - 4 * c;

n = ( -b + sqrt(d) ) / 2;

cout<<n;

return 0;

}

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

Для решения задачи воспользуемся формулой арифметической прогрессии, которая в данном случае равна: [latex](2a + n — 1)\frac{n}{2} + a + n — 1[/latex]. Отсюда получаем квадратное уравнение : [latex]\frac{n^{2}}{2} + n(a + \frac{1}{2}) + a — 1 = m[/latex], упростим и получим: [latex]n^{2} + 2an + n + 2a — 2 = 2m[/latex]. В коде задаем чему равно [latex]b[/latex], [latex]c[/latex] и [latex]d[/latex]. Где [latex]b[/latex] и [latex]c[/latex] — коэффициенты квадратного уравнения, а [latex]d[/latex] — дискриминант квадратного уравнения, который вычисляем по формуле: [latex]b^{2} — 4c[/latex]. Они нужны для нахождения корня данного квадратного уравнения. При этом ответом на задачу будет только один корень квадратного уравнения, так как количество пиратов не может принимать отрицательное значение. Поэтому вычисляем корень квадратного уравнения по формуле: [latex]\frac{-b + \sqrt{b}}{2}[/latex], тем самым получаем ответ на нашу задачу.

Код программы (с циклом)

#include <iostream>
using namespace std;

int main() {
    unsigned int a, m, n = 0;
    cin>>a>>m;
    while (m - 2 * a != 0){
            m -= a;
            a ++;
            n ++;
    }
    cout<<n + 1;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

unsigned int a, m, n = 0;

cin>>a>>m;

while (m - 2 * a != 0){

m -= a;

a ++;

n ++;

}

cout<<n + 1;

return 0;

}

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

В данном способе используем цикл. Как он работает: в условии цикла задаем проверку, когда наступит очередь капитана и будет выполнятся равенство вида [latex]m — 2a = 0[/latex] цикл прекратит свою работу. Пока это равенство не будет выполнятся цикл будет выполнять работу арифметической прогрессии, постоянно увеличивая количество монет [latex]a[/latex] на каждого пирата при этом, вычитая каждый раз из общего клада [latex]m[/latex], также, пока не выполняется данное равенство, считаем количество пиратов [latex]n[/latex], путем прибавления [latex]n + 1[/latex], пока работает цикл. И когда цикл прекращает свою работу, в конце учитываем капитана и к полученному количеству пиратов [latex]n[/latex] прибавляем [latex]n + 1[/latex]. И получаем ответ на нашу задачу.

Код программы (с условным оператором)

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

#include <iostream>

using namespace std;

int f(int a, int m, int n = 0) {

if (m - 2*a == 0) {

return n + 1;

}

else {

return f(a + 1, m - a, n + 1);

}

int main() {

int a, m;

cin >> a >> m;

cout << f(a, m);

return 0;

}

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

В данном способе воспользуемся рекурсивной функцией и условными операторами. Как это работает: внутри рекурсивной функции расписываем условные операторы, которые определяют равенством [latex]m — 2a = 0[/latex] — когда наступила очередь капитана, а пока это условие не выполняется, функция будет вызывать сама себя пока это условие не удовлетворится, функция каждый раз вызывается с новыми параметрами соответственно. Где [latex]a[/latex] — количество монет даваемое пиратам, увеличивается по рангу каждого пирата, [latex]m[/latex] — клад, от него отнимаем текущее [latex]a[/latex], и [latex]n[/latex] — количество пиратов, считаем пиратов. И в конце выводит количество пиратов. Задача решена.

C++ для приматов

Начальный курс программирования для студентов направления "Прикладная математика" Одесского национального университета имени И.И.Мечникова

Author Archives: Даниил Мозгунов

e-olymp 2099. Два массива

Задача

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

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

Тесты

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

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

Ссылки

Related Images:

e-olymp 928. Сумма наибольшего и наименьшего

Задача

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

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

Тесты

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

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

Ссылки

Related Images:

e-olymp 75. Пираты и монеты

Задача

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

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

Тесты

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

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

Код программы (с циклом)

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

Код программы (с условным оператором)

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

Ссылки

Related Images: