e-olymp 3738. Простая сортировка

16/03/2021 by Verheles Vladyslav

Задача

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

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

В первой строке входного файла содержится число $N (1 \leqslant N \leqslant 100000)$ — количество элементов в массиве. Во второй строке находятся N целых чисел, по модулю не превосходящих $10^9$.

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

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

Тесты

№	Входные данные	Выходные данные
1	10 1 8 2 1 4 7 3 2 3 6	1 1 2 2 3 3 4 6 7 8
2	9 7 39 8 1 4 2 65 10 5	1 2 4 5 7 8 10 39 65
3	12 -3 7 -7 -11 40 -30 25 30 2 7 -30 1	-30 -30 -11 -7 -3 1 2 7 7 25 30 40

Код

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

int main() {
    int a;
    cin >> a;
    int* arr = new int[a];
    for (int i = 0; i < a; i++) { cin >> arr[i]; }
    sort(arr, arr + a);
    for (int i = 0; i < a; i++) { cout << arr[i] << ' '; }
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int a;

cin >> a;

int* arr = new int[a];

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

sort(arr, arr + a);

for (int i = 0; i < a; i++) { cout << arr[i] << ' '; }

}

Решение

Для решения задачи используем функцию сортировки из библиотеки algorithm. Для начала создаем одномерный массив, потом с помощью цикла записываем значения в массив. С помощью функции sort(), сортируем и записываем изменения в массив. Потом с помощью цикла выводим результат.

Ссылки

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

Related Images:

e-olymp 1243. Наименьшее общее кратное

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

Условие

Наименьшим общим кратным ($НОК$) множества натуральных чисел называется такое наименьшее натуральное число, которое делится на каждое число в этом множестве. Например, $НОК$ чисел $5$, $7$ и $15$ равно $105$.

Вам необходимо найти $НОК$ $m$ заданных чисел.

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

Первая строка содержит количество тестов. Каждый тест состоит из одной строки и содержит числа $m$ $n_1$ $n_2$ $n_3$ $\ldots$ $n_m$, где $m$($1 \leqslant m \leqslant 100$) — количество заданных чисел, $n_1$ $\ldots$ $n_m$ — сами числа. Все числа натуральные и лежат в границах $32$-битового целого.

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

Для каждого теста в отдельной строке вывести соответствующее значение $НОК$. Все выводимые числа лежат в границах $32$-битового целого.

Тесты

№	ввод	вывод
1	2 3 5 7 15 6 4 10296 936 1287 792 1	105 10296
2	3 1 36 5 2 2 2 2 2 5 987 1597 2584 4181 6765 10946 17711	36 2 38400890173772280
3	0

Код

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

int main() {
    int n, m;
    cin >>n;
    for(int i=0; i<n; i++) {
        cin >>m;
        int temp, ans;
        cin >>ans;
        for(int j=1; j<m; j++) {
            cin >>temp;
            ans = ans/__gcd(ans, temp)*temp;
        }
        cout <<ans <<endl;
    }
}

#include <iostream>

#include <algorithm>

using namespace std;

int main() {

int n, m;

cin >>n;

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

cin >>m;

int temp, ans;

cin >>ans;

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

cin >>temp;

ans = ans/__gcd(ans, temp)*temp;

}

cout <<ans <<endl;

}

Код с алгоритмом Евклида

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

int gcd(int a, int b) {
  while(a and b) {
    if(a>b)
      a %= b;
    else
      b %= a;
  }
  return a+b;
}

int main() {
    int n, m;
    cin >>n;
    for(int i=0; i<n; i++) {
        cin >>m;
        int temp, ans;
        cin >>ans;
        for(int j=1; j<m; j++) {
            cin >>temp;
            ans = ans/gcd(ans, temp)*temp;
        }
        cout <<ans <<endl;
    }
}

#include <iostream>

#include <algorithm>

using namespace std;

int gcd(int a, int b) {

while(a and b) {

if(a>b)

a %= b;

else

b %= a;

}

return a+b;

}

