e-olymp 978. Получи дерево

26/04/2016 by Павел Загинайло

Задача с сайта e-olymp.com.

Условие

Дан связный неориентированный граф без петель и кратных ребер. Разрешается удалять из него ребра. Требуется получить дерево.

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

Первая строка содержит количество вершин [latex]n[/latex] (1 ≤ [latex]n[/latex] ≤ 100) и количество ребер [latex]m[/latex] графа. Следующие [latex]m[/latex] пар чисел задают ребра графа. Гарантируется, что граф связный.

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

Выведите [latex]n — 1[/latex] пару чисел — ребра, которые войдут в дерево. Ребра можно выводить в любом порядке.

Код

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


/*
Объявляем структуру Ребро, которой будем пользоваться для построения графа и дерева
*/
struct edge{
    int x, y; //вершины
    edge(){}
    edge(int a, int b){
        x = a;
        y = b;
    }
};

int main() {
    int n, m;
    cin >> n >> m;
    
    vector <edge> graph (m); //ребра исходного графа
    vector <edge> tree; //ребра дерева
    vector <int> variety (n); //множество вершин
    
    /*
    variety[n] = m - вершина n принадлежит множеству m.
    Следующий цикл определяет для каждой вершины свое множество
    */
    for (int i = 0; i < n; i++){
        variety[i] = i;
    }
    
    /*
    Заполняем ребра исходного графа значениями из стандартного ввода
    */
    for (int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        graph[i].x = a;
        graph[i].y = b;
    }
    
    /*
    Проверяем вершины каждого ребра. 
    Если вершины не принадлежат одному и тому же множеству, 
    но такое ребро добавляем в наше дерево, а вершины помещаем в одно множество
    */
    for (int i = 0; i < m; i++){
        int a = graph[i].x;
        int b = graph[i].y;
        if (variety[a] != variety[b]){
            tree.push_back(graph[i]);
            int old_variety = variety[b], new_variety = variety[a];
            for (int j = 0; j < n; j++){
                if (variety[j] == old_variety){
                    variety[j] = new_variety;
                }
            }
            
            
            
        }
    }

    
    for(int i = 0; i < n - 1; i++){ //по принципу построения дерева, оно содержит n-1 ребро
        cout << tree[i].x << " " << tree[i].y;
        if (i != n-2){
            cout << endl;
        }
    }
    return 0;
}

#include <algorithm>

#include <iostream>

#include <vector>

using namespace std;

Объявляем структуру Ребро, которой будем пользоваться для построения графа и дерева

struct edge{

int x, y; //вершины

edge(){}

edge(int a, int b){

x = a;

y = b;

}

};

int main() {

int n, m;

cin >> n >> m;

vector <edge> graph (m); //ребра исходного графа

vector <edge> tree; //ребра дерева

vector <int> variety (n); //множество вершин

variety[n] = m - вершина n принадлежит множеству m.

Следующий цикл определяет для каждой вершины свое множество

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

variety[i] = i;

}

Заполняем ребра исходного графа значениями из стандартного ввода

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

int a, b;

cin >> a >> b;

graph[i].x = a;

graph[i].y = b;

}

Проверяем вершины каждого ребра.

Если вершины не принадлежат одному и тому же множеству,

но такое ребро добавляем в наше дерево, а вершины помещаем в одно множество

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

int a = graph[i].x;

int b = graph[i].y;

