e-olymp 974. Флойд-1

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

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

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

В первой строке записано количество вершин графа n (1 ≤ n ≤ 100). В следующих n строках записано по n чисел — матрица смежности графа (j-ое число в i-ой строке соответствует весу ребра из вершины i в вершину j). Все числа по модулю не превышают 100. На главной диагонали матрицы — всегда нули.

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

Выведите n строк по n чисел — матрицу кратчайших расстояний между парами вершин. j-ое число в i-ой строке должно равняться весу кратчайшего пути из вершины i в вершину j.

Сам алгоритм хорошо описан на wikipedia

А вот сам код

#include <iostream>
using namespace std;

    
int main(){
    int n;
    cin >> n;
    int w[n][n];
    for( int i=0 ; i<n ; i++ ){
        for( int j=0 ; j<n ; j++ ){
            cin >> w[i][j];
        }
    }
    
    for( int k=0 ; k<n ; k++ ){
        for( int i=0 ; i<n ; i++ ){
            for( int j=0 ; j<n ; j++ ){
                w[i][j] = min(w[i][j], w[i][k]+w[k][j]);
            }
        }
    }
    
    for( int i=0 ; i<n ; i++ ){
        for( int j=0 ; j<n ; j++ ){
            cout << w[i][j] << " ";
        }
        cout<<endl;
    }
}

#include <iostream>

using namespace std;

int main(){

int n;

cin >> n;

int w[n][n];

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

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

cin >> w[i][j];

}

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

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

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

w[i][j] = min(w[i][j], w[i][k]+w[k][j]);

}

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

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

cout << w[i][j] << " ";

}

cout<<endl;

}

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

Related Images:

e-olimp 6129. Дек с защитой от ошибок

26/05/2016 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 программа должна проверять, содержится ли в деке хотя бы один элемент. Если во входных данных встречается операция pop_front, pop_back, front, back, и при этом дек пуст, то программа должна вместо числового значения вывести строку error.

#include <iostream>
#include <string>
using namespace std;
 
struct stack{
    int storage[1000];
    int end=0;
    int sizze=0;
    int start=1;
    int lol=100;
    int push_back(int x){
        end = (end + 1)%lol;
        storage[end] = x;
        sizze++;
    }
    int push_front(int x){start = (start - 1+lol)%lol;
                    storage[start] = x;
                    sizze++;}               
                    
    void pop_back(){end = (end - 1+lol)%lol;
                sizze--;}
    void pop_front(){start = (start + 1)%lol;
                sizze--;}           
                
    int back() const{return storage[end];}
    int size() const{return sizze;}
    void clear(){end = 0;
                sizze = 0;
                start = 1;
                }
                
    int front() const{
        return storage[start];
}
    
};

int main() {
    
    stack storage;
    string s;
    int n;
    
    while(cin >> s){
        if(s == "push_back"){
            cin >> n;
            storage.push_back(n);
            cout << "ok\n";
        }else if(s == "push_front"){
            cin >> n;
            storage.push_front(n);
            cout << "ok\n";
        }
        
        else if(s == "pop_back"){
            if(storage.size()){
                cout << storage.back() << endl;
                storage.pop_back();
            }else{
                cout << "error\n";
            }
        }else if(s == "pop_front"){
            if(storage.size()){
                cout << storage.front() << endl;
                storage.pop_front();
            }else{
                cout << "error\n";
            }
        }else if(s == "front"){
            if(storage.size()){
                cout << storage.front() << endl;
            }
            else{
                cout << "error\n";
            }
        }
        
        
        
        else if(s == "back"){
            if(storage.size()){
                cout << storage.back() << endl;
            }else{
                cout << "error\n";
            }
        }else if(s == "size"){
            cout << storage.size() << endl;
        }else if(s == "clear"){
            storage.clear();
            cout << "ok\n";
        }else if(s == "exit"){
            cout << "bye\n";
            return 0;
        }
    }
    return 0;
}

#include <iostream>

#include <string>

using namespace std;

struct stack{

int storage[1000];

int end=0;

int sizze=0;

int start=1;

int lol=100;

int push_back(int x){

end = (end + 1)%lol;

storage[end] = x;

sizze++;

}

int push_front(int x){start = (start - 1+lol)%lol;

storage[start] = x;

sizze++;}

void pop_back(){end = (end - 1+lol)%lol;

sizze--;}

void pop_front(){start = (start + 1)%lol;

sizze--;}

int back() const{return storage[end];}

int size() const{return sizze;}

void clear(){end = 0;

sizze = 0;

start = 1;

}

int front() const{

return storage[start];

}

};

