Category Archives: 5. Массивы

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

Массивы

Опубликовано: 20/10/2014

К этой рубрике относятся задания на использование классических массивов, работе с ними через указатели и ссылочные типы. Желательно снова перечитать параграф 3.5 и 3.6 из праймера. Размер массива обычно будет читаться из входного потока. Это вынуждает использовать динамические массивы. В качестве заготовки можно использовать такой код:

#include <iostream>
using namespace std;
 
int main() {
    size_t n;   
    cin >> n;
    double *x = new double [n];
    for(size_t i = 0; i < n; i++)
        cin >> x[i];
        
    // Processing 
    for(size_t i = 0; i < n; i++)
        cout << "x[" << i << "] = " << x[i] << "\t";
}

#include <iostream>

using namespace std;

int main() {

size_t n;

cin >> n;

double *x = new double [n];

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

cin >> x[i];

// Processing

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

cout << "x[" << i << "] = " << x[i] << "\t";

}

Выполнить программу Обратите внимание, что цикл в котором … Continue reading →

нет комментариев

В классе и дома решаются следующие тренировочные задачи (1 балл):

Санта Клаус
Кубики — 3 — используйте массив bool для хранения предположений о потери кубика для каждой из 26+26=52 букв.
Прямоугольник — используйте массив точек.

Опубликованные решения

e-olymp 1661. Рюкзак Алладина

29/01/2020 by Валентин Цушко

Условие

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

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

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

Будем считать, что в пещере имеются предметы $n$ различных типов, количество предметов каждого типа не ограничено. Максимальный вес, который может выдержать рюкзак, равен $w$. Каждый предмет типа $i$ имеет вес $w_{i}$ и стоимость $v_{i}$ $(i = 1, 2, \ldots, n)$.

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

В первой строке содержится два натуральных числа $w$ и $n$ $(1 \leqslant w \leqslant 250, 1 \leqslant n \leqslant 35)$ — максимальный вес предметов в рюкзаке и количество типов предметов. Следующие $n$ строк содержат по два числа $w_{i}$ и $v_{i}$ $(1 \leqslant w_{i} \leqslant 250, 1 \leqslant v_{i} \leqslant 250)$ — вес предмета типа $i$ и его стоимость.

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

Выведите максимальную стоимость груза, вес которого не превышает $w$.

Тесты

№	Входные данные	Выходные данные
1	10 2 5 10 6 19	20
2	250 35 187 100 28 109 245 142 123 83 237 78 36 172 15 248 90 24 181 137 40 233 8 99 231 128 79 132 43 217 156 104 45 191 130 113 105 225 206 5 26 120 26 119 64 138 23 147 19 202 79 54 149 185 158 79 209 88 110 133 235 209 188 230 15 220 107 164 235 137 60 167	4067
3	35 4 20 4 1 2 10 8 7 6	70

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

#include <iostream>
using namespace std;
 
int main()
{
    int w, n;
    const int NegNum = -1;
    cin >> w >> n;
    int WeiCos[n][2], s[w + 1];
    for(int i = 0; i < n; i++){
        for(int j = 0; j < 2; j++){
            cin >> WeiCos[i][j];
        }
    }
    s[0] = 0;
    for(int j = 1; j <= w; j++){
        s[j] = NegNum;
    }
    for(int i = 0; i < n; i++){
        for(int j = WeiCos[i][0]; j <= w; j++){
            if(s[j - WeiCos[i][0]] != NegNum && s[j] < s[j - WeiCos[i][0]] + WeiCos[i][1]){
                s[j] = s[j - WeiCos[i][0]] + WeiCos[i][1];
            }
        }
    }
    int maxS = 0;
    for(int i = 1; i <= w; i++){
        maxS = max(maxS, s[i]);
    }
    cout << maxS;
 
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int w, n;

const int NegNum = -1;

cin >> w >> n;

int WeiCos[n][2], s[w + 1];

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

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

cin >> WeiCos[i][j];

}

s[0] = 0;

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

s[j] = NegNum;

}

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

for(int j = WeiCos[i][0]; j <= w; j++){

if(s[j - WeiCos[i][0]] != NegNum && s[j] < s[j - WeiCos[i][0]] + WeiCos[i][1]){

s[j] = s[j - WeiCos[i][0]] + WeiCos[i][1];

}

int maxS = 0;

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

maxS = max(maxS, s[i]);

}

cout << maxS;

return 0;

}

Решение

Допустим $w = 9$, $n = 2$, первый предмет $w_{1} = 3$, $n_{1} = 4$, а второй предмет $w_{2} = 2$, $n_{2} = 1$. После того как считаем условие в два одномерных или один двумерный массив (как вам удобнее). Создадим одномерный массив в котором его размер будет равен $w$ и первый элемент будет равен 0, а остальные будут равны минус бесконечности или как в нашем случае (в коде) -1, как показано на (рис. 1). И дальше как показано на (рис. 2) начиная с элемента с номером веса предмета мы прибавляем его стоимость к стоимости предыдущей как показано в коде s[j] = s[j - WeiCos[i][0]] + WeiCos[i][1];, если прошлый не минус бесконечность. И так же со вторым элементом, когда они пересекаются с первым мы их сравниваем и вписываем в массив, больший. И в самом конце проходим заново массив и выбираем самый больший элемент, где бы он ни был как показано на (рис. 3). И таким образом на последних позициях которые равняются весу, будут записаны самые дорогие комбинации, благодаря записи самых дорогих элементов в ячейки.

Ссылки:
Задача на e-olymp
Код на OnlineGDB
Код на Ideone
Засчитанное решение на e-olymp

Related Images:

e-olymp 2663. Сортировка пузырьком

28/01/2020 by Даниил Кадочников

Условие

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

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

В первой строке содержится количество элементов $n$ ($1 \leqslant n \leqslant 1000$) в массиве. Во второй строке — сам массив. Гарантируется, что все элементы массива различны и не превышают по модулю $10$^$9$.

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

Выведите одно число — количество обменов пузырьковой сортировки.

Тесты

№	Ввод	Вывод
1	3 1 3 2	1
2	2 2 1	1
3	4 4 1 5 3	3
4	5 5 4 1 100000 7	4
5	6 6 5 4 3 2 1	15

Решение

Используем простой алгоритм пузырьковой сортировки: проходим по массиву циклом, если два элемента стоят не в том порядке, то меняем их местами. Так как задача состоит в том, чтобы вывести число обменов, при каждом обмене прибавляем к счётчику $1$. При каждом выполнении цикла по j ставится на место хотя бы 1 элемент, поэтому с каждым полным проходом его длина сокращается на $1$.

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

#include <iostream>
using namespace std;
int n;

int main() {
    cin >> n;
    int arr[n];

    for(int i=0; i<n; i++) cin >> arr[i];
    int counter=0;
    for(int u=0; u<n;u++) {
        for(int j=1; j<(n-u); j++) {
            if((arr[j]<arr[j-1])) {
                
                int prev;
                prev = arr[j-1];
                arr[j-1] = arr[j];
                arr[j] = prev;
                counter++;            
            }
        }
    }
    cout << counter;
    return 0;
}

#include <iostream>

using namespace std;

int n;

int main() {

cin >> n;

int arr[n];

for(int i=0; i<n; i++) cin >> arr[i];

int counter=0;

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

for(int j=1; j<(n-u); j++) {

if((arr[j]<arr[j-1])) {

int prev;

prev = arr[j-1];

arr[j-1] = arr[j];

arr[j] = prev;

counter++;

}

cout << counter;

return 0;

}

Ссылки

решение на e-olymp
код на ideone

Related Images:

e-olymp 8963. Наименьшие влево

19/01/2020 by Даниил Кадочников

Условие

Задан массив из [latex]n[/latex] целых чисел. Переместить все минимальные элементы в начало массива, не меняя порядок других.

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

В первой строке записано натуральное число [latex]n[/latex]. В следующей строке записаны [latex]n[/latex] целых чисел. Все числа по модулю не превышают [latex]100[/latex].

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

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

Тесты

№	Ввод	Вывод
1	7 6 -3 -7 4 -7 -4 5	-7 -7 6 -3 4 -4 5
2	2 100 -100	-100 100
3	6 -2 -2 7 3 99 -2	-2 -2 -2 7 3 99
4	5 1 1 1 1 1	1 1 1 1 1

Решение

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

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

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

int main()
{
    int n;
    cin >> n;
    vector <int> v, v2;
    int x;
    while(cin>>x) v.push_back(x);
    int min = v[0];
    for(int q=1; q<n; q++) {
        if(v[q]<min) min = v[q];
    }

    int min_counter = 0;
    for(int w=0; w<n; w++) {
        if(v[w] == min) min_counter++;
    }

    for(int e=0; e<min_counter; e++) v2.push_back(min);
    for(int r=0; r<n; r++) {
        if(v[r]!=min) v2.push_back(v[r]);
    }
    for(int t=0; t<n; t++) cout << v2[t] << " ";
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main()

{

int n;

cin >> n;

vector <int> v, v2;

int x;

while(cin>>x) v.push_back(x);

int min = v[0];

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

if(v[q]<min) min = v[q];

}

int min_counter = 0;

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

if(v[w] == min) min_counter++;

}

for(int e=0; e<min_counter; e++) v2.push_back(min);

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

if(v[r]!=min) v2.push_back(v[r]);

}