if (variety[a] != variety[b]){

tree.push_back(graph[i]);

int old_variety = variety[b], new_variety = variety[a];

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

if (variety[j] == old_variety){

variety[j] = new_variety;

}

for(int i = 0; i < n - 1; i++){ //по принципу построения дерева, оно содержит n-1 ребро

cout << tree[i].x << " " << tree[i].y;

if (i != n-2){

cout << endl;

}

return 0;

}

Тесты

Ввод	Вывод
4 4 1 2 2 3 3 4 4 1	1 2 2 3 3 4
6 7 1 2 2 3 3 4 4 5 5 6 6 1	1 2 2 3 3 4 4 5 5 6
6 5 1 2 2 3 3 4 4 5 5 6	1 2 2 3 3 4 4 5 5 6
4 5 4 3 2 4 2 3 1 2 1 3	4 3 2 4 1 2
6 9 1 2 1 3 1 5 2 5 2 4 3 5 3 6 4 5 5 6	1 2 1 3 1 5 2 4 3 6

Решение

Учитывая то, что по условию задачи нам дан связный неориентированный граф без петель и кратных ребер и то, что любое дерево с [latex]n[/latex] вершинами содержит [latex]n-1[/latex] ребро, то для получения дерева нужно удалить столько ребер, пока не останется [latex]n-1[/latex] ребро.

Данную задачу я решил, применяя упрощенный алгоритм Краскала, учитывая, что данное дерево не является взвешенным и сортировку применять не нужно. Для начала объявляем наш исходный граф используя вектор ребер (edge). Структура ребер является простой и содержит в себе только информацию о вершинах, которое ребро соединяет. Алгоритм Краскала заключается в том, что мы каждую вершину помещаем в свое множество. Затем при просмотре каждого ребра исходного графа мы проверяем принадлежат ли вершины ребра одному множеству. Если нет, то добавляем данное ребро в наше дерево (предварительно его создав с помощью вектора ребер), после добавления мы добавляем все вершины, которые принадлежали тому же множеству, что и вторая вершина ребра, в множество первой вершины. Если же вершины уже принадлежат одному множеству, то переходим к следующему этапу цикла. После этой процедуры нам достаточно вывести на экран значения из нашего дерева — это и будут необходимые ребра.

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

Код на ideone.com

UPD: обновил код, тесты, описание решения и ссылки.

Related Images:

A288

19/04/2016 by Павел Загинайло

Задача A288

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

Даны целые числа [latex]a_{1}[/latex], …, [latex]a_{n}[/latex], каждое из которых отлично от нуля. Если в последовательности отрицательные и положительные члены чередуются (+, –, +, –, или –, +, –, +, … ), то ответом должна служить сама исходная последовательность. Иначе получить все отрицательные члены последовательности, сохранив порядок их следования.

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

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


int main() {
	vector <int> a, b;
	bool alternate = true; //переменная, которая изменяет свое значение, в зависимости от того, чередуются знаки (true) или нет (false)
	int a1; //первый элемент
	
	cin >> a1;
	int tester = a1; //в переменной хранится значение, с которым будут сравниваться последующие
	if (a1 > 0){
		b.push_back(a1);
	}
	else if (a1 < 0){
		a.push_back(a1);
		b.push_back(a1);
	}
	
	int n;
	while (cin >> n){
		if (n > 0){
			b.push_back(n);
		}
		if (n < 0){
			a.push_back(n);
			b.push_back(n);
		}
		if (tester*n > 0) alternate = false;  //если встретили два значения подряд одного знака
		tester = n;
	}
	if (alternate == true){
		for (int i = 0; i < b.size(); i++){
			cout << b[i] << " ";
		}
	}
	if (alternate == false){
		for (int i = 0; i < a.size(); i++){
			cout << a[i] << " ";
		}
	}
	return 0;
}

#include <vector>

#include <iostream>

using namespace std;

int main() {

vector <int> a, b;

bool alternate = true; //переменная, которая изменяет свое значение, в зависимости от того, чередуются знаки (true) или нет (false)

int a1; //первый элемент

cin >> a1;

int tester = a1; //в переменной хранится значение, с которым будут сравниваться последующие

if (a1 > 0){

b.push_back(a1);

}

else if (a1 < 0){

a.push_back(a1);

b.push_back(a1);

}

int n;

while (cin >> n){

if (n > 0){

b.push_back(n);

}

if (n < 0){

a.push_back(n);

b.push_back(n);

}

if (tester*n > 0) alternate = false; //если встретили два значения подряд одного знака

tester = n;

}

if (alternate == true){

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

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

}

if (alternate == false){

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

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

}

return 0;

}

Тесты

Входные данные	Выходные данные
5 5 3 1 2 7 8 100000
-9 -5 -1 -3 -7 -4198 -852	-9 -5 -1 -3 -7 -4198 -852
5 -3 1 81 3 -7 1 -5 6	-3 -7 -5
-1 2 -8 995 -3 777 -42	-1 2 -8 995 -3 777 -42

Решение

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

Related Images:

e-olymp 1309. Блоки строки

20/12/2015 by Павел Загинайло

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

Блоком строки S в позиции i назовём наибольшую подстроку S, которая начинается в позиции i и совпадает с префиксом S. Длину блока в позиции 0 считать равной нулю.

Вычислить длины блоков строки S для всех позиций.

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

Единственная строка S (|S| ≤ 10⁶).

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

В одной строке вывести длины блоков строки S для всех позиций, разделённые пробелом.

Тесты:

abaabaab
0 0 1 5 0 2 0

1 2	abaabaab 0 0 1 5 0 2 0

abaabaabbaaaaaaaaaaaabbbbbbbabaaaaaabababaaaaaaaabaaabaabaaaaaaaabaaabaaababababbab
0 0 1 5 0 1 2 0 0 1 1 1 1 1 1 1 1 1 1 1 2 0 0 0 0 0 0 0 4 0 1 1 1 1 1 3 0 3 0 4 0 1 1 1 1 1 1 1 4 0 1 1 7 0 1 4 0 1 1 1 1 1 1 1 4 0 1 1 4 0 1 1 3 0 3 0 3 0 2 0 0 2 0

1 2	abaabaabbaaaaaaaaaaaabbbbbbbabaaaaaabababaaaaaaaabaaabaabaaaaaaaabaaabaaababababbab 0 0 1 5 0 1 2 0 0 1 1 1 1 1 1 1 1 1 1 1 2 0 0 0 0 0 0 0 4 0 1 1 1 1 1 3 0 3 0 4 0 1 1 1 1 1 1 1 4 0 1 1 7 0 1 4 0 1 1 1 1 1 1 1 4 0 1 1 4 0 1 1 3 0 3 0 3 0 2 0 0 2 0

aaaaaaaaaaaaaaaaaaaaa
0 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

1 2	aaaaaaaaaaaaaaaaaaaaa 0 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1

f2f
0 0 1

f2f

0 0 1

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

#include <iostream>
#include <cstring> 
using namespace std;
 
 
int main(){
	int zf[1000000];
	char s[1000000];
    scanf("%[^\n]%*c", s);
    int n = strlen(s);
    int right=0,left=0;
 
    for(int i=1; i < n; ++i){
           
            if(i<=right){
        		zf[i]=min(right-i+1,zf[i-left]);
            }
            while(s[zf[i]]==s[zf[i]+i]){
            	zf[i]++;
            }
            if(i+zf[i]-1>right){
    	        left=i;
                right=i+zf[i]-1;
            }
    }
 	
    for(int i=0; i < n; ++i){
    	cout << zf[i] << " ";	
    }
    
	return 0; 
}

#include <iostream>

#include <cstring>

using namespace std;

int main(){

int zf[1000000];

char s[1000000];

scanf("%[^\n]%*c", s);

int n = strlen(s);

int right=0,left=0;

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

if(i<=right){

zf[i]=min(right-i+1,zf[i-left]);

}

while(s[zf[i]]==s[zf[i]+i]){

zf[i]++;

}

if(i+zf[i]-1>right){

left=i;

right=i+zf[i]-1;

}

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

cout << zf[i] << " ";

}

return 0;

}

