e-olymp 4082. Произведение на отрезке

27/06/2016 by Настя Филипчук

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

Это нормально чувствовать себя взволнованным и напряженным за день до олимпиады по программированию. Чтобы расслабиться, вы пошли выпить со своими друзьями в соседний паб. Для сохранения остроты ума до следующего дня, Вы решили сыграть в следующую игру. Для начала Ваши друзья написали последовательность [latex] n [/latex] целых чисел [latex] x_{1}, x_{2},\cdots , x_{n} [/latex]. Потом следует [latex] k [/latex] раундов, на каждом из которых выполняется одна из следующих команд:

команда изменения, когда необходимо изменить одно значение в последовательности;
команда умножения, когда по заданным значениям [latex] i [/latex] и [latex] j [/latex] необходимо определить, является ли произведение [latex] x_{i}\cdot x_{i+1} \cdot \; \; \cdots \; \; \cdot x_{j-1} \cdot x_{j} [/latex] положительным, отрицательным или равным нулю.

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

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

Каждый тест состоит из нескольких строк. Первая строка каждого теста содержит два числа [latex] n [/latex] и [latex] k [/latex] ([latex] 1\leq n,k\leq 10^{5}[/latex]) — количество элементов в последовательности и число раундов в игре. Вторая строка содержит [latex] n [/latex] целых чисел [latex] x_{i} [/latex] — начальные значения последовательности ([latex] -100\leq x_{i}\leq 100[/latex] для [latex]i=1,2, \cdots ,n[/latex]). Каждая из следующих [latex] k [/latex] строк описывает команду, начинающуюся заглавной буквой [latex] C [/latex] или [latex] C [/latex]. Если это буква [latex] C [/latex], то строка содержит команду замены, за буквой следуют два числа [latex] i [/latex] и [latex] v [/latex], указывающих на то что [latex] x_{i} [/latex] необходимо заменить на [latex] v [/latex] ([latex] 1\leq i\leq n[/latex] и [latex]-100\leq v\leq 100[/latex]). Если это буква [latex] P [/latex], то строка задает команду умножения, за буквой следуют два числа [latex] i [/latex] и [latex] j [/latex] — необходимо вычислить произведение от [latex] x_{i} [/latex] до [latex] x_{i} [/latex] включительно ([latex] 1\leq i\leq j\leq n [/latex]) . Каждый тест содержит как минимум одну команду умножения.

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

Для каждого теста вывести одну строку, содержащую ответы на все команды умножения. [latex] i [/latex]-ый символ строки является результатом [latex] i [/latex]-ой команды умножения. Если произведение положительно, то вывести символ [latex] + [/latex] (плюс); если произведение отрицательно, то вывести [latex] — [/latex] (минус); если произведение равно нулю, то вывести [latex] 0 [/latex] (ноль).

Тесты

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

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

4 6

-2 6 0 -1

C 1 10

P 1 4

C 3 7

P 2 2

C 4 -5

P 1 4

5 9

1 5 -2 4 3

P 1 2

P 1 5

C 4 -5

P 1 5

P 4 5

C 3 0

P 1 5

C 4 -5

0+-

+-+-0

5 5

10 -2 0 5 1

C 1 0

P 1 4

C 2 7

P 1 1

C 2 0

6 4

0 20 0 30 0 -10

P 2 2

P 2 3

P 3 6

P 2 6

4 3

0 -1 -2 0

P 2 3

C 1 9

P 1 2

3 3

5 2 0

C 1 7

C 3 0

C 1 0

6 5

100 10 55 11 0 -33

P 1 4

C 5 6

C 3 72

C 5 -20

P 5 6

+000

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

#include <iostream>
using namespace std;
 
void sequence(int* tree, int* given, int position, int i, int j) // посторение дерева
{
    if (i == j)
        tree[position] = given[i] > 0 ? 1 : (given[i] < 0 ? -1 : 0); // заменяем элементы последовательности на "1","-1","0" в соответсвии с условием для команды "P" 
    else if (i!=j)  // для остальных элементов воспользуемся следующим алгоритмом
    {
        int m = (i + j) / 2;
        sequence(tree, given, position * 2, i, m);
        sequence(tree, given, position * 2 + 1, m + 1, j);
        tree[position] = tree[position * 2] * tree[position * 2 + 1]; // элемент с номером (pos * 2) – левый потомок, а с (pos * 2 + 1) - правый потомок
    }
}