for(int t=0; t<n; t++) cout << v2[t] << " ";

return 0;

}

Ссылки

решение на E-olymp
код на ideone

Related Images:

e-olimp 7848. Переставить соседние

14/01/2020 by Елизавета Савицкая

Задача

Задан массив из $n$ целых чисел. Переставьте соседние элементы массива ($a_{0}$ с $a_{1}$, $a_{2}$ с $a_{3}$ и так далее). Если элементов нечетное количество, то последний элемент следует оставить на своем месте.

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

В первой строке записано число $n$. В следующей строке записано $n$ целых чисел. Все числа по модулю не превышают $100$.

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

Вывести обновленный массив.

Тесты

Входные данные	Выходные данные
7 3 5 -7 7 5 -9 -4	5 3 7 -7 -9 5 -4
8 -9 81 27 -38 2 6 -56 -21	81 -9 -38 27 6 2 -21 -56
2 25 -76	-76 25
3 55 44 33	44 55 33
1 99	99

Код

#include <iostream>
using namespace std;

int main() {
   int n;
   cin >> n;
   int arr[n];
   for(int i = 0; i < n; i++){
      cin >> arr[i];
   } 
   for(int i = 1; i < n; i+=2){
      int q = arr[i];
      arr[i] = arr[i-1];
      arr[i-1] = q;
   }
   for(int i = 0; i < n; i++){
      cout << arr[i] << " ";
   }
   return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int arr[n];

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

cin >> arr[i];

}

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

int q = arr[i];

arr[i] = arr[i-1];

arr[i-1] = q;

}

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

cout << arr[i] << " ";

}

return 0;

}

Решение

Будем переставлять соседние элементы массива следующим образом: arr[1] с arr[0], arr[3] с arr[2] и так далее до конца массива (т.е. каждый нечетный по счету элемент меняем местами с предыдущим). При этом совершенно неважно, четное кол-во элементов или нечетное.

Ссылки

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

Related Images:

e-olymp 7847. Кількість різних елементів

12/01/2020 by Андрей Мартынюк

Задача

Дано масив з [latex]N[/latex] цілих чисел. Визначте, скільки в цьому масиві різних елементів.

Вхідні дані

В першому рядку записано число [latex]N[/latex]. В наступному рядку записано [latex]N[/latex] цілих чисел. Всі числа за модулем не перевищують [latex]100[/latex].

Вихідні дані

Кількість різних елементів в масиві.

Тести

№	Вхідні дані	Вихідні дані
1.	7 3 5 -7 7 5 -9 -4	6
2.	5 1 25 59 75 100	5
3.	6 1 2 3 1 2 4	4

Код 1

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int* a = new int[n];
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    int diffNum = 0;
    for (int i = 0; i < n; i++)
    {
        bool newNum = true;
        for (int j = 0; j < i; j++)
        {
            if (a[j] == a[i])
            {
                newNum = false;
                break;
            }
        }
        if (newNum == true)
        {
            diffNum++;
        }
    }
    cout << diffNum;
    
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

int* a = new int[n];

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

{

cin >> a[i];

}

int diffNum = 0;

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