int main() {

int n, m;

cin >>n;

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

cin >>m;

int temp, ans;

cin >>ans;

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

cin >>temp;

ans = ans/gcd(ans, temp)*temp;

}

cout <<ans <<endl;

}

Решение

$\DeclareMathOperator{\lcm}{lcm}$
$НОК$ ($\lcm$) проще всего считается по формуле $\operatorname {lcm}(a,b)={\frac {|a\cdot b|}{\operatorname {gcd}(a,b)}}$, где $\gcd$ — $НОД$. Для $\lcm$ от более чем двух чисел справедлива следующая формула: $\operatorname {lcm}(a_{1},a_{2},\ldots ,a_{n})=\operatorname {lcm}(\operatorname {lcm}(a_{1},a_{2},\ldots ,a_{{n-1}}),a_{n})$, из которой видно, что подсчёт $\lcm$ от $n$ чисел сводится к вычислению $n-1$-ого $\lcm$ от очередного числа и предыдущего результата вычислений.

$НОД$ ($\gcd$) в коде считается при помощи стандартной функции __gcd(a, b) из стандартной библиотеки algorithm в первом варианте кода или по алгоритму Евклида во втором.

Ссылки

Related Images:

Дистанционные учебные курсы

12/09/2015 by Мазурок Игорь Евгеньевич

stepik.org

Начнем с курсов которые проходить легко и просто даже с планшета или мобильного. В эти курсы уже встроена система выполнения кода. Устанавливать ничего не потребуется. Можно проходить даже с мобильного телефона или планшета.

Ввыедение в С++ — для не очень уверенных в себе студентов. Решение простых задач без привлечения серьезных возможностей яззыка.
Программирование на языке C++ — обязательный для всех. Действительно что-то говориться о С++ и ООП.
Основы программирования на C. Задачи. Этот курс относится к языку Си, а не С++. Но он достаточно полезен для нас тем, что мы увидим классические средста ввода вывода и научимся отличать новые возможности С++ от классики императивного программирования. В этом курсе только ссылки на теоретический материал но огромное количество задач. Иногда число однотипных задач очень велико и это несколько утомляет, но судя по комментариям, многим это полезно. Если набраться терпения и пройти все 270 заданий, вы обоснованно почувствуете себя достаточно уверенно.

coursera.org

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

Основы разработки на C++ №1 на русском
Основы разработки на C++ №2 на русском
Algorithms #1 на английском. Очень хороший и сложный курс.
Algorithms #2 на английском. Такой же хороший и сложный как и первая часть.

http://www.princeton.edu/

Продолжение может быть таким:

10 октября 2016 стартует курс по Структурам данных. Довольно полезный. К сожалению, все больше учебных курсов становятся платными. Однако, есть возможность получить его бесплатно как вольный слушатель. Сертификата Вам в этом случае не выдадут, но знания получите
Во-первых, 3 октября 2016 началась первая часть учебного курса по Алгоритмам. Один из ведущих преподавателей знаменитый Роберт Седжвик. Даже если Вы опоздали к указанной дате (даже на год или два) стоит записаться и пройти.
Во-вторых, одновременно с предыдущим запускается ещё один курс Седжвика — Анализ алгоритмов

Заявленная трудоёмкость каждого из этих курсов 6-8 часов в неделю. Продолжительность — до начала марта.
Хочу предупредить, что оба курса очень сложны и реально придётся потратить много больше времени, чтобы во всём полностью разобраться.

По обоим курсам указано, что

No certificates, statements of accomplishment, or other credentials will be awarded in connection with this course.

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

http://online.stanford.edu/

Наша выпускница Татьяна Полунина порекомендовала другой курс, который только начался 3 октября 2016. Я не знаком детально с этим курсом, но полностью полагаюсь на рекомендацию и добавляю курс в список:

Tim Roughgarden. Algorithms: Design and Analysis, Part 1

Это курс из Стэнфордского университета и по окончании можно получить сертификат от преподавателя.

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