void For_C_command(int* tree, int position, int i, int j, int nposition, int v) // функция изменения элемента (для выполнения команлы "С")
{
    if (i == j)
        tree[position] = v > 0 ? 1 : (v < 0 ? -1 : 0);
    else if (i!=j)
    {
        int m = (i + j) / 2;
        if (nposition <= m)
            For_C_command(tree, position * 2, i, m, nposition, v);
        else
            For_C_command(tree, position * 2 + 1, m + 1, j, nposition, v);
        tree[position] = tree[position * 2] * tree[position * 2 + 1];
    }
}
 
int For_P_command(int* tree, int position, int i, int j, int qi, int qj) // функция для выполнения команды "Р"
{
    if (i == qi && j == qj)
        return tree[position];
    else
    {
        int m = (i + j) / 2;
        if (qj <= m)
            return For_P_command(tree, position * 2, i, m, qi, qj);
        else if (qi >= m + 1)
            return For_P_command(tree, position * 2 + 1, m + 1, j, qi, qj);
        else
            return For_P_command(tree, position * 2, i, m, qi, m) * For_P_command(tree, position * 2 + 1, m + 1, j, m + 1, qj);
    }
}
 
int main() 
{
    ios::sync_with_stdio(false); // ускоряем чтение
    int n, k;
    while (cin >> n >> k)
    {
        int given[n];
        for (int i = 0; i < n; i++)
            cin >> given[i];
        int tree[n * 4];
        sequence(tree, given, 1, 0, n - 1);
        for (int i = 0; i < k; i++)
        {
            char command;
            int xi, xj;
            cin >> command >> xi >> xj;
            if (command == 'P')
            {   
                int x = For_P_command(tree, 1, 0, n - 1, xi - 1, xj - 1); // применяем функцию для команды "Р" и выполняем сравнения, соответствующие условию задачи
                if (x < 0)
                    printf("-");
                else if (x > 0)
                    printf("+");
                else 
                    printf("0");
            }
            else
                For_C_command(tree, 1, 0, n - 1, xi - 1, xj);
        }
        printf("\n");
    }
}

#include <iostream>

using namespace std;

void sequence(int* tree, int* given, int position, int i, int j) // посторение дерева