{

bool newNum = true;

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

{

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

{

newNum = false;

break;

}

if (newNum == true)

{

diffNum++;

}

cout << diffNum;

return 0;

}

Код 1(without break)

#include <iostream>
using namespace std;
int main()
{
    int n;
    cin >> n;
    int* a = new int[n];
    for (int i = 0; i < n; i++) { cin >> a[i];
    }
    int diffNum = 0;
    for (int i = 0; i < n; i++)
    {
        bool newNum = true;
        for (int j = 0; j < i && a[i-1] != a[j]; j++)
        {
            if (a[j] == a[i])
            {
                newNum = false;
            }
        }
        if (newNum == true)
        {
            diffNum++;
        }
    }
    cout << diffNum;
    
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

int* a = new int[n];

for (int i = 0; i < n; i++) { cin >> a[i];

}

int diffNum = 0;

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

{

bool newNum = true;

for (int j = 0; j < i && a[i-1] != a[j]; j++)

{

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

{

newNum = false;

}

if (newNum == true)

{

diffNum++;

}

cout << diffNum;

return 0;

}

Решение

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

Ссылки

Код 2

#include <iostream>
using namespace std;
#include 
int main() {
    vector a(202, false);
    int n, diffNum, curVal;
    cin >> n;
    diffNum = n;
    for(int i = 0; i < n; i++)
    {
        cin >> curVal;
        if(a[curVal + 100]) 
        {
            diffNum--;
        }
        else 
        {
            a[curVal + 100] = true;
        }
    }
    cout << diffNum << endl;
    return 0;
}

#include <iostream>

using namespace std;

#include

int main() {

vector a(202, false);

int n, diffNum, curVal;

cin >> n;

diffNum = n;

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

{

cin >> curVal;

if(a[curVal + 100])

{

diffNum--;

}

else

{

a[curVal + 100] = true;

}

cout << diffNum << endl;

return 0;

}

Решение

Сначала, предположим, что все числа разные. Т.е. количество различных чисел равно [latex]n.[/latex] Далее в цикле for отметим читаем числа из потока и отмечаем в векторе vector<bool> a, что число встретилось. Встретив число ранее уже отмеченное уменьшаем счетчик различных чисел.

Ссылки

Related Images:

e-olymp 1290. Номерной знак

20/12/2019 by Таня Осипенко

Задача

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

Сколько существует различных таких номеров?

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

В единственной строке через пробел $2$ неотрицательных целых числа $B$ и $A$. Оба числа не превышают $26$.

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

Единственное число — ответ к задаче.

Тесты

№	Входные данные	Выходные данные
1	3 3	17576000
2	2 5	67600000
3	7 1	80318101760
4	1 1	260
5	26 26	615611958020715731079667428840020377600000000000000000000000000

Код

#include <iostream>
#include <string.h>

using namespace std;

void print(char * x, int n) { // функция вывода массива чисел 
  for (int i = n - 1; i >= 0; i--) {
    cout << (int) x[i];
  }
}
int MULT(char * x, char * y, char * z, int n, int m) { // функция для перемножения больших чисел
  memset(z, 0, n + m); // обнуляем массив
  for (int i = 0; i < m; i++) {
    for (int j = 0; j < n; j++) {
      char w = x[j] * y[i] + z[i + j];
      z[i + j + 1] += w / 10;
      z[i + j] = w % 10;
    }
  }
  int res = (z[n + m - 1] == 0) ? (n + m - 1) : (n + m); //  кол-во разрядов
  return res;
}
const int N = 100; // кол-во элементов массивов с небольшим запасом
char acc[N] = {1};
int acc_size = 1;
char tmp[N] = {0};
char v_26[] = {6, 2}; // 26

int main() {
  int A, B; // входные данные
  cin >> B >> A;
  for (int i = 0; i < B; i++) { // возведение 26 в степень B
    memcpy(tmp, acc, acc_size);
    acc_size = MULT(tmp, v_26, acc, acc_size, 2); // 2 - число разрядов в 26
  }
  print(acc, acc_size); // вывод результата
  for (int i = 0; i < A; i++){ // домножение на 10 в степени A
    cout << "0";
  }
  return 0;
}

#include <iostream>

#include <string.h>

using namespace std;

void print(char * x, int n) { // функция вывода массива чисел

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

cout << (int) x[i];

}

int MULT(char * x, char * y, char * z, int n, int m) { // функция для перемножения больших чисел

memset(z, 0, n + m); // обнуляем массив

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

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

char w = x[j] * y[i] + z[i + j];

z[i + j + 1] += w / 10;

z[i + j] = w % 10;

}

int res = (z[n + m - 1] == 0) ? (n + m - 1) : (n + m); // кол-во разрядов

return res;

}

const int N = 100; // кол-во элементов массивов с небольшим запасом

char acc[N] = {1};

int acc_size = 1;

char tmp[N] = {0};

char v_26[] = {6, 2}; // 26

int main() {

int A, B; // входные данные

cin >> B >> A;

for (int i = 0; i < B; i++) { // возведение 26 в степень B

memcpy(tmp, acc, acc_size);

acc_size = MULT(tmp, v_26, acc, acc_size, 2); // 2 - число разрядов в 26

}

print(acc, acc_size); // вывод результата

for (int i = 0; i < A; i++){ // домножение на 10 в степени A

cout << "0";

}

return 0;

}

Решение

Начнем с того, что к условию задачи прилагается картинка, на которой видно, что во всех номерных знаках буквы и цифры не перемешаны между собой произвольно, а имеют свои четко распределенные места, в примере это последовательность, в которой на первой позиции стоит буква, далее три цифры и на последних двух позициях снова буквы. Это важный момент, поскольку если бы действительно было разрешено использовать любую последовательность, возможных комбинаций было бы гораздо больше. Поскольку в латинском алфавите $26$ букв, для выбора буквы на первое место существует $26$ возможных вариантов, на второе тоже $26$, как и на третье, четвертое и т. д. То есть для того чтобы найти все комбинации из букв для $B$ мест, нужно умножить $26$ на $26$ $B$ раз. Точно так же это работает с арабскими цифрами. Их всего $10$, соответственно, умножаем $10$ на $10$ $A$ раз, где $A$ — количество мест в номерном знаке для цифр. Поэтому, чтобы найти количество возможных комбинаций букв и цифр, перемножаем полученные результаты. Отсюда получаем формулу $26^B\cdot 10^A$.

Сложность задачи заключается скорее не в формуле вычисления, а в реализации кода, поскольку большинство значений уже на этапе возведения в степень не помещаются даже в самые большие типы данных. Именно поэтому код состоит не из пяти строк и встроенной операции возведения в степень, а из более сложных операций, подходящих для работы с большими числами. По сути, у нас возникает проблема, связанная с перемножением больших чисел, которые не помещаются в стандартные типы данных С++. Для решения этой проблемы я выбрала модель представления, в которой числа записываются в виде массивов в десятичной системе, и каждая цифра числа является элементом массива. Младший разряд числа находится в нулевом элементе массива, а старший в $n-1$-ом соответственно. Далее была реализована функция «MULT», которая фактически осуществляет алгоритм умножения поэлементно с сохранением остатка от деления на $10$ в соответствующем элементе массива и добавлением частного от деления на $10$ к следующему элементу массива. Следует отметить, что данная функция принимает два числа, записанные в выше указанной модели представления (в виде массивов), и характеристиками этих чисел является пара: сам массив и количество разрядов в числе (размер массивов иными словами). На выходе функция возвращает количество разрядов полученного произведения. Сам же результат умножения сохраняется в виде массива, который является одним из параметров функции. В коде данная функция внесена в цикл для многократного перемножения чисел, то есть для возведения в нужную степень. Домножение на $10^A$ осуществляется в последнем цикле приписыванием A нулей к полученному результату.

Ссылки

Задача на сайте e-olymp
Код решения на ideone

Related Images:

e-olymp 7849. Обменять max и min

20/12/2019 by Катя Романцова

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

Задан массив из $n$ целых чисел. Замените все наибольшие его элементы на наименьший, а наименьшие элементы на наибольший.

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

В первой строке записано число $n ( n \leqslant 100 )$. В следующей строке записано $n$ целых чисел, каждое из которых по модулю не превосходит $100$.

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

Вывести обновленный массив.

Тесты

№	Входные данные	Выходные данные
1	7 3 5 -7 7 5 -9 -4	3 5 -7 -9 5 7 -4
2	2 1 2	2 1
3	9 12 99 87 42 55 8 65 40 72	12 8 87 55 99 65 40 72
4	8 -9 0 7 -5 2 5 1 -2	7 0 -9 -5 2 5 1 -2

Код

#include <iostream>
using namespace std;
 
int main() {
    int n;
    cin >> n;
    int *x = new int [n];
    for ( int i = 0; i < n; i++ ) cin >> x [i];
    int min = 100; 
    int max = -100;
    for ( int i = 0; i < n; i++ ) {
        if ( x [i] > max ) max = x [i];
        if ( x [i] < min ) min = x [i];
    }
    for ( int i = 0; i < n; i++ ) {
        if ( x [i] == max ) x [i] = min;
        else if ( x [i] == min ) x [i] = max;
    }
    for ( int i = 0; i < n; i++ ) cout << x [i] << " ";
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

int *x = new int [n];

for ( int i = 0; i < n; i++ ) cin >> x [i];

int min = 100;

int max = -100;

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

if ( x [i] > max ) max = x [i];

if ( x [i] < min ) min = x [i];

}

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

if ( x [i] == max ) x [i] = min;

else if ( x [i] == min ) x [i] = max;

}

for ( int i = 0; i < n; i++ ) cout << x [i] << " ";

return 0;

}

Решение

Для начала нам надо найти максимум и минимум в массиве. Для этого введем переменные максимума и минимума равные $-100$ и $100$. (Так как элементы массива по условию не должны превышать значения $|100|$ ). Проверяем. Если значение элемента массива больше значения переменной максимума, присваиваем переменной это значение. Аналогично и для минимума. Затем присвоим максимальному элементу массива минимальное, а минимальному — максимальное.

Ссылки

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

Код на Ideone

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

Related Images:

e-olymp 5041. Синтаксический анализ вещественных чисел

14/12/2019 by Илья Балицкий

Задача

Напишите программу, которая считывает строку и проверяет, содержит ли она действительное число. Действительное число может содержать десятичную точку или показатель степени (начинающийся с $ e $ или $ E $), или и то и то одновременно. Также число может содержать обыкновенный набор десятичных цифр. Если число содержит десятичную точку, то должна присутствовать хотя бы одна цифра с каждой стороны точки. Перед числом или экспонентой может находиться плюс или минус (или одновременно и там и там) (без пробелов после знака). Экспонентой является целое число (не содержит десятичной запятой). Пробелы могут присутствовать до или после числа, но не внутри него. Обратите внимание, что границ диапазона входных чисел не существует, но для простоты будем предполагать, что входные строки содержат не более $ 1000 $ символов.

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

Первая строка содержит количество тестов $ t $. Дальше следует $ t $ строк, каждая из которых содержит одно число.

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

Вывести $ t $ строк, каждая из которых содержит слово $ LEGAL $ или $ ILLEGAL $.

Тесты

№	Входные данные	Выходные данные
1.	2 1.5e+2 3.	LEGAL ILLEGAL
2.	4 752.45e+24 0.762e. -0.355.6432e	LEGAL ILLEGAL ILLEGAL
3.	1 -652.32e+45	LEGAL
4.	3 542.512e+3 123.456E+42 123.456.789	LEGAL LEGAL ILLEGAL

Код

#include <iostream>
using namespace std;
 
bool isdigit(char x) { // проверка, является ли символ числом
    return (x >= '0' && x <= '9'? 1: 0);
}
 
bool isreal(char* x) { // сама функция синтаксического анализа
    if ((!isdigit(*x))||(*x == '+' || *x == '-' && !isdigit(*++x))) return 0;
    while (isdigit(*x)) ++x; // счетчик сдвигает указатель до символа, отличного от числа
    if (*x == '.' && !isdigit(*++x)) return 0;
    while (isdigit(*x))++x;
    if ((*x == 'e' || *x == 'E')&&((*++x == '+' || *x == '-')&&(!isdigit(*++x)))) return 0;
    while (isdigit(*x)) ++x;
    return *x == 0; // закончилось ли число
}
 
int main() {
    char x[1001];
    int n;
    cin >> n;
    for (int i = 0;i < n;i++) { // сама проверка
        cin >> x; // ввод игнорирует пробелы, которые по условию могут быть до и после числа
        cout << (isreal(x) ? "LEGAL" : "ILLEGAL") << "\n";
    }
    return 0;
}

#include <iostream>

using namespace std;

bool isdigit(char x) { // проверка, является ли символ числом

return (x >= '0' && x <= '9'? 1: 0);

}

bool isreal(char* x) { // сама функция синтаксического анализа

if ((!isdigit(*x))||(*x == '+' || *x == '-' && !isdigit(*++x))) return 0;

while (isdigit(*x)) ++x; // счетчик сдвигает указатель до символа, отличного от числа

if (*x == '.' && !isdigit(*++x)) return 0;

while (isdigit(*x))++x;

if ((*x == 'e' || *x == 'E')&&((*++x == '+' || *x == '-')&&(!isdigit(*++x)))) return 0;

while (isdigit(*x)) ++x;

return *x == 0; // закончилось ли число

}

int main() {

char x[1001];

int n;

cin >> n;

for (int i = 0;i < n;i++) { // сама проверка

cin >> x; // ввод игнорирует пробелы, которые по условию могут быть до и после числа

cout << (isreal(x) ? "LEGAL" : "ILLEGAL") << "\n";

}

return 0;

}

Решение

Для решения задачи нам понадобится функция idigit() проверки того, является ли символ цифрой. В STL существует одноименная функция, которая выполняет ту же самую задачу, однако для практики, я написал свою. В функции анализа вещественных чисел isreal() нужно указать условия, при которых синтаксис будет нарушен. Т.е. не будут выполнены условия, описанные в задаче. Затем, если в символьном массиве не было замечено ошибок — возвратить trueв основную функцию. Важно то, что в числе не должно по условию быть других символов кроме «e», «E», «.», «+», «-» и цифр. Что касается окаймляющих пробелов, то при вводе строки через cin они игнорируются.

Ссылки

Условие задачи на e-olymp
Код программы на ideone.com
Засчитанное решение на e-olymp

Related Images:

e-olymp 9036. Комбинация игральных костей

10/12/2019 by Алина Зозуля

Задача

Подсчитайте количество способов, которыми можно получить сумму $n$ бросая игральный кубик один или несколько раз. Каждый бросок дает результат между 1 и 6.

Например, если $n = 3$, то имеется 4 способа:
1 + 1 + 1
1 + 2
2 + 1
3

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

Одно целое число $n$ $(1 \leqslant n \leqslant 10^6)$.

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

Выведите количество способов по модулю $10^9+7$.

Тесты

№	Входные данные	Выходные данные
1	1	1
2	3	4
3	5	16
4	6	32
5	8	123

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

Первый способ (выполняется быстрее, но использует больше памяти)

#include <iostream>
using namespace std;

int main() {
    int n;
    int ans;
    cin >> n; //считываем сумму, для которой будем считать количество перестановок
    long long a[n+1]; //создаем массив
    if (n == 1) ans = 1;
    if (n == 2) ans = 2;
    if (n == 3) ans = 4;
    if (n == 4) ans = 8;
    if (n == 5) ans = 16;
    if (n == 6) ans = 32;
    // частные случаи
    
    if (n > 6)
    {
        a[1] = 1; 
        a[2] = 2; 
        a[3] = 4; 
        a[4] = 8;
        a[5] = 16; 
        a[6] = 32; 
        for (int i = 7; i < n + 1; i++)
        {
            a[i]=0;
            for (int j = 1; j < 7; j++) // вычисление количества для i-ой суммы
                a[i] = ( a[i] + a[i-j] ) % 1000000007;
        }
        ans = a[n];
    }
    
    cout << ans;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

int ans;

cin >> n; //считываем сумму, для которой будем считать количество перестановок

long long a[n+1]; //создаем массив

if (n == 1) ans = 1;

if (n == 2) ans = 2;

if (n == 3) ans = 4;

if (n == 4) ans = 8;

if (n == 5) ans = 16;

if (n == 6) ans = 32;

// частные случаи

if (n > 6)

{

a[1] = 1;

a[2] = 2;

a[3] = 4;

a[4] = 8;

a[5] = 16;

a[6] = 32;

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

{

a[i]=0;

for (int j = 1; j < 7; j++) // вычисление количества для i-ой суммы

a[i] = ( a[i] + a[i-j] ) % 1000000007;

}

ans = a[n];

}

cout << ans;

return 0;

}

Второй способ (использует меньше памяти, но выполняется дольше)

#include <iostream>
using namespace std;

int main() {
    int a[6]={1, 2, 4, 8, 16, 32}; //создаём массив на 6 элементов и заполняем для n от 1 до 6
    int n, quantity, counter = 6;
    cin >> n; //считываем сумму
    if (n > 6)
    {
        while (counter < n)
        {
            counter++; //счетик, значение которого - сумма, для которой мы ищем количество способов
            quantity = 0;
            for (int j = 1; j < 7; j++) //подсчет количества способов для k-ой суммы
                quantity = (quantity + a[6-j]) % 1000000007;
                
            for (int i = 0; i < 5; i++)  
                a[i] = a[i+1];
            a[5] = quantity;
        }
        cout << a[5];
    }
    else cout << a[n-1];
    
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a[6]={1, 2, 4, 8, 16, 32}; //создаём массив на 6 элементов и заполняем для n от 1 до 6

int n, quantity, counter = 6;

cin >> n; //считываем сумму

if (n > 6)

{

while (counter < n)

{

counter++; //счетик, значение которого - сумма, для которой мы ищем количество способов

quantity = 0;

for (int j = 1; j < 7; j++) //подсчет количества способов для k-ой суммы

quantity = (quantity + a[6-j]) % 1000000007;

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

a[i] = a[i+1];

a[5] = quantity;

}

cout << a[5];

}

else cout << a[n-1];

return 0;

}

Решение

Создадим массив на $n+1$ элемент. В который мы сразу запишем количество перестановок для сумм 1,2..,6. Для остальных случаев, когда $n>7$ воспользуемся следующей идеей. Будем вычислять количество перестановок для сумм, начиная с 7 до тех пор, пока не дойдем до заданного нам $n$. Будем делать это по такой формуле $a_{i}=a_{i-1}+a_{i-2}+a_{i-3}+a_{i-4}+a_{i-5}+a_{i-6}$ . Для первых шести сумм вычисляем по этой же формуле, с учетом, что $0 < i-k \; (1 \leqslant k \leqslant 6)$ и добавляя еще 1 перестановку, так как мы можем получить сумму ( $i$ ), подбросив кубик 1 раз. Рассмотрим для $n=7$. Чтобы получить 7 достаточно подбросить кубик ещё один раз, так как мы знаем количество для $n$ от 1 до 6. Если выпадет 1, то остается $a_{6}$ возможных перестановок, если выпадет 2, то остается $a_{5}$ и так далее. Затем нам требуется просуммировать, так как кубик может выпасть 6 способами, как было сказано ранее. Соответственно для $n=8$ количество комбинаций увеличится на $a_{7}$ и уменьшится на $a_{1}$, так как кубик имеет только 6 граней.

Ссылки

Условие задачи на e-olymp

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

Related Images:

e-olymp 9410. Студенческая любовь

01/12/2019 by Дмитрий Воротов

Задача

Нурдаулет и Жарасхан тренируют студентов. К каждому студенту у них имеется свое собственное отношение, которое выражается как числа $a_{i}$ (для Нурдаулета) и $b_{i}$ (для Жараскана), которые называются индексом любви студентов. Аскар попросил их рассчитать коэффициент несправедливого отношения. Коэффициент несправедливого отношения — это разница между самым большим и самым маленьким индексом любви. Чтобы не показывать свои, возможно, большие коэффициенты несправедливого отношения, они решили обмануть: каждый перемешивает свой массив, после чего формируется новый массив $c_{i}$ = $a_{i}$ + $b_{i}$, и его коэффициент несправедливого отношения передается Аскару. Какое минимально возможное значение коэффициента они могут достичь?

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

Первая строка содержит одно целое число $n$ $(1 ⩽ n ⩽ 200000)$. Вторая строка содержит $n$ целых чисел $a_{i}$ $(-10^6 ⩽ a_{i} ⩽ 10^6)$. Третья строка содержит $n$ целых чисел $b_{i}$ $(-10^6 ⩽ b_{i} ⩽ 10^6)$.

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

Выведите одно число — ответ на задачу.

Тесты

№	Входные данные	Выходные данные
1	2 -3 -5 3 5	0
2	1 5 -2	0
3	5 -5 -2 -1 0 4 5 4 0 0 -1	4
4	9 1000 -22 333 -56 1 2 -77 -650 10 -7 166 -333 90 -565 12 788 -800 111	523

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

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

int main() {
    int n;
    cin >> n;
    int *a = new int[n], *b = new int[n];
    for (int i = 0; i < n; i ++) cin >> a[i];  // Считываем массивы
    for (int i = 0; i < n; i ++) cin >> b[i];  
    sort(a, a + n);    // Сортируем массивы
    sort(b, b + n);    // Вместо сортировки по убыванию будем просматривать отсортированный массив в обратном порядке 
    for (int i = 0; i < n; i ++) a[i] += b[n - i - 1];  // Суммируем элементы
    int maxa = a[0], mina = a[0];
    for (int i = 0; i < n; i ++) {
        maxa = max(maxa, a[i]);    // Находим минимальный и максимальный элементы
        mina = min(mina, a[i]);     
    }
    cout << maxa - mina;  // Разность минимального и максимального и будет самым маленьким индексом любви 
    return 0;
}

#include <iostream>

#include

using namespace std;

int main() {

int n;

cin >> n;

int *a = new int[n], *b = new int[n];

for (int i = 0; i < n; i ++) cin >> a[i]; // Считываем массивы

for (int i = 0; i < n; i ++) cin >> b[i];

sort(a, a + n); // Сортируем массивы

sort(b, b + n); // Вместо сортировки по убыванию будем просматривать отсортированный массив в обратном порядке

for (int i = 0; i < n; i ++) a[i] += b[n - i - 1]; // Суммируем элементы

int maxa = a[0], mina = a[0];

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

maxa = max(maxa, a[i]); // Находим минимальный и максимальный элементы

mina = min(mina, a[i]);

}

cout << maxa - mina; // Разность минимального и максимального и будет самым маленьким индексом любви

return 0;

}