Не все студенты морально готовы проходить онлайн курсы на английском языке. Я уверен, что это стоит делать при любом уровне невладения английским. Однако, идя на уступки этой нерешительности, рекомендую несколько полезных курсов на русском языке. Все они стартуют с понедельника 10 октября 2016 и подготовлены для Coursera сотрудниками МФТИ.

Последний курс в этом списке требует от первокурсника очень серьёзного труда. Однако, он ценен тем, что имеет непосредственное отношение к одному из самых быстроразвивающихся направлений информационных технологий Big Data.

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

Чтобы тренироваться решать задачи мы будем чаще всего использовать сайт e-olymp.com. Также можно обратиться к

codewars.com — Решаем задачи («ката») разного уровня сложности и набираем уровень.
programmr.com — Будьте внимательны, есть ошибки в тестах. Например, задача на площадь треугольника предполагает целочисленное деление при вычислении полупериметра. (Проверялось 11.5.2017).
tutorialspoint.com — учебный курс с задачами.

Related Images:

А808 б

20/12/2014 by Сіренко Валерія Сергіївна

Задача :

Дан текст. Группы символов, разделенные пробелами (одним или несколькими) и не содержащие пробелов внутри себя, будем называть, как и прежде, словами. Найти все слова, содержащие наибольшее количество гласных латинских букв ( a, e, i, o, u ).

Тесты :

Исходный текст

Обработанный текст

Two households, both alike in dignity,
In fair Verona, where we lay our scene,
From ancient grudge break to new mutiny,
Where civil blood makes civil hands unclean.

households,
unclean.
alike
Verona,
ancient
makes
mutiny,
Where
break
grudge
civil
scene,
our
blood
where
fair
civil
dignity,
From
hands
new
to
Two
lay
we
in
both
In

For never was a story of more woe . Than this of Juliet and her Romeo.

Juliet Romeo never more woe for was a story of Than this of and her

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

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
 
int counter(string a){
	int c = 0;
	for (unsigned int i = 0; i < a.length(); i++){
		if (a[i]=='e'||'u'==a[i]||'o'==a[i]||'i'==a[i]||'a'==a[i]){
			c++;
		}
	}
	return c;
}
	bool mod(string a, string b){
	return counter(a) >  counter(b);
}
	int main() {
		vector <string> Words;
		string word;
		for (unsigned int i=0; cin >> word; i++){
			Words.push_back(word);
		}
			sort(Words.begin(),Words.end(), mod);
			for(auto i: Words){
			cout << i <<endl;
		}
	return 0;
}

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

using namespace std;

int counter(string a){

int c = 0;

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

if (a[i]=='e'||'u'==a[i]||'o'==a[i]||'i'==a[i]||'a'==a[i]){

c++;

}

return c;

}

bool mod(string a, string b){

return counter(a) > counter(b);

}

int main() {

vector <string> Words;

string word;

for (unsigned int i=0; cin >> word; i++){

Words.push_back(word);

}

sort(Words.begin(),Words.end(), mod);

for(auto i: Words){

cout << i <<endl;

}

return 0;

}

Ссылка на программу : http://ideone.com/xXCrPe

Решение :

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

Объявляем переменные – флаги и счетчики для всех видов слов.
Функция для завершения чтения слова и увеличение счетчика слова на единицу
Стандартный строковый объект класса string.
Ввод текста из стандартного потока ввода
Проход по символам текста
Считаем
Сортируем

Related Images:

Ю12.19

24/11/2014 by Марченко Філіп Олександрович

Задача: В имеющемся словаре найти группы слов, записанных одними и теми же буквами и отличающиеся только их порядком, то есть перестановкой, например, (КОРМА, КОМАР).

Код:

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

using namespace std;
int count_words (string s) //функция подсчитывает слова в строке
{
    s+=' ';
    int a = 0;
    for (size_t i=0; i<s.length(); i++)
        if (s[i]==' ') a++;
    return a;
}
string * cut_words (string s) //функция разрезает строку на слова и возвращает массив
{
    s+=' ';
    int c = 0;
    int p = 0;
    int i=0;
    string *s_return = new string [count_words(s)];
    while (s.length() != 0)
        {
            if (s[i] != ' ')
            {
                c++;
                i++;
            }
            else
            {
                i=0;
                s_return[p] = s.substr(0, c);
                s.erase(0, c+1);
                c = 0;
                p++;
            }
        }
   return s_return;
}