Алгоритм

В данной задаче из-за того, что наша строка может принимать длину до 10⁶ включительно, то необходим эффективный алгоритм. Я воспользовался алгоритмом вычисления Z-функции. Для начала мы заводим переменные left и right, в которых мы будем хранить координаты самого длинного отрезка, который совпадает с началом нашей строки. В начале цикла проверяем находится ли ячейчка, для которой ищется результат в отрезке между left и right. После прохождения цикла while, мы обновляем границы подстроки.

Код на ideone.com

Принятая задача на e-olymp.

Related Images:

e-olymp 2459. Юбилей Винни-Пуха

20/12/2015 by Павел Загинайло

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

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

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

Входной файл содержит дату Юбилея Винни-Пуха в формате dd.mm.gggg. Гарантируется, что дата корректна.

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

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

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

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

string reverse(string s){
	string y;
	for (int i = 0; !s.empty(); i++){
		if (s.back() != '.'){
			y.push_back(s.back());
			s.pop_back();
		}
		if (s.back() == '.') s.pop_back();
	}
	return y;
}

bool is_leap(int year){
	bool leap;
	if ((year % 400) == 0) leap = true;
	else if ((year % 100) == 0) leap = false;
	else if ((year % 4) == 0) leap = true;
	else leap = false;
	return leap;
}

