e-olymp 1462. Хитрая сортировка

26/02/2020 by Николай Жирко

Задача

Дана последовательность чисел. Вам следует упорядочить их по неубыванию последней цифры, а при равенстве последних цифр – по неубыванию самих чисел.

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

Первая строка содержит число [latex] n [/latex] ([latex] 1 \leqslant n \leqslant 100 [/latex]), а вторая — сами натуральные числа, не превышающие [latex] 32000 [/latex].

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

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

Тесты

№	Входные данные	Выходные данные
1	7 12 15 43 13 20 1 15	20 1 12 13 43 15 15
2	10 82 22 19 90 34 17 588 921 200 121	90 200 121 921 22 82 34 17 588 19
3	4 162 9801 37 14	9801 162 14 37

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

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

bool comp (const int& a, const int& b) {
    if (a % 10 == b % 10) return (a < b);
    else return a % 10 < b % 10;
}

int main() {
    int n, a;
    vector<int> array;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a;
        array.push_back(a);
    }
    
    sort (array.begin(), array.end(), comp);
    
    for (int a = 0; a < n; a++) {
        cout << array[a] << " ";
    }
    return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

bool comp (const int& a, const int& b) {

if (a % 10 == b % 10) return (a < b);

else return a % 10 < b % 10;

}

int main() {

int n, a;

vector<int> array;

cin >> n;

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

cin >> a;

array.push_back(a);

}

sort (array.begin(), array.end(), comp);

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

cout << array[a] << " ";

}

return 0;

}

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

Для решения этой задачи необходимо объявить вектор, который будет хранить все числа, введенные пользователем, например, array.
Сортировку будем проводить с помощью функции sort. Для правильного упорядочивания чисел, напишем функцию компаратор comp, для сравнения чисел и решения, стоит ли их менять местами.
В конце выводим вектор array.

Ссылки

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

Решение на e-olymp

Решение на ideone.com

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

Анаграммы

26/11/2018 by Иван Киреев

Анаграммы

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

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

Игоря будут интересовать только слова которые записаны в словаре, так как других он не знает.

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

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

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

Задан словарь английских слов. Каждое слово в новой строке. Длинна слова не более $255$ символов. Количество слов любое.

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

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

Решение

Прочитаем словарь. Запишем в структуру pair строку с исходным словом в first и отсортированную в second. Анаграммами будут являться слова с одинаковыми second строками. Так как они будут состоять из одних и тех же букв, которые выстроены в одинаковом порядке. Отсортируем множество слов из словаря по second. Таким образом все слова анаграммы будут находиться рядом.

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

На выходе получим массив индексов слов у которых существует максимальное количество анаграмм, в данном словаре. Выведем эти слова и все анаграммы к ним в исходном варианте. Для этого нам и нужна строка first.

Тесты

№

Ввод

Вывод

2500 слов английского языка

trace react crate

dear dare read

post stop spot

Код

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
#define DIFFERENCE ('A' - 'a') // разность регистров
using namespace std;
bool IsBigAlpha(char a) {
	return (a >= 'A' && a <= 'Z');
}
bool IsSmalAlpha(char a) {
	return (a >= 'a' && a <= 'z');
}
string edit(const string &str) { // приводим всё к нижнему регистру и  убираем лишние символы
	string rez = "";
	for(char a : str) {
		if (IsBigAlpha(a)) a -= DIFERENSE;
		if (IsSmalAlpha(a)) rez += a;
	}
	return rez;
}
bool comp(const pair<string, string> &a, const pair<string, string> &b) { // сравнитель по второй строке
	return a.second < b.second;
}
int main() {
	vector <pair<string, string>> words; // словарь
	string str;
	while (getline(cin, str, '\n')) {
		pair<string, string> word; // слово
		word.first = str;
		word.second = edit(str);
		sort(word.second.begin(), word.second.end()); // сортируем буквы в слове
		words.push_back(word);
	}
	sort(words.begin(), words.end(), comp); // сортируем словарь по анаграммам
	vector <int> indeces; // массив индексов
	int Count = 0, MaxCount = 0, n = words.size();
	for (int i = 1; i < n; i++) {
		if (words[i-1].second == words[i].second) Count++; 
		else {
			if (Count > MaxCount) { 
				MaxCount = Count;
				indeces.clear();
				indeces.push_back(i-1);
			} else if (Count == MaxCount) indeces.push_back(i-1);
			Count = 0;
		}
	}
	if (Count > MaxCount) {  // обрабатываем последний найденный набор анаграмм
				MaxCount = Count;
				indeces.clear();
				indeces.push_back(n-1);
	} else if (Count == MaxCount) indeces.push_back(n-1);
	bool first = 1;
	for (int index : indeces) { // выводим
		if (!first) cout << endl << "---------------" << endl;
		else first = 0;
		for (int i = 0; i <= MaxCount; i++) {
			if (i != 0) cout << endl;
			cout << words[index - i].first;
		}
	}
	return 0;
}

#include <iostream>

#include <string>

#include <algorithm>

#include <vector>

#define DIFFERENCE ('A' - 'a') // разность регистров

using namespace std;

bool IsBigAlpha(char a) {

return (a >= 'A' && a <= 'Z');

}

bool IsSmalAlpha(char a) {

return (a >= 'a' && a <= 'z');

}

string edit(const string &str) { // приводим всё к нижнему регистру и убираем лишние символы

string rez = "";

for(char a : str) {

if (IsBigAlpha(a)) a -= DIFERENSE;

if (IsSmalAlpha(a)) rez += a;

}

return rez;

}

bool comp(const pair<string, string> &a, const pair<string, string> &b) { // сравнитель по второй строке

return a.second < b.second;

}

int main() {

vector <pair<string, string>> words; // словарь

string str;

while (getline(cin, str, '\n')) {

pair<string, string> word; // слово

word.first = str;

word.second = edit(str);

sort(word.second.begin(), word.second.end()); // сортируем буквы в слове

words.push_back(word);

}

sort(words.begin(), words.end(), comp); // сортируем словарь по анаграммам

vector <int> indeces; // массив индексов

int Count = 0, MaxCount = 0, n = words.size();

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

if (words[i-1].second == words[i].second) Count++;

else {

if (Count > MaxCount) {

MaxCount = Count;

indeces.clear();

indeces.push_back(i-1);

} else if (Count == MaxCount) indeces.push_back(i-1);

Count = 0;

}

if (Count > MaxCount) { // обрабатываем последний найденный набор анаграмм

MaxCount = Count;

indeces.clear();

indeces.push_back(n-1);

} else if (Count == MaxCount) indeces.push_back(n-1);

bool first = 1;

for (int index : indeces) { // выводим

if (!first) cout << endl << "---------------" << endl;

else first = 0;

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

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

cout << words[index - i].first;

}

return 0;

}

Код на ideone

e-olymp 72. Дорога домой

26/12/2017 by Павел Жуков

Задача

Бедный Иа

Возвращаясь домой, после захватывающей игры в гостях у Винни Пуха, ослик Иа решил немного прогуляться. Поскольку во время прогулки он все время думал о своем приближавшемся дне рождения, то не заметил, как заблудился. Известно, что ослик во время прогулки всегда передвигается по определенному алгоритму: в начале прогулки он всегда начинает движение на северо-восток, делает при этом один шаг (перемещаясь при этом в точку [latex]left langle 1,1 right rangle[/latex]), потом меняет направление и двигается на юго-восток, далее на юго-запад, на северо-запад и так далее. При каждом изменении направления ослик всегда делает на [latex]n[/latex] шагов больше, чем было сделано до изменения направления.

Когда ослик все же решил возвратится домой, то обнаружил, что зашел глубоко в лес. Надвигалась ночь и Иа захотел поскорее попасть домой. Помогите узнать, удастся ли сегодня ослику попасть домой до заката солнца, если известно, что солнце зайдет через [latex]t[/latex] часов, а скорость передвижения ослика [latex]v[/latex] шагов в час (длина шага у ослика постоянна). Известно, что движение ослик начинал из точки с координатами [latex]left langle 0,0 right rangle[/latex], а его дом расположен в точке [latex]left langle x_{h},y_{h} right rangle[/latex], и направление движения он менял [latex]k[/latex] раз.

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

В первой строке задано четыре целых числа [latex]n[/latex], [latex]k[/latex], [latex]t[/latex], [latex]v[/latex] [latex](0leq n,k,t,vleq 100)[/latex] . Во второй строке размещено два целых числа [latex]x_{h}[/latex], [latex]y_{h}[/latex] – координаты домика ослика [latex](-10^5leq x_{h}, y_{h}leq 10^5)[/latex] .

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

Вывести Good night Ia, если ослик успеет дойти домой до заката солнца или Poor Ia в противоположном случае.

Тесты

Входные данные	Выходные данные
[latex]1[/latex] [latex]5[/latex] [latex]3[/latex] [latex]2[/latex] [latex]5[/latex] [latex]7[/latex]	Good night Ia
[latex]5[/latex] [latex]2[/latex] [latex]3[/latex] [latex]9[/latex] [latex]15[/latex] [latex]15[/latex]	Good night Ia
[latex]4[/latex] [latex]4[/latex] [latex]3[/latex] [latex]20[/latex] [latex]105[/latex] [latex]-105[/latex]	Poor Ia
[latex]3[/latex] [latex]4[/latex] [latex]2[/latex] [latex]3[/latex] [latex]40[/latex] [latex]-20[/latex]	Good night Ia
[latex]1[/latex] [latex]3[/latex] [latex]7[/latex] [latex]2[/latex] [latex]-24[/latex] [latex]0[/latex]	Poor Ia
[latex]1[/latex] [latex]3[/latex] [latex]7[/latex] [latex]2[/latex] [latex]-23[/latex] [latex]0[/latex]	Good night Ia