{

if (i == j)

tree[position] = given[i] > 0 ? 1 : (given[i] < 0 ? -1 : 0); // заменяем элементы последовательности на "1","-1","0" в соответсвии с условием для команды "P"

else if (i!=j) // для остальных элементов воспользуемся следующим алгоритмом

{

int m = (i + j) / 2;

sequence(tree, given, position * 2, i, m);

sequence(tree, given, position * 2 + 1, m + 1, j);

tree[position] = tree[position * 2] * tree[position * 2 + 1]; // элемент с номером (pos * 2) – левый потомок, а с (pos * 2 + 1) - правый потомок

}

void For_C_command(int* tree, int position, int i, int j, int nposition, int v) // функция изменения элемента (для выполнения команлы "С")

{

if (i == j)

tree[position] = v > 0 ? 1 : (v < 0 ? -1 : 0);

else if (i!=j)

{

int m = (i + j) / 2;

if (nposition <= m)

For_C_command(tree, position * 2, i, m, nposition, v);

else

For_C_command(tree, position * 2 + 1, m + 1, j, nposition, v);

tree[position] = tree[position * 2] * tree[position * 2 + 1];

}

int For_P_command(int* tree, int position, int i, int j, int qi, int qj) // функция для выполнения команды "Р"

{

if (i == qi && j == qj)

return tree[position];

else

{

int m = (i + j) / 2;

if (qj <= m)

return For_P_command(tree, position * 2, i, m, qi, qj);

else if (qi >= m + 1)

return For_P_command(tree, position * 2 + 1, m + 1, j, qi, qj);

else

return For_P_command(tree, position * 2, i, m, qi, m) * For_P_command(tree, position * 2 + 1, m + 1, j, m + 1, qj);

}

int main()

{

ios::sync_with_stdio(false); // ускоряем чтение

int n, k;

while (cin >> n >> k)

{

int given[n];

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

cin >> given[i];

int tree[n * 4];

sequence(tree, given, 1, 0, n - 1);

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

{

char command;

int xi, xj;

cin >> command >> xi >> xj;

if (command == 'P')

{

int x = For_P_command(tree, 1, 0, n - 1, xi - 1, xj - 1); // применяем функцию для команды "Р" и выполняем сравнения, соответствующие условию задачи

if (x < 0)

printf("-");

else if (x > 0)

printf("+");

else

printf("0");

}

else

For_C_command(tree, 1, 0, n - 1, xi - 1, xj);

}

printf("\n");

}

Решение

Данная задача решается при помощи стандартного алгоритма по теме «Дерево отрезков» (данный алгоритм можно посмотреть на сайте e-maxx). Следовательно, при построении дерева сначала считывается массив, а после выполняется построение дерева (от корня). В том случае, если функция, строящая дерево, вызывалась от листа, все значения элементов массива записываются в дерево как [latex]1[/latex], если элемент больше нуля, если меньше нуля, то записывается как [latex]-1[/latex], а в случае равенства элемента нулю, он записывается [latex]0[/latex] (нулём). В ином случае (если функция вызывалась не от листа), она начинает вызываться рекурсивно от каждого из двух сыновей и перемножает вычесленные значения.

Для выполнения функции изменения элемента ей (функции) передаётся текущая вершина. Затем выполняется вызов из сына, сожержащего элемент с данным номером. Таким образом процесс доходит до листа, которому и присваевается значение. При чём, аналогично построению дерева, элементы записываются как [latex]1[/latex],[latex]-1[/latex] или же [latex]0[/latex].

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

Далее (в программе) идёт процесс построения дерева и выполнение действий, удовлетворяющих команды, описанные в уловии задачи.

Ссылки

Рабочий код на Ideone.com
Засчитанное решение на e-olymp.com
При ришении данной задачи был использован материал по структурам данных «дерево отрезков» с сайта e-maxx.ru
Задача взята с сайта e-olymp.com

Related Images:

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.

Related Images:

e-olymp 494. Гласные

22/11/2015 by Настя Филипчук

К гласным буквам в латинском алфавите относятся буквы A, E, I, O, U и Y. Остальные буквы считаются согласными. Напишите программу, считающую количество гласных букв в тексте.

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

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

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

В выходной файл вывести одно целое число – количество гласных во входном тексте.

Код

#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
int main (){
	int length,i,j,kol=0; 
	char vowel []="AEIOUY"; 
	char text [100]; 
	gets (text); //функция считывает все введённые символы с пробелами до тех пор, пока не будет нажата клавиша Enter 
	length=strlen (text); 
	for (j=0; j<=5; j++){
		for (i=0; i<=length; i++)
			if (text[i]==vowel[j])//сравниваем введённые элементы с заданными значениями строки
				kol=kol+1;
	}
	cout << kol << endl;
	return 0;
}

#include <iostream>

#include <stdio.h>

#include <cstring>

using namespace std;

int main (){

int length,i,j,kol=0;

char vowel []="AEIOUY";

char text [100];

gets (text); //функция считывает все введённые символы с пробелами до тех пор, пока не будет нажата клавиша Enter

length=strlen (text);

for (j=0; j<=5; j++){

for (i=0; i<=length; i++)

if (text[i]==vowel[j])//сравниваем введённые элементы с заданными значениями строки

kol=kol+1;

}

cout << kol << endl;

return 0;

}

Код с функцией strpbrk()

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

int main ()
{
	int counter=0;
	char text[100];
	char vowel[] = "AEOUIY";
	char * pch;
	cin.getline(text,100);
	pch = strpbrk (text, vowel);
	while (pch != NULL) // пока есть гласные буквы
	{
		pch = strpbrk (pch+1,vowel); // поиск гласных букв
		counter++;
	}
	cout << counter;
	return 0;
}

#include <iostream>

#include <cstring>

using namespace std;

int main ()

{

int counter=0;

char text[100];

char vowel[] = "AEOUIY";

char * pch;

cin.getline(text,100);

pch = strpbrk (text, vowel);

while (pch != NULL) // пока есть гласные буквы

{

pch = strpbrk (pch+1,vowel); // поиск гласных букв

counter++;

}

cout << counter;

return 0;

}

Решение

Объявляется инициализированная строка, в которой может поместиться шесть символов, а последнее, седьмое место отводится под нуль-терминатор. Далее считываются все веденные символы, включая пробелы. Сравнивается первый элемент строки с каждым элементом считываемых символов. Если считываемый символ соответствует символу строки, то увеличиваем количество гласных на единицу и так далее для всех гласных букв. Когда первый элемент строки сравнили со всеми считываемыми символами, начинаем так же сравнивать каждый последующий элемент.

Реализация с использованием string

#include <iostream>
#include <string>
using namespace std;
 
int main() {
	int counter=0;
	string text; //инициализируем строку
	getline (cin,text); //извлекает строки из входного потока
	string vowel="AEOUIY"; 
	size_t found=text.find_first_of(vowel); //Поиск по строке text для первого символа, который соответствует любому элементу строки vowel
	while (found!=-1) 
	{
		counter++;
		found=text.find_first_of(vowel,found+1);
	}
	cout << counter << endl;
	return 0;
}

#include <iostream>

#include <string>

using namespace std;

int main() {

int counter=0;

string text; //инициализируем строку

getline (cin,text); //извлекает строки из входного потока

string vowel="AEOUIY";

size_t found=text.find_first_of(vowel); //Поиск по строке text для первого символа, который соответствует любому элементу строки vowel

while (found!=-1)

{

counter++;

found=text.find_first_of(vowel,found+1);

}

cout << counter << endl;

return 0;

}

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

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

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

№	Входные данные	Выходные данные
1	COBBRA	2
2	REE BA	3
3	U GFD	1

Ссылки

Условие задачи можно найти на сайте e-olymp;
Засчитанное решение;
Решение задачи cфункцией strpbrk() на ideone.com;
Решение задачи с использованием string;

Related Images:

MLoops8

07/11/2015 by Настя Филипчук

Задача

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

Два числа:количество столбцов и строк.

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

Таблица размером n*m со следующей закономерностью:

+21++21++21++21++21++21++
1++21++21++21++21++21++21
+21++21++21++21++21++21++
1++21++21++21++21++21++21
+21++21++21++21++21++21++
1++21++21++21++21++21++21
+21++21++21++21++21++21++
1++21++21++21++21++21++21

Код

#include <iostream>
using namespace std;
int main(){
	int m,n; 
	cin>>n>>m;
	for(int i=1;i<m+1;i++){ 
		for(int j=1;j<n+1;j++){  
			if(i%2==0){
				if ((j+3)%4==0) 
					cout<< "1"; 
				else 
					cout<<(j%4==0?"2":"+");
			}
			else{
				if ((j+1)%4==0)
					cout<<"1";
				else 
					cout<<((j+2)%4==0?"2":"+");
			}
		}
	cout<<endl;
	}	
	return 0;
}

#include <iostream>

using namespace std;

int main(){

int m,n;

cin>>n>>m;

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

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

if(i%2==0){

if ((j+3)%4==0)

cout<< "1";

else

cout<<(j%4==0?"2":"+");

}

else{

if ((j+1)%4==0)

cout<<"1";

else

cout<<((j+2)%4==0?"2":"+");

}

cout<<endl;

}

return 0;

}

Упрощенный вариант

#include <iostream>
using namespace std;
int main()
{
	int m,n; 
	cin>>n>>m;
	for(int i=1;i<m+1;i++)
	{ 
		for(int j=1;j<n+1;j++)
		{  
			if( ((i%2==0) && ((j+3)%4==0))||((i%2!=0) && ((j+1)%4==0)))
			{
				cout<< "1"; 
			}
			if ((j+3-2*(i%2))%4!=0)
			{
				cout<<((j+2*(i%2))%4==0?"2":"+");
			}
		}
		cout<<endl;
	}	
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

int m,n;

cin>>n>>m;

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

{

for(int j=1;j<n+1;j++)

{

if( ((i%2==0) && ((j+3)%4==0))||((i%2!=0) && ((j+1)%4==0)))

{

cout<< "1";

}

if ((j+3-2*(i%2))%4!=0)

{

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

}

cout<<endl;

}

return 0;

}

Тесты

[latex]n[/latex]	[latex]m[/latex]	Выходные данные
1	1	+
7	7	+21++21 1++21++ +21++21 1++21++ +21++21 1++21++ +21++21
15	6	+21++21++21++21 1++21++21++21++ +21++21++21++21 1++21++21++21++ +21++21++21++21 1++21++21++21++
25	8	+21++21++21++21++21++21++ 1++21++21++21++21++21++21 +21++21++21++21++21++21++ 1++21++21++21++21++21++21 +21++21++21++21++21++21++ 1++21++21++21++21++21++21 +21++21++21++21++21++21++ 1++21++21++21++21++21++21

Решение

Для решения сначала нужно найти закономерность чередования символов в таблице. Пусть нумерация столбцов и строк будет начинаться с единицы, тогда, если строка [latex]i \vdots 2[/latex], то символы в ней чередуются по такому принципу: если результат от прибавления номера столбца к 1 кратен 4 ([latex] (j+1)\vdots 4 [/latex]), то в данной строке и столбце находится «1», если же результат от прибавления номера столбца к 2 кратен 4([latex] (j+2)\vdots 4 [/latex]), то в данной строке и столбце находится «2», если ни одно из этих условий не выполняется, значит на данном месте находится «+».

Если же строка [latex]i\vdots 2[/latex], то символы в ней чередуются по такому принципу: если результат от прибавления номера столбца к 3 кратен 4 ([latex] (j+3)\vdots 4[/latex]), то в данной строке и столбце находится «1», а если номер столбца кратен 4([latex] j\vdots 4 [/latex]), то в данной строке и столбце находится «2», если ни одно из этих условий не выполняется, значит на данном месте находится «+».

Ссылки

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

Упрощенный код

Related Images:

MLoop 24

31/10/2015 by Настя Филипчук

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

Вычислите с точностью [latex]\varepsilon [/latex] сумму ряда [latex]\sum_{i=1}^{\infty} (-1)^{i}\cdot \frac{2^{i}}{\left ( 2\cdot i+1 \right )!} [/latex].

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

В условии нужно найти сумму ряда,задан его общий член. Благодаря этому можно найти формулу, согласно которой каждый последующий член ряда выражается как предыдущий, умноженный на выражение: [latex]\frac{-2}{2 \cdot k + 3}[/latex].
Вычисляется первый член ряда, предполагается, что он и будет равен сумме ряда, и этот член ряда сравнивается по модулю с заданной точностью [latex]\varepsilon [/latex].
В случае, если требуемая точность не достигнута — подсчитывается следующий член ряда, он прибавляется к сумме и сравнивается по модулю с заданной точностью.
Пункт 3 повторяется до тех пор, пока заданная точность не достигнута.

Код

#include <iostream>
#include <cmath>
using namespace std;
int main(){
	double sum, eps, prev,next,dif;
	int i;
	eps=1e-10;
	prev=1; next=-1/3.0;
	i=2; 
	sum=1;
	dif=abs(next-prev);
	while (dif>eps){
		sum=sum+next;
		prev=next;
		next=-prev/((2*i+1)*i);
		i=i+1;
		dif=abs(prev-next);
	}
 	cout << "sum="<< sum << "\n" << endl;
 	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main(){

double sum, eps, prev,next,dif;

int i;

eps=1e-10;

prev=1; next=-1/3.0;

i=2;

sum=1;

dif=abs(next-prev);

while (dif>eps){

sum=sum+next;

prev=next;

next=-prev/((2*i+1)*i);

i=i+1;

dif=abs(prev-next);

}

cout << "sum="<< sum << "\n" << endl;

return 0;

}

Исправленный вариант

#include <iostream>
#include <cmath>
using namespace std;
int main(){
	double sum, eps, A;
	cin >> eps;
	int i=1;
	A=-1/3.0;
	sum=A;
	while (abs(A)>eps){
		i++;
		A=A*(-2)/(2*i+3);
		sum+=A;
	}
 	cout << "sum="<< sum << endl;
 	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main(){

double sum, eps, A;

cin >> eps;

int i=1;

A=-1/3.0;

sum=A;

while (abs(A)>eps){

i++;

A=A*(-2)/(2*i+3);

sum+=A;

}

cout << "sum="<< sum << endl;

return 0;

}

#include <iostream>
#include <cmath>
using namespace std;
int main(){
	double long sum, eps, A;
	cin >> eps;
	int i=0;
	A=-1/3.0;
	sum=A;
	while (abs(A)>=eps){
		i++;
		A=A*(-2)/((2*i+2)*(2*i+3));
		sum+=A;
	}
 	cout << "sum="<< sum << endl; 
 	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main(){

double long sum, eps, A;

cin >> eps;

int i=0;

A=-1/3.0;

sum=A;

while (abs(A)>=eps){

i++;

A=A*(-2)/((2*i+2)*(2*i+3));

sum+=A;

}

cout << "sum="<< sum << endl;

return 0;

}

Тесты

Входные данные (точность [latex]\epsilon [/latex])	Выходные данные (сумма ряда [latex]\sum_{i=1}^{\infty} (-1)^{i}\cdot \frac{2^{i}}{2\cdot i+1}[/latex])
e=1e-10	sum=-0.301544
e=0.0001	sum=-0.301543
e=0.001	sum=-0.301543
e=0.01	sum=-0.301587
e=0.1	sum=-0.3

Ссылки

условие задачи;
решение на ideone;
исправленное решение на ideone;
подсчёт суммы ряда в WolframAlpha;

Related Images:

e-olymp 916. Интересное произведение

07/10/2015 by Настя Филипчук

Определить все возможные значения произведения [latex]i\cdot j[/latex], если целочисленные значения переменных [latex]i[/latex] и [latex]j[/latex] меняются соответственно [latex]i[/latex] от [latex]a[/latex] до [latex]b[/latex] и [latex]j[/latex] от [latex]c[/latex] до [latex]d[/latex] ([latex]1\leq a,b,c,d\leq 10[/latex]).

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

В одной строке заданы 4 числа [latex]a,b,c,d[/latex] ( [latex]a[/latex] может быть больше [latex]b[/latex], [latex]c[/latex] может быть больше [latex]d[/latex] ).

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

Вывести количество возможных вариантов произведения.

Код

#include <iostream> 
using namespace std; 
int main()
{ 
 int a,b,c,d; 
 int p,pmin,pmax,j,imin,imax,jmin,jmax;
 int rez,flag; 
 cin >>a>>b>>c>>d;
 if (a<b)
     {
         imin=a; 
         imax=b;
     }
 else
     {
         imin=b; 
         imax=a;
     }
 if (c<d)
     {
         jmin=c; 
         jmax=d;
     }
 else
     {
         jmin=d; 
         jmax=c;
     }
 pmin=imin*jmin;
 pmax=imax*jmax;
 rez=0;
 for (p=pmin; p<=pmax; p++)
     { 
         flag=0;
         for (int i=imin; i<=imax;i++)
             { 
                 j=p/i;
                 if ((p%i==0) && (j>=jmin) && (j<=jmax))
                 flag=1;
             }
         if (flag==1)
         rez=rez+1;
     }
 cout << rez; 
 return 0; 
}

#include <iostream>

using namespace std;

int main()

{

int a,b,c,d;

int p,pmin,pmax,j,imin,imax,jmin,jmax;

int rez,flag;

cin >>a>>b>>c>>d;

if (a<b)

{

imin=a;

imax=b;

}

else

{

imin=b;

imax=a;

}

if (c<d)

{

jmin=c;

jmax=d;

}

else

{

jmin=d;

jmax=c;

}

pmin=imin*jmin;

pmax=imax*jmax;

rez=0;

for (p=pmin; p<=pmax; p++)

{

flag=0;

for (int i=imin; i<=imax;i++)

{

j=p/i;

if ((p%i==0) && (j>=jmin) && (j<=jmax))

flag=1;

}

if (flag==1)

rez=rez+1;

}

cout << rez;

return 0;

}

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

№	Входные данные	Выходные данные
1	1 10 1 10	42
2	7 2 4 1	18
3	2 7 1 4	18
4	3 9 2 4	16

Решение

Для нахождения всех возможных результатов произведения без повторений [latex]i\cdot j[/latex] будем проверять каждое число [latex] p [/latex] (которое находится в диапазоне от произведения минимальных значений [latex] i [/latex] и [latex] j [/latex] до произведения их максимальных значений) на то, возможно ли его получить при помощи данного произведения. Если получить число хотя бы один раз, перемножив [latex] i [/latex] и [latex] j [/latex], реально,тогда значению [latex] flag [/latex] присваиваем 1. Если [latex] flag [/latex] присваивается 1, тогда [latex] rez [/latex] увеличивается на 1. В результате выводим итоговое [latex] rez [/latex].

Ссылки

Условие задачи на E-Olymp;
Код программы на Ideone.com;
Подтверждение решения на E-Olymp.

Related Images:

Mif 17.12

01/10/2015 by Настя Филипчук

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

Принадлежит ли точка [latex] (x;y) [/latex] фигуре на рисунке?

Код

#include <iostream>
using namespace std;
int main(){
	double x,y,a;
	cin >> x >> y;
	a=x*x+y*y;
	if (((x>=0)&&(y>=0) && (a<=36))|| ((x>=0)&&(y<=0) && (y>=x-6)))
		cout << "Yes";
	else
		cout << "No";
	return 0;
}

#include <iostream>

using namespace std;

int main(){

double x,y,a;

cin >> x >> y;

a=x*x+y*y;

if (((x>=0)&&(y>=0) && (a<=36))|| ((x>=0)&&(y<=0) && (y>=x-6)))

cout << "Yes";

else

cout << "No";

return 0;

}

Тесты

Входные данные		Выходные данные
x	y
9	0	No
-5	3	No
1	2	Yes
-3	5	Yes
1	-1	Yes
4	-4	No

Решение

Сначала ищем длину отрезка ([latex] a [/latex]) от начала координат к точке [latex] (x;y) [/latex] по формуле: [latex]\sqrt{{({x}_{0}-x)}^{2}+{({y}_{0}-y)}^{2}}[/latex], где [latex]({x}_{0};{y}_{0})[/latex] — координаты начала координат.
Дальше проверяем, если [latex]a^{2}\leq 36[/latex] (т.е. точка находится в круге, т.к радиус четверти круга равен 6, а, возведя [latex]a[/latex] в квадрат, радиус также нужно возвести в квадрат) и [latex] (x;y) [/latex] находятся в первой четверти координат, то программа выводит «Yes» (можем возвести радиус ([latex] a=\sqrt{x^{2}+y^{2}} [/latex] )в квадрат,т.к. радиус не может быть отрицательным).
Также, если сумма [latex] x + y [/latex] в четвертой четверти координат не превышает 6, то точка принадлежит треугольнику и программа выводит «Yes».
В том случае, если тока не принадлежит фигуре, программа выводит «No».

Ссылки

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

Related Images:

Mif 1

30/09/2015 by Настя Филипчук

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

Даны действительные числа [latex] x [/latex], [latex] y [/latex]. Получить [latex]\min (x, y)[/latex].

Код

#include <iostream>
using namespace std;
 
int main(){
	double x, y;
	cin >> x >> y;
	if (x<y)
		cout << x << endl;
	else
		cout << y << endl;
	return 0;
}

#include <iostream>

using namespace std;

int main(){

double x, y;

cin >> x >> y;

if (x<y)

cout << x << endl;

else

cout << y << endl;

return 0;

}

Код (с тернарной операцией)

#include <iostream>
using namespace std;
 
int main(){
	int x, y;
	cin >> x >> y;
	cout << (x<y? x:y);//сравниваем x и y, если x меньше либо равен y, то выводится x, иначе - y
	return 0;
}

#include <iostream>

using namespace std;

int main(){

int x, y;

cin >> x >> y;

cout << (x<y? x:y);//сравниваем x и y, если x меньше либо равен y, то выводится x, иначе - y

return 0;

}

Тесты

Входные данные		Выходные данные
[latex]x[/latex]	[latex]y[/latex]	[latex]\min (x, y)[/latex]
4	9	min=4
23	32	min=23
48	125	min=48
842	361	min=361
15	15	min=15

Решение

Вводим данные [latex] x [/latex], [latex] y [/latex]. Затем сравниваем их. Если [latex] x\leq y [/latex], то выводится [latex] x [/latex]. Иначе, то есть,если [latex] y < x [/latex], то выводится [latex] y [/latex].

Ссылки

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

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

Related Images:

ML16

23/09/2015 by Настя Филипчук

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

На какую высоту [latex] h [/latex](в метрах) поднимется тело брошенное вертикально вверх со скоростью [latex] v [/latex] м/сек с поверхности планеты масса которой [latex] m [/latex] кг а радиус [latex] R [/latex] м? Вращением планеты можно пренебречь.

Код

#include <iostream>
using namespace std;
 
int main() 
{
    double v, m, R, G, h;
    cin>>v>>R>>m;
    G=6.67408*1e-11;
    h=(v*v*R*R)/(2*m*G); 
    cout<<h<<endl;
    return 0;
}

#include <iostream>

using namespace std;

int main()

{

double v, m, R, G, h;

cin>>v>>R>>m;

G=6.67408*1e-11;

h=(v*v*R*R)/(2*m*G);

cout<<h<<endl;

return 0;

}

Тесты

v	m	R	h
3	7	9	3.67092e+11
10	20	25	1.19867e+13
6	15	9	6.7425e+12
7	11	23	1.93122e+12

Решение

Прямолинейное равноускоренное движение описывается двумя формулами: [latex]v=v_{0}+g \cdot t[/latex] (в этой формуле [latex] v_{0} [/latex] — начальная скорость , а [latex] v [/latex] — текущая скорость) и [latex]h=v\cdot t-\frac{g \cdot t^{2}}{2}[/latex]. Однако, тело бросали вверх, следовательно, произведение ускорения на время надо вычитать из начальной скорости:[latex]v=v_{0}-g \cdot t[/latex].
В условии спрашивается на какую высоту [latex] h [/latex] (в метрах) поднимется тело брошенное вертикально вверх. Т.к тело начало равноускоренное движение из состояния покоя имеем: [latex] v_{0}=0 [/latex], отсюда получаем: [latex] v=0-g \cdot t[/latex] . Теперь можем выразить [latex] t [/latex]: [latex]t=-\frac{v}{g}[/latex].
Подставляем [latex] t [/latex] во вторую формулу. Получаем: [latex] h=\frac{v^{2}}{g}-\frac{v^{2}}{2\cdot g} [/latex], т.е [latex]h=\frac{v^{2}}{2\cdot g}[/latex].
Остается только найти ускорение свободного падения ( [latex] g [/latex] ).Для этого нужно найти силу притяжения ([latex] F [/latex]).Согласно закону гравитации сила притяжения ([latex] F [/latex]), которая действует на тело массой [latex] M [/latex] возле поверхности планеты равна: [latex] F=\frac{G\cdot m\cdot M}{R^{2}} [/latex], где [latex] m [/latex]- масса планеты, [latex] R [/latex] — радиус планеты, а [latex] G [/latex] — гравитационная постоянная, которая равна: [latex] G=6.67408\cdot 10^{-11} [/latex].
Согласно второму закону Ньютона: [latex] g=\frac{F}{M} [/latex]. Подставляем [latex] F [/latex] и получаем:[latex] g=\frac{G\cdot m}{R^{2}} [/latex].
Теперь есть все составляющие для нахождения высоты: [latex] h=\frac{v^{2}\cdot R^{2}}{2\cdot G\cdot m} [/latex].

Ссылки

Related Images:

e-olymp 478. Белые кубики

14/09/2015 by Настя Филипчук

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

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

В одной строке задано три целых числа – размеры бруска в дм, не превышающие 1000000.

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

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

Код

<span class="sy4">#include <iostream>
using namespace std;

int main()
{
 long a,b,c;
 cin>>a>>b>>c;
 cout<<a*b*c<< " " <<a*b*c*6-2*(a*b+a*c+b*c)<< endl;
 return 0;
}
</span>

<span class="sy4">#include <iostream>

using namespace std;

int main()

{

long a,b,c;

cin>>a>>b>>c;

cout<<a*b*c<< " " <<a*b*c*6-2*(a*b+a*c+b*c)<< endl;

return 0;

}

</span>

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

№	Входные данные	Выходные данные
1	1 2 3	6 14
2	1 1 2	2 2
3	2 2 2	8 24
4	3 4 5	60 266

Решение

Т.к. сторона изготовленных кубиков равна 1 дм, можем узнать их количество, найдя объём бруска по формуле:[latex] a \cdot b \cdot c[/latex]. Что бы узнать сколько сторон необходимо покрасить покрасить, нужно от количества всех сторон отнять уже окрашенные в белый цвет. Для нахождения всех сторон умножаем количество всех кубиков на количество сторон одного кубика: [latex]6 \cdot a \cdot b \cdot c[/latex]. Количество уже окрашенных сторон кубиков можно получить, узнав площадь поверхности бруска: [latex] 2 \cdot (a \cdot b+a \cdot c+b \cdot c)[/latex]. Находим разность (кол-во неокрашенных сторон): [latex]a \cdot b \cdot c \cdot 6 — 2 \cdot (a \cdot b+a \cdot c+b \cdot c)[/latex].

Ссылки

Условие задачи на E-Olymp;

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

Подтверждение решения на E-Olymp.