int get_days (int month, int year){
	int days;
	switch (month) {
		case 1:
		case 3:
		case 5:
		case 7:
		case 8:
		case 10:
		case 12:
		    days = 31;
		    break;
		case 4:
		case 6:
		case 9:
		case 11:
		    days = 30;
		    break;
		case 2:
			is_leap(year)?days = 29:days=28;
		    break;
		default:
		    days = -1;
    }
    return days;
}

int main() {
	string s,y;
	getline(cin, s);
	y = reverse(s);
	int day = stoi(y.substr(0,2));
	int month = stoi(y.substr(2,2));
	int year = stoi(y.substr(4,4));
	cout << (((month>=1)&&(month<=12)&&(day >= 1)&&(day <= (get_days(month, year))))?"YES":"NO");

	return 0;
}

#include <iostream>

#include <string>

using namespace std;

string reverse(string s){

string y;

for (int i = 0; !s.empty(); i++){

if (s.back() != '.'){

y.push_back(s.back());

s.pop_back();

}

if (s.back() == '.') s.pop_back();

}

return y;

}

bool is_leap(int year){

bool leap;

if ((year % 400) == 0) leap = true;

else if ((year % 100) == 0) leap = false;

else if ((year % 4) == 0) leap = true;

else leap = false;

return leap;

}

int get_days (int month, int year){

int days;

switch (month) {

case 1:

case 3:

case 5:

case 7:

case 8:

case 10:

case 12:

days = 31;

break;

case 4:

case 6:

case 9:

case 11:

days = 30;

break;

case 2:

is_leap(year)?days = 29:days=28;

break;

default:

days = -1;

}

return days;

}

int main() {

string s,y;

getline(cin, s);

y = reverse(s);

int day = stoi(y.substr(0,2));

int month = stoi(y.substr(2,2));

int year = stoi(y.substr(4,4));

cout << (((month>=1)&&(month<=12)&&(day >= 1)&&(day <= (get_days(month, year))))?"YES":"NO");

return 0;

}

Тесты

Входные данные	Выходные данные
23.02.2002	YES
20.02.2023	NO
20.12.2015	NO
20.12.2051	YES

Решение

Как только получили строку из стандартного ввода, воспользуемся функцией reverse(). Эта функция записывает нашу строку «задом наперед», в это же время удаляя символ ‘.’ из строки. Так как я точно знаю, что строка из ввода записана верно, то я могу не проверять остальные символы. Пользуясь этим же фактом я завел три переменные целочисленного типа: day, month, year. В новой строке присутствуют только цифры, поэтому я присваиваю каждой новой переменной соответствующие подстроки, после приведения типа string к типу int с помощью функции stoi(). В выводе проверяется соответствуют ли значения дня и месяца требованиям. День проверяется с помощью функции get_days(). Она позволяет получить количество дней в зависимости от месяца и года. В самой функции get_days() используется функция is_leap(), которая проверяет год на високосность и возвращается булевское значение. В зависимости от этого значения, изменяется значение количества дней в феврале — 28 или 29 соответственно. Когда наши числа прошли все проверки, то мы получаем на вывод «YES», если новая дата является корректной или «NO» в ином случае.

Код на ideone.com

Засчитанная задача на e-olymp.com

Related Images:

MLoops 17

16/11/2015 by Павел Загинайло

Задача

+++++++++++++++++++++++++++++++
+....^....+....^....+....^....+
+....|....+....|....+....|....+
+<-- k -->+<-- k -->+<-- k -->+
+....|....+....|....+....|....+
+....v....+....v....+....v....+
+++++++++++++++++++++++++++++++
+....^....+....^....+....^....+
+....|....+....|....+....|....+
+<-- k -->+<-- k -->+<-- k -->+
+....|....+....|....+....|....+
+....v....+....v....+....v....+
+++++++++++++++++++++++++++++++