Первый вариант кода программы

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
    long int n, k, t, v, hx, hy;
    long int x = 0, y = 0;
    cin >> n >> k >> t >> v;
    cin >> hx >> hy;
    for(long int i = 0; i <= k; i++){
         if(i%4 == 0){ 
             x += 1 + n*i;
             y += 1 + n*i; 
         } else if (i%4 == 1){ 
             x += 1 + n*i;
             y -= 1 + n*i; 
         } else if(i%4 == 2){
             x -= 1 + n*i; 
             y -= 1 + n*i; 
         } else if(i%4 == 3){ 
             x -= 1 + n*i; 
             y += 1 + n*i; 
         } 
    } 
    if(t * t * v * v * 2 >= (x - hx) * (x - hx) + (y - hy) * (y - hy)){
        cout << "Good night Ia";
    } else {
        cout << "Poor Ia";
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

long int n, k, t, v, hx, hy;

long int x = 0, y = 0;

cin >> n >> k >> t >> v;

cin >> hx >> hy;

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

if(i%4 == 0){

x += 1 + n*i;

y += 1 + n*i;

} else if (i%4 == 1){

x += 1 + n*i;

y -= 1 + n*i;

} else if(i%4 == 2){

x -= 1 + n*i;

y -= 1 + n*i;

} else if(i%4 == 3){

x -= 1 + n*i;

y += 1 + n*i;

}

if(t * t * v * v * 2 >= (x - hx) * (x - hx) + (y - hy) * (y - hy)){

cout << "Good night Ia";

} else {

cout << "Poor Ia";

}

return 0;

}

Второй вариант кода программы

#include <iostream>
using namespace std;

