Category Archives: 9. Последовательные контейнеры

Рассматриваются следующие последовательные контейнеры:

vector
Особый случай vector <bool>
array
forward_list
list

Задачи на использование контейнеров начинаются с класса vector. Данный класс позволяет реализовать массив с динамически изменяющимся размером. Познакомившись с материалом учебника, для тренировки постарайтесь решить задачу Банкомат.

Если в качестве домашнего задания на эту тему Вам достались задачи из задачника А.Абрамова А271-А316, то условие задачи следует модифицировать так, чтобы количество вводимых данных было произвольным. Т.е. данные должны читаться до исчерпания потока ввода. Например, вместо 15 элементов в задаче А271 следует читать все данные стандартного потока ввода.

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

e-olymp 7213. Шашка на кубе

12/12/2020 by Максим Ливитчук

Условие

Поверхность куба отрезками, параллельными рёбрам куба, разделена на квадратные клетки, длина сторон которых в $l$ (нечетное натуральное число) раз меньше длины ребра куба. Шашку передвигают за один ход из клетки на произвольную смежную с ней клетку (что имеет с данной общую сторону).

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

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

Содержит натуральные числа $l$ и $m$ ($l < 52$, $m < 200$).

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

Вывести искомое количество способов.

Тесты

l	m	вывод
3	3	1
3	4	0
3	5	25
51	199	4009263689513240276071196173369495212494629453793821392879244551766927964742684514532573281589075237363501397360
3	199	11954860546705755218324706261555627152268568460810054501274297031890136116190373877274924800908756150285132065690107399

Код

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

#define cr(a, b, x, y) case a: return CellCoord{b, x, y}
#define SIDENUM 3 //количество сторон куба которые хранятся
#define MAX_L 51 //максимальное значение L

#define BASE 1000000000 //10^9, основание системы счисления для длинной арифметики 
#define DNUM 9 //количество цифр 10-ичной системы счисления в 1 "цифре" длинной арифметики

struct LongNum {
    //реализация длинной арифметики на векторах со сложением и выводом
    vector<int> v;
    LongNum() {} //стандартный конструктор
    LongNum(int s) { //конструктор из int
        v.push_back(s);
    }
    void print() { //вывод числа
        cout <<(v.empty() ? 0 : v.back());
        for (int i = (int)v.size() - 2; i>=0; i--)
            cout <<setfill('0') <<setw(DNUM) <<v[i];
    }
    void add(LongNum term) { //прибавление длинного числа
        auto b = term.v;
        int carry = 0;
        for (size_t i = 0; i < max(v.size(), b.size()) || carry; i++) {
            if (i == v.size())
                v.push_back(0);
            v[i] += carry + (i < b.size() ? b[i] : 0);
            carry = v[i] >= BASE;
            if (carry)  v[i] -= BASE;
        }
    }
};

struct CellCoord {
    //хранит данные о положении клетки
    short side;
    short x, y;
};

struct CellNeighbors {
    //хранит данные о положении всех(4) соседей определённой клетки
    CellCoord n[4];
};

CellCoord FixNeighbor(short l, short side, short x, short y) {
    //исправляет данные о положении клетки, если она выходит за края грани
    if(x == -1) { //если сосед находится левее грани
        switch(side) {
        //если координаты выходят за левую границу 0-ой грани - меняет грань на 1-ую,
        //обнуляя y, а в x записывает старый y 
        cr(0, 1, y,     0); //и так далее
        cr(1, 1, l-1,   y);
        cr(2, 1, l-y-1, l-1);
        }
    } else if(x == l) {//правее
        switch(side) {
        cr(0, 1, l-y-1, 0);
        cr(1, 1, 0,     y);
        cr(2, 1, y,     l-1);
        }
    } else if(y == -1) {//выше
        switch(side) {
        cr(0, 1, l-x-1, 0);
        cr(1, 0, x,     l-1);
        cr(2, 1, x,     l-1);
        }
    } else if(y == l) {//ниже
        switch(side) {
        cr(0, 1, x,     0);
        cr(1, 2, x,     0);
        cr(2, 1, l-x-1, l-1);
        }
    } else {
        // если координаты не вышли за границы грани просто возвращаем неизменёные координаты
        return CellCoord{side, x, y};
    }
}

CellNeighbors GetNeighbors(short l, short side, short x, short y) {
    //возвращает исправленные координаты всех(4) соседних клеток
    return CellNeighbors{{
        FixNeighbor(l, side, x-1, y),
        FixNeighbor(l, side, x+1, y),
        FixNeighbor(l, side, x, y-1),
        FixNeighbor(l, side, x, y+1)
    }};
}