+++++++++++++++++++++++++++++++

+....^....+....^....+....^....+

+....|....+....|....+....|....+

+<-- k -->+<-- k -->+<-- k -->+

+....|....+....|....+....|....+

+....v....+....v....+....v....+

+++++++++++++++++++++++++++++++

+....^....+....^....+....^....+

+....|....+....|....+....|....+

+<-- k -->+<-- k -->+<-- k -->+

+....|....+....|....+....|....+

+....v....+....v....+....v....+

+++++++++++++++++++++++++++++++

Тесты

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

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

+++++++++++++++++++++++++++++++
+.........+.........+.........+
+.........+.........+.........+
+.........+.........+.........+
+.........+.........+.........+
+.........+.........+.........+
+++++++++++++++++++++++++++++++
+.........+.........+.........+
+.........+.........+.........+
+.........+.........+.........+
+.........+.........+.........+
+.........+.........+.........+
+++++++++++++++++++++++++++++++

+++++++++++++++++++++++++++++++

+.........+.........+.........+

+++++++++++++++++++++++++++++++

+.........+.........+.........+

+++++++++++++++++++++++++++++++

++++++++
+....+..
+....+..
+....+..
+....+..

++++++++

+....+..

++++++++++++++++++++
+...+...+...+...+...
+...+...+...+...+...
+...+...+...+...+...
+...+...+...+...+...
+...+...+...+...+...
++++++++++++++++++++
+...+...+...+...+...
+...+...+...+...+...
+...+...+...+...+...
+...+...+...+...+...
+...+...+...+...+...
++++++++++++++++++++
+...+...+...+...+...
+...+...+...+...+...
+...+...+...+...+...
+...+...+...+...+...
+...+...+...+...+...
++++++++++++++++++++
+...+...+...+...+...

++++++++++++++++++++

+...+...+...+...+...

++++++++++++++++++++

+...+...+...+...+...

++++++++++++++++++++

+...+...+...+...+...

++++++++++++++++++++

+...+...+...+...+...

Алгоритм

Программа выполняется с помощью двух циклов. Первый цикл отвечает за строки, второй за столбцы. Метод заключается в том, чтобы узнать, когда мы записываем именно ‘+’, а уже в остальные места записываем ‘.’. Для начала проверяем делится ли номер строки, уменьшенный на 1, нацело на 6. Если да, то записываем +. Далее проверяем, делится ли номер столбца, уменьшенный на 1, на число [latex]k+1[/latex], где [latex]k[/latex] — вводимый параметр. Во всех остальных случаях пишем ‘.’.

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

#include <iostream>
using namespace std;

int main() {
	int m, n, k; //m-строки, n - столбцы
	cin >> m >> n >> k;
	for (int i = 0; i < m; i++){
		for (int j = 0; j < n; j++){
			if (i%6 == 0) cout << '+';
			else if (j%(k+1) == 0) cout << '+';
			else cout << '.';
		}
	cout << endl;	
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int m, n, k; //m-строки, n - столбцы

cin >> m >> n >> k;

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

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

if (i%6 == 0) cout << '+';

else if (j%(k+1) == 0) cout << '+';

else cout << '.';

}

cout << endl;

}

return 0;

}

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

Related Images:

MLoop 11

04/11/2015 by Павел Загинайло

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

Вычислите с точностью $\epsilon$ значение функции $f\left( x \right) = \arccos x$ . При вычислениях допустимо использовать только арифметические операции.

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

#include <iostream>
#include <cmath>
#define PI 3.1415926
using namespace std;

double f(double e, double x){
	int i = 0;
	double p = x;
	double s = x;
	while (p > e){
		p*=(x*x*(2*i + 1)*(2*i + 1))/(2*(i+1)*(2*i + 3));
		s+=p;
		i++;
	}
	return s;
}

int main() {
	double e; //точность
	double x;
	cin >> e >> x;
	cout << PI/2 - f(e, x) << endl;
	return 0;
}

#include <iostream>

#include <cmath>

#define PI 3.1415926

using namespace std;