int main() {
    long int n, k, t, v, hx, hy;
    cin >> n >> k >> t >> v >> hx >> hy;
    long int s1, s2, s3, s4;
    long int m1, m2, m3, m4;
    m1 = ((k + 1) % 4 >= 1) ? (k + 1) / 4 + 1 : (k + 1) / 4;
    m2 = ((k + 1) % 4 >= 2) ? (k + 1) / 4 + 1 : (k + 1) / 4;
    m3 = ((k + 1) % 4 >= 3) ? (k + 1) / 4 + 1 : (k + 1) / 4;
    m4 = (k + 1) / 4;
    s1 = (1 + (m1 - 1) * 2 * n) * m1;
    s2 = (1 + n + 2 * n * (m2 - 1)) * m2;
    s3 = (1 + 2 * n + 2 * n * (m3 - 1)) * m3;
    s4 = (1 + 3 * n + 2 * n * (m4 - 1)) * m4;
    long int x = s1 + s2 - s3 - s4, y = s1 - s2 - s3 + s4;
    if (t * t * v * v * 2 >= (x - hx) * (x - hx) + (y - hy) * (y - hy)){
        cout << "Good night Ia";
    } else {
        cout << "Poor Ia";
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long int n, k, t, v, hx, hy;

cin >> n >> k >> t >> v >> hx >> hy;

long int s1, s2, s3, s4;

long int m1, m2, m3, m4;

m1 = ((k + 1) % 4 >= 1) ? (k + 1) / 4 + 1 : (k + 1) / 4;

m2 = ((k + 1) % 4 >= 2) ? (k + 1) / 4 + 1 : (k + 1) / 4;

m3 = ((k + 1) % 4 >= 3) ? (k + 1) / 4 + 1 : (k + 1) / 4;

m4 = (k + 1) / 4;

s1 = (1 + (m1 - 1) * 2 * n) * m1;

s2 = (1 + n + 2 * n * (m2 - 1)) * m2;

s3 = (1 + 2 * n + 2 * n * (m3 - 1)) * m3;

s4 = (1 + 3 * n + 2 * n * (m4 - 1)) * m4;

long int x = s1 + s2 - s3 - s4, y = s1 - s2 - s3 + s4;

if (t * t * v * v * 2 >= (x - hx) * (x - hx) + (y - hy) * (y - hy)){

cout << "Good night Ia";

} else {

cout << "Poor Ia";

}

return 0;

}

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

Вариант 1

Разделим решение задачи на две части: поиск местоположения Иа после прогулки и расчет пути домой.
Имеем следующую формулу вычисления вектора нахождения Иа после прогулки:
[latex]sumlimits_{i=0}^k f(i, n)[/latex], где [latex]n[/latex] — изменение количества шагов Иа в каждой итерации, [latex]k[/latex] — cколько раз он менял движение, и функции:

[latex]f(x,y) = begin{cases} left langle1 + xy, 1 + xyright rangle & textit{if } xvdots 4 = 0 \ left langle1 + xy, (-1) cdot (1 + xy)right rangle & textit{if } xvdots 4 = 1 \ left langle(-1) cdot (1 + xy), (-1) \cdot (1 + xy)right rangle & textit{if } xvdots 4 = 2 \ left langle(-1) cdot (1 + xy), 1 + xyright rangle & textit{if } xvdots 4 = 3 end{cases}[/latex]

То есть, результат функции [latex]f(x,y)[/latex] это вектор, на который передвинулся Иа в итерации номер [latex]x[/latex] с изменением шага [latex]y[/latex], а результат [latex]sumlimits_{i=0}^k f(i, n)[/latex] — это вектор [latex]left langle a,b right rangle[/latex] местоположения Иа в конце прогулки. Теперь нужно посчитать расстояние между местоположением Иа и его домом. Считаем из вектора [latex]left langle a,b right rangle[/latex] и вектора [latex]left langle x_{h},y_{h} right rangle[/latex]:

$$sqrt{(x_{h} — a)^2 + (y_{h} — b)^2}$$

И считаем максимальное расстояние, которое может пройти Иа до заката солнца. Тут нужно учесть то, что скорость в условии измеряется в шагах в час, а шаг это расстояние между [latex]left langle 0,0 right rangle[/latex] и [latex]left langle 1,1 right rangle[/latex], то есть — [latex]sqrt{2}[/latex].

$$ sqrt{2} tv$$

Итого, выводим Good night Ia, если [latex]2t^2v^2 geq (x_{h} — a)^2 + (y_{h} — b)^2[/latex] и Poor Ia в противном случае.

Вариант 2

Если рассмотреть каждое направление спирали, как элемент арифметической прогрессии, то можно следующим образом получить алгоритм решения данной задачи с вычислительной сложностью [latex]O(1)[/latex]. Используем сумму арифметической прогрессии $S = displaystylefrac{a_1 + a_m}{2}$, где $a_m = 1+(m-1)d$

Для направления на северо-восток:
$$a_1 = 1, d = 4n Rightarrow S_{1}=frac{1 + 1 +4n(m_1-1)}{2}Rightarrow S_{1} = m_1(1+2n(m_1-1)),$$
где $m_1 = displaystylefrac{k+1}{4} + 1,$ если$ (k+1)vdots 4 >=1$ иначе, $m_1=displaystylefrac{k+1}{4}$

Для направления на юго-восток:
$$a_2 = 1+n, d = 4n Rightarrow S_{2} = m_2(1+n+2n(m_2-1)),$$
где $m_2 = displaystylefrac{k+1}{4} + 1,$ если$ (k+1)vdots 4 >=2$ иначе, $m_2=displaystylefrac{k+1}{4}$

Для направления на юго-запад:
$$a_3 = 1+2n, d = 4n Rightarrow S_{3} = m_3(1+2n+2n(m_3-1)),$$
где $m_3 = displaystylefrac{k+1}{4} + 1,$ если$ (k+1)vdots 4 >=3$ иначе, $m_3=displaystylefrac{k+1}{4}$

Для направления на северо-запад:
$$a_4 = 1+3n, d = 4n Rightarrow S_{4} = m_4(1+3n+2n(m_4-1)),$$
где $m_4 = displaystylefrac{k+1}{4} + 1,$ если$ (k+1)vdots 4 >=4$ иначе, $m_4=displaystylefrac{k+1}{4}$

Тогда, для вычисления координат [latex]left langle x,y right rangle[/latex] воспользуемся следующей формулами:
$$x = S_{1} + S_{2} — S_{3} — S_{4}$$
$$y = S_{1} — S_{2} — S_{3} + S_{4}$$
Последующие вычисления эквивалентны первому варианту решения.

Ссылки

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

e-olymp 6128. Простой дек

01/06/2017 by Сабиров Ильдар

Задача. Простой дек

Реализуйте структуру данных «дек». Напишите программу, содержащую описание дека и моделирующую работу дека, реализовав все указанные здесь методы. Программа считывает последовательность команд и в зависимости от команды выполняет ту или иную операцию. После выполнения каждой команды программа должна вывести одну строчку. Возможные команды для программы:

push_front

Добавить (положить) в начало дека новый элемент. Программа должна вывести ok.

push_back

Добавить (положить) в конец дека новый элемент. Программа должна вывести ok.

pop_front
Извлечь из дека первый элемент. Программа должна вывести его значение.

pop_back

Извлечь из дека последний элемент. Программа должна вывести его значение.

front

Узнать значение первого элемента (не удаляя его). Программа должна вывести его значение.

back

Узнать значение последнего элемента (не удаляя его). Программа должна вывести его значение.

size

Вывести количество элементов в деке.

clear

Очистить дек (удалить из него все элементы) и вывести ok.

exit

Программа должна вывести bye и завершить работу.

Гарантируется, что количество элементов в деке в любой момент не превосходит 100. Все операции:

pop_front
pop_back
front
back

всегда корректны.

Объяснение: Количество элементов во всех структурах данных не превышает 10000, если это не указано особо.

Тесты

№

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

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

push_back 3

push_back 14

size

clear

push_front 1

back

push_back 2

front

pop_back

size

pop_front

size

exit

bye

size

push_back 8

push_front 4

size

front

back

push_back 3

pop_front

front

pop_back

back

exit

bye

Решение

#include <iostream>
#include <vector>
#include <string>
using namespace std;
struct Deque
{
    vector<int> box1;
    vector<int> box2;
    int n, box_size=0;
    void push_front(int n)
    {
        box1.push_back(n);
        box_size++;
    }
    void push_back(int n)
    {
        box2.push_back(n);
        box_size++;
    }
    int pop_front()
    {
        if(box1.size()>0)
        {
            int a=box1[box1.size()-1];
            box1.erase(box1.end()-1);
            box_size--;
            return a;
        }
        else if(box2.size()>0)
        {
            int a=box2[0];
            box2.erase(box2.begin());
            box_size--;
            return a;
        }
        return 1;
    }
    int pop_back()
    {
        if(box2.size()>0)
        {
            int a=box2[box2.size()-1];
            box2.erase(box2.end()-1);
            box_size--;
            return a;
        }
        else if(box1.size()>0)
        {
            int a=box1[0];
            box1.erase(box1.begin());
            box_size--;
            return a;
        }
        return 1;
    }
    int front()
    {
        if(box1.size()>0)
        {
            int a=box1[box1.size()-1];
            return a;
        }
        else if(box2.size()>0)
        {
            int a=box2[0];
            return a;
        }
        return 1;
    }
    int back()
    {
        if(box2.size()>0)
        {
            int a=box2[box2.size()-1];
            return a;
        }
        else if(box1.size()>0)
        {
            int a=box1[0];
            return a;
        }
        return 1;
    }
    int size()
    {
        return box_size;
    }
    string clear()
    {
        box1.erase(box1.begin(), box1.end());
        box2.erase(box2.begin(), box2.end());
        box_size=0;
        return "ok";
    }
    string exit()
    {
        return "bye";
    }
};
int main() 
{
    Deque a;
    string s;
    while(cin>>s)
    {
        if(s=="push_front")
        {
            int n;
            cin>>n;
            a.push_front(n);
            cout<<"ok"<<endl;
        }
        if(s=="push_back")
        {
            int n;
            cin>>n;
            a.push_back(n);
            cout<<"ok"<<endl;
        }
        if(s=="pop_front")
        {
            cout<<a.pop_front()<<endl;
        }
        if(s=="pop_back")
        {
            cout<<a.pop_back()<<endl;
        }
        if(s=="front")
        {
            cout<<a.front()<<endl;
        }
        if(s=="back")
        {
            cout<<a.back()<<endl;
        }
        if(s=="size")
        {
            cout<<a.size()<<endl;
        }
        if(s=="clear"){
            a.clear();
            cout<<a.clear()<<endl;
        }
        if(s=="exit")
        {
            cout<<a.exit()<<endl;
            break;
        }
    }
    return 0;
}

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

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

#include <iostream>

#include <vector>

#include <string>

using namespace std;

struct Deque

{

vector<int> box1;

vector<int> box2;

int n, box_size=0;

void push_front(int n)

{

box1.push_back(n);

box_size++;

}

void push_back(int n)

{

box2.push_back(n);

box_size++;

}

int pop_front()

{

if(box1.size()>0)

{

int a=box1[box1.size()-1];

box1.erase(box1.end()-1);

box_size--;

return a;

}

else if(box2.size()>0)

{

int a=box2[0];

box2.erase(box2.begin());

box_size--;

return a;

}

return 1;

}

int pop_back()

{

if(box2.size()>0)

{

int a=box2[box2.size()-1];

box2.erase(box2.end()-1);

box_size--;

return a;

}

else if(box1.size()>0)

{

int a=box1[0];

box1.erase(box1.begin());

box_size--;

return a;

}

return 1;

}

int front()

{

if(box1.size()>0)

{

int a=box1[box1.size()-1];

return a;

}

else if(box2.size()>0)

{

int a=box2[0];

return a;

}

return 1;

}

int back()

{

if(box2.size()>0)

{

int a=box2[box2.size()-1];

return a;

}

else if(box1.size()>0)

{

int a=box1[0];

return a;

}

return 1;

}

int size()

{

return box_size;

}

string clear()

{

box1.erase(box1.begin(), box1.end());

box2.erase(box2.begin(), box2.end());

box_size=0;

return "ok";

}

string exit()

{

return "bye";

}

};

int main()

{

Deque a;

string s;

while(cin>>s)

{

if(s=="push_front")

{

int n;

cin>>n;

a.push_front(n);

cout<<"ok"<<endl;

}

if(s=="push_back")

{

int n;

cin>>n;

a.push_back(n);

cout<<"ok"<<endl;

}

if(s=="pop_front")

{

cout<<a.pop_front()<<endl;

}

if(s=="pop_back")

{

cout<<a.pop_back()<<endl;

}

if(s=="front")

{

cout<<a.front()<<endl;

}

if(s=="back")

{

cout<<a.back()<<endl;

}

if(s=="size")

{

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

}

if(s=="clear"){

a.clear();

cout<<a.clear()<<endl;

}

if(s=="exit")

{

cout<<a.exit()<<endl;

break;

}

return 0;

}

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

Реализация двусторонней очереди идет посредством векторов [latex]box1[/latex] и [latex]box2[/latex], поэтому нет необходимости делать проверку на переполнение. Команды [latex]push_front[/latex] и [latex]push_back[/latex] соответственно добавляют в концы векторов [latex]box1[/latex] и [latex]box2[/latex] элементы и увеличивают размер дека box_size (на единицу за каждый добавленный элемент). Рассмотрим команду [latex]front[/latex]. Проверяя присутствие элементов в [latex]box1[/latex] мы выводим последний элемент вектора, так как добавляли элемент с помощью [latex]push_front[/latex] в конец вектора [latex]box1[/latex]. Если же вектор [latex]box1[/latex] пуст, то выводим первый элемент вектора [latex]box2[/latex], который в случае пустого вектора [latex]box1[/latex] является первым элементом дека. Команда [latex]back[/latex] относительно [latex]front[/latex] с векторами работает инверсивно. Т.е. Проверяя присутствие элементов в [latex]box2[/latex] выводим последний элемент данного вектора. Если же вектор [latex]box2[/latex] пуст, то выводим первый элемент вектора [latex]box1[/latex] , который в случае пустого вектора [latex]box2[/latex] является последним элементом дека. С командами [latex]pop_front[/latex] и [latex]pop_back[/latex] работают идентично [latex]front[/latex] и [latex]back[/latex]. Отличие лишь в том, что команды [latex]pop[/latex] в дополнении к выводу элемента удаляют его, уменьшая размер дека [latex]box_size[/latex] (на единицу за каждый удаленный элемент). Команда [latex]size[/latex] выводит размер дека [latex]box_size[/latex]. Команда clear удаляет все элементы векторов [latex]box1[/latex], [latex]box2[/latex] и обнуляет размер дека. Команда [latex]exit[/latex] выводит «bye» и завершает работу программы. Команды принимаются из потока ввода посредством строки s.

Ссылка на код.

e-olymp.

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)

Монстр

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, так как моменты на данном промежутке не были равны ни разу. Если же вектор непустой, выходим первый элемент вектора. Он и будет искомым первым одновременным криком.

Код Хаффмана

15/04/2017 by Вадим Гордийчук

Задача

Дана строка, после которой следует символ перехода на следующую строку (далее — endl. Вывести:

Код графа на языке DOT, иллюстрирующий кодирование символов строки;
Символы строки и соответствующие им коды Хаффмана;
Закодированную строку.

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

Некоторая последовательность символов и endl.

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

Код графа на языке DOT, иллюстрирующий кодирование символов строки;
Символы строки и соответствующие им коды Хаффмана;
Закодированная строка.

Тест

Входные данные	Выходные данные
MOLOKO KIPIT	digraph G { "'MLO KITP', 12, code: ''" -> "'MLO', 5, code: '0'" [ label = "0" ]; "'MLO KITP', 12, code: ''" -> "' KITP', 7, code: '1'" [ label = "1" ]; "'MLO', 5, code: '0'" -> "'ML', 2, code: '00'" [ label = "0" ]; "'MLO', 5, code: '0'" -> "'O', 3, code: '01'" [ label = "1" ]; "'ML', 2, code: '00'" -> "'M', 1, code: '000'" [ label = "0" ]; "'ML', 2, code: '00'" -> "'L', 1, code: '001'" [ label = "1" ]; "' KITP', 7, code: '1'" -> "' K', 3, code: '10'" [ label = "0" ]; "' KITP', 7, code: '1'" -> "'ITP', 4, code: '11'" [ label = "1" ]; "' K', 3, code: '10'" -> "' ', 1, code: '100'" [ label = "0" ]; "' K', 3, code: '10'" -> "'K', 2, code: '101'" [ label = "1" ]; "'ITP', 4, code: '11'" -> "'I', 2, code: '110'" [ label = "0" ]; "'ITP', 4, code: '11'" -> "'TP', 2, code: '111'" [ label = "1" ]; "'TP', 2, code: '111'" -> "'T', 1, code: '1110'" [ label = "0" ]; "'TP', 2, code: '111'" -> "'P', 1, code: '1111'" [ label = "1" ]; } Codes of letters: 'O'(01) 'K'(101) 'I'(110) 'T'(1110) 'P'(1111) 'M'(000) 'L'(001) ' '(100) Encoded string: 00001001011010110010111011111101110

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

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

MOLOKO KIPIT

digraph G {
"'MLO KITP', 12, code: ''" -> "'MLO', 5, code: '0'" [ label = "0" ];
"'MLO KITP', 12, code: ''" -> "' KITP', 7, code: '1'" [ label = "1" ];
"'MLO', 5, code: '0'" -> "'ML', 2, code: '00'" [ label = "0" ];
"'MLO', 5, code: '0'" -> "'O', 3, code: '01'" [ label = "1" ];
"'ML', 2, code: '00'" -> "'M', 1, code: '000'" [ label = "0" ];
"'ML', 2, code: '00'" -> "'L', 1, code: '001'" [ label = "1" ];
"' KITP', 7, code: '1'" -> "' K', 3, code: '10'" [ label = "0" ];
"' KITP', 7, code: '1'" -> "'ITP', 4, code: '11'" [ label = "1" ];
"' K', 3, code: '10'" -> "' ', 1, code: '100'" [ label = "0" ];
"' K', 3, code: '10'" -> "'K', 2, code: '101'" [ label = "1" ];
"'ITP', 4, code: '11'" -> "'I', 2, code: '110'" [ label = "0" ];
"'ITP', 4, code: '11'" -> "'TP', 2, code: '111'" [ label = "1" ];
"'TP', 2, code: '111'" -> "'T', 1, code: '1110'" [ label = "0" ];
"'TP', 2, code: '111'" -> "'P', 1, code: '1111'" [ label = "1" ];
}

Codes of letters:
'O'(01) 'K'(101) 'I'(110) 'T'(1110) 'P'(1111) 'M'(000) 'L'(001) ' '(100)

Encoded string:
00001001011010110010111011111101110

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

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

struct ltcode
{
    unsigned long long frequency;
    unsigned char letter;
    string code = "";
};

void zeroset(ltcode *c)
{
    for (unsigned int i = 0; i < 256; ++i)
    {
        c[i].frequency = 0;
        c[i].letter = i;
    }
}

bool f(ltcode x, ltcode y)
{
    if (x.frequency != y.frequency) return x.frequency > y.frequency;
    else return x.letter > y.letter;
}

struct B
{
    string list;
    int i;
    
    int left;
    int right;
    
    string code = "";
    
    B()
    {
        list = "";
        i = 0;
    }
};

void print_binary_tree(int num, vector <B> &tree)
{
    if (tree[num].list.size() > 1)
    {
        cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].left].list << "', " << tree[tree[num].left].i << ", code: \'" << tree[tree[num].left].code << "\'\" [ label = \"0\" ];\n";
        cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].right].list << "', " << tree[tree[num].right].i << ", code: \'" << tree[tree[num].right].code << "\'\" [ label = \"1\" ];\n";
        print_binary_tree(tree[num].left, tree);
        print_binary_tree(tree[num].right, tree);
    }
}