Решение

Коэффициент будет минимальным в том случае, когда все элементы массива $c_{i}$ будут отличаться друг от друга как можно меньше. Для этого отсортируем один массив по убыванию, другой — по возрастанию и почленно сложим. После этого останется только найти максимальный и минимальный элементы полученного массива.

Ссылки

Условие задачи e-olymp

Код решения ideone

Related Images:

e-olymp 972. Сортировка времени

26/06/2019 by Максим Евчук

Задача

Отсортируйте время согласно заданному критерию

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

Сначала задано число $n\, \left ( 1\leqslant n\leqslant 100 \right )$, а затем n моментов времени. Каждый момент времени задается 3 целыми числами — часы (от 0 до 23), минуты (от 0 до 60) и секунды (от 0 до 60)

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

Выведите моменты времени, упорядоченные в порядке неубывания (момент времени также выводится в виде трех чисел, ведущие нули выводить не нужно)

Тесты

№	Входные данные	Выходные данные
1	[latex]\begin{matrix} 4 & & \\ 10 &20 &30 \\ 7 &30 &00 \\ 23&59 &59 \\ 13&30 &30 \end{matrix}[/latex]	[latex]\begin{matrix} 7 & 30 &00 \\ 10&20 &30 \\ 13&30 &30 \\ 23& 59 & 59 \end{matrix}[/latex]
2	$\begin{matrix} 6\\ 12 &55 &59 \\ 8 &33 &34 \\ 6 &56 &46 \\ 10 &23 &52 \\ 3 &20 &00 \\ 19 &31 &0\\ 10&23&52 \end{matrix}$	$\begin{matrix} 3 &20 &0 \\ 6 &56 &46 \\ 8 &33 &34 \\ 10 &23 &52 \\ 12 &55 &59 \\ 19 &31 &0 \end{matrix}$