double f(double e, double x){

int i = 0;

double p = x;

double s = x;

while (p > e){

p*=(x*x*(2*i + 1)*(2*i + 1))/(2*(i+1)*(2*i + 3));

s+=p;

i++;

}

return s;

}

int main() {

double e; //точность

double x;

cin >> e >> x;

cout << PI/2 - f(e, x) << endl;

return 0;

}

Тесты

Входные данные		Выходные данные	Арккосинус
e	x	arccos = ([latex]\pi[/latex]/2 — f)	Арккосинус
0.000001	0.866	0.523651	0.5236495809
0.01	0.5	1.04727	1.0471975512
0.00000000000001	0.35	1.21323	1.2132252231
0.00001	0.99	0.141873	0.1415394733

Решение

Для того, чтобы представить функцию $f\left( x \right) = \arccos x$ необходимо воспользоваться формулой Тейлора, а именно рядом Маклорена для арккосинуса. Она имеет следующий вид:

[latex]\arccos x=\frac{\pi}{2}-\sum_{n=1}^\infty\frac{(2n)!}{4^{n}(n!)^{2}(2n+1)}x^{2n+1}[/latex]

Чтобы при вычислениях использовать только арифметические операции необходимо преобразовать это выражение. Первый член данной суммы — [latex]x[/latex]. Нужно узнать на что нужно домножить первый элемент, чтобы получить следующий. Для этого следует найти, чему будет равно отношение [latex]\frac{a_{n+1}}{a_{n}}[/latex]. В результате мы получим следующее: [latex]\frac{x^{2}(2n+1)^{2}}{2(n+1)(2n+3)}[/latex].

В функции [latex]f[/latex] переменная [latex]p[/latex] — слагаемые нашей суммы, а изначально — первый элемент. Также, в начале мы присвоили переменной суммы значение первого элемента. Затем в цикле мы домножаем наше слагаемое на полученный ранее коэффициент и складываем его с суммой до тех пор, пока значение [latex]p[/latex] превышает значение заданной точности [latex]e[/latex]. В основной части программы мы лишь выводим разность [latex]\pi/2[/latex] и нашей суммы. Это и будет значение арккосинуса.

Код на ideone.com

Related Images:

e-olymp 517. Задачка от Николая

30/09/2015 by Павел Загинайло

Задача на e-olymp

Приближается Новый год! Третьеклассники уже мечтают побывать возле новогодней елки в Киеве. Учительница математики одного из 3-х классов г. Александрия им сообщила, что она сможет свозить на ёлку в Киев только тех учеников, которые решать задачку от святого Николая. Он хочет узнать качество заданного числа.

По мнению Николая, качеством числа [latex]N[/latex] является сумма цифр всех натуральных чисел [latex] A[/latex] не больших самого числа [latex] N[/latex] таких что остаток от деления числа [latex] N[/latex] на число [latex] A[/latex] равен [latex] 0[/latex] .

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

Первая строка содержит натуральное число [latex]N[/latex] – количество учеников в 3-м классе. В последующих [latex]N[/latex] строках размещены задания для каждого ученика: натуральное число не больше чем [latex] 15 000 000[/latex] (Николай решил пожалеть учеников и числа выбрал не очень большие)

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

Для каждого из чисел, заданных Николаем ученикам, укажите его качество.

Код:

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

int SumOfDigit(int n) {
	int f = 0;
	while (n >= 1) {
		f += n % 10;
		n /= 10;
	}
	return f;
}


int main()
{
	int N;
	cin >> N;
	for (int i = 1; i <= N; i++) {
		int A;
		cin >> A;
		int sum = 0;
		double f = sqrt(A);
		for (int j = 1; j*1.0 <= f; j++) {
			if (A%j == 0) sum += SumOfDigit(j) + SumOfDigit(A/j);
			}
		if ((int) f == f) sum-=f;
		cout<<sum<<endl;
	}
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int SumOfDigit(int n) {

int f = 0;

while (n >= 1) {

f += n % 10;

n /= 10;

}

return f;

}

int main()

{

int N;

cin >> N;

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

int A;

cin >> A;

int sum = 0;

double f = sqrt(A);

for (int j = 1; j*1.0 <= f; j++) {

if (A%j == 0) sum += SumOfDigit(j) + SumOfDigit(A/j);

}

if ((int) f == f) sum-=f;

cout<<sum<<endl;

}

return 0;

}