void print_tree_graph(vector <B> &tree)
{
    cout << "digraph G {\n";
    print_binary_tree(tree.size()-1, tree);
    cout << "}\n";
}

void huffman_encoding_in(int num, string code, vector <B> &tree, ltcode *letter_codes)
{
    tree[num].code = code;
    if (tree[num].list.size() > 1)
    {
        huffman_encoding_in(tree[num].left, code+"0", tree, letter_codes);
        huffman_encoding_in(tree[num].right, code+"1", tree, letter_codes);
    }
    else
    {
        for (int j = 0; ; ++j)
        {
            if (letter_codes[j].letter == tree[num].list[0])
            {
                letter_codes[j].code = code;
                break;
            }
        }
    }
}

void huffman_encoding(vector <B> &sorted_tree, ltcode *letter_codes)
{
    huffman_encoding_in(sorted_tree.size()-1, "", sorted_tree, letter_codes);
}

int main() {
    unsigned char c;
    string S;
    ltcode count[256], stringlinks[256];
    zeroset(count);

    while (scanf("%c", &c))
    {
        if (c == '\n') break;
        S += c;
        ++count[c].frequency;
    }
    sort(count, count+256, f);
    
    vector <B> tree;
    B tmp;
    tmp.list = "0";
    int j = 0, letter_amount;
    for (j = 0; (count[j].frequency); ++j)
    {
        tmp.i = count[j].frequency;
        tmp.list[0] = count[j].letter;
        tree.push_back(tmp);
    }
    int maxsize = j-1, size;
    
    sort(tree.begin(), tree.end(), [] (B a, B b)
    {
        if (a.i != b.i) return (a.i < b.i);
        else return (a.list.size() < b.list.size());
    });
    
    for (j = 0; size < maxsize;)
    {
        tmp.list = tree[j].list + tree[j+1].list;
        tmp.i = tree[j].i + tree[j+1].i;
        tmp.left = j;
        tmp.right = j+1;
        
        size = tmp.list.size();
        
        tree.push_back(tmp);
        j += 2;
        sort(tree.begin()+j, tree.end(), [] (B a, B b)
        {
            if (a.i != b.i) return (a.i < b.i);
            else return (a.list.size() < b.list.size());
        }
        );
    }
    huffman_encoding(tree, count);
    print_tree_graph(tree);
    cout << "\nCodes of letters:\n";
    for (j = 0; (count[j].frequency); ++j)
    {
        cout << '\'' << count[j].letter << "\'(" << count[j].code << ")  ";
        stringlinks[count[j].letter].code = count[j].code;
    }
    cout << "\n\nEncoded string:\n";
    for (unsigned int i = 0; i < S.size(); ++i)
    {
        cout << stringlinks[S[i]].code;
    }
    cout << '\n';
    return 0;
}

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

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

#include <iostream>

#include <algorithm>

#include <vector>

#include <string>

using namespace std;

struct ltcode

{

unsigned long long frequency;

unsigned char letter;

string code = "";

};

void zeroset(ltcode *c)

{

for (unsigned int i = 0; i < 256; ++i)

{

c[i].frequency = 0;

c[i].letter = i;

}

bool f(ltcode x, ltcode y)

{

if (x.frequency != y.frequency) return x.frequency > y.frequency;

else return x.letter > y.letter;

}

struct B

{

string list;

int i;

int left;

int right;

string code = "";

B()

{

list = "";

i = 0;

}

};

void print_binary_tree(int num, vector &tree)

{

if (tree[num].list.size() > 1)

{

cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].left].list << "', " << tree[tree[num].left].i << ", code: \'" << tree[tree[num].left].code << "\'\" [ label = \"0\" ];\n";

cout << "\"'" << tree[num].list << "', " << tree[num].i << ", code: \'" << tree[num].code << "\'\" -> \"'" << tree[tree[num].right].list << "', " << tree[tree[num].right].i << ", code: \'" << tree[tree[num].right].code << "\'\" [ label = \"1\" ];\n";

print_binary_tree(tree[num].left, tree);

print_binary_tree(tree[num].right, tree);

}

void print_tree_graph(vector &tree)

{

cout << "digraph G {\n";

print_binary_tree(tree.size()-1, tree);

cout << "}\n";

}

void huffman_encoding_in(int num, string code, vector &tree, ltcode *letter_codes)