int main() {
    short l, m;
    bool flag = false;
    cin >>l >>m;
    LongNum cubes[2][SIDENUM][MAX_L][MAX_L];

    cubes[0][0][l/2][l/2] = LongNum(1);
    //за 0 ходов можно дойти 1 путём в изначальную точку

    CellNeighbors nbs[SIDENUM][MAX_L][MAX_L];
    //массив координат соседей

    for(short side=0; side<SIDENUM; side++) {
        for(short xi=0; xi<l; xi++) {
            for(short yi=0; yi<l; yi++) { //перебор координат всех клеток
                nbs[side][xi][yi] = GetNeighbors(l, side, xi, yi);
                //кэш координат соседних клеток
            }
        }
    }

    for(short i=0; i<m; i++) {
        for(short side=0; side<SIDENUM; side++) {
            for(short xi=0; xi<l; xi++) {
                for(short yi=0; yi<l; yi++) { //перебор всех клеток
                    LongNum neighbor_sum;
                    for(auto e: nbs[side][xi][yi].n) { //перебор всех соседей
                        neighbor_sum.add(cubes[flag][e.side][e.x][e.y]);
                        //сложение количества путей ко всем соседям на предыдущем шаге
                    }
                    cubes[!flag][side][xi][yi] = neighbor_sum;
                    //запись получившейся суммы в клетку
                }
            }
        }
        flag = !flag; //замена местами массива для предыдущего шага и нынешнего
    }
    cubes[flag][1][l/2][l/2].print();
    //вывод количества путей к центру соседней грани на m-ом шаге
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

#include <iostream>

#include <iomanip>

#include <vector>

using namespace std;

#define cr(a, b, x, y) case a: return CellCoord{b, x, y}

#define SIDENUM 3 //количество сторон куба которые хранятся

#define MAX_L 51 //максимальное значение L

#define BASE 1000000000 //10^9, основание системы счисления для длинной арифметики

#define DNUM 9 //количество цифр 10-ичной системы счисления в 1 "цифре" длинной арифметики

struct LongNum {

//реализация длинной арифметики на векторах со сложением и выводом

vector<int> v;

LongNum() {} //стандартный конструктор

LongNum(int s) { //конструктор из int

v.push_back(s);

}

void print() { //вывод числа

cout <<(v.empty() ? 0 : v.back());

for (int i = (int)v.size() - 2; i>=0; i--)

cout <<setfill('0') <<setw(DNUM) <<v[i];

}

void add(LongNum term) { //прибавление длинного числа

auto b = term.v;

int carry = 0;

for (size_t i = 0; i < max(v.size(), b.size()) || carry; i++) {

if (i == v.size())

v.push_back(0);

v[i] += carry + (i < b.size() ? b[i] : 0);

carry = v[i] >= BASE;

if (carry) v[i] -= BASE;

}

};

struct CellCoord {

//хранит данные о положении клетки

short side;

short x, y;

};

struct CellNeighbors {

//хранит данные о положении всех(4) соседей определённой клетки

CellCoord n[4];

};

CellCoord FixNeighbor(short l, short side, short x, short y) {

//исправляет данные о положении клетки, если она выходит за края грани

if(x == -1) { //если сосед находится левее грани

switch(side) {

//если координаты выходят за левую границу 0-ой грани - меняет грань на 1-ую,

//обнуляя y, а в x записывает старый y

cr(0, 1, y, 0); //и так далее

cr(1, 1, l-1, y);

cr(2, 1, l-y-1, l-1);

}

} else if(x == l) {//правее

switch(side) {

cr(0, 1, l-y-1, 0);

cr(1, 1, 0, y);

cr(2, 1, y, l-1);

}

} else if(y == -1) {//выше

switch(side) {

cr(0, 1, l-x-1, 0);

cr(1, 0, x, l-1);

cr(2, 1, x, l-1);

}

} else if(y == l) {//ниже

switch(side) {

cr(0, 1, x, 0);

cr(1, 2, x, 0);

cr(2, 1, l-x-1, l-1);

}

} else {

// если координаты не вышли за границы грани просто возвращаем неизменёные координаты

return CellCoord{side, x, y};

}

CellNeighbors GetNeighbors(short l, short side, short x, short y) {

//возвращает исправленные координаты всех(4) соседних клеток

return CellNeighbors{{

FixNeighbor(l, side, x-1, y),

FixNeighbor(l, side, x+1, y),

FixNeighbor(l, side, x, y-1),

FixNeighbor(l, side, x, y+1)

}};

}

int main() {

short l, m;

bool flag = false;

cin >>l >>m;

LongNum cubes[2][SIDENUM][MAX_L][MAX_L];

cubes[0][0][l/2][l/2] = LongNum(1);

//за 0 ходов можно дойти 1 путём в изначальную точку

CellNeighbors nbs[SIDENUM][MAX_L][MAX_L];

//массив координат соседей

for(short side=0; side<SIDENUM; side++) {

for(short xi=0; xi<l; xi++) {

for(short yi=0; yi<l; yi++) { //перебор координат всех клеток

nbs[side][xi][yi] = GetNeighbors(l, side, xi, yi);

//кэш координат соседних клеток

}

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

for(short side=0; side<SIDENUM; side++) {

for(short xi=0; xi<l; xi++) {

for(short yi=0; yi<l; yi++) { //перебор всех клеток

LongNum neighbor_sum;

for(auto e: nbs[side][xi][yi].n) { //перебор всех соседей

neighbor_sum.add(cubes[flag][e.side][e.x][e.y]);

//сложение количества путей ко всем соседям на предыдущем шаге

}

cubes[!flag][side][xi][yi] = neighbor_sum;

//запись получившейся суммы в клетку

}

flag = !flag; //замена местами массива для предыдущего шага и нынешнего

}

cubes[flag][1][l/2][l/2].print();

//вывод количества путей к центру соседней грани на m-ом шаге

}

Решение

Из условия можно понять, что задача про специфического вида граф, по которому движется шашка. Его вершинами являются клетки на гранях куба, а дуги лежат между клетками с общими границами. Очевидно количество путей за $m$ шагов до любой точки в графе будет равняться сумме количества путей за $m-1$ шагов ко всем соседним вершинам, то есть мы можем получать решение задачи для $m$ шагов из решения меньшей задачи для $m-1$ шагов, из чего можно понять что это задача на динамическое программирование.
Для решения создадим массив со всеми вершинами и будем хранить в нём количество путей к каждой из них на i-ом шаге. Удобнее всего задать такой массив как 6 числовых матриц размером $ l \times l$, по одной на каждую грань куба.

Раскладка шести граней куба с переходами между границами

Соседство будем определять, прибавляя или отнимая единицу от одной из координат клетки в матрице, например $(x-1, y)$ всегда будет соседом $(x, y)$, не считая крайних случаев, когда $x-1$ будет меньше нуля. Такие ситуации в коде обрабатывает функция FixNeighbor(...), в которой прописаны все подобные крайние случаи.

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

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

Оптимизированный вариант хранения куба

Так как для получения значения клетки через $i$ шагов нужны значения всех её соседей через $i-1$ шагов, а для получения значения соседей через $i$ шагов нужно значение клетки через $i-1$ шагов, нам не хватит только одного массива для перезаписи, надо использовать минимум два для хранения предыдущего и нынешнего состояния. В программе это реализовано с помощью булевой переменной flag — сначала мы вычисляем следующее состояние на основании 0-ого массива ( flag), записывая результат 1-ый ( !flag), а потом инвертируем значение переменной на противоположное и массивы в алгоритме меняются местами.

Ссылки

Related Images:

e-olymp 1327. Ладьи на шахматной доске

14/12/2019 by Эвелина Алексютенко

Задача

Ещё в детстве маленького Гарика заинтересовал вопрос: а сколькими способами на шахматной доске размером [latex]n \times n[/latex] можно расставить [latex] n [/latex] ладей так, чтобы они не били друг друга. Он очень долго решал эту задачку для каждого варианта, а когда решил — бросил шахматы.

А как быстро Вы управитесь с этой задачкой?

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

Размер шахматной доски — натуральное число, не превышающее [latex] 1000 [/latex].

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

Выведите ответ, найденный Гариком.

Тесты

Входные данные	Выходные данные
2	2
10	3628800
500	122013682599111006870123878542304692625357434280319284219241 358838584537315388199760549644750220328186301361647714820358 416337872207817720048078520515932928547790757193933060377296 085908627042917454788242491272634430567017327076946106280231 045264421887878946575477714986349436778103764427403382736539 747138647787849543848959553753799042324106127132698432774571 554630997720278101456108118837370953101635632443298702956389 662891165897476957208792692887128178007026517450776841071962 439039432253642260523494585012991857150124870696156814162535 905669342381300885624924689156412677565448188650659384795177 536089400574523894033579847636394490531306232374906644504882 466507594673586207463792518420045936969298102226397195259719 094521782333175693458150855233282076282002340262690789834245 171200620771464097945611612762914595123722991334016955236385 094288559201872743379517301458635757082835578015873543276888 868012039988238470215146760544540766353598417443048012893831 389688163948746965881750450692636533817505547812864000000000 000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000
999	402387260077093773543702433923003985719374864210714632543799 910429938512398629020592044208486969404800479988610197196058 631666872994808558901323829669944590997424504087073759918823 627727188732519779505950995276120874975462497043601418278094 646496291056393887437886487337119181045825783647849977012476 632889835955735432513185323958463075557409114262417474349347 553428646576611667797396668820291207379143853719588249808126 867838374559731746136085379534524221586593201928090878297308 431392844403281231558611036976801357304216168747609675871348 312025478589320767169132448426236131412508780208000261683151 027341827977704784635868170164365024153691398281264810213092 761244896359928705114964975419909342221566832572080821333186 116811553615836546984046708975602900950537616475847728421889 679646244945160765353408198901385442487984959953319101723355 556602139450399736280750137837615307127761926849034352625200 015888535147331611702103968175921510907788019393178114194545 257223865541461062892187960223838971476088506276862967146674 697562911234082439208160153780889893964518263243671616762179 168909779911903754031274622289988005195444414282012187361745 992642956581746628302955570299024324153181617210465832036786 906117260158783520751516284225540265170483304226143974286933 061690897968482590125458327168226458066526769958652682272807 075781391858178889652208164348344825993266043367660176999612 831860788386150279465955131156552036093988180612138558600301 435694527224206344631797460594682573103790084024432438465657 245014402821885252470935190620929023136493273497565513958720 559654228749774011413346962715422845862377387538230483865688 976461927383814900140767310446640259899490222221765904339901 886018566526485061799702356193897017860040811889729918311021 171229845901641921068884387121855646124960798722908519296819 372388642614839657382291123125024186649353143970137428531926 649875337218940694281434118520158014123344828015051399694290 153483077644569099073152433278288269864602789864321139083506 217095002597389863554277196742822248757586765752344220207573 630569498825087968928162753848863396909959826280956121450994 871701244516461260379029309120889086942028510640182154399457 156805941872748998094254742173582401063677404595741785160829 230135358081840096996372524230560855903700624271243416909004 153690105933983835777939410970027753472000000000000000000000 000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000

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

#include <iostream>
#include <vector>
#include <iomanip>
using namespace std;
vector<int> multiply (const vector<int> &s, int b, int base) {
  vector<int> c;
  int carry = 0;
  for (int i = 0; i < s.size(); i++) {
    long long res = (long long)s[i] * b + carry;
    carry = res / 1000;
    c.push_back(res % base);    
  }
  if (carry > 0) { // если в разряде переноса все еще остались цифры
    c.push_back(carry);
  }
  return c;
}
int main() {
  int n;
  int base = 1000;
  cin >> n;
  vector<int> res;
  res.push_back(0);
  res.push_back(1);
  for (int i = 1; i < n; i++) {
    res = multiply(res, i + 1, base);
  }
  cout << res[res.size() - 1];
  for (int i = res.size() - 2; i >= 1; i--) {
    cout << setw(3) << setfill('0') << res[i];
  }
}

#include <iostream>

#include <vector>

#include <iomanip>

using namespace std;

vector<int> multiply (const vector<int> &s, int b, int base) {

vector<int> c;

int carry = 0;

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

long long res = (long long)s[i] * b + carry;

carry = res / 1000;

c.push_back(res % base);

}

if (carry > 0) { // если в разряде переноса все еще остались цифры

c.push_back(carry);

}

return c;

}

int main() {

int n;

int base = 1000;

cin >> n;

vector<int> res;

res.push_back(0);

res.push_back(1);

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

res = multiply(res, i + 1, base);

}

cout << res[res.size() - 1];

for (int i = res.size() - 2; i >= 1; i--) {

cout << setw(3) << setfill('0') << res[i];

}

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

string multiplication (string x, int y) { 
    int carry = 0, temporary = 0;
    string answer = "";
    for (int i = x.size() - 1; i >= 0; i--) {
    temporary = int(x[i] - '0') * y + carry;
    carry = temporary / 10;
    answer = char(temporary % 10 + '0') + answer;
}
while (carry) {
    answer = char(carry % 10 + '0') + answer;
    carry /= 10;
}
return answer;
}
int main() {
    int n;
    string s = "1";
    cin >> n;
    for (int i = 2; i <= n; i++) {
         s = multiplication(s, i);
    } 
    cout << s << endl;
}

#include <iostream>

#include <string>

using namespace std;

string multiplication (string x, int y) {

int carry = 0, temporary = 0;

string answer = "";

for (int i = x.size() - 1; i >= 0; i--) {

temporary = int(x[i] - '0') * y + carry;

carry = temporary / 10;

answer = char(temporary % 10 + '0') + answer;

}

while (carry) {

answer = char(carry % 10 + '0') + answer;

carry /= 10;

}

return answer;

}

int main() {

int n;

string s = "1";

cin >> n;

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

s = multiplication(s, i);

}

cout << s << endl;

}

Алгоритм решения

Алгоритм решения данной задачи заключается в том, что нужно вычислить [latex]n! = 1\times 2\times 3\times \cdots\times n [/latex] , используя длинную арифметику ( умножение длинного числа на короткое ).
Иллюстрация для восьми ладей:

В коде № 1 разбиваем вектор на ячейки по три цифры. Но, некоторые ячейки могут иметь менее чем три цифры. С учетом того, что перенос может состоять не из трех цифр, следует выводить результат так: cout << setw(3) << setfill('0') << res[i];.
В коде № 2 разбиваем строку посимвольно.

Детали реализации

Безусловно, для использования векторов и строк нам понадобятся соответствующие библиотеки: #include <vector> и #include <string>.
Для вывода данных в коде № 1 стоит подключить библиотеку #include <iomanip>.

Ссылки :
Задача на e-olymp
Код № 1 на ideone
Код № 2 на ideone
Засчитанное решение № 1
Засчитанное решение № 2

Related Images:

e-olymp 1442. Одномерная Кликомания

26/06/2019 by Наталья Федина

Задача

«Одномерная Кликомания» — это логическая компьютерная игра. Для нее используется полоска размеров $1 \times N$, разбитая на $N$ квадратов $1 \times 1.$ Каждый из квадратов окрашен в красный или желтый цвет.
За один ход игрок может выбрать любой из квадратов и щелкнуть по нему мышкой. В результате компьютер выделяет на полоске группу максимальной длины, состоящую из стоящих подряд квадратов одинакового цвета и содержащую выделенный квадрат, и удаляет все квадраты из этой группы. При этом все квадраты, находящиеся правее удаленной группы (если они существуют), сдвигаются влево так, чтобы пристыковаться к квадратам, находящимся левее удаленной группы (если они существуют) и сохранить целостность полоски:

Игрок может удалять группы квадратов любой длины, в том числе, состоящие из одного квадрата. Игра продолжается до тех пор, пока все квадраты не удалены.
В начале игры количество баллов у игрока равно нулю. После каждого его хода количество баллов пересчитывается. Если игрок очередным ходом удалил группу из $L$ квадратов, то вычисляется число $X = A \cdot L + B$, где $A$ и $B$ — некоторые целочисленные константы. Если число $X$ неотрицательное, то количество баллов игрока увеличивается на $X$, иначе оно уменьшается на $-X$.
Цель игрока — набрать по окочанию игры как можно больше баллов. Напишите программу, оптимально играющую в «Одномерную Кликоманию». Программа должна получать на входе цвета всех квадратов исходной полоски, а также целые числа $A$ и $B$, и возвращать максимальное количество баллов, которое может набрать игрок по окончанию игры.

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

В первой строке задана строка, состоящая из символов $’R’/’Y’$, перечисляющих слева направо цвета всех квадратов исходной полоски. Символ $’R’$ соответствует квадрату красного цвета, а символ $’Y’$ — квадрату желтого цвета.
Во второй и третьей строках соответственно целые числа $A(1 \leq A \leq 1000)$ и $B(-100 \leq B \leq 100)$, задающие константы в формуле начисления очков за каждый сделанный ход.

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

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

Тесты

	Входные данные	Выходные данные
1	YYYYYYY 73 14	525
2	RYRYRYR 100 -100	300
3	YYYRRR 1 -100	-194
4	YRYYRRRYYYYY 12 34	314

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

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
int main() {
 int a, b, count = 1;
 vector <int> vec;
 string str;
 getline(cin, str);
 int n = str.length();
 for (int i = 1; i < n; i++) if (str[i - 1] != str[i]) {
        vec.push_back(count);
        count = 1;
    } else count++;
 vec.push_back(count);
 cin >> a >> b;
 int sum = 0;
 for (int e : vec) sum += e;
 int len = vec.size();
 cout << a * sum + ((b < 0) ? (len / 2 + 1) : len) * b;
 return 0;
}

#include <iostream>

#include <string>

#include <vector>

using namespace std;

int main() {

int a, b, count = 1;

vector <int> vec;

string str;

getline(cin, str);

int n = str.length();

for (int i = 1; i < n; i++) if (str[i - 1] != str[i]) {

vec.push_back(count);

count = 1;

} else count++;

vec.push_back(count);

cin >> a >> b;

int sum = 0;

for (int e : vec) sum += e;

int len = vec.size();

cout << a * sum + ((b < 0) ? (len / 2 + 1) : len) * b;

return 0;

}

Решение

По условию задачи необходимо определить максимальное количество очков которое можно получить в игре. Число $a$ всегда положительное и умножается на количество квадратов удалённых за один ход. В конце игры будут удалены все квадраты, а значит этот вклад в общий счёт игры равен $a \cdot n$, где $n$ — количество квадратиков в игре. Число $b$ может быть как положительным так и отрицательным. В первом случае, нам выгодно, что бы игрок совершил максимальное число ходов, то есть ровно столько, сколько содержится последовательностей из квадратиков одного цвета. Если $b$ меньше нуля, то счёт будет наибольший, если игрок сделает наименьшее количество ходов, а именно избавиться от чередования цветов и за один ход удалит все квадраты, это количество последовательностей пополам, плюс один.
Считаем необходимые данные и выводим ответ в зависимости от положительности $b$.

Ссылки

Related Images:

e-olymp 555. Ближайшие точки

30/03/2019 by Кирилл Веремйов

Задача

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

Готовясь к контрольной работе, Антон столкнулся со следующей задачей: На числовой прямой задано $n$ точек. Необходимо найти среди них две ближайшие. Расстояние между двумя точками числовой прямой $x$ и $y$ равно $|x-y|$.

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

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

Первая строка содержит количество точек $n$ $\left(2\leq n \leq 10^{5}\right)$. Вторая строка содержит $n$ различных целых чисел $x_{i}$- координаты заданных точек числовой прямой. Числа в строке разделены пробелом. Значение любой координаты $x_{i}$ не превосходит $10^{9}$
по абсолютной величине.

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

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

Тесты

Входные данные	Выходные данные
5 10 3 6 2 5	1 2 4
6 10 3 6 1 5 11	1 3 5
9 14545690 4343 -6 10 500 1100 -1 2 10	0 4 9
2 1 5	4 2 1
2 -1000000000 1000000000	2000000000 2 1
9 1 5 9 15 3 100 -1 4 10	1 8 5
10 0 1 5 10 20 100 120 250 -100 55	1 2 1

Решение

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

int main() {
    long long n;
    cin >> n;
    map<long long, long long> Ox;
    long long dis = 0,A = 0,B = 0;//dis- distance
    bool zero_dis = 0;
    for(long long i = 1;i <= n && !zero_dis;i++){
        long long tmp;
        cin >> tmp;
        if(Ox[tmp] != 0){
            zero_dis = true;
            A = Ox[tmp];
            B = i;
            dis = 0;
        }
        else Ox[tmp] = i;
    }
    
    if(!zero_dis){
        dis = -1;
        for(auto i = Ox.begin(),j = ++Ox.begin(); j != Ox.end(); i++, j++){
            long long tmp_dis = j->first - i->first;
            if(dis>tmp_dis || dis<0){
                dis = tmp_dis;
                A = j->second;
                B = i->second;
            }
        }
    }
    cout << dis << "\n" << A << " " << B;
    return 0;
}

#include <iostream>

#include <map>

using namespace std;

int main() {

long long n;

cin >> n;

map<long long, long long> Ox;

long long dis = 0,A = 0,B = 0;//dis- distance

bool zero_dis = 0;

for(long long i = 1;i <= n && !zero_dis;i++){

long long tmp;

cin >> tmp;

if(Ox[tmp] != 0){

zero_dis = true;

A = Ox[tmp];

B = i;

dis = 0;

}

else Ox[tmp] = i;

}

if(!zero_dis){

dis = -1;

for(auto i = Ox.begin(),j = ++Ox.begin(); j != Ox.end(); i++, j++){

long long tmp_dis = j->first - i->first;

if(dis>tmp_dis || dis<0){

dis = tmp_dis;

A = j->second;

B = i->second;

}

cout << dis << "\n" << A << " " << B;

return 0;

}

Объяснение

В начале создаётся ассоциативный контейнер, где каждой точке на прямой ставится в соответствие её номер. Попутно выполняется проверка, не было ли до этого точки с такой же координатой (тогда расстояние между ними равно $0$, соответственно). Затем, поскольку map автоматически выполняет сортировку, сравниваем разность координат рядом стоящих элементов с текущим минимальным расстоянием, и, при необходимости, обновляем значение расстояния и индексы точек, для которых это расстояние верно.

Замечание

Видимо, тесты e-olymp не требуют проверки на случай, если точки совпадают. Тем не менее, я решил оставить это в коде, поскольку в условии не оговорено недопустимости этой ситуации

e-olymp

ideone

Related Images:

e-olymp 1228. Добавить все

26/06/2018 by Александра Рябова

Условие

Условие задачи отражает Вашу задачу: необходимо просто сложить числа. Но это будет унизительно если Вас попросят просто написать такую программу на языке C/C++ для заданного множества чисел. Давайте внесем в задачу оттенок изобретательности.

Введем понятие стоимости для операции сложения. Стоимость сложения двух чисел положим равным их сумме. Например, сложить числа $1$ и $10$ стоит $11$. Стоимость сложения $1,$ $2$ равна $3$. Складывать числа можно разными способами:

$1 + 2 = 3 \left(стоимость = 3\right), 3 + 3 = 6 \left(стоимость = 6\right), Всего = 9 $
$1 + 3 = 4 \left(стоимость = 4\right), 2 + 4 = 6 \left(стоимость = 6\right), Всего = 10 $
$2 + 3 = 5 \left(стоимость = 5\right), 1 + 5 = 6 \left(стоимость = 6\right), Всего = 11 $

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

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

Начинаются целым числом $n (2 \leqslant n \leqslant 100000)$, за которым следуют $n$ целых неотрицательных чисел (все числа меньше $100000$).

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

Вывести наименьшую стоимость сложения всех чисел.

Тесты

Ввод	Вывод
$4$ $10$ $12$ $13$ $11$	$92$
$5$ $100$ $11$ $8$ $30$ $12$	$272$
$4$ $2$ $2$ $2$ $2$	$16$
$6$ $1$ $2$ $3$ $4$ $5$ $6$	$51$

Код

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

int main() {
    priority_queue <long long> nums;
    long long n;
    cin >> n;
    long long number = 0;
    for (int i = 0; i < n; i++) {
        cin >> number;
        nums.push(-number);
    }
    long long min_sum = 0;
    long long a = 0;
    long long b = 0;
    while ( !nums.empty() )
    {
        a = nums.top();
        nums.pop();
        if (nums.empty()) break;
        b = nums.top();
        nums.pop();
        min_sum -= a+b;
        nums.emplace(a+b);
        
    }
    cout << " " << min_sum;
    return 0;
}

#include <iostream>

#include <queue>

using namespace std;

int main() {

priority_queue <long long> nums;

long long n;

cin >> n;

long long number = 0;

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

cin >> number;

nums.push(-number);

}

long long min_sum = 0;

long long a = 0;

long long b = 0;

while ( !nums.empty() )

{

a = nums.top();

nums.pop();

if (nums.empty()) break;

b = nums.top();

nums.pop();

min_sum -= a+b;

nums.emplace(a+b);

}

cout << " " << min_sum;

return 0;

}

Решение

Стоимость сложения всех чисел будет минимальной, если на каждом следующем шаге мы будем складывать два наименьшие числа из множества $A$, состоящего из данного ряда чисел и уже вычисленных «частичных сумм». Таким образом, каждый шаг цикла поиска минимальной стоимости сложения будет состоять из нахождения двух минимальных чисел из множества, удаления этих чисел из множества $A$ и добавления в него результата их суммирования. В специальную переменную $min\_sum$ будем также каждый раз добавлять результат этого суммирования. Таким образом, количество элементов во множестве будет с каждым шагом уменьшаться на одно, и в конце, когда в нем останется единственный элемент, переменная $min\_sum$ будет содержать искомую стоимость сложения всех чисел.

Реализовать такой код достаточно просто, если реализовать множество $A$ в виде очереди с приоритетом. Так как в задаче нужны минимальные элементы множества, а очередь располагает элементы в порядке их увеличения, то будем хранить в ней не сами элементы множества $A$, а противоположные им числа.

Ссылки

Условие на e-olymp.com
Код на ideone.com

Related Images:

e-olymp 1226. Обмен иностранцами

13/05/2018 by Мороз Дима

Задача

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

Программа обмена работает следующим образом. Каждый из участников дает информацию о месте своем проживания и месте, куда бы он хотел переехать. Программа считается успешной, если каждый студент найдет для обмена подходящего партнера. Другими словами, если некоторый студент желает переехать из $A$ в $B$, то обязательно должен быть другой студент, который хочет переехать из $B$ в $A$. Это простая задача, если участников программы всего $10$. Но что делать если их будет $100001$?

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

Первая строка содержит количество тестов $t$. Первая строка каждого теста содержит количество студентов $n$ $(1 ≤ n ≤ 100001)$, за которыми следуют $n$ строк, описывающие данные по обмену. Каждая из этих строк содержит информацию об одном студенте — два целых числа, разделенные пробелом, соответствующих текущему месту проживания студента и месту, куда он желает переехать. Места описываются неотрицательными целыми числами, не большими $10^9$. Ни у одного из кандидатов место проживания и место желаемого переезда не совпадают.

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

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

Тесты

Входные данные	Выходные данные
2 2 1 2 2 1 2 31 13 13 31	YES YES
1 4 17 3 28 15 15 28 3 17	YES
1 4 17 3 28 15 15 28 3 18	NO
3 2 1 2 3 4 2 47 7 7 47 2 12 34 12 34	NO YES NO

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

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

multiset <pair <unsigned int, unsigned int>> M;
multiset <pair <unsigned int, unsigned int>>::iterator it;

int main() {
    unsigned int t, n, a, b;
    cin >> t;
    while (t != 0) {
        cin >> n;
        M.clear();
        for (int i = 0; i < n; i++) {
            cin >> a >> b;
            if ((it = M.find (make_pair(b, a))) == M.end()) {
                M.insert (make_pair(a, b));
            } else M.erase(it);
        }
        (M.empty()) ? cout << "YES" << endl : cout << "NO" << endl;
        t--;
    }
    
    return 0;
}

#include <iostream>

#include <set>

using namespace std;

multiset <pair <unsigned int, unsigned int>> M;

multiset <pair <unsigned int, unsigned int>>::iterator it;

int main() {

unsigned int t, n, a, b;

cin >> t;

while (t != 0) {

cin >> n;

M.clear();

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

cin >> a >> b;

if ((it = M.find (make_pair(b, a))) == M.end()) {

M.insert (make_pair(a, b));

} else M.erase(it);

}

(M.empty()) ? cout << "YES" << endl : cout << "NO" << endl;

t--;

}

return 0;

}

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

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

Ссылки

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

Related Images:

e-olymp 333. Детская железная дорога-2

18/06/2017 by Антон Куперман

Задача

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

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

Сколько всего разных слов может быть в таком необычном «английском» словаре Витэка?

Тесты

Входные данные	Выходные данные
ALPHABET	35
AAAA	4
UNIVERSITY	54
ABABABABC	24

Код на C++

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

int main() {
    string a;
    vector <string> c;
    vector<string> :: iterator it;// задаем итератор
    cin>>a;
    for(int i=0;i<a.size();i++)
    {
        for(int j=1;j<a.size();j++)
        {
            c.push_back(a.substr(i,j));
        }
    }
    sort(c.begin(), c.end()); // сортируем вектор для функции unique
    it = unique(c.begin(), c.end()); // задаем итератору значение функции unigue
    c.resize(it - c.begin());// производим resize вектора при помощи итератора
    cout<<c.size()+1;
    return 0;
}

#include <iostream>

#include <string>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

string a;

vector <string> c;

vector<string> :: iterator it;// задаем итератор

cin>>a;

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

{

for(int j=1;j<a.size();j++)

{

c.push_back(a.substr(i,j));

}

sort(c.begin(), c.end()); // сортируем вектор для функции unique

it = unique(c.begin(), c.end()); // задаем итератору значение функции unigue

c.resize(it - c.begin());// производим resize вектора при помощи итератора

cout<<c.size()+1;

return 0;

}

Код на Java

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

public class Main
{
    public static void main (String[] args) 
    {
        Scanner in = new Scanner(System.in);
        Vector<String> c = new Vector<String>();
        String a = in.nextLine();
        for(int i=0;i<a.length();i++)
        {
            for(int j=i+1;j<=a.length();j++)
            {
                c.add(a.substring(i,j));
            }
        }
        HashSet<String> unique = new HashSet<String>(c);
        Vector<String> d = new Vector<String>(unique);
        System.out.print(d.size());
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

public class Main

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

Vector<String> c = new Vector<String>();

String a = in.nextLine();

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

{

for(int j=i+1;j<=a.length();j++)

{

c.add(a.substring(i,j));

}

HashSet<String> unique = new HashSet<String>(c);

Vector<String> d = new Vector<String>(unique);

System.out.print(d.size());

}

Решение

Казалось бы, задачу можно решить простым циклом. Ведь в 6-буквенном слове: 6 однобуквенных слов, 5 двубуквенных и т.д. Однако очевидной становится проблема повторения,причем не только повторений букв, но и повторений подстрок, что изрядно усложняет наше решение. Создадим вектор, состоящий из строк, куда мы будем добавлять все подстроки строки из входного потока. Отсортируем полученный вектор. Это нужно для того чтобы одинаковые элементы шли рядом с друг другом. Тогда мы можем использовать функцию unique(), которая удалит из вектора все повторяющиеся элементы, кроме одного. Для того, чтобы провести resize() вектора нам понадобится итератор, который мы приравняем к функции unique(). После resize() останется только вывести размер вектора и прибавить к нему единицу, так как само слово не является подстрокой.

Ссылки

1.Код на С++

2.Код на Java

3.Условие на e-olymp

Related Images:

A272. Количество осадков

07/05/2017 by Тимур Фирсов

Задача

Даны действительные числа [latex]a_{1}, a_{2}, …, a_{n}[/latex] – количество осадков (в миллиметрах), выпавших в Москве в течение [latex]n[/latex] лет. Вычислить среднее количество осадков [latex]average[/latex] и отклонение от среднего для каждого года [latex]d_{1}, d_{2}, …, d_{n}[/latex].

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

Последовательность действительных чисел.

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

Среднее количество осадков [latex]average[/latex].
Последовательность действительных чисел [latex]d_{1}, d_{2}, …, d_{n}[/latex] — отклонение от среднего.

Тесты

№	Входные данные	Выходные данные
1	0 0 0 0 0 0 1 0 0 0	0.1 0.1 0.1 0.1 0.1 0.1 0.1 0.9 0.1 0.1 0.1
2	1.23 2.34 3.45 4.56 5.67	3.45 2.22 1.11 0 1.11 2.22
3	234.109 4655.15 43.629 14.109	1236.75 1002.64 3418.4 1193.12 1222.64
4	5 5 5 5 5 5	5 0 0 0 0 0 0

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

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

int main() {
    vector <long double> v;
    long double a, average=0;
    while(cin>>a){
        average+=a;
        v.push_back(a);
    }
    average/=v.size();
    cout<<average<<'\n';
    for(int i=0; i<v.size(); i++)cout<<abs(v[i]-average)<<' ';
    return 0;
}

#include <iostream>

#include <vector>

#include <cmath>

using namespace std;

int main() {

vector <long double> v;

long double a, average=0;

while(cin>>a){

average+=a;

v.push_back(a);

}

average/=v.size();

cout<<average<<'\n';

for(int i=0; i<v.size(); i++)cout<<abs(v[i]-average)<<' ';

return 0;

}

Решение

В цикле считываем числа из входного потока и прибавляем их к переменной [latex]average[/latex] (изначально [latex]average=0[/latex]), а также помещаем их в вектор [latex]v[/latex]. Далее делим [latex]average[/latex] на количество элементов в векторе, таким образом получим среднее количество осадков. Затем при помощи цикла поочередно будем выводить отклонение от среднего количества осадков для каждого года. Отклонением от среднего будет абсолютная величина разности соответствующего элемента вектора [latex]v[/latex] и среднего значения [latex]average[/latex].

Ссылки

Код программы
Условие задачи (страница 117).

Related Images:

А273. Центр тяжести системы

05/05/2017 by Иванна Ялымова

Задача. Задача из сборника задач по программированию С.А.Абрамова за 2000 год.
Система из 25 материальных точек в пространстве задана с помощью последовательности действительных чисел [latex]x_{1}, y_{1}, z_{1}, p_{1}, x_{2}, y_{2}, z_{2}, p_{2},\ldots,x_{25}, y_{25}, z_{25}, p_{25}[/latex], где [latex]x_{i}, y_{i}, z_{i}[/latex] — координаты [latex]i[/latex]-ой точки, а [latex]p_{i}[/latex] — ее вес ([latex]i=1,2,\ldots,25[/latex]). Получить координаты центра тяжести системы, а также расстояние от центра тяжести до всех точек системы.

Входные данные:
[latex]x, y, z, p[/latex] — координаты и вес точки.

Выходные данные:
[latex]sum(x,y,z)[/latex] — координаты центра тяжести системы, [latex]l[/latex] — расстояние от центра тяжести до одной из точек.

Тесты:

Входные данные	Выходные данные
[latex]x[/latex] [latex]y[/latex] [latex]z[/latex] [latex]p[/latex]	[latex]sum[/latex] [latex](x[/latex] [latex]y[/latex] [latex]z)[/latex]	[latex]l[/latex]
2 2 1 2 3 1 2 1	2.33333 1.66667 1.33333	0.57735 1.1547
7 10 5 20 1 0 3 1 43 50 6 3 0 9 0 200 4 8 15 66	1.84138 9.23448 3.83103	5.34452 9.3099 57.9704 4.25705 11.4424

Код программы на С++

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

struct dot {
    double x;
    double y;
    double z;
    dot() {
        x=0;
        y=0;
        z=0;
    }
    dot (double a, double b, double c) {
        x=a;
        y=b;
        z=c;
    }
};
int main() {
    vector <dot> a;
    double x, y, z, p;
    double sump=0;
    dot sum=dot();
    while (cin>>x && 
           cin>>y && 
           cin>>z && 
           cin>>p) 
    {                                           
        a.push_back(dot(x,y,z));
        sum.x+=x*p;
        sum.y+=y*p;
        sum.z+=z*p;
        sump+=p;
    }
    sum.x/=sump;
    sum.y/=sump;
    sum.z/=sump;
    
    cout << sum.x << " " << sum.y << " " << sum.z << endl;
    
    for (int i=0; i<a.size(); i++)
    {
        double l=sqrt((a[i].x-sum.x)*(a[i].x-sum.x) + (a[i].y-sum.y)*(a[i].y-sum.y) + (a[i].z-sum.z)*(a[i].z-sum.z));
        cout << l << endl; 
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <cmath>

using namespace std;

struct dot {

double x;

double y;

double z;

dot() {

x=0;

y=0;

z=0;

}

dot (double a, double b, double c) {

x=a;

y=b;

z=c;

}

};

int main() {

vector <dot> a;

double x, y, z, p;

double sump=0;

dot sum=dot();

while (cin>>x &&

cin>>y &&

cin>>z &&

cin>>p)

{

a.push_back(dot(x,y,z));

sum.x+=x*p;

sum.y+=y*p;

sum.z+=z*p;

sump+=p;

}

sum.x/=sump;

sum.y/=sump;

sum.z/=sump;

cout << sum.x << " " << sum.y << " " << sum.z << endl;

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

{

double l=sqrt((a[i].x-sum.x)*(a[i].x-sum.x) + (a[i].y-sum.y)*(a[i].y-sum.y) + (a[i].z-sum.z)*(a[i].z-sum.z));

cout << l << endl;

}

return 0;

}

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

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

class Dot {
    double x;
    double y;
    double z;
    public Dot() {
        x = 0;
        y = 0;
        z = 0;
    }
    Dot (double a, double b, double c) {
        x=a;
        y=b;
        z=c;
    }
}
class Ideone{
    public static void main (String[] args) throws java.lang.Exception{
        Scanner in = new Scanner(System.in);
        Vector a = new Vector();
        double x, y, z, p;
        double sump=0;
        Dot sum = new Dot();
        while (in.hasNextDouble()){
            x = in.nextDouble();
            y = in.nextDouble();
            z = in.nextDouble();
            p = in.nextDouble();
            a.add(new Dot(x,y,z));
            
            sum.x += x*p;
            sum.y += y*p;
            sum.z += z*p;
            sump+=p;
        }
        sum.x/=sump;
        sum.y/=sump;
        sum.z/=sump;
        
        System.out.println(sum.x + " " + sum.y + " " + sum.z);
        Dot dot;
        for (int i=0; i<a.size(); i++)
        {
            dot = (Dot)a.elementAt(i);
            double l = Math.sqrt((dot.x-sum.x)*(dot.x-sum.x) + (dot.y-sum.y)*(dot.y-sum.y) + (dot.z-sum.z)*(dot.z-sum.z));
            System.out.println(l);
        }
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Dot {

double x;

double y;

double z;

public Dot() {

x = 0;

y = 0;

z = 0;

}

Dot (double a, double b, double c) {

x=a;

y=b;

z=c;

}

class Ideone{

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

Scanner in = new Scanner(System.in);

Vector a = new Vector();

double x, y, z, p;

double sump=0;

Dot sum = new Dot();

while (in.hasNextDouble()){

x = in.nextDouble();

y = in.nextDouble();

z = in.nextDouble();

p = in.nextDouble();

a.add(new Dot(x,y,z));

sum.x += x*p;

sum.y += y*p;

sum.z += z*p;

sump+=p;

}

sum.x/=sump;

sum.y/=sump;

sum.z/=sump;

System.out.println(sum.x + " " + sum.y + " " + sum.z);

Dot dot;

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

{

dot = (Dot)a.elementAt(i);

double l = Math.sqrt((dot.x-sum.x)*(dot.x-sum.x) + (dot.y-sum.y)*(dot.y-sum.y) + (dot.z-sum.z)*(dot.z-sum.z));

System.out.println(l);

}

Решение
В цикле «[latex]while[/latex]» читаем числа из входного потока и запоминаем координаты точек в векторе [latex]а[/latex], к переменной [latex]sum[/latex] прибавляем эти координаты, умноженные на [latex]p[/latex].
Потом подсчитываем координаты центра тяжести системы и выводим эти координаты.
В цикле «[latex]for[/latex]» берем из вектора координаты одной из точек системы, считаем расстояние от центра тяжести до одной из точек системы и выводим это расстояние.

Ссылки
Код в ideone.com (C++)
Код в ideone.com (Java)
Условие задачи (с.117)

Related Images:

А282(а)

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

Задача

Даны действительные числа [latex]a_1,a_2, …,a_{2n}[/latex]. Получить:

[latex]a_1,a_{n+1},a_2,a_{n+2}, …,a_n,a_{2n}[/latex]

Тесты

Ввод	Вывод
1 2 3 4 5 6 7 8 9 10	1 6 2 7 3 8 4 9 5 10
8 25 3 7	8 3 25 7
5.5 6.025 2.387 1.0986 7.762 3.5958	5.5 1.0986 6.025 7.762 2.387 3.5958

Хороший код

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

int main() {
    vector <double> s;
    vector <double> l;
    double a,n;
    while(cin>>a)
    {
        s.push_back(a);
    }
    n=s.size()/2;
    for(int i=0;i<n;i++)
    {
        l.push_back(s.at(i));
        l.push_back(s.at(i+n));
    }
    for(int i=0;i<l.size();i++)
    {
        cout<<l.at(i)<<" ";
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

vector <double> s;

vector <double> l;

double a,n;

while(cin>>a)

{

s.push_back(a);

}

n=s.size()/2;

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

{

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

l.push_back(s.at(i+n));

}

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

{

cout<<l.at(i)<<" ";

}

return 0;

}

Решение

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

Лучший код на C++

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
        vector <double> s;
        double a,n;
        int b=0;
        while(cin>>a)
        {
                s.push_back(a);
        }
        n=s.size()/2;
        for(int i=0;i<n;i++)
        {
                s.insert(s.begin()+2*i+1,s.at(n+b+i));
                b++;
        }
        s.resize(2*n);
        for(int i=0;i<s.size();i++)
        {
                cout<<s.at(i)<<" ";
        }
        return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

vector <double> s;

double a,n;

int b=0;

while(cin>>a)

{

s.push_back(a);

}

n=s.size()/2;

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

{

s.insert(s.begin()+2*i+1,s.at(n+b+i));

b++;

}

s.resize(2*n);

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

{

cout<<s.at(i)<<" ";

}

return 0;

}

Лучший код на Java

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

class Ideone
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        Vector a = new Vector();
        while(in.hasNextDouble()){ 
            a.add(in.nextDouble()); 
        }
        int n=a.size()/2;
        int b=0;
        for(int i=0;i<n;i++){
            a.add(2*i+1,a.get(n+b+i));
            b++;
        }
        a.setSize(2*n);
        Double[] s = new Double[a.size()];
        a.toArray(s);
        for(int i=0;i<s.length;i++){
            System.out.print(s[i]+" "); 
        }
    }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

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

{

Scanner in = new Scanner(System.in);

Vector a = new Vector();

while(in.hasNextDouble()){

a.add(in.nextDouble());

}

int n=a.size()/2;

int b=0;

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

a.add(2*i+1,a.get(n+b+i));

b++;

}

a.setSize(2*n);

Double[] s = new Double[a.size()];

a.toArray(s);

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

System.out.print(s[i]+" ");

}

Решение

В первом способе мы задавали два вектора, чем естественно увеличивали занимаемую память. C помощью функции insert() мы можем вставлять элементы в вектор, не используя дополнительных средств. Однако мы сталкиваемся с тем, что функция по определению вставляет в вектор константу из-за чего наш цикл не будет правильно работать. Чтобы изменять параметр вводимого элемента, заводим отдельный счетчик. Теперь каждый [latex]2*i+1[/latex]-ый шаг мы вставляем [latex]n+b+i[/latex]-ый элемент вектора. Проведем resize() вектора чтобы убрать лишние элементы и получим готовый результат.

Ссылки

Related Images:

A274. Среднее арифметическое всех членов последовательности, кроме одного

27/04/2017 by Эммануил Прокопов

Задача из сборника задач по программированию Абрамова С.А. 2000г.
Даны действительные числа [latex]a_{ 1 }[/latex],…,[latex]a_{ 20 }[/latex]. Получить числа [latex]b_{ 1 }[/latex],…,[latex]b_{ 20 }[/latex], где [latex]b_{ i }[/latex] – среднее арифметическое всех членов последовательности [latex]a_{ 1 }[/latex],…,[latex]a_{ 20 }[/latex], кроме [latex]a_{ i }[/latex] ([latex]i[/latex] = 1,2,…,20).

Обобщим задачу для последовательности длины [latex]n[/latex]
Даны действительные числа [latex]a_{ 1 }[/latex],…,[latex]a_{ n }[/latex]. Получить числа [latex]b_{ 1 }[/latex],…,[latex]b_{ n }[/latex], где [latex]b_{ i }[/latex] – среднее арифметическое всех членов последовательности [latex]a_{ 1 }[/latex],…,[latex]a_{ n }[/latex], кроме [latex]a_{ i }[/latex] ([latex]i[/latex] = 1,2,…,[latex]n[/latex]).

Входные данные:
Последовательность действительных чисел.

Выходные данные:
[latex]n[/latex] чисел, [latex]i[/latex]-ое из которых является средним арифметическим всех членов последовательности, кроме [latex]i[/latex]-го ([latex]i[/latex] = 1,2,…,[latex]n[/latex]).

Тесты

№	Входные данные	Выходные данные
1	4	The sequence must consist of at least two elements.
2	1 0 1	The arithmetic average of all elements of this series except the element №i is: for i = 1: 0.5 for i = 2: 1 for i = 3: 0.5
3	10.1 2.4 11.3 0.8	The arithmetic average of all elements of this series except the element №i is: for i = 1: 4.8(3) for i = 2: 7.4 for i = 3: 4.4(3) for i = 4: 7.9(3)
4	2.5 -1.5 4 -9 1.22	The arithmetic average of all elements of this series except the element №i is: for i = 1: -1.32 for i = 2: -0.32 for i = 3: -1.695 for i = 4: 1.555 for i = 5: -1

Код на C++

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

int main() {
    vector <double> a, b;
    double cur, sum = 0;
    while(cin >> cur){
        a.push_back(cur);
        sum += cur;
    }
    //Если последовательность состоит мене чем из двух элементов.
    if(a.size() < 2){
        cout << "The sequence must consist of at least two elements.";
    }
    
    else{
        //Заполняем вектор b.
        for(int i=0; i < a.size(); ++i){
            b.push_back((sum - a[i])/(a.size() - 1));
        }
        
        //Выводим ответ.
        cout << "The arithmetic average of all elements of this series except the element №i is:\n";
        for(int i=0; i < b.size(); ++i){
            cout << "for i = " << i+1 << ": " << b[i] << '\n';
        }
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

vector <double> a, b;

double cur, sum = 0;

while(cin >> cur){

a.push_back(cur);

sum += cur;

}

//Если последовательность состоит мене чем из двух элементов.

if(a.size() < 2){

cout << "The sequence must consist of at least two elements.";

}

else{

//Заполняем вектор b.

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

b.push_back((sum - a[i])/(a.size() - 1));

}

//Выводим ответ.

cout << "The arithmetic average of all elements of this series except the element №i is:\n";

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

cout << "for i = " << i+1 << ": " << b[i] << '\n';

}

return 0;

}

Код на Java

import java.util.*;

class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        Vector a,b;
        a = new Vector();
        b = new Vector();
        double cur, sum = 0;
        
        while(in.hasNext()){
            cur = in.nextDouble();
            a.add(cur);
            sum += cur;
        }
        //Если последовательность состоит только из одного числа.
        if(a.size() < 2){
            System.out.print("The sequence must consist of at least two elements.");
        }
        else{
            //Заполняем вектор b.
            for(int i=0; i < a.size(); ++i){
                b.add((sum - (double)(a.elementAt(i)))/(a.size() - 1));
            }
        
            //Выводим ответ.
            System.out.print("The arithmetic average of all elements of this series except the element №i is:\n");
            for(int i=0; i < b.size(); ++i){
                System.out.print("for i = " + (i+1) + ": " + b.elementAt(i) + '\n');
            }
        }
    }
}

import java.util.*;

class Main

{

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

{

Scanner in = new Scanner(System.in);

Vector a,b;

a = new Vector();

b = new Vector();

double cur, sum = 0;

while(in.hasNext()){

cur = in.nextDouble();

a.add(cur);

sum += cur;

}

//Если последовательность состоит только из одного числа.

if(a.size() < 2){

System.out.print("The sequence must consist of at least two elements.");

}

else{

//Заполняем вектор b.

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

b.add((sum - (double)(a.elementAt(i)))/(a.size() - 1));

}

//Выводим ответ.

System.out.print("The arithmetic average of all elements of this series except the element №i is:\n");

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

System.out.print("for i = " + (i+1) + ": " + b.elementAt(i) + '\n');

}

Решение
Для начала, в первом цикле мы читаем числа из входного потока, помещаем их в вектор a и прибавляем к переменной sum, предназначенной для хранения суммы всех чисел последовательности. Последовательность должна состоять как минимум из двух элементов. Чтобы получить среднее арифметическое всех её членов, кроме [latex]i[/latex]-го, достаточно отнять [latex]i[/latex]-й элемент вектора a от значения переменной sum и разделить результат на количество членов такой неполной последовательности, а оно будет на единицу меньше размера вектора a. Таким образом заполняется вектор b, в котором хранятся элементы последовательности [latex]b_{ 1 }[/latex],…,[latex]b_{ n }[/latex], после чего требуемая последовательность выводится.

Код на ideone.com (C++)
Код на ideone.com (Java)
Условие задачи (с.118)

Related Images:

Монстр

18/04/2017 by Антон Куперман

Задача 787A с сайта codeforces.com.

Задача

Монстр гонится за Риком и Морти на другой планете. Они настолько напуганы, что иногда кричат. Точнее, Рик кричит в моменты времени b, b + a, b + 2a, b + 3a, …, а Морти кричит в моменты времени d, d + c, d + 2c, d + 3c, ….

Монстр поймает их, если в какой-то момент времени они закричат одновременно. Так что он хочет знать, когда он поймает их (первый момент времени, когда они закричат одновременно) или они никогда не закричат одновременно.

Ввод

Первая строка входных данных содержит два целых числа a и b (1 ≤ a, b ≤ 100).

Вторая строка входных данных содержит два целых числа c и d (1 ≤ c, d ≤ 100).

Вывод

Выведите первый момент времени, когда Рик и Морти закричат одновременно, или - 1, если они никогда не закричат одновременно.

Тесты

Ввод	Вывод
20 2 9 19	82
2 1 16 12	-1

Код

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

int main() {
    int a,b,c,d,n,m;
    vector <int> s;
    cin>>a>>b;
    cin>>c>>d;
    for(int i=0;i<=100;i++)
    {
        for(int j=0;j<=100;j++)
        {
            n=b+i*a;
            m=d+j*c;
            if(m==n)
            {   
                s.push_back(n);
            } 
        }
    }
    if(s.empty()==true)
    {
        cout<<-1;
    } else cout<<s.at(0);
    
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

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

vector <int> s;

cin>>a>>b;

cin>>c>>d;

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

{

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

{

n=b+i*a;

m=d+j*c;

if(m==n)

{

s.push_back(n);

}

if(s.empty()==true)

{

cout<<-1;

} else cout<<s.at(0);

return 0;

}

Решение

В этих моментах времени, заданных прогрессиями, изменяется только коэффициент при a и c. Создадим для них 2 цикла. Так как равных моментов времени может быть много, а нам нужен только первый, создаем вектор и ,когда моменты равны, добавляем в него этот момент. Затем, уже вне цикла, проверяем пустой ли вектор, и в таком случаем выводим -1, так как моменты на данном промежутке не были равны ни разу. Если же вектор непустой, выходим первый элемент вектора. Он и будет искомым первым одновременным криком.

Related Images:

А282в

27/06/2016 by Станислав Коциевский

Задача

Даны действительные числа [latex]a_{1}, a_{2}, \cdots, a_{2n}.[/latex] Получить [latex]a_{1}+a_{2n}, a_{2}+ a_{2n-1}, \cdots, a_{n}+a_{n+1}.[/latex]

Тесты

Входные данные	Выходные данные
2 4 6 2 2 9 7 5	7 11 15 4
1 2 2 1	1 4
139 64 15 20 10 5 6 1	140 70 20 30
111111 22222 33333 11 25 4	111115 22247 33344
15 7 6 9	24 13
2 2	4
138 56 78 3	141 134

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

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

int main()
{
    vector <int> a;
    int b;
    while (cin>>b)
    {
        a.push_back(b);
    }
    for (int i = 0; i<a.size()/2; i++)
    {
        cout<<a[i] + a[a.size()-i-1]<<" ";
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main()

{

vector <int> a;

int b;

while (cin>>b)

{

a.push_back(b);

}

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

{

cout<<a[i] + a[a.size()-i-1]<<" ";

}

return 0;

}

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

Считаем все числа [latex]a_{1}, \cdots, a_{2n}[/latex] в ранее объявленный вектор, пока есть, что считывать. Поскольку мы используем класс vector и цикл while (cin >> b) и метод push_back(), в числе [latex]n[/latex] нет необходимости, а во входых данных присутствуют только сами числа [latex]a_{1}, \cdots, a_{2n}[/latex]. Далее, чтобы узнать количество элементов в векторе, будем использовать метод size(). Остается только выводить в цикле сумму двух текущих чисел, начиная с краев вектора и сдвигаясь в каждом витке на элемент ближе к центру вектора, пока не дойдем до центра.

Ссылки

Задача взята из задачника С. Абрамова;
Ссылка на код на ideone.com.

Related Images:

A271

24/06/2016 by Сабиров Ильдар

Задача.
Даны действительные числа [latex]a_{1},\ldots,a_{k}[/latex]. Получить [latex]\sqrt{\frac{\sum\limits_{i=1}^{k}(a_{i}-\tilde{a})^{2}}{k-1}},[/latex] где [latex]\tilde{a}=\frac{1}{k}\sum\limits_{i=1}^{k}a_{i}.[/latex]

Тесты

input	[latex]\tilde{a}[/latex]	[latex]\sqrt{\frac{\sum\limits_{i=1}^{k}(a_{i}-\tilde{a})^{2}}{k-1}}[/latex]	Комментарий
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15	8	4.4712	Пройдено
2 8 3 4 5 6 7 9 11 15 17 12 19 7 5 1 7 9 19 14	9	6.35834659	Пройдено
3 3 3 3 3 0 0 0 5 5 5 15 15 15 15	6	5.8554	Пройдено

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

int main() {
    double a=0,s=0,z;
    int y;
    vector<int> x;
    while(cin>>z){
        x.push_back(z);
    }
    for (int i=0;i<x.size();i++){
        a+=x[i];
    }
    a=a/x.size();
    for (int i=0;i<x.size();i++){
        s=s+(a-x[i])*(a-x[i]);
    }
    s=s/(x.size()-1);
    s=sqrt(s);
    cout<<a<<" ";
    cout<<s<<" ";
    return 0;
}

#include <iostream>

#include <vector>

#include <cmath>

using namespace std;

int main() {

double a=0,s=0,z;

int y;

vector<int> x;

while(cin>>z){

x.push_back(z);

}

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

a+=x[i];

}

a=a/x.size();

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

s=s+(a-x[i])*(a-x[i]);

}

s=s/(x.size()-1);

s=sqrt(s);

cout<<a<<" ";

cout<<s<<" ";

return 0;

}

Решение

Заполняем вектор действительными числами
Считаем их сумму (с помощью цикла прибавляем каждый элемент вектора).
Находим значение [latex]\tilde{a}[/latex].
Находим сумму под корнем второй формулы через цикл (аналогично п.2)
Производим необходимые арифметические операции для нахождения значения второй формулы.
Вывод значений.
Ссылка на код

Related Images:

A285

01/06/2016 by Максим Носов

Задача

Даны действительные числа [latex]{ a }_{ 1 }[/latex]…[latex]{ a }_{ n }[/latex] . Если в результате замены отрицательных членов последовательности [latex]{ a }_{ 1 }[/latex]…[latex]{ a }_{ n }[/latex] их квадратами члены будут образовывать неубывающую последовательность, то получить сумму членов исходной последовательности ; в противном случае получить их произведение.

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

Последовательность

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

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

Тесты

№	Последовательность	Результат
1	1 2 3 4	10
2	1 2 -3 4	-24
3	1 -2 5 6 7 8	25
4	-1 -1 -2 -3 -4 -5	-16

Код

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector <double> x; //задаем элемент типа vector
    double a,m=0,k=0,n=0;
    while(cin>>a){     //вводим последовательность
        x.push_back(a);  //для дальнейшего преобразования последовательности
    }
    for(int i=0;i<x.size();i++)n+=x[i]; //находим сумму
    for(int i=0;i<x.size();i++){
        if(i==0)k=x[0];
        else k*=x[i];
    } //и произведение исходной последовательности
    for(int i=0;i<x.size();i++){   //задаем цикл, в котором заменяем все отрицательные элементы их квадратами
        if(x[i]<0)x[i]=x[i]*x[i];
        if(x[i]<m){  //проверяем возрастаемая последовательность или нет
            m=0;
            break;
        }
        m=x[i];
    }
    if(m!=0){    //если возрастающая - то выводим сумму
        cout<<n;
    }
    else {
        cout<<k; //если нет - то произведение
    }
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

vector <double> x; //задаем элемент типа vector

double a,m=0,k=0,n=0;

while(cin>>a){ //вводим последовательность

x.push_back(a); //для дальнейшего преобразования последовательности

}

for(int i=0;i<x.size();i++)n+=x[i]; //находим сумму

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

if(i==0)k=x[0];

else k*=x[i];

} //и произведение исходной последовательности

for(int i=0;i<x.size();i++){ //задаем цикл, в котором заменяем все отрицательные элементы их квадратами

if(x[i]<0)x[i]=x[i]*x[i];

if(x[i]<m){ //проверяем возрастаемая последовательность или нет

m=0;

break;

}

m=x[i];

}

if(m!=0){ //если возрастающая - то выводим сумму

cout<<n;

}

else {

cout<<k; //если нет - то произведение

}

Решение

Предлагаю следующее решение. Записываем каждый член последовательности в элемент типа vector. Сразу находим их сумму и произведение. Затем заменяем каждый отрицательный элемент его квадратом и проверяем возрастающая ли последовательность. Если да — то выводим сумму, если нет — то произведение.

Код на ideone.

Related Images:

A298

25/05/2016 by Грешилов Константин

Условие взято со сборника задач С.Абрамова и др.

Задача

Даны целые числа [latex]a_1,\ldots,a_n[/latex],[latex]b_1,\ldots,b_n[/latex]. Преобразовать последовательность [latex]b_1,\ldots,b_n[/latex] по правилу: если [latex] a_i \leq 0[/latex], то [latex]b_i[/latex] увеличить в 10 раз, иначе [latex]b_i[/latex] заменить нулем [latex](i=1,\ldots,n[/latex]). Данные принимать до конца входного потока.

Тесты:

№	Входные данные	Выходные данные
1	-1 0 12 4 5 0 1 2 3 4 5 6	-1 0 12 4 5 0 10 20 0 0 0 60
2	0 2147483647	0 21474836470
3	1 2 3 4 5 6 7 8 0 0 1 2 3 4 5 6 7 8 9 10	1 2 3 4 5 6 7 8 0 0 0 0 0 0 0 0 0 0 90 100

Решение:

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

int main() {
    vector <long long> a;
    long long b;
    while (cin >> b)
    {
        a.push_back(b);
    }
    for (int i = 0; i < a.size()/2; i++)
    {
        if(a[i] <= 0)
        {
            a[a.size()/2 + i] *= 10;
        }
        else
        {
            a[a.size()/2 + i] = 0;
        }
    }
    for (auto c : a)
    {
        cout << c << " ";
    }
    cout << endl;
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

vector <long long> a;

long long b;

while (cin >> b)

{

a.push_back(b);

}

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

{

if(a[i] <= 0)

{

a[a.size()/2 + i] *= 10;

}

else

{

a[a.size()/2 + i] = 0;

}

for (auto c : a)

{

cout << c << " ";

}

cout << endl;

return 0;

}

Описание решения:

При решении данной задачи был использован тип данных [latex]long long[/latex], так как было необходимо охватить как можно больший диапазон значений. Заданные последовательности чисел будем хранить в одном векторе [latex]a[/latex], где последним элементов первой последовательности будем элемент под номером [latex]a.size()/2-1[/latex]. Отсюда, в цикле будем просматривать каждый элемент первой последовательности. Если данный элемент не положителен, то увеличим в 10 раз соответствующий элемент второй последовательности, иначе, присвоим ему значение нуля. Номер в векторе соответствующего элемента из второй последовательности можно найти по формуле [latex]a.size()/2+i[/latex], где [latex]i[/latex] — это номер элемента из первой последовательности. После прохода по всей первой последовательности, выведем весь вектор на экран.

Код можно запустить и опробовать здесь.

Related Images:

А291а

25/05/2016 by Андрей Яроцкий

Задача: А291а

Условие:

Даны действительные числа [latex]a_{1},\ldots,a_{30}.[/latex] Получить [latex]\max (a_{1}+ a_{30},a_{2}+a_{29},\ldots,a_{15}+a_{n}).[/latex]

Тесты:

№	Входные данные	Выходные данные
1	2 3 5 4	8
2	2 3 7 5 4	14
3	4.5 1.1 3 9.25 0.75	10.35
4	-4.5 -2 0 -7.1 5	0.5

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

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

bool f(double a, double b){ //Вспомогательная функция для сортировки вектора по убыванию
    return a>b;
}

int main() {
    vector<double> real;
    double value;
    while(cin >> value){
        real.push_back(value);
    }
    int size = real.size();
    int size_of_sum = ceil(size%2==0?size/2:size/2+1); //Размер вектора сумм
    vector<double> sum;
    for(int i = 0; i < size_of_sum; i++){
        if(i == size_of_sum-1 && size%2 != 0) sum.push_back(2*real[i]);// Средний элемент массива real при нечетном size
        else sum.push_back(real[i] + real[size - i - 1]);
    }
    sort(sum.begin(),sum.end(),f); // Сортировка по убыванию
    cout << sum[0];
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

#include <cmath>

using namespace std;

bool f(double a, double b){ //Вспомогательная функция для сортировки вектора по убыванию

return a>b;

}

int main() {

vector<double> real;

double value;

while(cin >> value){

real.push_back(value);

}

int size = real.size();

int size_of_sum = ceil(size%2==0?size/2:size/2+1); //Размер вектора сумм

vector<double> sum;

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

if(i == size_of_sum-1 && size%2 != 0) sum.push_back(2*real[i]);// Средний элемент массива real при нечетном size

else sum.push_back(real[i] + real[size - i - 1]);

}

sort(sum.begin(),sum.end(),f); // Сортировка по убыванию

cout << sum[0];

return 0;

}

Решение:

После считывания входного потока данных в вектор [latex]real[/latex] вещественных чисел, вычисляем размер вектора [latex]sum[/latex], равный половине количества элементов входного потока с округлением вверх. В случае нечетного количества элементов, последним элементом вектора [latex]sum[/latex] будет центральный элемент вектора [latex]real[/latex] увеличенный в два раза. Далее, после сортировки полученного вектора по убыванию, выводим первый элемент вектора.

Ссылки:

Задачник по программированию С. Абрамова.

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

Related Images:

A280

20/05/2016 by Радик Сиденко

Условие: Пусть [latex] x_{i},y_{i} [/latex] ( i=1,2, . . .) и определены, как в задаче 167. Получить [latex] x_{1},\ldots ,x_{25},y_{1},\ldots y_{25}. [/latex]

Задача А167: Пусть [latex] x_{1}=y_{1}=1;[/latex] [latex] x_{2}=y_{2}=2;[/latex] [latex]x_{i}=\dfrac{y_{i-1}-y_{i-2}}{i};[/latex] [latex] y_{i}=\dfrac{x_{i-1}^{2}+x_{i-2}+y_{i-1}}{i!};[/latex] [latex]i=3,4,\ldots[/latex]

#include <iostream>   
using namespace std; 
long double fact(int f){
    if(f < 0) 
        return 0; 
    if (f == 0) 
        return 1;
    else 
        return f * fact(f - 1); 
}
int main()
{
    long double x[31];
    long double y[31];
    x[1]=1;
    x[2]=2;
    y[1]=1;
    y[2]=2;
    for(int i=3; i<=25;i++){
        x[i] = (y[i-1] - y[i-2])/i;
        y[i]=((x[i-1]*x[i-1])+x[i-2]+y[i-1])/fact(i);
 
    }
    for(int i=1;i<=25;i++){
        cout<<"x"<<i<<" = ";
        cout<<x[i]<<endl;
 
    }
    for(int i=1;i<=25;i++){
        cout<<"y"<<i<<" = ";
        cout<<y[i]<<endl;
 
    }
 
 
    return 0; 
}

#include <iostream>

using namespace std;

long double fact(int f){

if(f < 0)

return 0;

if (f == 0)

return 1;

else

return f * fact(f - 1);

}

int main()

{

long double x[31];

long double y[31];

x[1]=1;

x[2]=2;

y[1]=1;

y[2]=2;

for(int i=3; i<=25;i++){

x[i] = (y[i-1] - y[i-2])/i;

y[i]=((x[i-1]*x[i-1])+x[i-2]+y[i-1])/fact(i);

}

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

cout<<"x"<<i<<" = ";

cout<<x[i]<<endl;

}

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

cout<<"y"<<i<<" = ";

cout<<y[i]<<endl;

}

return 0;

}

Ссылка на код в ideone

Related Images:

A276

20/05/2016 by Радик Сиденко

Условие: Построить последовательность целых чисел [latex]a_{1},\ldots ,a_{30},[/latex] где [latex]a_{1}=1,a_{2}=1;a_{i}=a_{i/2}+a_{i-2}\left( i=3,\ldots ,30\right) .[/latex]

#include <iostream>   
using namespace std; 
 
int main()
{
    int a[31];
    a[1]=1;
    a[2]=1;
    for(int i=3; i<=30;i++){
        a[i] = a[i/2] + a[i-2];
 
    }
    for(int i=1;i<=30;){
        cout<<i<<" "<<" element of the sequence = ";
        cout<<a[i]<<endl;
        i++;
    }
 
 
    return 0; 
}

#include <iostream>

using namespace std;

int main()

{

int a[31];

a[1]=1;

a[2]=1;

for(int i=3; i<=30;i++){

a[i] = a[i/2] + a[i-2];

}

for(int i=1;i<=30;){

cout<<i<<" "<<" element of the sequence = ";

cout<<a[i]<<endl;

i++;

}

return 0;

}

Ссылка на код в ideone

Related Images:

A305

27/04/2016 by Кудымовская Вика

Задача A305

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

Даны действительные числа [latex]a_{1},\dots,a_{n}[/latex]. Оставить без изменения последовательность [latex]a_{1},\dots,a_{n}[/latex], если она упорядочена по неубыванию или по невозрастанию; в противном случае удалить из последовательности те члены, порядковые номера которых кратны четырём, сохранив прежним порядок оставленных членов.

Тестирование

№	Входные данные	Выходные данные
1.	5 -1 2 3 4 5	-1 2 3 4 5
2.	6 6 0 2 3 4 6.7	0 2 3 6.7
3.	10 1 2 5 7 -10 3 1 3 2 1	2 5 7 3 1 3 1
4.	5 1 5 6 7.5 0	5 6 7.5
5.	3 -23 46 -80	46 -80

Реализация

#include <iostream>
#include <vector>
#include <iterator>
 
using namespace std;
 
int main()
{
    int size_of_the_sequence;
    int temp = 0; //счетчик
    cin >> size_of_the_sequence;  
    vector<double> v1 (size_of_the_sequence);
    vector<double> v2;
    bool h = true, l = true;
    for (int i = 0; i < size_of_the_sequence; i++)
    {
        cin >> v1[i];
        if (i % 4 == 0) temp++;
    }
    for (int i = 1; i < size_of_the_sequence; i++)
    {
        if (v1[i - 1] <= v1[i])
        {
            l = false;
        }
        if (v1[i - 1] >= v1[i])
        {
            h = false;
        }
    }
    if (!l && !h)//исходная последовательность не упорядочена ни по возрастанию, ни по убыванию
    {
        v2.resize(size_of_the_sequence - temp);
        int size_of_the_sequence = 0;
        for (int i = 0; i < v1.size(); i++)
        {
            if (i % 4 == 0) { size_of_the_sequence++; continue; }
            else v2[i - size_of_the_sequence] = v1[i];
        }
        v1.resize(size_of_the_sequence - temp);
        v1 = v2;
        v1.shrink_to_fit();
        v2.clear();
    }
    copy(v1.begin(), v1.end(), ostream_iterator<double>(cout, " "));//выводим исходную последовательность без изменений
    return 0;
}

#include <iostream>

#include <vector>

#include <iterator>

using namespace std;

int main()

{

int size_of_the_sequence;

int temp = 0; //счетчик

cin >> size_of_the_sequence;

vector<double> v1 (size_of_the_sequence);

vector<double> v2;

bool h = true, l = true;

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

{

cin >> v1[i];

if (i % 4 == 0) temp++;

}

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

{

if (v1[i - 1] <= v1[i])

{

l = false;

}

if (v1[i - 1] >= v1[i])

{

h = false;

}

if (!l && !h)//исходная последовательность не упорядочена ни по возрастанию, ни по убыванию

{

v2.resize(size_of_the_sequence - temp);

int size_of_the_sequence = 0;

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

{

if (i % 4 == 0) { size_of_the_sequence++; continue; }

else v2[i - size_of_the_sequence] = v1[i];

}

v1.resize(size_of_the_sequence - temp);

v1 = v2;

v1.shrink_to_fit();

v2.clear();

}

copy(v1.begin(), v1.end(), ostream_iterator<double>(cout, " "));//выводим исходную последовательность без изменений

return 0;

}

Алгоритм решения

Считываем все действительные числа до конца входного потока и записываем их в вектор v1. Проверяем, упорядочена ли последовательность по возрастанию или по убыванию. Если да, выводим на экран исходную последовательность без изменений с помощью функции copy() и итератора вывода ostream_iterator, который записывает элементы последовательно в выходной поток. Если же последовательность не упорядочена ни по убыванию, ни по возрастанию, удаляем из неё элементы, порядковые номера которых кратны четырём. Важно сохранить прежним порядок оставленных членов.
Работаем следующим образом:
1. Создаём вектор v_2.
2. Уменьшаем размер контейнера с помощью функции resize(): v2.resize(size_of_the_sequence - temp). Инициализируем переменную size_of_the_sequence значением ноль.
3. Если порядковый номер элемента неупорядоченной последовательности кратен четырём, то увеличиваем количество элементов на единицу с каждой итерацией. Иначе, присваиваем вектору v_2 значение вектора v_1: v2[i - size_of_the_sequence] = v1[i].
4. Уменьшаем размер контейнера v_1. Присваиваем вектору v_1 значение вектора v_2.
5. С помощью функции shrink_to_fit() уменьшаем количество используемой памяти вектора v_1.
6. Извлекаем все элементы из вектора v_2 с помощью функции clear().

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