#include <iostream>

#include <algorithm>

using namespace std;
int main() {
  int hours[100];
  int mins[100];
  int secs[100];
  int all_time[100];
  int n;
  cin >> n;
  for (int i = 0; i < n; i++) {
    cin >> hours[i] >> mins[i] >> secs[i];
    all_time[i] = hours[i] * 3600 + mins[i] * 60 + secs[i];
  }
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      if (all_time[i] > all_time[j]) {
        swap(hours[i], hours[j]); swap(mins[i], mins[j]);
        swap(secs[i], secs[j]); swap(all_time[i], all_time[j]);
      }
    }
  }
  for (int i = 0; i < n; i++) cout << hours[i] << " " << mins[i] << " " << secs[i] << endl;
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int hours[100];

int mins[100];

int secs[100];

int all_time[100];

int n;

cin >> n;

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

cin >> hours[i] >> mins[i] >> secs[i];

all_time[i] = hours[i] * 3600 + mins[i] * 60 + secs[i];

}

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

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

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

swap(hours[i], hours[j]); swap(mins[i], mins[j]);

swap(secs[i], secs[j]); swap(all_time[i], all_time[j]);

}

for (int i = 0; i < n; i++) cout << hours[i] << " " << mins[i] << " " << secs[i] << endl;

}

Решение

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

Ссылки

e-olymp
ideone

Related Images:

e-olymp 2667. Змейка

26/06/2019 by Дмитрий Калинин

Задача

Напишите программу, которая выводит элемент из строки $x$ и столбца $y$ матрицы размера $n × m$, которая заполнена змейкой:

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

Даны натуральные числа $n, m, x, y (1 \leqslant x \leqslant n \leqslant 50, 1 \leqslant y \leqslant m\leqslant 50)$. Здесь $n$- количество строк матрицы, $m$ — количество столбцов матрицы, $x$ и $y$ — номера строки и столбца искомого элемента.

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

Вывести элемент из строки $x$ и столбца $y$.

Решение

Для решения создаётся матрица в представлении массива размера $n* m$, который заполняется следующим образом: если текущая строка матрицы нечётная, то элемент массива принимает значение номера строки, умноженного на количество $m$ столбцов матрицы плюс номер текущего столбца, а если текущая строка — чётная, то текущему элементу массива присваивается значение, равное произведению увеличенного на единицу номера $n$ строки на количество $m$ столбцов матрицы минус увеличенный на единицу номер текущего столбца. Для вывода значения матрицы по двум координатам мы используем элемент массива с индексом равным сумме координаты $y$ на произведение координаты $x$ на количество столбцов $m$, которое используется для «прыжка» через необходимое количество строк.

Тесты

№	Ввод	Вывод
1	5 2 3 1	4
2	4 5 3 1	10
3	50 48 45 20	2131

Код

#include <iostream>
using namespace std;

int main() {
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    x--, y--;
    int *arr = new int[n * m];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            arr[i * m + j] = (i % 2 == 0 ? i * m + j : (i + 1) * m - (j + 1)); 
        }
    }
    cout << arr[x * m + y];
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m, x, y;

cin >> n >> m >> x >> y;

x--, y--;

int *arr = new int[n * m];

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

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

arr[i * m + j] = (i % 2 == 0 ? i * m + j : (i + 1) * m - (j + 1));

}

cout << arr[x * m + y];

return 0;

}

Ссылки

Related Images:

e-olymp 4749. Выручка театра

25/06/2019 by Никита Семерня

Задача

В театре $n$ рядов по $m$ мест в каждом. Даны две матрицы — в первой записаны стоимости билетов. Вторая сообщает, какие билеты проданы, а какие — нет ($1$ — соответствующий билет продан, $0$ — не продан).
Определите общую выручку от спектакля.

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

Сначала записано число $n$, затем число $m$ $(n, m \le 500)$. После задана матрица стоимостей билетов ($n$ строк по $m$ чисел, каждое из чисел от $0$ до $10000$). Далее задана матрица проданных билетов — снова $n$ строк по $m$ чисел.

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

Выведите общую выручку от продажи билетов.

Тесты

Входные данные	Выходные данные
3 3 1 2 3 4 5 6 7 8 9 1 0 1 0 1 0 1 0 1	25
1 1 1 0	0
1 1 1 1	1

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

#include <iostream>
using namespace std;

int main() {
    int n, m, totalRevenue = 0;
    cin >> n >> m;
    int* tickets = new int[n * m];
    for (int i = 0; i < n * m; i++) {
        cin >> tickets[i];
    }
    for (int i = 0, isSold; i < n * m; i++) {
        cin >> isSold;
        totalRevenue += tickets[i] * isSold;
    }
    cout << totalRevenue;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, m, totalRevenue = 0;

cin >> n >> m;

int* tickets = new int[n * m];

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

cin >> tickets[i];

}

for (int i = 0, isSold; i < n * m; i++) {

cin >> isSold;

totalRevenue += tickets[i] * isSold;

}

cout << totalRevenue;

return 0;

}

Решение

Считаем выручку, суммируя цену каждого билета, умноженную на $1$ либо $0$ в зависимости от того продан он или нет соответственно.

Ссылки

Ideone
e-olymp

Related Images:

e-olymp-8577. Супер платформи

25/06/2019 by Евгений Рудницкий

Условие

У багатьох старих іграх з двовимірною графікою можна зіткнутися з такою ситуацією. Який-небудь герой стрибає по платформам (або острівкам), які висять у повітрі. Він повинен перебратись від одного краю екрану до іншого. При цьому, при стрибку з однієї платформи на сусідню, у героя витрачається $\left|y_2–y_1\right|$енергії, де $y_2$ та $y_1$ – висоти, на яких розміщені ці платформи. Крім того у героя є суперприйом, який дозволяє перестрибнути через платформу, причому на це витрачається $3·|y_2–y_1|$ одиниць енергії. Кількість використань суперприйому обмежена й повинна перебувати в межах від $k_{min}$ до $k_{max}$ разів (обидві межі включно). Звичайно ж, енергію потрібно витрачати максимально економно.

Припустимо, що вам відомі координати усіх платформ у порядку від лівого краю до правого та обмеження на кількість використань суперприйому $k_{min}$ та $k_{max}$. Чи зможете ви знайти, яку мінімальну кількість енергії потрібно герою, щоб дістатись від першої платформи до останньої?

Вхідні дані

У першому рядку записана кількість платформ $n (1 \leq n ≤ 10000)$. Другий рядок містить n натуральних чисел, які не перевищують 30000 – висоти, на яких розміщено платформи. Третій рядок містить два цілі невід’ємні числа $k_{min}$ та $k_{max}$ $\left(0 ≤ k_{min} ≤ k_{max} ≤ \frac{n–1}{2}\right)$.

Вихідні дані

Виведіть єдине число – мінімальну кількість енергії, яку повинен витратити гравець на подолання платформ (звісно ж у припущенні, що cheat-коди використовувати не можна).

Тесты

№	Ввод	Вывод
1	3 1 5 10 0 1	9
2	9 1 3 2 3 8 10 25 17 25 2 4	24

Код

#include <iostream>

using namespace std;
#define ll long long

int main() {
    ll n, i, j, minjumps, maxjumps, me = 1000000000;
    cin >> n;
    ll p[n];
    for (i = 0; i < n; i++) {
        cin >> p[i];
    }
    cin >> minjumps >> maxjumps;
    ll a[2][n + 1];
    a[0][0] = 0;
    for (i = 1; i < n; i++)a[0][i] = a[0][i - 1] + abs(p[i] - p[i - 1]);
    if (minjumps == 0)me = a[0][n - 1];
    for (j = 1; j <= maxjumps; j++) {
        a[j % 2][j * 2] = a[(j - 1) % 2][j * 2 - 2] + 3 * abs(p[j * 2] - p[j * 2 - 2]);
        for (i = j * 2 + 1; i < n; i++) {
            a[j % 2][i] = min(a[j % 2][i - 1] + abs(p[i - 1] - p[i]), a[(j - 1) % 2][i - 2] + 3 * abs(p[i - 2] - p[i]));
        }
        if ((j >= minjumps) and (me > a[j % 2][n - 1])) { me = a[j % 2][n - 1]; }
    }
    cout << me << endl;
    return 0;
}

#include <iostream>

using namespace std;

#define ll long long

int main() {

ll n, i, j, minjumps, maxjumps, me = 1000000000;

cin >> n;

ll p[n];

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

cin >> p[i];

}

cin >> minjumps >> maxjumps;

ll a[2][n + 1];

a[0][0] = 0;

for (i = 1; i < n; i++)a[0][i] = a[0][i - 1] + abs(p[i] - p[i - 1]);

if (minjumps == 0)me = a[0][n - 1];

for (j = 1; j <= maxjumps; j++) {

a[j % 2][j * 2] = a[(j - 1) % 2][j * 2 - 2] + 3 * abs(p[j * 2] - p[j * 2 - 2]);

for (i = j * 2 + 1; i < n; i++) {

a[j % 2][i] = min(a[j % 2][i - 1] + abs(p[i - 1] - p[i]), a[(j - 1) % 2][i - 2] + 3 * abs(p[i - 2] - p[i]));

}

if ((j >= minjumps) and (me > a[j % 2][n - 1])) { me = a[j % 2][n - 1]; }

}

cout << me << endl;

return 0;

}

Решение

В решении суперприёмы из условия для удобства буду называть суперпрыжками.
Решим эту задачу динамически. На каждом шаге будем искать масив, где записано сколько минимально надо потратить энергии что б добраться до каждой платформы, сделав ровно $j$ суперпрыжков. Легко получить рекурсивную зависимость: для того, что бы попасть на $i$ платформу нам надо либо прыгнуть с предыдущей $(a_{j (i-1)}+|p_i-p_{i-1}|)$ либо сделать суперпрыжок с платформы под номером $i-2$ $( a_{(j — 1)(i — 2)} + 3|p_{i — 2} — p_i| )$. Не забудем про то, что не всегда можно прыгнуть с предыдущей так как мы могли бы и не попасть на нее за $j$ суперпрыжков. Таким образом для некоторых платформ( а именно первых в каждом масиве) мы будем делать суперпрыжок с платформы под номером $i-2$. На каждом шаге если нам разрешено сделать столько суперпрыжком сколько мы сделали обновляем общее минимальное количество затраченной энергии если оно больше чем результат, полученный нами на последней платформе. Таким образом на каждом шаге мы будем получать минимальные затраты для определенного количества прыжков. Таким образом минимальное из этих самых ответов и будет тем что требуется в задаче.

Оптимизация

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

Ссылки

Related Images:

e-olymp 972. Сортировка времени

20/06/2019 by Виктор Иванов

Задача

Отсортируйте время согласно заданному критерию.

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

Сначала задано число $n$ $\left(1 \leqslant n \leqslant 100 \right),$ а затем $n$ моментов времени. Каждый момент времени задается $3$ целыми числами — часы (от $0$ до $23$), минуты (от $0$ до $60$), и секунды (от $0$ до $60$).

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

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

Тесты

№	Входные данные	Выходные данные
1	4 10 20 30 7 30 00 23 59 59 13 30 30	7 30 0 10 20 30 13 30 30 23 59 59
2	5 12 40 45 23 56 12 7 45 34 8 23 34 2 56 45	2 56 45 7 45 34 8 23 34 12 40 45 23 56 12
3	3 23 56 45 21 45 54 6 45 23	6 45 23 21 45 54 23 56 45

Код 1

#include <iostream>
using namespace std;
int a[101], b[101], c[101], d[101];
 
int main() {
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i] >> b[i] >> c[i];
        d[i] = a[i] * 3600 + b[i] * 60 + c[i];
    }
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (d[i] > d[j]) {
                swap(a[i], a[j]);
                swap(b[i], b[j]);
                swap(c[i], c[j]);
                swap(d[i], d[j]);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        cout << a[i] << " " << b[i] << " " << c[i] << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int a[101], b[101], c[101], d[101];

int main() {

int n;

cin >> n;

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

cin >> a[i] >> b[i] >> c[i];

d[i] = a[i] * 3600 + b[i] * 60 + c[i];

}

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

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

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

swap(a[i], a[j]);

swap(b[i], b[j]);

swap(c[i], c[j]);

swap(d[i], d[j]);

}

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

cout << a[i] << " " << b[i] << " " << c[i] << endl;

}

return 0;

}

Код 2

#include <iostream>
using namespace std;
 