Тесты:

Количество строк	1 задание	2 задание	Вывод
2	2	10	3; 9
2	2	1500000	3; 666
2	5	9	6; 13
2	60	15000000	42; 978
2	1	0	1; 0

Решение

В данной задаче я выделил отдельную функцию — [latex]SumOfDigit()[/latex]. Не трудно догадаться, что она считает сумму цифр числа для будущих вычислений. Для первого цикла мы сначала должны ввести число [latex]N[/latex] — количество заданий для учеников. Именно столько раз будет выполняться основной цикл. Чтобы определить качество числа, необходимо найти все его натуральные делители. Для решения данной задачи я воспользовался методом перебора всех чисел до корня из исходного, что значительно ускоряет вычисление по сравнению с перебором вплоть до самого числа. Во внутреннем цикле проверяется каждое число, и если оно удовлетворяет условию, то вызывается функция [latex]SumOfDigit[/latex], а в переменную [latex]sum[/latex] записываются значения сумм.

if ((int) f == f) sum-=f;

1	if ((int) f == f) sum-=f;

Данная строка необходима для проверки, если исходное число является квадратом.

В конце основного цикла программа печатает на экран качество данного числа.

Данная задача решалась совместно со Стасом Коциевским на факультативе.

Код на ideone.com

Принятое решение на e-olymp

Related Images:

Mif 17.19

30/09/2015 by Павел Загинайло

Задача. Принадлежит ли точка (х;у) фигуре на рисунке?

Тесты:

[latex]x[/latex]	[latex]y[/latex]	Вывод
-3	0	no
-1.5	2	yes
2	5	yes
3	4	yes
3	3	no

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

#include <iostream>
using namespace std;
 
int main() {
	double x,y;
	cin >> x >> y;
	cout << ((((x>=-4)&&(x<=-1)&&(y>=1)&&(y<=7))||((x>=-1)&&(x<=3)&&(y>=4)&&(y<=7))) ? "yes" : "no");
	return 0;
}

#include <iostream>

using namespace std;

int main() {

double x,y;

cin >> x >> y;

cout << ((((x>=-4)&&(x<=-1)&&(y>=1)&&(y<=7))||((x>=-1)&&(x<=3)&&(y>=4)&&(y<=7))) ? "yes" : "no");

return 0;

}

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

В данной программе проверяются допустимые значения [latex]x[/latex] и [latex]y[/latex], при которых точка с данными координатами может принадлежать данной фигуре. Если координаты соблюдают все условия, то программа выводит «yes», т.е. принадлежит . В остальных случаях на экран выводится «no».

Related Images:

Ю2.28

30/09/2015 by Павел Загинайло

Задача.

Вклад. Банк предлагает 3 вида срочных вкладов: на 3 месяца под [latex]p_{1}[/latex]%, на 6 месяцев под [latex]p_{2}[/latex]% и на год под [latex]p_{3}[/latex]%. Какой из вкладов наиболее выгоден для вкладчика?

Тесты:

[latex]p1[/latex]	[latex]p2[/latex]	[latex]p3[/latex]	Вывод программы
0	0	0	Нет наиболее выгодного вклада из трех
10	10	10	Первый вклад выгоднее
10	10	50	Третий вклад выгоднее
50	10	10	Первый вклад выгоднее
5	20	20	Второй вклад выгоднее

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

#include <iostream>
using namespace std;
 
int main() {
	double p1, p2, p3, x, y, z;
	cin >> p1 >> p2 >> p3;

	x = (1 + (p1/4)/100)*(1 + (p1/4)/100)*(1 + (p1/4)/100)*(1 + (p1/4)/100);
	y = (1 + (p2/2)/100)*(1 + (p2/2)/100);
	z = 1 + p3/100;
	
	if ((x > y) && (x > z))
		cout << "Первый вклад выгоднее";
	else if ((y > x) && (y > z))
		cout << "Второй вклад выгоднее";
	else if ((z > x) && (z > y))
		cout << "Третий вклад выгоднее";
	else 
		cout << "Нет наиболее выгодного вклада из трех";
	return 0;
}