{

tree[num].code = code;

if (tree[num].list.size() > 1)

{

huffman_encoding_in(tree[num].left, code+"0", tree, letter_codes);

huffman_encoding_in(tree[num].right, code+"1", tree, letter_codes);

}

else

{

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

{

if (letter_codes[j].letter == tree[num].list[0])

{

letter_codes[j].code = code;

break;

}

void huffman_encoding(vector &sorted_tree, ltcode *letter_codes)

{

huffman_encoding_in(sorted_tree.size()-1, "", sorted_tree, letter_codes);

}

int main() {

unsigned char c;

string S;

ltcode count[256], stringlinks[256];

zeroset(count);

while (scanf("%c", &c))

{

if (c == '\n') break;

S += c;

++count[c].frequency;

}

sort(count, count+256, f);

vector tree;

B tmp;

tmp.list = "0";

int j = 0, letter_amount;

for (j = 0; (count[j].frequency); ++j)

{

tmp.i = count[j].frequency;

tmp.list[0] = count[j].letter;

tree.push_back(tmp);

}

int maxsize = j-1, size;

sort(tree.begin(), tree.end(), [] (B a, B b)

{

if (a.i != b.i) return (a.i < b.i);

else return (a.list.size() < b.list.size());

});

for (j = 0; size < maxsize;)

{

tmp.list = tree[j].list + tree[j+1].list;

tmp.i = tree[j].i + tree[j+1].i;

tmp.left = j;

tmp.right = j+1;

size = tmp.list.size();

tree.push_back(tmp);

j += 2;

sort(tree.begin()+j, tree.end(), [] (B a, B b)

{

if (a.i != b.i) return (a.i < b.i);

else return (a.list.size() < b.list.size());

}

);

}

huffman_encoding(tree, count);

print_tree_graph(tree);

cout << "\nCodes of letters:\n";

for (j = 0; (count[j].frequency); ++j)

{

cout << '\'' << count[j].letter << "\'(" << count[j].code << ") ";

stringlinks[count[j].letter].code = count[j].code;

}

cout << "\n\nEncoded string:\n";

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

{

cout << stringlinks[S[i]].code;

}

cout << '\n';

return 0;

}

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

Для начала считываем посимвольно строку и запоминаем её, параллельно запоминая частоты появлений символов в ней в массиве count. Останавливаем считывание, когда встречается endl. После этого отсортировуем массив count в порядке убывания частот.

После этого элементы массива count, которые имеют ненулевую частоту, преобразовываем в элементы вектора tree (при этом символы конвертируются в строки), который после сортируется в порядке возрастания частот. Затем обрабатываем массив по алгортиму Хаффмана, объединяя элементы вектора с номерами [latex]j[/latex], [latex]j+1[/latex] в новый (который будет представлять собой структуру из конкатенации строк ранее упомянутых элементов и суммы их частот, а так же номеров его «предков»). После этого вектор вновь сортируется по частотам/суммам частот в порядке возрастания начиная с номера[latex]j+2[/latex], при этом элементы, которые имеют больший размер строк будут иметь меньший приоритет.

Такой алгоритм приводит к тому, что элементы с меньшей частотой/суммой частот не затрагиваются при добавлении новых, и система индексов (условных указателей на «предков») не нарушается.

После этого, используя поиск в глубину, кодируем элементы массива tree, начиная с последнего (строка которого в результате использования алгоритма всегда оказывается объединением всех символов). Остальная часть решения поставленной задачи — вопрос техники.

Ссылки

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

A327. Простые числа

13/11/2016 by Эммануил Прокопов

Задача из сборника задач по программированию Абрамова С.А. 2000г.
Даны натуральные числа [latex]a, b (a\le b)[/latex]. Получить все простые числа [latex]p[/latex], удовлетворяющие неравенствам [latex]a\le p\le b[/latex].

Входные данные:
Два натуральных числа [latex]a[/latex] и [latex]b[/latex].

Выходные данные:
Некоторое количество натуральных чисел.

Тесты.

№	Входные данные		Выходные данные
	[latex]a[/latex]	[latex]b[/latex]	[latex]p[/latex]
1	1	4	2, 3
2	0	1	Not found
3	5	5	5
4	6	20	7, 11, 13, 17, 19

Код программы (C++).

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

int main() {
    cout<<"Primes: ";
    bool prime;
    int a,b;
    cin>>a>>b;
    vector<int> primes;
    for(int e=2; e<=b; e++)
    {
        prime=true;
        for(int i=0; i<primes.size(); i++)
        {
            if((e%primes[i])==0) prime=false;
        }
        if(prime==true)
        {
            primes.push_back(e);
            if(e>=a) cout<<e<<" ";
        }
    }
    if(b<2) cout<<"Not found.";
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

cout<<"Primes: ";

bool prime;

int a,b;

cin>>a>>b;

vector<int> primes;

for(int e=2; e<=b; e++)

{

prime=true;

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

{

if((e%primes[i])==0) prime=false;

}

if(prime==true)

{

primes.push_back(e);

if(e>=a) cout<<e<<" ";

}

if(b<2) cout<<"Not found.";

return 0;

}

Код программы (Java).

import java.util.*;
import java.math.*;
 
class sieveOfEratosthenes
{
    public void find(int a, int b){
        boolean[] prime = new boolean[b+1];
        Arrays.fill(prime, Boolean.TRUE);
        prime[0] = false;
        prime[1] = false;
        for(int i = 2; i <= b; ++i){
            if(prime[i]){
                for(int j = i*i; j <= b; j += i){
                    prime[j] = false;
                }   
            }   
        }
 
        boolean primes_found = false; //Попадает ли в промежуток хоть одно простое число?
        for(int i = a; i <= b; ++i){
            if(prime[i]){
                System.out.print(i + " ");
                primes_found = true;
            }
        }
        if(!primes_found) System.out.print("Not found");
    }
}
 
class Main
{
    public static void main (String[] args)
    {
        Scanner in = new Scanner(System.in);
        int a, b;
        a = in.nextInt();
        b = in.nextInt();
        sieveOfEratosthenes c = new sieveOfEratosthenes();
        c.find(a, b);
    }
}

import java.util.*;

import java.math.*;

class sieveOfEratosthenes

{

public void find(int a, int b){

boolean[] prime = new boolean[b+1];

Arrays.fill(prime, Boolean.TRUE);

prime[0] = false;

prime[1] = false;

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

if(prime[i]){

for(int j = i*i; j <= b; j += i){

prime[j] = false;

}

boolean primes_found = false; //Попадает ли в промежуток хоть одно простое число?

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

if(prime[i]){

System.out.print(i + " ");

primes_found = true;

}

if(!primes_found) System.out.print("Not found");

}

class Main

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

int a, b;

a = in.nextInt();

b = in.nextInt();

sieveOfEratosthenes c = new sieveOfEratosthenes();

c.find(a, b);

}

Решение.
C++:
Для начала, вводятся два целых числа. Очевидно, что придётся проверять, являются ли простыми числа, большие чем [latex]a[/latex] и меньшие чем [latex]b[/latex]. Не представляется возможным заранее узнать, насколько большими будут эти числа, потому, на мой взгляд, наиболее подходящим решением будет каждый запуск программы заново находить все простые числа до [latex]b[/latex]. Создаётся вектор, в котором они будут храниться (целесообразно использовать именно вектор, поскольку неизвестно точно, сколько чисел придётся хранить). Далее идёт цикл, в котором каждое число от двух до [latex]b[/latex], если оно не делится нацело ни на один из элементов вектора (это проверяется при по мощи вложенного цикла), добавляется в этот вектор и, если оно больше чем [latex]a[/latex], выводится. В случае, если [latex]b<2[/latex], очевидно, простые числа найдены не будут, потому выводится "Not found."
Java:
Решение на Java представляет собой реализацию Решета Эратосфена.
Код на ideone.com: C++, Java.
Условие задачи (с.135)

ML30. Объём параллелепипеда

29/10/2016 by Оля Вдовиченко

Задача. Найти объём параллелепипеда три стороны которого образованы векторами [latex] \overrightarrow{a}=(a_x,a_y,a_z),[/latex] [latex]\overrightarrow{b}=(b_x,b_y,b_z)[/latex] и [latex]\overrightarrow{c}=(c_x,c_y,c_z).[/latex]

Входные данные: Координаты векторов [latex]\overrightarrow{a},[/latex] [latex] \overrightarrow{b},[/latex] [latex]\overrightarrow{c}. [/latex]

Выходные данные: Объём параллелепипеда.

Тесты

Входные данные	Выходные данные
0 0 1 0 1 0 1 0 0	1
0 0 0 1 0 0 0 0 1	0
1 0 0 0 0 1 0 0 1	0
2 5 3 4 1 0 -2 7 6	18
3 5 1 0 -7 2 6 -4 5	21

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

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

int main() {
    double ax, ay, az, bx, by, bz, cx, cy, cz, V, V1;
    cin >> ax >> ay >> az >> bx >> by >> bz >> cx >> cy >> cz; //Ввод координат векторов.
    V = (ax*((by*cz)+(cy*bz)))-ay*((bx*cz)+(cx*bz))+az*((bx*cy)+(cx*by)); //Вычисление объёма.
    cout << abs(V); //Выводим модуль значения определителя.
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double ax, ay, az, bx, by, bz, cx, cy, cz, V, V1;

cin >> ax >> ay >> az >> bx >> by >> bz >> cx >> cy >> cz; //Ввод координат векторов.

V = (ax*((by*cz)+(cy*bz)))-ay*((bx*cz)+(cx*bz))+az*((bx*cy)+(cx*by)); //Вычисление объёма.

cout << abs(V); //Выводим модуль значения определителя.

return 0;

}

Решение

Для решения данной задачи можно составить матрицу и вывести из неё формулу для нахождения определителя:
[latex]\triangle = \begin{vmatrix}a_x & a_y & a_z \\ b_x & b_y & b_z \\ c_x & c_y & c_z\end{vmatrix} =[/latex] [latex] a_x \left(b_y c_z+c_y b_z\right)[/latex] [latex]-a_y \left(b_x c_z+c_x b_z\right)+[/latex] [latex]a_z\left(b_x c_y+c_x b_y\right).[/latex]

Модуль определителя матрицы равен объёму параллелепипеда.

Решение на ideone.

ML 27. Угол между векторами

03/10/2016 by Лена Бригарь

Условие:

Найти угол в градусах, минутах и секундах между векторами [latex]\overrightarrow{a}=(a_x,a_y,a_z)[/latex] и [latex]\overrightarrow{b}=(b_x,b_y,b_z)[/latex].

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

Координаты векторов [latex] \overrightarrow{a}[/latex] и [latex]\overrightarrow{b}[/latex].

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

Угол в градусах, минутах и секундах.

Тесты

№	Входные данные	Выходные данные
1	1 1 4 20 31 12	53° 1′ 23″
2	1 61 12 1 11 1	7° 17′ 33″
3	1 0 0 0 0 1	90° 0′ 0″
4	-1 0 1 -2 2 1	44° 59′ 59″

Код

#define _USE_MATH_DEFINES
#include 
#include 
using namespace std;

int main() {
    double ax, ay, az, bx, by, bz, mdla, mdlb, mdlab, ccos, ugl;
    int gr = 0,mn=0, sc=0;
    cin >> ax >> ay >> az >> bx >> by >> bz;
    mdla = sqrt(ax*ax + ay*ay + az*az); //формула длины вектора
    mdlb = sqrt(bx*bx + by*by + bz*bz);
    mdlab = mdla*mdlb;
    ccos = (ax*bx + ay*by + az*bz) / mdlab; // формула косинус угла между векторами
    ugl = acos(ccos)*180/M_PI;// получим угол по формуле перевода радиан в градусы
    gr = ugl; // найдем градусы
    ugl -= gr;
    mn = ugl * 60; // оставшаяся часть угла в минутах
    ugl -= (double)mn / 60;
    sc = ugl * 3600; // оставшаяся часть угла в секундах
    cout << gr << "° " << mn << "' " << sc << "''";
    return 0;
}

#define _USE_MATH_DEFINES

#include

using namespace std;

int main() {

double ax, ay, az, bx, by, bz, mdla, mdlb, mdlab, ccos, ugl;

int gr = 0,mn=0, sc=0;

cin >> ax >> ay >> az >> bx >> by >> bz;

mdla = sqrt(ax*ax + ay*ay + az*az); //формула длины вектора

mdlb = sqrt(bx*bx + by*by + bz*bz);

mdlab = mdla*mdlb;

ccos = (ax*bx + ay*by + az*bz) / mdlab; // формула косинус угла между векторами

ugl = acos(ccos)*180/M_PI;// получим угол по формуле перевода радиан в градусы

gr = ugl; // найдем градусы

ugl -= gr;

mn = ugl * 60; // оставшаяся часть угла в минутах

ugl -= (double)mn / 60;

sc = ugl * 3600; // оставшаяся часть угла в секундах

cout << gr << "° " << mn << "' " << sc << "''";

return 0;

}

Решение:

Для решения данной задачи необходимо найти косинус между векторами, а после перевести радианы в градусы.
Косинус между векторами найдем по формуле [latex] \cos \alpha = \frac{\vec{a}\vec{b}}{\left|\vec{a} \right|\left|\vec{b} \right|}[/latex] .
Скалярное произведение найдем по формуле [latex] \left|\vec{a} \right| \left|\vec{b} \right|={a}_{x}{b}_{x}+{a}_{y}{b}_{y}+{a}_{z}{b}_{z} [/latex] .
Модуль вектора найдем по формуле [latex] \left|\vec{a} \right| = \sqrt{ {{a}_{x}}^{2}+{{a}_{y}}^{2}+{{a}_{z}}^{2} } [/latex] ; [latex] \left|\vec{b} \right| = \sqrt{ {{b}_{x}}^{2}+{{b}_{y}}^{2}+{{b}_{z}}^{2} } [/latex] .
Затем переведем радианы в градусы по формуле [latex] \frac{180}{ \arccos (-1.0) \arccos (\cos \alpha )} [/latex] .
[latex] \arccos (-1.0) [/latex] это число [latex] \pi [/latex] .

Ссылки:

Решение задачи на ideone.com: http://ideone.com/Gx3IVU
Косинус угла между векторами: http://ru.onlinemschool.com/math/library/vector/angl/
Скалярное произведение векторов: http://ru.onlinemschool.com/math/library/vector/multiply/
Модуль вектора: http://ru.onlinemschool.com/math/library/vector/length/
Перевод радиан в градусы: http://www.cleverstudents.ru/trigonometry/radian_and_degree_conversion.html
Условие задачи: https://cpp.mazurok.com/mtasks/

ML28. Объём тетраэдра

28/09/2016 by Вадим Гордийчук

Задача

Найти объём тетраэдра три стороны которого образованы векторами [latex]\vec {a} = \left( x_a, y_a, z_a \right)[/latex], [latex]\vec {b} = \left( x_b, y_b, z_x \right)[/latex], [latex]\vec {c} = \left( x_c, y_c, z_c \right)[/latex].

Пояснительный рисунок

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

Координаты векторов [latex]\vec {a}[/latex], [latex]\vec {b}[/latex], [latex]\vec {c}[/latex].

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

Объём тетраэдра.

Тесты

Входные данные									Выходные данные
[latex]x_a[/latex]	[latex]y_a[/latex]	[latex]z_a[/latex]	[latex]x_b[/latex]	[latex]y_b[/latex]	[latex]z_b[/latex]	[latex]x_c[/latex]	[latex]y_c[/latex]	[latex]z_c[/latex]	[latex]V[/latex]
0	0	1	0	1	0	1	0	0	0.166667
3	6	3	1	3	-2	2	2	2	3
0	0	0	1	3	-2	2	2	2	0

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

#include <iostream>
using namespace std;
int main()
{
    double Ax, Ay, Az, Bx, By, Bz, Cx, Cy, Cz, V;
    cin >> Ax >> Ay >> Az >> Bx >> By >> Bz >> Cx >> Cy >> Cz; //Считывание координат векторов.
    V = (Ax * (By * Cz - Bz * Cy) - Bx * (Ay * Cz - Az * Cy) + Cx * (Ay * Bz - Az * By)) / 6.0; //Подсчитывание объёма.
    if (V < 0) V *= -1; //Определитель матрицы может быть отрицательным числом, объём - нет. Поэтому если объём отрицательный, умножаем его на -1.
    cout << V; //Вывод объёма.
}

#include <iostream>

using namespace std;

int main()

{

double Ax, Ay, Az, Bx, By, Bz, Cx, Cy, Cz, V;

cin >> Ax >> Ay >> Az >> Bx >> By >> Bz >> Cx >> Cy >> Cz; //Считывание координат векторов.

V = (Ax * (By * Cz - Bz * Cy) - Bx * (Ay * Cz - Az * Cy) + Cx * (Ay * Bz - Az * By)) / 6.0; //Подсчитывание объёма.

if (V < 0) V *= -1; //Определитель матрицы может быть отрицательным числом, объём - нет. Поэтому если объём отрицательный, умножаем его на -1.

cout << V; //Вывод объёма.

}

import java.util.*;

public class Main
{
    public static void main (String[] args) throws java.lang.Exception
    {
        Scanner in = new Scanner(System.in);
        double
            Ax = in.nextDouble(),
            Ay = in.nextDouble(),
            Az = in.nextDouble(),
            Bx = in.nextDouble(),
            By = in.nextDouble(),
            Bz = in.nextDouble(),
            Cx = in.nextDouble(),
            Cy = in.nextDouble(),
            Cz = in.nextDouble();
        double V = (Ax * (By * Cz - Bz * Cy) - Bx * (Ay * Cz - Az * Cy) + Cx * (Ay * Bz - Az * By)) / 6.0;
        if (V < 0) V *= -1;
        System.out.print(V);
    }
}

import java.util.*;

public class Main

{

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

{

Scanner in = new Scanner(System.in);

double

Ax = in.nextDouble(),

Ay = in.nextDouble(),

Az = in.nextDouble(),

Bx = in.nextDouble(),

By = in.nextDouble(),

Bz = in.nextDouble(),

Cx = in.nextDouble(),

Cy = in.nextDouble(),

Cz = in.nextDouble();

double V = (Ax * (By * Cz - Bz * Cy) - Bx * (Ay * Cz - Az * Cy) + Cx * (Ay * Bz - Az * By)) / 6.0;

if (V < 0) V *= -1;

System.out.print(V);

}

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

Так как тетраэдр построен на векторах [latex]\vec {a} = \left( x_a, y_a, z_a \right)[/latex], [latex]\vec {b} = \left( x_b, y_b, z_x \right)[/latex], [latex]\vec {c} = \left( x_c, y_c, z_c \right)[/latex], для данной задачи оптимальным решением будет использовать следующие формулы:

[latex]V = \frac {|\Delta|} {6}[/latex], где [latex]V[/latex] — объём тетраэдра, а [latex]\Delta[/latex] — определитель матрицы.
[latex] \Delta =
\begin{vmatrix}
x_a & y_a & z_a \\
x_b & y_b & z_b \\
x_c & y_c & z_c
\end{vmatrix}
= x_a \left(y_b z_c-z_b y_c \right)-x_b \left( y_a z_c-z_a y_c \right)+x_c \left( y_a z_b-z_a y_b \right)
[/latex].

Итоги:

если значение определителя матрицы равно нулю, то либо некоторые из заданных векторов коллинеарны, либо нулевые, либо все они лежат в одной плоскости. Во всех этих случаях тетраэдр не может существовать, и программа выведет [latex]0[/latex];
если значение определителя не равно нулю, то программа вычислит объём тетраэдра. В случае, если определитель примет отрицательное значение, программа домножит значение объёма на [latex]-1[/latex], в результате чего оно станет положительным.

Ссылки

ML29. Площадь тетраэдра

25/09/2016 by Алла Марокко

Тетраэдр

Задача. Найти площадь полной поверхности тетраэдра три стороны которого образованы векторами [latex]\overrightarrow{a}=(a_x,a_y,a_z)[/latex], [latex] \overrightarrow{b}=(b_x,b_y,b_z)[/latex] и [latex]\overrightarrow{c}=(c_x,c_y,c_z)[/latex].
Тесты:

№	Вход									Выход
№	[latex]a_x[/latex]	[latex]a_y[/latex]	[latex]a_z[/latex]	[latex]b_x[/latex]	[latex]b_y[/latex]	[latex]b_z[/latex]	[latex]c_x[/latex]	[latex]c_y[/latex]	[latex]c_z[/latex]	[latex]S[/latex]
1	-3	3	3	3	-3	3	3	3	-3	69.3607
2	-1	1	1	1	-1	1	1	1	-1	7.70674
3	-2	2	2	2	-2	2	2	2	-2	30.827
4	0	0	1	1	0	0	1	1	-1	2.07313

Код на C++:

#include <iostream>
#include <cmath>
using namespace std;
 
int main() {
    double ax, ay, az, bx, by, bz, cx, cy, cz;//обозначим переменные
    cin >> ax >> ay >> az >> bx >> by >> bz >> cx >> cy >> cz;//введём переменные
    double A1A2 = sqrt(ax*ax+ay*ay+az*az); //вычислим длину ребра А1A2
    double A1A3 = sqrt(bx*bx+by*by+bz*bz);//вычислим длину ребра А1A3
    double cosa =(ax*bz+ay*by+az*bz)/(A1A2*A1A3);//вычислим косинус угла между ребрами А1A2 и А1A3
    double sina =sqrt(1-cosa*cosa);//вычислим их синус
    double s1 = 0.5*A1A2*A1A3*sina;//найдём площадь поверхности
    double A1A4 = sqrt(cx*cx+cy*cy+cz*cz);//вычислим длину ребра А1A4
    double cosb =(ax*cx+ay*cy+az*cz)/(A1A2*A1A4);//вычислим косинус угла между ребрами А1A2 и А1A4
    double sinb =sqrt(1-cosb*cosb);//вычислим их синус
    double s2 = 0.5*A1A2*A1A4*sinb;//найдём площадь поверхности
    double cosc =(bx*cx+by*cy+bz*cz)/(A1A2*A1A3);//вычислим косинус угла между ребрами А1A3 и А1A4
    double sinc =sqrt(1-cosc*cosc);//вычислим их синус
    double s3 = 0.5*A1A3*A1A4*sinc;//найдём площадь поверхности
    double A2A3 = sqrt((cx-bx)*(cx-bx)+(cy-by)*(cy-by)+(cz-bz)*(cz-bz));//вычислим длину ребра А2A3
    double A2A4 = sqrt((cx-ax)*(cx-ax)+(cy-ay)*(cy-ay)+(cz-az)*(cz-az));//вычислим длину ребра А2A4
    double cosd =((cx-bx)*(cx-ax)+(cy-ay)*(cy-by)+(cz-az)*(cz-bz))/(A2A3*A2A4);//вычислим косинус угла между ребрами А2A3 и А2A4
    double sind =sqrt(1-cosd*cosd);//вычислим их синус
    double s4 = 0.5*A2A3*A2A4*sind;//найдём площадь поверхности
    double s = s1+s2+s3+s4;//найдём площадь полной поверхности
    cout << s ;//выведем её результат
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

double ax, ay, az, bx, by, bz, cx, cy, cz;//обозначим переменные

cin >> ax >> ay >> az >> bx >> by >> bz >> cx >> cy >> cz;//введём переменные

double A1A2 = sqrt(ax*ax+ay*ay+az*az); //вычислим длину ребра А1A2

double A1A3 = sqrt(bx*bx+by*by+bz*bz);//вычислим длину ребра А1A3

double cosa =(ax*bz+ay*by+az*bz)/(A1A2*A1A3);//вычислим косинус угла между ребрами А1A2 и А1A3

double sina =sqrt(1-cosa*cosa);//вычислим их синус

double s1 = 0.5*A1A2*A1A3*sina;//найдём площадь поверхности

double A1A4 = sqrt(cx*cx+cy*cy+cz*cz);//вычислим длину ребра А1A4

double cosb =(ax*cx+ay*cy+az*cz)/(A1A2*A1A4);//вычислим косинус угла между ребрами А1A2 и А1A4

double sinb =sqrt(1-cosb*cosb);//вычислим их синус

double s2 = 0.5*A1A2*A1A4*sinb;//найдём площадь поверхности

double cosc =(bx*cx+by*cy+bz*cz)/(A1A2*A1A3);//вычислим косинус угла между ребрами А1A3 и А1A4

double sinc =sqrt(1-cosc*cosc);//вычислим их синус

double s3 = 0.5*A1A3*A1A4*sinc;//найдём площадь поверхности

double A2A3 = sqrt((cx-bx)*(cx-bx)+(cy-by)*(cy-by)+(cz-bz)*(cz-bz));//вычислим длину ребра А2A3

double A2A4 = sqrt((cx-ax)*(cx-ax)+(cy-ay)*(cy-ay)+(cz-az)*(cz-az));//вычислим длину ребра А2A4

double cosd =((cx-bx)*(cx-ax)+(cy-ay)*(cy-by)+(cz-az)*(cz-bz))/(A2A3*A2A4);//вычислим косинус угла между ребрами А2A3 и А2A4

double sind =sqrt(1-cosd*cosd);//вычислим их синус

double s4 = 0.5*A2A3*A2A4*sind;//найдём площадь поверхности

double s = s1+s2+s3+s4;//найдём площадь полной поверхности

cout << s ;//выведем её результат

return 0;

}

Код на Java:

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

class Main{
    public static void main (String[] args) throws java.lang.Exception{
                Scanner in = new Scanner(System.in);
                PrintWriter out = new PrintWriter(System.out);
                double ax = in.nextDouble();
                double ay = in.nextDouble();
                double az = in.nextDouble();
                double bx = in.nextDouble();
                double by = in.nextDouble();
                double bz = in.nextDouble();
                double cx = in.nextDouble();
                double cy = in.nextDouble();
                double cz = in.nextDouble();
                double A1A2 = Math.sqrt(ax*ax+ay*ay+az*az); //вычислим длину ребра А1A2
                double A1A3 = Math.sqrt(bx*bx+by*by+bz*bz);//вычислим длину ребра А1A3
                double cosa =(ax*bz+ay*by+az*bz)/(A1A2*A1A3);//вычислим косинус угла между ребрами А1A2 и А1A3
                double sina = Math.sqrt(1-cosa*cosa);//вычислим их синус
                double s1 = 0.5*A1A2*A1A3*sina;//найдём площадь поверхности
                double A1A4 = Math.sqrt(cx*cx+cy*cy+cz*cz);//вычислим длину ребра А1A4
                double cosb =(ax*cx+ay*cy+az*cz)/(A1A2*A1A4);//вычислим косинус угла между ребрами А1A2 и А1A4
                double sinb = Math.sqrt(1-cosb*cosb);//вычислим их синус
                double s2 = 0.5*A1A2*A1A4*sinb;//найдём площадь поверхности
                double cosc =(bx*cx+by*cy+bz*cz)/(A1A2*A1A3);//вычислим косинус угла между ребрами А1A3 и А1A4
                double sinc = Math.sqrt(1-cosc*cosc);//вычислим их синус
                double s3 = 0.5*A1A3*A1A4*sinc;//найдём площадь поверхности
                double A2A3 = Math.sqrt((cx-bx)*(cx-bx)+(cy-by)*(cy-by)+(cz-bz)*(cz-bz));//вычислим длину ребра А2A3
                double A2A4 = Math.sqrt((cx-ax)*(cx-ax)+(cy-ay)*(cy-ay)+(cz-az)*(cz-az));//вычислим длину ребра А2A4
                double cosd =((cx-bx)*(cx-ax)+(cy-ay)*(cy-by)+(cz-az)*(cz-bz))/(A2A3*A2A4);//вычислим косинус угла между ребрами А2A3 и А2A4
                double sind = Math.sqrt(1-cosd*cosd);//вычислим их синус
                double s4 = 0.5*A2A3*A2A4*sind;//найдём площадь поверхности
                double s = s1+s2+s3+s4;//найдём площадь полной поверхности
                System.out.println(s) ;//выведем её результат
        }
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Main{

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

Scanner in = new Scanner(System.in);

PrintWriter out = new PrintWriter(System.out);

double ax = in.nextDouble();

double ay = in.nextDouble();

double az = in.nextDouble();

double bx = in.nextDouble();

double by = in.nextDouble();

double bz = in.nextDouble();

double cx = in.nextDouble();

double cy = in.nextDouble();

double cz = in.nextDouble();

double A1A2 = Math.sqrt(ax*ax+ay*ay+az*az); //вычислим длину ребра А1A2

double A1A3 = Math.sqrt(bx*bx+by*by+bz*bz);//вычислим длину ребра А1A3

double cosa =(ax*bz+ay*by+az*bz)/(A1A2*A1A3);//вычислим косинус угла между ребрами А1A2 и А1A3

double sina = Math.sqrt(1-cosa*cosa);//вычислим их синус

double s1 = 0.5*A1A2*A1A3*sina;//найдём площадь поверхности

double A1A4 = Math.sqrt(cx*cx+cy*cy+cz*cz);//вычислим длину ребра А1A4

double cosb =(ax*cx+ay*cy+az*cz)/(A1A2*A1A4);//вычислим косинус угла между ребрами А1A2 и А1A4

double sinb = Math.sqrt(1-cosb*cosb);//вычислим их синус

double s2 = 0.5*A1A2*A1A4*sinb;//найдём площадь поверхности

double cosc =(bx*cx+by*cy+bz*cz)/(A1A2*A1A3);//вычислим косинус угла между ребрами А1A3 и А1A4

double sinc = Math.sqrt(1-cosc*cosc);//вычислим их синус

double s3 = 0.5*A1A3*A1A4*sinc;//найдём площадь поверхности

double A2A3 = Math.sqrt((cx-bx)*(cx-bx)+(cy-by)*(cy-by)+(cz-bz)*(cz-bz));//вычислим длину ребра А2A3

double A2A4 = Math.sqrt((cx-ax)*(cx-ax)+(cy-ay)*(cy-ay)+(cz-az)*(cz-az));//вычислим длину ребра А2A4

double cosd =((cx-bx)*(cx-ax)+(cy-ay)*(cy-by)+(cz-az)*(cz-bz))/(A2A3*A2A4);//вычислим косинус угла между ребрами А2A3 и А2A4

double sind = Math.sqrt(1-cosd*cosd);//вычислим их синус

double s4 = 0.5*A2A3*A2A4*sind;//найдём площадь поверхности

double s = s1+s2+s3+s4;//найдём площадь полной поверхности

System.out.println(s) ;//выведем её результат

}

Решение:
Координаты векторов находим по формуле:
[latex] \overrightarrow{A_2A_4}=(c_x-a_x,c_y-a_y,c_z-a_z) [/latex] здесь [latex] a_x, a_y, a_z[/latex] — координаты точки [latex]A_2[/latex]; [latex]c_x, c_y, c_z[/latex] — координаты точки [latex]A_4[/latex];
Таким же образом находим остальные координаты векторов.
Модули векторов (длина ребер пирамиды)
Длина вектора [latex]\overrightarrow{a}(a_x;a_y;a_z)[/latex] выражается через его координаты формулой:
[latex] \left| \overrightarrow{A_1A_2} \right| =\sqrt { ({ a_x) }^{ 2 }+({ a_y) }^{ 2 }+({ a_z) }^{ 2 } } [/latex];
Таким же способом находим другие модули векторов.
Площадь грани можно найти по формуле:
[latex] s_1=\frac { 1 }{ 2 } \vec{A_1} \times \vec{A_2} \sin \angle{A_2A_3} [/latex] где
[latex] \sin \angle{ A_2A_3 =\sqrt { 1-{ (\cos \angle{ A_2A_3) } }^{ 2 } } } [/latex] Так же будем находить и другие.
Найдем угол между ребрами [latex] A_1A_2(a_x;a_y;a_z) [/latex] и [latex] A_1A_3(b_x;b_y;b_z) [/latex]:
[latex] \cos \angle{ A_2A_3 =\frac { a_x b_x+a_y b_y+a_z b_z }{ \left| A_2A_3 \right| } } [/latex] Так мы найдём и другие 3 площади граней.
Площадь полной поверхности.
[latex] s=s_1+s_2+s_3+s_4. [/latex]

Ссылки:

Онлайн компилятор ideone C++ .
Онлайн компилятор ideone Java .
Онлайн калькулятор .

ML33. Угол между вектором и осями координат

19/09/2016 by Курьянов Павел

Задача

Найдите углы между вектором [latex] \overrightarrow{a}=(x,y,z)[/latex] и координатными осями [latex]Ox, Oy, Oz[/latex].

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

Координаты вектора [latex]\overrightarrow{a}=(x,y,z)[/latex].

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

Угол между заданным вектором и [latex]Ox[/latex].
Угол между заданным вектором и [latex]Oy[/latex].
Угол между заданным вектором и [latex]Oz[/latex].

Тесты

Входные данные			Выходные данные
x	y	z	угол c Ox	угол c Oy	угол c Oz
0	0	1	90	90	0
0	9999.99	0	90	0	90
1	1	1	54.7456	54.7456	54.7456
-9999.5	-9999.5	-9999.5	-54.7456	-54.7456	-54.7456
0	0	0	невозможно при нулевом векторе

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

#include 
#include 
using namespace std;
 
int main() {
  double x,y,z, cosx,cosy,cosz;
  cin>>x>>y>>z;//вводим координаты нашего вектора
    if (x==0 && y==0 && z==0)//проверяем не является ли наш вектор нулевым
    {
      cout<<"Невозможно при нулевом векторе";//если у нас нулевой ветор выводить ошибку
    }
    else
    {
      cosx=x/(sqrt(x*x+y*y+z*z));//при ином условии подсчитываем косинусы углов между вектором и осями координат
      cosy=y/(sqrt(x*x+y*y+z*z));
      cosz=z/(sqrt(x*x+y*y+z*z));
      cout<<acos(cosx)*180/M_PI<<" "<<acos(cosy)*180/M_PI<<" "<<acos(cosz)*180/M_PI;// выводим полученые углы координат в градусах
    }
    return 0;
}

#include

using namespace std;

int main() {

double x,y,z, cosx,cosy,cosz;

cin>>x>>y>>z;//вводим координаты нашего вектора

if (x==0 && y==0 && z==0)//проверяем не является ли наш вектор нулевым

{

cout<<"Невозможно при нулевом векторе";//если у нас нулевой ветор выводить ошибку

}

else

{

cosx=x/(sqrt(x*x+y*y+z*z));//при ином условии подсчитываем косинусы углов между вектором и осями координат

cosy=y/(sqrt(x*x+y*y+z*z));

cosz=z/(sqrt(x*x+y*y+z*z));

cout<<acos(cosx)*180/M_PI<<" "<<acos(cosy)*180/M_PI<<" "<<acos(cosz)*180/M_PI;// выводим полученые углы координат в градусах

}

return 0;

}

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

Для начала проверим не является ли заданный вектор нулевым, так как он не будет образовывать угол между векторами. Если это нулевой, то выводить, что это невозможно при нулевом векторе. При другом условии решим задачу,а поскольку в условии нам даны координаты только 1 вектора, а для вычисления угла между 2 векторами нужно 2 пары координат, то будем считать, что [latex] Ox(1,0,0) [/latex], [latex] Oy(0,1,0) [/latex],[latex] Oz(0,0,1) [/latex].
Теперь мы можем вычислить угол между векторами через формулу[latex] \cos{ |\widehat { a,b } }|=\frac { \overrightarrow { a } \overrightarrow { b } }{ \left| \overrightarrow { a } \right| \left| \overrightarrow { b } \right| } [/latex], где [latex] \overrightarrow { a } \overrightarrow { b }=\ x_a\cdot{x_b}+y_a\cdot{y_b}+z_a\cdot{z_b}\[/latex] и [latex] { \left| \overrightarrow { a } \right| }=\sqrt{x_a^2+y_a^2+z_a^2} [/latex], которую можно сократить в соответствии с нашими значениями координат [latex]Ox,Oy,Oz [/latex] и в итоге получаем формулу [latex] \arccos=\frac{o}{\sqrt{x_a^2+y_a^2+z_a^2}} [/latex], где [latex] O [/latex] ось координат и [latex]o [/latex] значение по этой оси координат. В эту формулу поочередно подставляем наши значения и получаем косинусы углов между осями координат и заданным вектором. Для вычисления углов в радианах воспользуемся встроенной функцией [latex] acos [/latex], а для вычисления в градусах домножим полученный результат на 180 и разделим на встроенное значение числа [latex] \pi [/latex].

Ссылки
Ideone

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)
Производим необходимые арифметические операции для нахождения значения второй формулы.
Вывод значений.
Ссылка на код

А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.

A287

31/03/2016 by Настя Филипчук

Задача A287

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

Даны целые числа [latex] a_{1}\dots a_{n} [/latex]. Все члены последовательности с четными номерами, предшествующие первому по порядку члену со значением [latex] max(a_{1}\dots a_{n}) [/latex], домножить на [latex] max(a_{1}\dots a_{n}) [/latex].

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

№	Входные данные	Выходные данные
1.	1 2 3 4 3 2 1	1 8 3 4 3 2 1
2.	1 2 3 4 4 2 5 5 3 3 2 1	1 10 3 20 4 10 5 5 3 3 2 1
3.	11 4 6 7 9	11 4 6 7 9
4.	9 8 10 1 2 4 5 4 6 13	9 104 10 13 2 52 5 52 6 13
5.	-10 -4 -6 -7 -3 0 -1 -20	-10 0 -6 0 -3 0 -1 -20

Реализация

#include "iostream"
#include <vector>
using namespace std;
 
int main()
{
	vector <int> a;
	int n;
	int max_i = 0; //номер максимального элемента
	while (cin >> n) 
		a.push_back(n); 
	for (int i=0; i < a.size(); i++)
	{
		if (a[i] > a[max_i])
			 max_i=i;
	}
	for (int i=0; i<max_i; i++)
	{
		if (i % 2 != 0)
			a[i] *= a[max_i];			
	}
	for (int i = 0; i < a.size(); i++)
		cout << a[i] << " ";
	return 0;
}

#include "iostream"

#include <vector>

using namespace std;

int main()

{

vector <int> a;

int n;

int max_i = 0; //номер максимального элемента

while (cin >> n)

a.push_back(n);

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

{

if (a[i] > a[max_i])

max_i=i;

}

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

{

if (i % 2 != 0)

a[i] *= a[max_i];

}

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

cout << a[i] << " ";

return 0;

}

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

Считываем все целые числа до конца входного потока и записываем их в вектор [latex] a [/latex]. Затем:

Сравниваем между собой каждый элемент вектора, и если находится большее значение, то запоминается номер данного элемента.
Далее проходим все члены последовательности, предшествующие первому по порядку члену с максимальным значением.
Умножаем все элементы с четными номерами на [latex] max(a_{1}\dots a_{n}) [/latex].

Ссылки

Код на ideaone.

A293

29/03/2016 by Алина Гончарова

Задача

Даны целые числа [latex]a_1,\ldots,a_n[/latex].

Если в данной последовательности ни одно четное число не расположено после нечетного,

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

Тесты

Входные данные	Выходные данные
-1 -4 5 7	7 5
1 2 3 4 5 -6	5 4 3 2 1
2 1 1 1 1	—

Алгоритм

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

Код

#include <cmath>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
 
int main() {
    vector <int> a, b;
    int element;
    while (cin >> element) {
        a.push_back(element);
    }
    bool getNegative = true;
    for (int i = 0; i < a.size() - 1; i++) {
        if (abs(a[i]) % 2 == 1 && a[i + 1] % 2 == 0) {
            getNegative = false;
            break;
        }
    }
    if (getNegative) {
        for (int i = a.size() - 1; i >= 0; i--) {
            if (a[i] < 0) {
                b.push_back(a[i]);
            }
        }
    } else {
        for (int i = a.size() - 1; i >= 0; i--) {
            if (a[i] > 0) {
                b.push_back(a[i]);
            }
        }
    }
    for (int i = 0; i < b.size(); i++) {
        cout << b[i] << " ";
    }
    return 0;
}

#include <cmath>

#include <vector>

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

vector <int> a, b;

int element;

while (cin >> element) {

a.push_back(element);

}

bool getNegative = true;

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

if (abs(a[i]) % 2 == 1 && a[i + 1] % 2 == 0) {

getNegative = false;

break;

}

if (getNegative) {

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

if (a[i] < 0) {

b.push_back(a[i]);

}

} else {

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

if (a[i] > 0) {

b.push_back(a[i]);

}

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

cout << b[i] << " ";

}

return 0;

}

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

A299

26/03/2016 by Сплошнов Кирилл

Условие

Дана последовательность действительных чисел [latex]a_1, a_2, \dots, a_n[/latex]. Требуется домножить все члены последовательности на квадрат её наименьшего члена, если [latex]a_1 \geq 0[/latex], в противном случае — на квадрат наибольшего.

Решение

Для решения воспользуемся стандартным классом vector. Для этого заведем переменную данного типа, заполним её числами со входного потока. Далее, в зависимости от первого (нулевого) элемента вектора, воспользуемся стандартной функцией min_element() или max_element() (библиотека algorithm). Далее умножим каждый элемент на (соответственно) минимум/максимум и выведем последовательность.

Тесты

№	Входные данные	Выходные данные
1	-2 2 43 5 -10 12 0 -1	-3698 3698 79507 9245 -18490 22188 0 -1849
2	0 100 99 0 -1 1	0 100 99 0 -1 1
3	42 1 1 1 0 -1 24 -24 -42	74088 1764 1764 1764 0 -1764 42336 -42336 -74088

Код

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

int main() 
{
	vector<int> x;
	int a;
	while (cin >> a)
		x.push_back(a);
	if (x.at(0) >= 0)
	{
		int min = *min_element(x.begin(), x.end());
		for (int &i : x)
			i *= min * min;
	}
	else
	{
		int max = *max_element(x.begin(), x.end());
		for (int &i : x)
			i *= max * max;
	}
	for (int i : x)
		cout << i << " ";
	return 0;
}

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main()

{

vector<int> x;

int a;

while (cin >> a)

x.push_back(a);

if (x.at(0) >= 0)

{

int min = *min_element(x.begin(), x.end());

for (int &i : x)

i *= min * min;

}

else

{

int max = *max_element(x.begin(), x.end());

for (int &i : x)

i *= max * max;

}

for (int i : x)

cout << i << " ";

return 0;

}

Замечание

Перед изменением значения членов последовательности и их выводом нам необходимо найти минимум или максимум, для чего необходимо знать значения всех её членов. В связи с этим, решить задачу в формате «считал — вывел» (потоковой обработкой) невозможно.

Ссылки

Код на ideaone (vector).

А282б

16/03/2016 by Антон Локтев

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

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

Данную задачу можно найти здесь.

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

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

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

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

Тесты

№	Входные данные	Выходные данные
1	1 2 3 4 5 6	1 6 2 5 3 4
2	0 0 0 0 0 1	0 1 0 0 0 0
3	3 12 42 -6 15 0 0 0 501 20 20 20	3 20 12 20 42 20 -6 501 15 0 0 0
4	42 0 17 -2.6 -54 41888 0.25 13 1.3333 -284.73	42 -284.73 0 1.3333 17 13 -2.6 0.25 -54 41888
5	0 1 -1 0 1 -1 97 113 -7.777 0 48 -69	0 -69 1 48 -1 0 0 -7.777 1 113 -1 97

Код

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    vector <double> sequence, result_sequence;
    double term_of_sequence;
    while (cin >> term_of_sequence){
        sequence.push_back(term_of_sequence);
    }
    for (int i = 0; i < sequence.size() / 2; i++){
        result_sequence.push_back(sequence[i]);
        result_sequence.push_back(sequence[sequence.size() - 1 - i]);
    }
    for (int i = 0; i < result_sequence.size(); i++){
        cout << result_sequence[i] << " ";
    }
    return 0;
}

#include <iostream>

#include <vector>

using namespace std;

int main() {

vector <double> sequence, result_sequence;

double term_of_sequence;

while (cin >> term_of_sequence){

sequence.push_back(term_of_sequence);

}

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

result_sequence.push_back(sequence[i]);

result_sequence.push_back(sequence[sequence.size() - 1 - i]);

}

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

cout << result_sequence[i] << " ";

}

return 0;

}

Код на ideone можно найти здесь.

Ход решения

Считываем все числа из входного потока и записываем их в вектор исходной последовательности sequence. Результатом работы нашей программы должна быть новая последовательность действительных чисел result_sequence, которая задаётся по следующему правилу: первый член новой последовательности совпадает с первым членом исходной, второй член новой последовательности является последним членом исходной, третий – второй член исходной и так далее до исчерпания чисел. Иными словами, новая последовательность из [latex]2n[/latex] чисел на нечётных номерах имеет члены исходной последовательности (от первого и до [latex]n[/latex]-го включительно), чётным же номерам новой последовательности соответствуют члены исходной с номерами от [latex]n+1[/latex] до [latex]2n[/latex] включительно, записанные в обратном порядке.