struct unsortedtime {
    int hours;
    int minutes;
    int seconds;
};
 
bool operator > (const unsortedtime &a, const unsortedtime &b) {
    bool res = false;
    if (a.hours > b.hours) res = true;
    else if (a.hours == b.hours) {
        if (a.minutes > b.minutes) res = true;
        else if (a.minutes == b.minutes) {
            if (a.seconds > b.seconds) res = true;
        }
    }
    return res;
};
 
int main() {
    int n;
    cin >> n;
    unsortedtime *a = new unsortedtime[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i].hours >> a[i].minutes >> a[i].seconds;
    }
    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].hours << " " << a[i].minutes << " " << a[i].seconds << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

struct unsortedtime {

int hours;

int minutes;

int seconds;

};

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

bool res = false;

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

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

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

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

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

}

return res;

};

int main() {

int n;

cin >> n;

unsortedtime *a = new unsortedtime[n];

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

cin >> a[i].hours >> a[i].minutes >> a[i].seconds;

}

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].hours << " " << a[i].minutes << " " << a[i].seconds << endl;

}

return 0;

}

Решение задачи (код 1)

Для решения задачи переведём в секунды каждый момент времени и введём их в массив d[i]. Далее, в этом массиве проверяем какой элемент больше if (d[i] > d[j]) и упорядочиваем эти элементы в порядке возрастания используя swap().

Решение задачи (код 2)

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

Ссылки

Условие задачи на e-olymp
Код программы (1) на ideone
Код программы (2) на ideone

Related Images:

e-olymp 8678. Birches

05/06/2019 by Виктор Иванов

Task

The State National Park $Q$ recently acquired a beautiful birch avenue consisting of $n$ trees. Each tree has a height of $H_i$.

International Classification of national parks is a list of the most beautiful nature reserves in the world. Used to rank parks such a thing as $distinctiveness$ which is understood as the number of pairs ($i$, $j$), for which the observed ratio of $H_i$ $mod$ $H_j$ = $k$, where $k$ is a special number, which is selected by the Expert Council of the international organization of national parks.

What $distinctiveness$ has national park state $Q$?

Input

The first line has two positive integers $n$ and $k$ [latex]\left(1\leqslant n\leqslant 10^5, 0\leqslant k\leqslant 10^6\right)[/latex] — the number of trees in the national park and a special number of the advisory council, respectively.

The second line has $n$ numbers $H_i$ [latex]\left(1\leqslant H_i\leqslant 10^6\right)[/latex] — the height of the trees in the park.

Output

In the single line print $Q$ national park $distinctiveness$.

Tests

№	Input	Output
1	5 1 1 2 3 4 5	8
2	6 2 2 6 7 8 10 14	8
3	15 6 1 4 5 6 9 13 15 16 19 20 2124 27 45 49	14
4	7 3 1 5 7 8 9 23 46	2
5	10 15 23 26 67 79 82 110 118 200 450 900	2

Program code

#include <iostream>
#define SIZE 1000001
using namespace std;

long long n, k, a, cnt[SIZE], i, j, x = 0;
int main() {
    cin >> n >> k;
    for (i = 0; i < n; ++i) {
        cin >> a;
        ++cnt[a];
    }
    for (i = k + 1; i < SIZE; ++i) {
        if (cnt[i] > 0) {
            for (j = k; j < SIZE; j += i) //add each time k + 1
                if (cnt[j] > 0) {
                    if (i == j) {
                        x += cnt[i] * (cnt[i] - 1);
                    }
                    else {
                        x += cnt[j] * cnt[i];
                    }
            }
        }
    }
    cout << x << endl;
}

#include <iostream>

#define SIZE 1000001

using namespace std;

long long n, k, a, cnt[SIZE], i, j, x = 0;

int main() {

cin >> n >> k;

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

cin >> a;

++cnt[a];

}

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

if (cnt[i] > 0) {

for (j = k; j < SIZE; j += i) //add each time k + 1

if (cnt[j] > 0) {

if (i == j) {

x += cnt[i] * (cnt[i] - 1);

}

else {

x += cnt[j] * cnt[i];

}

cout << x << endl;

}

Solution

To solve this problem, we will count the number of identical elements, while entering the array. Next, if $i$ and $j$ were met more than $0$ times and $i$ is not equal $j$, we add the counter x + = cnt [j] * cnt [i], and if $i$ = $j$ — x + = cnt [i] * (cnt [i] - 1).

e-olymp 8688. Количество чисел без 8

05/06/2019 by Андрей Зиновьев

Задача

Напишите программу, которая определяет количество чисел от $1$ до $n$, в записи которых нет цифры $8$.

Входные данные:
В первой строке задано число $n$ $(1 \le n \le 10^{18})$.

Выходные данные:
Выведите одно число — количество чисел от $1$ до $n$, в записи которых нет цифры $8$.

Тесты

Входные данные	Вывод программы
10	9
25833798135522720	4918510377816614
88888888888888	20334926626631

Continue reading →

Related Images:

e-olymp 682. Сумма на отрезке

30/05/2019 by Никита Пушкин

Задача

Задан набор чисел $a_{1}, …, a_{n}$. Для заданных индексов $l$ и $r$ найдите $$S_{l,r}=a_{l}+a_{l+1}+..+a_{r}$$

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

В первой строке записано количество чисел $n$ $\left(1 \leq n \leq 10^{6}\right)$. Во второй строке записаны числа $a_{i}$ $\left(1 \leq a_{i} \leq 1000\right)$, разделенные пробелом. На третьей строке записано число $m$ $\left(1 \leq m \leq 10^{6}\right)$ — количество запросов. Далее на отдельных строках записаны сами запросы $l_{i}$ и $r_{i}$ $\left(1 \leq l_{i} \leq r_{i} \leq n\right)$.

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

Выведите в отдельных строках $m$ чисел $S_{l_i,r_i}$.

Тесты

#	Входные данные	Выходные данные
1	5 1 2 3 4 5 5 1 5 2 3 3 4 2 5 1 4	15 5 7 14 10
2	10 10 10 10 10 10 10 10 10 10 10 5 1 3 3 5 5 7 7 9 3 7	30 30 30 30 50
3	10 57 42 24 73 98 71 65 76 12 33 7 1 2 4 5 8 10 1 10 7 10 2 5 3 8	99 171 121 551 186 237 407
4	3 10 15 20 2 1 2 1 3	25 45
5	7 299 38924 2388 4399 7549 79475 57947 10 1 3 2 3 3 3 4 7 6 7 3 5 5 5 6 6 1 6 1 7	41611 41312 2388 149370 137422 14336 7549 79475 133034 190981

#include <iostream>
 
using namespace std;

int main() {
    std::ios::sync_with_stdio(false);
    int n;
    cin>>n;
    long long a[n];
    for (int i = 0; i < n; i++) {
        cin>>a[i];
    }
    long long summ[n + 1];
    summ[0] = 0;
    for (int i = 1; i < n + 1; i++) {
        summ[i] = summ[i - 1] + a[i - 1];
    }
    int m;
    cin>>m;
    while (m--) {
        int l, r;
        cin>>l>>r;
        printf("%d", summ[r] - summ[l - 1]);
        printf("%s", "\n");
    }
}

#include <iostream>

using namespace std;

int main() {

std::ios::sync_with_stdio(false);

int n;

cin>>n;

long long a[n];

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

cin>>a[i];

}

long long summ[n + 1];

summ[0] = 0;

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

summ[i] = summ[i - 1] + a[i - 1];

}

int m;

cin>>m;

while (m--) {

int l, r;

cin>>l>>r;

printf("%d", summ[r] - summ[l - 1]);

printf("%s", "\n");

}

Решение

Сначала читаем с клавиатуры набор $n$ чисел и добавляем их в массив $a\left[n\right]$. Далее создаем массив $summ$ из $n+1$ элементов, $i$-ый элемент которого равен сумме всех элементов $a$ до $i-1$ включительно. Затем $m$ раз считываем $l$ и $r$ с клавиатуры, и отнимаем от $summ\left[r\right]$ «хвост» в виде суммы элементов до $l-1$ элемента.

Условие задачи можно найти на e-olymp
Код решения — ideone

Related Images:

e-olymp 4749. Выручка театра

30/05/2019 by Иван Дуков

Задача