#include <iostream>

using namespace std;

int main() {

double p1, p2, p3, x, y, z;

cin >> p1 >> p2 >> p3;

x = (1 + (p1/4)/100)*(1 + (p1/4)/100)*(1 + (p1/4)/100)*(1 + (p1/4)/100);

y = (1 + (p2/2)/100)*(1 + (p2/2)/100);

z = 1 + p3/100;

if ((x > y) && (x > z))

cout << "Первый вклад выгоднее";

else if ((y > x) && (y > z))

cout << "Второй вклад выгоднее";

else if ((z > x) && (z > y))

cout << "Третий вклад выгоднее";

else

cout << "Нет наиболее выгодного вклада из трех";

return 0;

}

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

Для решения этой задачи я пользовался следующей формулой: [latex]B = A(1 + \frac{P}{100\%})[/latex], где [latex]B[/latex] — будущая стоимость, [latex]A[/latex] — текущая стоимость, [latex]P[/latex] — процентная ставка за расчетный период, [latex]n[/latex] — количество расчетных периодов. В программе я ее представил в другом виде, так как для сравнения выгодности вкладов одинаковой суммы, саму сумму можно не учитывать.

Код на ideone.com

Related Images:

ML21

29/09/2015 by Павел Загинайло

Задача. Найти сумму членов арифметической прогрессии $a, a+d, a+2d \dots, a+(n-1)d$ по данным значениям $a, d, n$ .

Тесты:

[latex]a[/latex]	[latex]d[/latex]	[latex]n[/latex]	[latex]Sn[/latex]
8	657	0	0
5	0	2	10
5	8	1	5
0	5565	88	21302776

Код:

#include <iostream>
using namespace std;

int main() {
	int a, d, n;
	cin >> a >> d >> n;
	cout << ((2*a + d*(n - 1))/2)*n;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, d, n;

cin >> a >> d >> n;

cout << ((2*a + d*(n - 1))/2)*n;

return 0;

}

Алгоритм.

В данной программе я воспользовался формулой суммы арифметической прогрессии. А именно [latex] S_{n} = \frac{a_{1} + d(n — 1)}{2} * n [/latex], где [latex]a_{1}[/latex] — первый член арифметической прогрессии, [latex]d[/latex] -разница арифметической прогрессии и [latex]n[/latex] — номер последнего члена суммы. Программа же просто выводит результат данных вычислений на экран.

Related Images:

e-olymp 931. Отношение произведения к сумме

14/09/2015 by Павел Загинайло

Задача с сайта e-olymp #931.

Ссылка на засчитанное решение

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

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

Натуральное число n, не превышающее 2·10⁹.

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

Вывести отношение произведения цифр числа n к их сумме с 3 десятичными цифрами.

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

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


int SumOfDigits (int n)
{
	int s = 0;
	while (n)
	{
			s+=n%10;
			n/=10;
	}
	return s;
}

double MultOfDigits (int n)
{
	double m = 1;
	while(n)
	{
		m*=n%10;
		n/=10;
	}
	return m;
}

int main() {
    int n;
    cin>>n;
    cout<<fixed<<setprecision(3)<<MultOfDigits(n)/SumOfDigits(n);
	return 0;
}

#include <iostream>

#include <cmath>

#include <iomanip>

using namespace std;

int SumOfDigits (int n)

{

int s = 0;

while (n)

{

s+=n%10;

n/=10;

}

return s;

}

double MultOfDigits (int n)

{

double m = 1;

while(n)

{

m*=n%10;

n/=10;

}

return m;

}

int main() {

int n;

cin>>n;

cout<<fixed<<setprecision(3)<<MultOfDigits(n)/SumOfDigits(n);

return 0;

}

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

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

Более краткий вариант программы.

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


int main() {
    int n, sum = 0; 
    double k = 0, mult = 1;
    cin>>n;
    while(n!=0)
    {
    	k=n%10;
    	sum+=k;
    	mult*=k;
    	n/=10;
    }
    
    cout<<fixed<<setprecision(3)<<mult/sum;
	return 0;
}