int main ()
{
    string s;
    getline (cin, s);
	string *s_return;
	s_return = cut_words(s);
	for (int i=0; i<count_words(s); i++)
    {
    	string s_tmp = s_return[i];
        if (s_tmp.empty())					//если ячейка пуста, то продолжаем дальше
            {
                continue;
            }
        else				//а если нет, то ищем перестановки.
        {
        	int p = 0;
            for (int j=i+1; j<count_words(s); j++)
            {
                if ( is_permutation (s_tmp.begin(), s_tmp.end(), s_return[j].begin()))	//если перестановка
                    if (s_tmp.length() == s_return[j].length())		//и если одинаковая длина слов
                    {
                        cout<<s_return[j]<<endl;		//выводим на экран
                        s_return[j].clear(); //очищаем строку
                        p++;
                    }
            }
            if (p>=1) cout<<s_tmp<<endl;	
        }
    }
    return 0;
}

#include <iostream>

#include <stdio.h>

#include <algorithm>

#include <string>

using namespace std;

int count_words (string s) //функция подсчитывает слова в строке

{

s+=' ';

int a = 0;

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

if (s[i]==' ') a++;

return a;

}

string * cut_words (string s) //функция разрезает строку на слова и возвращает массив

{

s+=' ';

int c = 0;

int p = 0;

int i=0;

string *s_return = new string [count_words(s)];

while (s.length() != 0)

{

if (s[i] != ' ')

{

c++;

i++;

}

else

{

i=0;

s_return[p] = s.substr(0, c);

s.erase(0, c+1);

c = 0;

p++;

}

return s_return;

}

int main ()

{

string s;

getline (cin, s);

string *s_return;

s_return = cut_words(s);

for (int i=0; i<count_words(s); i++)

{

string s_tmp = s_return[i];

if (s_tmp.empty()) //если ячейка пуста, то продолжаем дальше

{

continue;

}

else //а если нет, то ищем перестановки.

{

int p = 0;

for (int j=i+1; j<count_words(s); j++)

{

if ( is_permutation (s_tmp.begin(), s_tmp.end(), s_return[j].begin())) //если перестановка

if (s_tmp.length() == s_return[j].length()) //и если одинаковая длина слов

{

cout<<s_return[j]<<endl; //выводим на экран

s_return[j].clear(); //очищаем строку

p++;

}

if (p>=1) cout<<s_tmp<<endl;

}

return 0;

}

Тесты:

Исходный словарь	Обработанный словарь
the and a to I is of have you he it in not was that his do on with she at say her for as are we but can him they up what out me go get this from be look my there know all one no see will back into like if were then an come think so down your them would about man take just by am now over make been or time when hand who want here tell off right their turn two through eye head other how some more around door room face day where way night well thing open away give only something ask move stand good find again little try too still hear walk before leave sit let long call feel close very why which car any hold work run never start even light than after put yes stop old watch first may talk another cut mean pull behind smile our toward towards much its house keep place begin nothing year woman side because three seem wait need moment himself stare arm use voice last late across sure front sound big really name should new anything against guy kill point small happen wall black step window life maybe fall own far under boy	no on three there own now how who thing night its sit name mean
Все слова

Алгоритм:

Для решения данной задачи я воспользовался возможностью, которую мне предоставляет библиотека <algorithm> . Поскольку мне надо было проверить, являются ли строки перестановками строки s_tmp, которую я ставлю в роли исходной с каждой итерацией, я воспользовался функцией is_permutation . Если некая строка является перестановкой, то она выводится на экран и стирается. С последующими итерациями будет проводится проверка на наличие на том или ином месте строки. Если строки обнаружено не будет, программа перейдёт к следующей итерации.

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

UPD: Поскольку я понял, что вводить вначале количество слов неудобно, я решил написать функцию, которая сама создаст массив из введённой мной строкой.