int main() {

stack storage;

string s;

int n;

while(cin >> s){

if(s == "push_back"){

cin >> n;

storage.push_back(n);

cout << "ok\n";

}else if(s == "push_front"){

cin >> n;

storage.push_front(n);

cout << "ok\n";

}

else if(s == "pop_back"){

if(storage.size()){

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

storage.pop_back();

}else{

cout << "error\n";

}

}else if(s == "pop_front"){

if(storage.size()){

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

storage.pop_front();

}else{

cout << "error\n";

}

}else if(s == "front"){

if(storage.size()){

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

}

else{

cout << "error\n";

}

else if(s == "back"){

if(storage.size()){

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

}else{

cout << "error\n";

}

}else if(s == "size"){

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

}else if(s == "clear"){

storage.clear();

cout << "ok\n";

}else if(s == "exit"){

cout << "bye\n";

return 0;

}

return 0;

}

Решенная задача на e-olimp

Код на ideone

Related Images:

A280

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

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

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

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

#include <iostream>

using namespace std;

long double fact(int f){

if(f < 0)

return 0;

if (f == 0)

return 1;

else

return f * fact(f - 1);

}

int main()

{

long double x[31];

long double y[31];

x[1]=1;

x[2]=2;

y[1]=1;

y[2]=2;

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

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

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

}

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

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

cout<<x[i]<<endl;

}

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

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

cout<<y[i]<<endl;

}

return 0;

}

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

Related Images:

A276

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

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

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

#include <iostream>

using namespace std;

int main()

{

int a[31];

a[1]=1;

a[2]=1;

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

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

}

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

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

cout<<a[i]<<endl;

i++;

}

return 0;

}

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

Related Images:

Mloops3

30/10/2015 by Радик Сиденко

Задача:

Найдите закономерность и напишите программу, которая выводит аналогичную таблицу для любых чисел [latex]n>0[/latex] (количество столбцов) и [latex]m>0[/latex] (количество строк).

-*+*+*-*+*+*-*+*+*-*+*+*-
*+*+*-*+*+*-*+*+*-*+*+*-*
+*+*-*+*+*-*+*+*-*+*+*-*+
*+*-*+*+*-*+*+*-*+*+*-*+*
+*-*+*+*-*+*+*-*+*+*-*+*+
*-*+*+*-*+*+*-*+*+*-*+*+*
-*+*+*-*+*+*-*+*+*-*+*+*-
*+*+*-*+*+*-*+*+*-*+*+*-*

-*+*+*-*+*+*-*+*+*-*+*+*-

*+*+*-*+*+*-*+*+*-*+*+*-*

+*+*-*+*+*-*+*+*-*+*+*-*+

*+*-*+*+*-*+*+*-*+*+*-*+*

+*-*+*+*-*+*+*-*+*+*-*+*+

*-*+*+*-*+*+*-*+*+*-*+*+*

-*+*+*-*+*+*-*+*+*-*+*+*-

*+*+*-*+*+*-*+*+*-*+*+*-*

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

Количество столбцов [latex]n>0[/latex] и строк [latex]m>0[/latex]

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

Таблица размером [latex]n\quad x\quad m[/latex] из символов +*-.

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

#include <iostream>
using namespace std;

int main() {
	int n,m;
	cin>>n>>m; 
	
	for(int i=0; i<m;i++){
		for(int j=0;j<n;j++){
			cout<<(((i+j)%2==0)?(((i+j)%3==0)?"-":"+" ):"*");
		}
		cout<<endl;
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n,m;

cin>>n>>m;

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

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

cout<<(((i+j)%2==0)?(((i+j)%3==0)?"-":"+" ):"*");

}

cout<<endl;

}

return 0;

}

Решение:

У нас имеются две переменные [latex]n[/latex] и [latex]m[/latex] (количество столбцов и строк).
Нам надо создаем два цикла (for) один из которого содержит другой. Внешний цикл нужен для переноса на следующую строку внутренний же нужен для на рисования самих строк.

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

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

Related Images:

MLoop6

30/10/2015 by Радик Сиденко

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

Вычислите с точностью [latex]\varepsilon[/latex] значение функции [latex]f\left( x \right) =\cos x[/latex] . При вычислениях допустимо использовать только арифметические операции.

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

Для решения данной задачи я использовал Ряд Маклорена:.
[latex]\cos x = 1-\frac {x^{2}}{2!}+\frac{x^{4}}{4!}-\cdots = \displaystyle\sum_{n=0}^{\infty}\frac{(-1)^{n} }{(2n)!}x^{ 2n },x\in{C}[/latex].

Тесты:

X	E	Answer
1	0.0001	0.540278
1	0.000001	0.540303
-1	0.0001	0.540278
5	0.0001	0.283625

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