В театре [latex]n[/latex] рядов по [latex]m[/latex] мест в каждом. Даны две матрицы — в первой записаны стоимости билетов. Вторая сообщает, какие билеты проданы, а какие — нет ([latex]1[/latex] — соответствующий билет продан, [latex]0[/latex] — не продан).
Определите общую выручку от спектакля.

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

Сначала записано число [latex]n[/latex], затем число [latex]m[/latex] ([latex]n[/latex], [latex]m \leqslant 500[/latex]). После задана матрица стоимостей билетов ([latex]n[/latex] строк по [latex]m[/latex] чисел, каждое из чисел от [latex]0[/latex] до [latex]10000[/latex]). Далее задана матрица проданных билетов — снова [latex]n[/latex] строк по [latex]m[/latex] чисел.

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

Выведите общую выручку от продажи билетов.

Тесты

№	Входные данные	Выходные данные
1	3 3	25
	1 2 3
	4 5 6
	7 8 9

	1 0 1
	0 1 0
	1 0 1
2	2 2	0
	1 1
	2 2

	0 0
	0 0
3	4 5	380
	15 16 17 18 19
	19 18 17 16 15
	19 20 21 22 23
	23 22 21 20 19

	1 1 1 1 1
	1 1 1 1 1
	1 1 1 1 1
	1 1 1 1 1

Код программы с использованием одномерных массивов

#include <iostream>
using namespace std;
 
int main() {
    int x [500*500];
    int n, m;
    cin >> n >> m;
    int nm= n*m;
    for(int i = 1; i <= nm; i++){
        cin >> x[i];
    }
    int k;
    long long int v = 0;
    for(int i = 1; i <= nm; i++){
        cin >> k;
        v+= k*x[i];
    }
    cout << v << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int x [500*500];

int n, m;

cin >> n >> m;

int nm= n*m;

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

cin >> x[i];

}

int k;

long long int v = 0;

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

cin >> k;

v+= k*x[i];

}

cout << v << endl;

return 0;

}

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

Описываем целочисленный одномерный массив x [500*500] для хранения матрицы стоимостей билетов. Описываем целочисленные переменные [latex]n[/latex] и [latex]m[/latex] (количество строк и столбцов матрицы) и считываем их. Описываем целочисленную переменную [latex]nm[/latex] (количество мест в зале) и инициализируем ее произведением [latex]n \cdot m[/latex]. Цикл инициализирует [latex]nm[/latex] элементов массива [latex]x[/latex]. Описываем целочисленную переменную [latex]k[/latex], которая принимает значения [latex]0[/latex] или [latex]1[/latex] (билет не продан или продан), и целочисленную переменную [latex]v[/latex] — стоимость проданных билетов ([latex]v[/latex] имеет тип long long int, так как максимальное значение, которое она может принять, составляет [latex]500 \cdot 500 \cdot 10000=2500000000[/latex]). Цикл считывает значения [latex]k[/latex] и увеличивает [latex]v[/latex] на k*x[i].

Код программы с использованием многомерных массивов

#include <iostream>
using namespace std;
 
int x[500][500];
int main(){
    int n, m, p;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> x[i][j];
    unsigned long long v = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> p;
            if (p) v += x[i][j];
        }
    }
    cout << v;
}

#include <iostream>

using namespace std;

int x[500][500];

int main(){

int n, m, p;

cin >> n >> m;

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

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

cin >> x[i][j];

unsigned long long v = 0;

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

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

cin >> p;

if (p) v += x[i][j];

}

cout << v;

}

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

По условию заданы количество строк [latex]n[/latex] и количество столбцов [latex]m[/latex] матрицы стоимости театральных билетов ( [latex] n,m\leqslant 500[/latex], каждое из чисел от [latex]0[/latex] до [latex]10000[/latex] ). Описываем целочисленную матрицу x[500][500]. Объявляем целочисленные переменные [latex]n[/latex] и [latex]m[/latex] и вводим их значения с клавиатуры. Считываем матрицу x. Объявляем переменную unsigned long long v = 0 — стоимость проданных билетов. Целочисленная переменная [latex]p = 1[/latex], если билет на ( [latex]i,j[/latex] )-е место продан, и [latex]p = 0[/latex] — в противном случае. Во вложенных циклах считываем значение [latex]p[/latex] из матрицы проданных билетов. Проверяем [latex]p[/latex] на положительность и увеличиваем [latex]v[/latex] на стоимость билета на ( [latex]i,j[/latex] )-е место.

Ссылки

e-olymp
ideone (код с одномерными массивами)
ideone (код с многомерными массивами)

Related Images:

e-olymp 2524. Строки Фибоначчи

26/05/2019 by Дария Даниленко

Задача

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

Одним из примеров строк, задаваемых рекуррентным соотношением являются строки Фибоначчи $F_{0} = a$, $F_{1} = b$, … . Они задаются следующим образом: $F_{0} = a$, $F_{1} = b$, $F_{i} = F_{i-2}F_{i-1}$, $i >1$. Первые семь строк Фибоначчи выглядят следующим образом: $a$, $b$, $ab$, $bab$, $abbab$, $bababbab$, $abbabbababbab$.

Дима занимается в кружке олимпиадного программирования и интересуется алгоритмами на строках. Недавно он узнал о строках Фибоначчи. Он быстро понял, что их длина с увеличением номера $n$ растет очень быстро, поэтому задача нахождения всех символов строки $F_{n}$ требует слишком большого объема памяти. Поэтому он решил ограничиться задачей нахождения некоторых символов.

Напишите программу, которая находит $k$-ый символ строки $F_{n}$.

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

Первая строка содержит количество тестов $t$ ($1 ≤ t ≤ 100$). Каждая из следующих $t$ строк содержит два целых числа $n$ и $k$ ($0 ≤ n ≤ 45$, $1 ≤ k ≤ |F_{n}|$, через $|F_{n}|$ обозначена длина строки $F_{n}$, позиции символов в строке нумеруются с единицы).

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

Выведите $t$ строк, каждая из которых содержит $k$-ый символ строки $F_{n}$.

Тесты

Входные данные	Выходные данные
4 0 1 1 1 3 2 7 7	a b a a
1 10 15	a
6 45 6 38 30 6 5 24 40 0 1 2 2	b a b b a b

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

#include <iostream>
using namespace std;

int fib[45];

char solve(int n, int k) {
    if (n == 0) return 'a';
    if (n == 1) return 'b';
    if (k <= fib[n - 2]) return solve(n - 2, k);
    return solve(n - 1, k - fib[n - 2]);
}

int main() {
    int n, k, tests;
    fib[0] = 1;
    fib[1] = 1;
    for (int i = 2; i < 45; i++) fib[i] = fib[i - 1] + fib[i - 2];
    cin >> tests;
    while (tests--) {
        cin >> n >> k;
        cout << solve(n, k) << endl;
    }
    return 0;
}

#include <iostream>

using namespace std;

int fib[45];

char solve(int n, int k) {

if (n == 0) return 'a';

if (n == 1) return 'b';

if (k <= fib[n - 2]) return solve(n - 2, k);

return solve(n - 1, k - fib[n - 2]);

}

int main() {

int n, k, tests;

fib[0] = 1;

fib[1] = 1;

for (int i = 2; i < 45; i++) fib[i] = fib[i - 1] + fib[i - 2];

cin >> tests;

while (tests--) {

cin >> n >> k;

cout << solve(n, k) << endl;

}

return 0;

}

Решение

Воспользуемся тем, что длина $i$-той строки Фибоначчи будет равна $i$-тому числу Фибоначчи, так как для них справедливо одно и то же рекуррентное соотношение. Заводим массив fib[45]; , куда мы вычислим первые ($n ≤ 45$) числа Фибоначчи. Функция solve(int n, int k) находит $k$-ый символ строки $F_{n}$: так как $F_{i} = F_{i-2}F_{i-1}$, то если $k ≤ |F_{n-2}|$, то $k$-ый символ строки следует искать в $F_{n-2}$, в другом случае следует искать $(k — F_{n-2})$-ый символ в $F_{n-1}$. Таким образом, постепенно углубляясь в рекурсию, программа будет иметь дело с задачами все меньших размеров, пока наконец не выйдет на одну из единичных строк ( n == 0 или n == 1 ), и не выведет $a$ или $b$ соответственно.