#include <iostream>
#include <cmath> 
using namespace std;
double cos (double x, double e) {
    double x2,c,n,f,z;
    x2= x*x;
    f= 2;
    c= 1;
    n= 2;
    z= -1; 
    while ((x2/f)>=e) {
        c=c+z*x2/f;
        n=n+2;
        x2=x2*x*x;
        f=f*(n-1)*n;
        z=z*(-1);
    }
    return c;
}
int main() {
    double x,e;
    cin>>x;
    cin>>e;
    cout<<cos(x,e)<<endl;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

double cos (double x, double e) {

double x2,c,n,f,z;

x2= x*x;

f= 2;

c= 1;

n= 2;

z= -1;

while ((x2/f)>=e) {

c=c+z*x2/f;

n=n+2;

x2=x2*x*x;

f=f*(n-1)*n;

z=z*(-1);

}

return c;

}

int main() {

double x,e;

cin>>x;

cin>>e;

cout<<cos(x,e)<<endl;

return 0;

}

Объяснение Кода:

В коде используются 7 переменных а именно: [latex]x[/latex], [latex]x2[/latex], [latex]c[/latex], [latex]e[/latex], [latex]n[/latex], [latex]f[/latex], [latex]z[/latex].
Переменная [latex]x[/latex] отвечает за [latex]x[/latex], [latex]x2[/latex] за [latex]{ x }^{ n }[/latex], [latex]c[/latex] за [latex]\cos x[/latex], [latex]e[/latex] за [latex]\varepsilon[/latex] (epsilon-точность вычисления), [latex]n[/latex] за порядковый номер, [latex]f[/latex] за [latex]n![/latex] и [latex]z[/latex] за [latex]{ (-1) }^{ n }[/latex].

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

Related Images:

e-olymp 1154. Кружок хорового пения.

30/09/2015 by Радик Сиденко

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

В некотором учебном заведении функционирует кружок хорового пения. Начало кружка всегда происходит единообразно: по сигналу руководителя кружка все [latex]N[/latex] участников становятся в круг и каждый [latex]M[/latex] -й для распевки поёт гамму.

Руководитель кружка заметил, что размять голосовые связки не всегда удаётся всем участникам кружка. По заданным [latex]N[/latex] и [latex]M[/latex] помогите ему определить, или в очередной раз в разминке примут участие все участники хора.

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

Входные данные состоят из нескольких тестовых случаев. Каждый тестовый случай расположен в отдельной строке и содержит два целых числа [latex]N[/latex] и [latex]M[/latex], где [latex]\left( 1 \le N, M \le {10}^{3} \right).[/latex]

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

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

Тесты:

n	m	answer
4	1	YES
6	3	NO

Решение:

Для начала нам надо найти наибольший общий делитель(НОД). Для этого хорошо подойдет алгоритм Евклида и если НОД равен единице то все ученики распоются и мы выводим «YES» в другом случае мы выводим «NO».

Код:

#include <iostream> 
using namespace std; 
int main() { 
    int n, m, p; 
    while(cin >> n >> m) {
        if (m > n) { 
            p = n; 
            n = m; 
            m = p; 
        } 
        while (m > 0) { 
            p = n % m; 
            if (p != 0) {
                n = m; 
                m = p; 
            } 
            else break; 
        } 
        cout<<(m==1?"YES": "NO")<<endl;
    } 
    return 0; 
}

#include <iostream>

using namespace std;

int main() {

int n, m, p;

while(cin >> n >> m) {

if (m > n) {

p = n;

n = m;

m = p;

}

while (m > 0) {

p = n % m;

if (p != 0) {

n = m;

m = p;

}

else break;

}

cout<<(m==1?"YES": "NO")<<endl;

}

return 0;

}

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

Related Images:

ML 1

27/09/2015 by Радик Сиденко

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

Даны два действительных числа [latex]a[/latex] и [latex]b[/latex]. Получить их сумму, разность и произведение.

Код №1

#include <iostream>
#include <cmath>
using namespace std;
int main() {
	long double a, b, sum;
	char z;
	cin >> a >> z >> b;
	if (z == '+') {
		sum = a + b;
	} else if (z== '-') {
		sum = a - b;
	} else if (z == '*') {
		sum = a * b;
	}
	cout << a << z << b << "= " << sum << endl;
	return 0;                   
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

long double a, b, sum;

char z;

cin >> a >> z >> b;

if (z == '+') {

sum = a + b;

} else if (z== '-') {

sum = a - b;

} else if (z == '*') {

sum = a * b;

}

cout << a << z << b << "= " << sum << endl;

return 0;

}

Тесты

a	z	b	sum
5	+	6	11
7	—	8	-1
9	*	11	99

Решение №1

Для создания данной программы я описал 4 переменных: [latex]a[/latex], [latex]b[/latex], [latex]z[/latex], sum. Для переменных [latex]a[/latex], [latex]b[/latex], [latex]sum[/latex] я взял тип переменных «long double» — так как не указано какие числа должны быть. Символом z мы обозначим переменную в типе «char» — так как мне надо указать знак операции. Для вычисления суммы надо ввести знак операции «+», для разности «-» и для произведения «*» выглядит все примерно так мы вводим (первое число «[latex]a[/latex]») (знак «[latex]z[/latex]» ) (второе число «[latex]b[/latex]») и получаем (ответ «[latex]sum[/latex]»).

Код №2

#include <iostream>
#include <cmath>
using namespace std;
int main() {
	long double a, b, sum;
	char z;
	cin >> a >> z >> b;
	if (z == '+') {
		sum = a + b;
	} else if (z== '-') {
		sum = a - b;
	} else if (z == '*') {
		sum = a * b;
	} else if (z == '/') {
		if (b==0){
			cout << "You can't divide by zero"<< endl;
            return 0;
		}
		sum = a / b;
	} else if (z == '%') {
		if (b==0){
			cout << "You can't take remainder of the division by zero"<< endl;
            return 0;
		}
		sum= fmod (a,b);
	}else if (z == '^') {
		sum=pow(a,b);
	}
	cout << a <<" "<< z <<" "<< b << " = " << sum << endl;
	return 0;                   
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

long double a, b, sum;

char z;

cin >> a >> z >> b;

if (z == '+') {

sum = a + b;

} else if (z== '-') {

sum = a - b;

} else if (z == '*') {

sum = a * b;

} else if (z == '/') {

if (b==0){

cout << "You can't divide by zero"<< endl;

return 0;

}

sum = a / b;

} else if (z == '%') {

if (b==0){

cout << "You can't take remainder of the division by zero"<< endl;

return 0;

}

sum= fmod (a,b);

}else if (z == '^') {

sum=pow(a,b);

}

cout << a <<" "<< z <<" "<< b << " = " << sum << endl;

return 0;

}

Решение №2

Это не то, что просили сделать изначально, но я думаю это тоже будет интересно.

Отличие от первого кода состоит в том, что я добавил дополнительные команды, а именно: деления «/», возведения в степень «^» и остаток от деления «%».

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

Ссылки

Условие задачи;
Код программы №1 на Ideone.com;
Код программы №2 на Ideone.com;

Related Images:

e-olymp 915. Прямоугольный или нет?

14/09/2015 by Радик Сиденко

Задача. Прямоугольный или нет?

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

Задано длины сторон треугольника. Определить, является ли этот треугольник прямоугольным.

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

В единственной строке задано 3 натуральных числа — длины сторон треугольника. Длины сторон не превышают 1000.

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

Вывести «YES» (без кавычек), если треугольник прямоугольный, или «NO» (без кавычек) в противном случае.

Тесты

a	b	c	answer
3	4	5	«YES»
1	2	3	«NO»
5	3	4	«YES»

Код:

#include <iostream>
#include <math.h>
using namespace std;
int main()
{
 long int a,b,c;
 cin>>a>>b>>c;
 cout << (((a*a)+(b*b))==(c*c)||((a*a)+(c*c))==(b*b)|| ((c*c)+(b*b))==(a*a)?"YES":"NO")<< endl; 
 return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main()

{

long int a,b,c;

cin>>a>>b>>c;

cout << (((a*a)+(b*b))==(c*c)||((a*a)+(c*c))==(b*b)|| ((c*c)+(b*b))==(a*a)?"YES":"NO")<< endl;

return 0;

}

Объяснение Кода:

Нам надо проверить является ли прямоугольным треугольник из сторон: a, b, c.

Я проверял через теорему Пифагора «В прямоугольном треугольнике площадь квадрата, построенного на гипотенузе, равна сумме площадей квадратов, построенных на катетах. (wikipedia)». То есть стороны подставлял в формулу [latex]a^2+b^2=c^2[/latex], где [latex]a[/latex] и [latex] b[/latex] катеты а [latex]c[/latex] гипотенуза. Если стороны подходят в формулу то можно построить прямоугольник и выводим «YES» в противном случае выводим «NO». Проверял я через тернарный оператор _?_:_ c проверкой трёх вариантов гипотенузы.

Ссылка на задачу в e-olimp.

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

Ссылка на пройденные тесты в e-olimp.

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

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

Author Archives: Радик Сиденко

e-olymp 974. Флойд-1

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

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

Related Images:

e-olimp 6129. Дек с защитой от ошибок

Задача:

Related Images:

A280

Related Images:

A276

Related Images:

Mloops3

Related Images:

MLoop6

Related Images:

e-olymp 1154. Кружок хорового пения.

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

Тесты:

Решение:

Код:

Related Images:

ML 1

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

Код №1

Тесты

Решение №1

Код №2

Решение №2

Ссылки

Related Images:

e-olymp 915. Прямоугольный или нет?

Тесты

Related Images: