Category Archives: 3. Циклы

Программы, основным элементом которых являются простые циклические вычисления.

Циклы

Опубликовано: 11/10/2014

Циклические, повторяющиеся много раз однотипные вычисления позволяют наилучшим образом продемонстрировать вычислительные возможности компьютеров. Ради этого их изначально и создавали. В задачах этого раздела желательно снова перечитать параграф 5.4 из праймера посвященный «итерационным операторам» (так они назвали семейство из нескольких операторов цикла). Часть 5.4.3 можете пока пропустить, поскольку мы еще не изучали структур данных для которых … Continue reading →

нет комментариев

В классе и дома решаются следующие тренировочные задачи (1 балл):

Цифры
Младший бит
Постоянная сумма цифр
Садовник
Большая точность
Дракон
Змей Горыныч
Уровень палиндромности
Нумерация
Битовое представление
Часы
Счастливые билеты
Роботы — сложная задача, предлагается всем желающим
Юный садовод
Максимум
Баксы в банке
Циклические сдвиги
Минимальная сумма цифр
Просто Фибоначчи
Превращение
Увеличить на 2
Двоичные числа
Интересное произведение
Кружок хорового пения
Очень просто!!!
Юные программисты
Коды Грея — только не перемудрите. Если выходит значительно больше 20 строчек кода,
то лучше остановиться и подумать.
Кубики — 3 —
используйте битовые операции для смены предположения о потере кубика для каждой из 52-х букв
Степень симметрии
Сколько можно?
«Зеркально простые» числа
Max — Min

Опубликованные решения

MLoops 4

31/10/2015 by Андрей Яроцкий

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

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

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

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

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

Таблица размером [latex]n[/latex] [latex]\times[/latex] [latex]m[/latex] аналогичная таблице в условии.

Тесты:

№	[latex]n[/latex] [latex]m[/latex]	Таблица
1	1 1	—
2	1 7	— + — + — * —
3	7 1	-+-+-*-
4	10 10	-+-+--+-+ +-+--+-+- -+--+-+- +--+-+-- --+-+--+ -+-+--+- -+-+--+-+ +-+--+-+- -+--+-+- +--+-+--
5	25 8	-+-+--+-+--+-+--+-+-- +-+--+-+--+-+--+-+--+ -+--+-+--+-+--+-+--+- +--+-+--+-+--+-+--+-+ --+-+--+-+--+-+--+-+- -+-+--+-+--+-+--+-+-* -+-+--+-+--+-+--+-+-- +-+--+-+--+-+--+-+--+

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

#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++){         // Цикл вычисления номера члена
			if(((i+j+1) % 6 == 0)&&((i+j) != 0)){ // Проверка на кратность шести
				cout << "*";
			}
			else cout << ((i+j+1) % 2 == 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++){ // Цикл вычисления номера члена

if(((i+j+1) % 6 == 0)&&((i+j) != 0)){ // Проверка на кратность шести

cout << "*";

}

else cout << ((i+j+1) % 2 == 0?"+":"-"); // Проверка на кратность двум

}

cout << endl;

}

return 0;

}

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

Посмотрев на таблицу можно заметить, что знак «-» выводится когда номер члена последовательности нечетный, знак «+» когда четный и знак «*» когда член последовательности кратный 6. После объявления переменных [latex]n[/latex] и [latex]m[/latex](количество столбцов и строк соответственно) создаем два цикла — один внутри другого. Внешний цикл считает номер строки и, после выполнения внутреннего, переносит последовательность на новую строку. Внутренний цикл считает номер столбца и выполняет проверку на кратность шести, в этом случае выводится знак «*». В противном случае проводится проверка на кратность двум. Если номер члена последовательности кратен двум выводиться знак «+», в противном случае — «-«.

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

Код в компиляторе

Related Images:

MLoops 6

31/10/2015 by Максим Носов

Задача

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

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

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

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

0+1+0+1+0+1+0+1+0+1+0+1+0
+0+1+0+1+0+1+0+1+0+1+0+1+
1+0+1+0+1+0+1+0+1+0+1+0+1
+1+0+1+0+1+0+1+0+1+0+1+0+
0+1+0+1+0+1+0+1+0+1+0+1+0
+0+1+0+1+0+1+0+1+0+1+0+1+
1+0+1+0+1+0+1+0+1+0+1+0+1
+1+0+1+0+1+0+1+0+1+0+1+0+

0+1+0+1+0+1+0+1+0+1+0+1+0

+0+1+0+1+0+1+0+1+0+1+0+1+

1+0+1+0+1+0+1+0+1+0+1+0+1

+1+0+1+0+1+0+1+0+1+0+1+0+

0+1+0+1+0+1+0+1+0+1+0+1+0

+0+1+0+1+0+1+0+1+0+1+0+1+

1+0+1+0+1+0+1+0+1+0+1+0+1

+1+0+1+0+1+0+1+0+1+0+1+0+

Код

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

int main() {
    int n,m; //задаем переменные(количество столбцов и строк)
    cin>>n>>m; //вводим их
    for(int i=1;i<n+1;i++) { //запускаем цикл по стобцам
        for(int j=1;j<m+1;j++) { //запускаем цикл по строкам
            int k=abs(i-j);
            if ((k%4)==0) cout<<"0"; //задаем условие, согласно с закономерностью
            else if ((k%2)==0) cout<<"1";
            else cout<<"+";
        }
        cout<<endl;
    }
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n,m; //задаем переменные(количество столбцов и строк)

cin>>n>>m; //вводим их

for(int i=1;i<n+1;i++) { //запускаем цикл по стобцам

for(int j=1;j<m+1;j++) { //запускаем цикл по строкам

int k=abs(i-j);

if ((k%4)==0) cout<<"0"; //задаем условие, согласно с закономерностью

else if ((k%2)==0) cout<<"1";

else cout<<"+";

}

cout<<endl;

}

return 0;

}

Решение

Для того, чтобы решить поставленную задачу, нужно сначала понять закономерность чередования символов в таблице. Каждый символ имеет свой номер столбца([latex]n[/latex]) и строки([latex]m[/latex]). Запускаем первый цикл для столбцов, в нем вложенный цикл по строкам. Используя «счетчики» в циклах ([latex]i[/latex] и [latex]j[/latex]) задаем условия, учитывая закономерность. Закономерность такая, что в каждой новой строке «0» сдвигается вправо на позицию [latex]i=j[/latex] , а остальные элементы «подстраиваются под » «0». Таким образом, » 1″ задаем по формуле [latex]|i-j|%2==0[/latex], «0» задаем по формуле [latex]|i-j|%4==0[/latex], а «+» остаются все остальные. После того как цикл по строкам заканчивается — ставим переход на новую строку.

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

Related Images:

MLoop 1

31/10/2015 by Сплошнов Кирилл

Условие

Используйте метод бисекции для того, чтобы отыскать с точностью [latex]\varepsilon[/latex] все действительные корни уравнения [latex]\ln{(1 + x^2 -\sin{x})} = 3^{\cos{2x}}[/latex]. Для подготовки необходимых графиков воспользуйтесь этим ресурсом.

График

Тесты

Точность [latex]\epsilon[/latex]	Корень на [latex](-4; -3)[/latex]	Корень на [latex](-3; -2)[/latex]	Корень на [latex](-1; 0)[/latex]	Корень на [latex](1; 2)[/latex]	Корень на [latex](2; 3)[/latex]	Корень на [latex](3; 4)[/latex]
0.1	-3.40625	-2.78125	-0.84375	1.21875	2.71875	3.40625
0.01	-3.42578	-2.75391	-0.839844	1.21484	2.72266	3.41016
0.001	-3.42627	-2.75439	-0.836426	1.21729	2.72021	3.41357
0.0001	-3.42636	-2.75443	-0.836884	1.21707	2.72061	3.41391

Код

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

double f(double x)
{
	return log(1 + x*x - sin(x)) - pow(3, cos(2*x));
}

double findRoot(double a, double b, double e) // функция, которая ищет ноль на промежутке от a до b
{
	while (b - a > e) // пока не будет достигнута необходимая точность
	{
		if (f(a) * f((b + a) / 2) == 0)
			break;
		else if (f(a) * f((b + a) / 2) > 0)
			a = (b + a) / 2;
		else
			b = (b + a) / 2;
	}
	return (b + a) / 2;
}

int main() 
{
	double e;
	cin >> e;
	cout << findRoot(-4, -3, e) << endl;
	cout << findRoot(-3, -2, e) << endl;
	cout << findRoot(-1, 0, e) << endl;
	cout << findRoot(1, 2, e) << endl;
	cout << findRoot(2, 3, e) << endl;
	cout << findRoot(3, 4, e) << endl;
	return 0;
}

#include <iostream>

#include<cmath>

using namespace std;

double f(double x)

{

return log(1 + x*x - sin(x)) - pow(3, cos(2*x));

}

double findRoot(double a, double b, double e) // функция, которая ищет ноль на промежутке от a до b

{

while (b - a > e) // пока не будет достигнута необходимая точность

{

if (f(a) * f((b + a) / 2) == 0)

break;

else if (f(a) * f((b + a) / 2) > 0)

a = (b + a) / 2;

else

b = (b + a) / 2;

}

return (b + a) / 2;

}

int main()

{

double e;

cin >> e;

cout << findRoot(-4, -3, e) << endl;

cout << findRoot(-3, -2, e) << endl;

cout << findRoot(-1, 0, e) << endl;

cout << findRoot(1, 2, e) << endl;

cout << findRoot(2, 3, e) << endl;

cout << findRoot(3, 4, e) << endl;

return 0;

}

Решение

Рассмотрим функцию [latex]f(x) = \ln{(1 + x^2 -\sin{x})} — 3^{\cos{2x}}[/latex]. По графику видно, что функция имеет 6 нулей. Таким образом, уравнение имеет 6 корней, которые находятся на интервалах [latex](-4; -3)[/latex], [latex](-3; -2)[/latex], [latex](-1; 0)[/latex], [latex](1; 2)[/latex], [latex](2; 3)[/latex], [latex](3; 4)[/latex] соответственно. Так как корней довольно много, чтобы не копировать 6 раз алгоритм поиска корня, вынесем его в отдельную функцию [latex]findRoot[/latex], у которой будет 3 параметра: начало отрезка [latex]a[/latex], его конец [latex]b[/latex] и заданная точность [latex]\epsilon[/latex].

Далее воспользуемся методом бисекции : рассмотрим значение функции на середине отрезка (в точке [latex]\frac{a + b}{2}[/latex]) и в точке [latex]a[/latex]. Если их произведение равно нулю, то [latex]\frac{a + b}{2}[/latex] — корень уравнения, если меньше, корень — на промежутке [latex](a; \frac{a + b}{2})[/latex], больше — на промежутке [latex](\frac{a + b}{2}; b)[/latex]. Меняем координаты начала и конца отрезка на соответствующие, продолжаем, пока не будет найден корень или достигнута необходимая точность.

Ссылки

Рабочая версия кода на Ideaone.com.

Related Images:

MLoops2

31/10/2015 by Алина Гончарова

Задача

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

-*-*-*-*-*-*-*-*-*-*-*-*-
*-*-*-*-*-*-*-*-*-*-*-*-*
-*-*-*-*-*-*-*-*-*-*-*-*-
*-*-*-*-*-*-*-*-*-*-*-*-*
-*-*-*-*-*-*-*-*-*-*-*-*-
*-*-*-*-*-*-*-*-*-*-*-*-*
-*-*-*-*-*-*-*-*-*-*-*-*-
*-*-*-*-*-*-*-*-*-*-*-*-*

Решение

Для того, чтобы решить поставленную задачу, нужно сначала понять закономерность чередования символов — и * в таблице. Каждый символ имеет свой номер строки([latex]m[/latex]) и столбца([latex]n[/latex]), а чтобы определить их номера зададим счетчики [latex]i[/latex] и [latex]j[/latex]. Задача состоит из того, что нужно определить закономерность появления символа [latex]-[/latex], в остальных случаях нужно выводить символ [latex]*[/latex]. Символ [latex]-[/latex] чередуется с символом [latex]*[/latex], и поэтому можно увидеть, что этот символ [latex]-[/latex] ставится на место, при котором сумма номеров столбцов и строк делится нацело на 2. Решить данную задачу можно с помощью тернарной операции.

Код

#include <iostream>
using namespace std;

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

#include <iostream>

using namespace std;

int main() {

int m, n;

cin >> m >> n;

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

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

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

}

cout << endl;

}

return 0;

}

Тесты

Входные данные	10 10	8 5	25 8
Выходные данные	-----* ----- ----- ----- ----- ----- ----- ----- ----- ----*-	---- ---- ---- ---- ----	------------- ------------* ------------- ------------* ------------- ------------* ------------- ------------*

Задача взята отсюда.

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

Related Images:

Mloops 5

30/10/2015 by Антон Локтев

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

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

Задача находится здесь.

Тесты

№	n	m	Таблица
1	25	8	+++++++++++++++++++++ +++++++++++++++++++++ +++++++++++++++++++++ +++++++++++++++++++++ +++++++++++++++++++++ ++++++++++++++++++++* +++++++++++++++++++++ +++++++++++++++++++++
2	6	6	+++++* +++++ +++++ +++++ +++++ *+++++
3	2	5	++ ++ ++ ++ +*

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

Таблица, которую необходимо вывести на экран представляет собой определённую последовательность. Каждый символ таблицы имеет номера столбца и строки (нумерация от 0 до n или m не включительно). Для этого задаём счётчики [latex] i [/latex] и [latex] j [/latex] . Наша задача — определить закономерность появления символа [latex] \ast [/latex] в данной таблице, поскольку в иных случаях необходимо вывести символ [latex] + [/latex]. В первой строке «звёздочка» встречается в данной таблице в [latex] 6,12,18,24[/latex] столбцах. Во второй строке «звёздочка» находится в [latex] 5,11,17,23[/latex] столбцах. В последующих строках ситуация аналогичная. Можно заметить, что символ [latex] \ast [/latex] стоит на позициях, при которых сумма номера строки и номера столбца делится нацело на 6. Проверяем это условие с помощью тернарной операции:

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

1	cout << ((i+j-5)%6== 0? "*":"+");

от суммы номеров столбца и строки отнимаем число [latex] 5 [/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-5)%6== 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-5)%6== 0? "*":"+");

}

cout << endl;

}

return 0;

}

Ссылка на рабочий код программы находится здесь.

Related Images:

Mloops3

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

Задача:

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

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

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

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

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

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

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

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

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

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

Количество столбцов [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 111. Часы

27/10/2015 by Александр Коломеец

Часы.

Постановка задачи

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

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

Заведем переменную, которая будет отвечать за количество пробитых ударов. Если в начальное время минутная стрелка указывает на число 12, то увеличиваем значение нашей переменной на такое число, на которое указывает часовая стрелка, если же в начальное время минутная стрелка указывает на число 6, то увеличиваем значение переменной на 1. Увеличиваем начальное время на 1 минуту. Повторяем, пока начальное время не будет совпадать с конечным.

Тесты

Входные данные		Выходные данные
Начальное время	Конечное время	Количество ударов
13:30	15:10	7
0:00	23:59	180
12:30	12:30	1
22:08	22:22	0

Реализация

ideone: ссылка
Засчитаное решение на e-olymp: ссылка

#include <iostream>
using namespace std;

int main() {
    int h1, m1, h2, m2, result = 0;
    cin >> h1 >> m1 >> h2 >> m2;
    while(true) {
        if(m1 == 0) {
            result += h1 > 12 ? h1 - 12 : h1 == 0 ? 12 : h1;
        } else if(m1 == 30) {
            result++;
        }
        if(h1 == h2 && m1 == m2) {
            break;
        }
        m1++;
        if(m1 == 60) {
            m1 = 0;
            h1++;
        }
    }
    cout << result << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int h1, m1, h2, m2, result = 0;

cin >> h1 >> m1 >> h2 >> m2;

while(true) {

if(m1 == 0) {

result += h1 > 12 ? h1 - 12 : h1 == 0 ? 12 : h1;

} else if(m1 == 30) {

result++;

}

if(h1 == h2 && m1 == m2) {

break;

}

m1++;

if(m1 == 60) {

m1 = 0;

h1++;

}

cout << result << endl;

return 0;

}

Related Images:

e-olymp 474. Максимум

22/10/2015 by Станислав Коциевский

Задача.

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

Он предложил Васе находить суммы цифр последовательных чисел — 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21 — и так далее, пока Васе не надоест. Вася оказался в восторге от идеи и принялся за работу. За вчерашний день Вася нашёл суммы цифр каждого из чисел от 1 до 115. Посмотрев на результаты младшего брата, Петя заметил, что суммы цифр последовательных чисел не являются случайными, часто они идут подряд, но полностью закономерность он так и не понял.

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

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

В первой строке входных данных находится число N (1 <= N <= 2 147 483 647).

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

Выведите число от 1 до N включительно с максимальной суммой цифр. Если чисел с максимальной суммой цифр несколько, выведите наибольшее из них.

Тесты:

число N	результат
1	1
98	98
13759	9999
999756	998999
2147483647	1999999999

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

#include <iostream>
using namespace std;

int TheNumberOfDigits(int n)//Количество цифр в числе
{
	int i=1;
    while ((n/=10)>0)
    {
    	i++;
    }
    return i;
}

int sc(int a) //Сумма цифр числа
{
	int sum = 0;
	while (a/1>0)
	{
		sum+=a%10;
		a/=10;
	}	
	return sum;
}

int main()
{
	int n, v, t, x;
	cin>>n;
	unsigned long long int a=10;
	t=TheNumberOfDigits(n);
	x=n;
	for (int i=1;i<t;i++)
	{
		unsigned long long int b = a*10;
		v=(n/b)*b+(n%b/a-1)*a+a-1;
		if (sc(v)>sc(x))
			x=v;
		a*=10;
	}
	cout<<x<<endl;
	return 0;
}

#include <iostream>

using namespace std;

int TheNumberOfDigits(int n)//Количество цифр в числе

{

int i=1;

while ((n/=10)>0)

{

i++;

}

return i;

}

int sc(int a) //Сумма цифр числа

{

int sum = 0;

while (a/1>0)

{

sum+=a%10;

a/=10;

}

return sum;

}

int main()

{

int n, v, t, x;

cin>>n;

unsigned long long int a=10;

t=TheNumberOfDigits(n);

x=n;

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

{

unsigned long long int b = a*10;

v=(n/b)*b+(n%b/a-1)*a+a-1;

if (sc(v)>sc(x))

x=v;

a*=10;

}

cout<<x<<endl;

return 0;

}

Решение.

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

Сумму цифр и их количество в числе считают две простых в написании функции, степени (i-я и i+1-я)десятки считаются непосредственно в основном цикле.

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

Ссылка на условие задачи

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

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

примечание: ссылка на код может выдавать старый вариант кода, где [latex]a[/latex] и [latex]b[/latex] считаются отдельно, а не [latex]b[/latex] выражается через [latex]a[/latex], как в этом коде, в связи с техническими проблемами на ideone. Этот вариант тоже проходит все тесты, однако является несколько менее эффективным.

Related Images:

MLoop 4

15/10/2015 by Настя Панько

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

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

#include <iostream>
#include <cmath>
using namespace std;
double sin (double x, double e) {
     double k, a = x;
     double s = x;
     int n=1;
     while (abs(a) > e) {
	   k = - x * x / (2 * n * (2 * n + 1));
	   a *= k;
	   s += a;
	   n++;
     }
     return s;
}
int main () {
      double x, e;
      cin >> x >> e;
      cout << endl << sin(x, e);
}

#include <iostream>

#include <cmath>

using namespace std;

double sin (double x, double e) {

double k, a = x;

double s = x;

int n=1;

while (abs(a) > e) {

k = - x * x / (2 * n * (2 * n + 1));

a *= k;

s += a;

n++;

}

return s;

}

int main () {

double x, e;

cin >> x >> e;

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

}

Тесты

Входные данные	Входные данные	Выходные данные
x	e	sin(x)
1	0,01	0,841471
3	0,01	0,14112
4	0,001	-0,756802
7	0,0001	0, 656987

Решение

Необходимо использовать формулу Тейлора, а именно ряд Маклорена, чтобы представить функцию

[latex]f(x)[/latex] = [latex]\sin x[/latex]

Эта формула имеет такой вид [latex]\sin x[/latex] = [latex]\sum _ { n=0 }^{ \infty }{ { (-1) }^{ n } } \frac { { x }^{ 2n+1 } }{ (2n+1)! }[/latex].

Подключаем заголовочный файл cmath для использования функции abs(). Построим реккурентную формулу для [latex]x_n[/latex] через [latex]x_{n-1}[/latex] для [latex]n > 1 \left(x_0=x\right)[/latex]. Для этого найдем отношение последующего члена ряда к предыдущему [latex]k = \frac{x_n}{x_{n-1}} = -\frac{x^2}{2n\cdot(2n + 1)}[/latex].

Используем функцию while, чтобы проверить является ли член ряда [latex]x_n[/latex] больше [latex]e[/latex].

Ideone.com

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:

e-olymp 10. Садовник

07/10/2015 by Таня Корнилова

Задача e-olymp №10

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

Условие

Садовник посадил за день [latex]n[/latex] деревьев и должен был вылить под каждое деревцо по ведру воды. Так как в день посадки шёл дождь, садовник начал поливку деревьев не в день посадки, а начиная с какого-то [latex]k[/latex]-го дня.

Сколько дней садовник не поливал деревья, если в последний день он под каждое из деревьев вылил [latex]\frac{1}{n}[/latex] часть воды из ведра, в предпоследний [latex]\frac{1}{n-1}[/latex]часть, и т.д., а всего под каждое из деревьев вылил не более, чем по половине ведра воды?

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

Количество деревьев [latex]n[/latex]. [latex]0 < n \le 1000000[/latex]

Тесты

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

(количество деревьев)

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

(искомое количество дней)

1000000

606531

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

#include <iostream>
using namespace std;

int main() {
	int n, k;
	double waterPerTree = 0;
	cin >> n;
	int days = 0;
	while(waterPerTree <= 0.5) {
		waterPerTree += (double) 1 / (n - days++);
	}
	k = n - days +1;
	cout << k;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, k;

double waterPerTree = 0;

cin >> n;

int days = 0;

while(waterPerTree <= 0.5) {

waterPerTree += (double) 1 / (n - days++);

}

k = n - days +1;

cout << k;

return 0;

}

Для запроса на выполнение нажать здесь.

Решение

Пускай в переменной [latex]days[/latex] будет храниться количество дней, в которые садовник поливал деревья, но так как отсчёт начинает с [latex]days = 0[/latex], ([latex]\frac{1}{n}[/latex]), то количество всех дней, когда садовник поливал деревья будет равно максимальному значению [latex]days[/latex] в цикле плюс 1; в переменной [latex]waterPerTree[/latex] — количество вёдер воды, вылитых на одно дерево. Количество вёдер воды, вылитых под одно дерево в определённый день: [latex]\frac{1}{n — days}[/latex]. Так как под каждое дерево садовник вылил не больше [latex]\frac{1}{2}[/latex] ведра воды, то будем выполнять цикл, пока [latex]waterPerTree[/latex] не будет равно этому значению.

Чтоб найти количество дней, на протяжении которых садовник поливал деревья, разделим количество воды, потраченное садовником за всё время поливки [latex]\frac{1}{2}[/latex] на количество вёдер воды, вылитых под одно дерево в определённый день [latex]\frac{1}{n — days}[/latex]. Тогда получим, что [latex]\frac{n — days}{2}[/latex].

По условию задачи, садовник должен был вылить по ведру воды под каждое деревцо, но вылил всего по половине из-за дождя. Из этого следует, что количество воды, выпавшей на каждое деревцо, пиблизительно равно [latex]\frac{1}{2}[/latex] ведра воды. Тогда если всего под каждым деревом по 1 ведру воды за [latex]x[/latex] дней, а садовник вылил по [latex]\frac{1}{2}[/latex] ведра воды за [latex]days + 1[/latex] дней, то [latex]x = 2n — 2days[/latex]. В итоге, [latex]k = \frac{1}{2}x = n — days[/latex]. Но, так как в последнем действии цикла вычисленное [latex]waterPerTree[/latex] будет больше [latex]\frac{1}{2}[/latex], то [latex]k = n — (days — 1)[/latex].

Related Images:

e-olymp 60. Площадь многоугольника

06/10/2015 by Кудымовская Вика

Задача. Площадь многоугольника

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

Заданы координаты [latex]n[/latex] последовательных вершин многоугольника. Определить его площадь.

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

Первая строка содержит количество вершин многоугольника [latex]n[/latex]. В следующих [latex]n[/latex] строках через пробел заданы целочисленные координаты его последовательных вершин [latex]x_i, y_i[/latex]. Известно, что [latex]3 \leq n \leq 1000, -1000 \leq x[i], y[i] \leq 1000[/latex].

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

Площадь многоугольника [latex]S[/latex], вычисленная с точностью до трех десятичных знаков.

Также условие задачи можно посмотреть здесь.

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

№	Входные данные ([latex]n[/latex], [latex]x_i, y_i[/latex])	Выходные данные
1.	3, (0, 0), (0, 2), (2, 0)	2.000
2.	4, (-1000, 500), (-500, 1000), (2, 10), (35, 60)	339865.000
3.	10, (51, -20), (15, 3), (45, 200), (100, -100), (201, 55), (70, -80), (25, 333), (999, 0), (500, 77), (5, -6)	124562.500
4.	5, (13, -92), (44, 0), (-800, 30), (27, 2), (1, 2)	1446.000

Реализация

#include <iostream>
#include <iomanip>
#include <cmath>
using namespace std;
 
int main() { 
    int n, x1, x2, y1, y2, x, y; 
    double sum=0; 
    cin >> n >> x >> y; 
    x1=x; 
    y1=y; 
    for (int i=0; i<(n-1); i++) { 
        cin >> x2 >> y2; 
        sum=sum+(x1+x2)*(y2-y1); 
        x1=x2; 
        y1=y2; 
    } 
    sum=sum+(x+x2)*(y-y2); 
    cout << fixed << setprecision(3) << abs(sum) / 2 << endl;
    return 0; 
}

#include <iostream>

#include <iomanip>

#include <cmath>

using namespace std;

int main() {

int n, x1, x2, y1, y2, x, y;

double sum=0;

cin >> n >> x >> y;

x1=x;

y1=y;

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

cin >> x2 >> y2;

sum=sum+(x1+x2)*(y2-y1);

x1=x2;

y1=y2;

}

sum=sum+(x+x2)*(y-y2);

cout << fixed << setprecision(3) << abs(sum) / 2 << endl;

return 0;

}

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

Даны координаты последовательных [latex]n[/latex] вершин многоугольника: [latex]x_i, y_i[/latex]. Для того, чтобы вычислить его площадь, воспользуемся формулой: [latex]S=\frac{1}{2}\cdot |\sum_{i=1}^{n}{(x_i + x_{i+1})\cdot (y_i — y_{i+1})}|[/latex], где [latex]x_0, y_0=x_{n+1}, y_{n+1}[/latex].

Подробнее о вычислении площади произвольного многоугольника можно прочесть здесь.

Для запроса на выполнение перейдите по ссылке.

Ссылка на засчитанное решение на e-olymp.com.

Related Images:

e-olymp 16. Дракон

05/10/2015 by Таран Таня

У каждой [latex]S[/latex]-ножки [latex]1[/latex] голова. Найти количество ног [latex]N[/latex] у [latex]K[/latex]-главого дракона, если у всех вместе [latex]A[/latex] голов и [latex]B[/latex] ног.

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

4 числа: [latex]S[/latex], [latex]K[/latex], [latex]A[/latex], [latex]B[/latex]. Все числа не превышают [latex]1000[/latex].

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

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

Задача взята с сайта e-olymp.

Тесты

[latex]S[/latex]	[latex]K[/latex]	[latex]A[/latex]	[latex]B[/latex]	[latex]N[/latex]	Комментарий
4	7	35	36	2	7 многоножек и 4 2-ногих дракона
10	3	10	34	8	1 многоножка и 3 8-ногих дракона
44	17	37	132	0	3 многоножки и 2 0 — ногих дракона
4	19	42	42	13	4 многоножки и 2 13 — ногих дракона
1	0	1	1	0	1 многоножка и 1 0 — ногий дракон
5	8	3	6	-1	Количество голов в сумме меньше чем у одного дракона
5	17	6	2	-1	Количество ног в сумме меньше чем у одной многоножки

Алгоритм

Для начала введем несколько дополнительных параметров. Обозначим количество имеющихся драконов через [latex]D[/latex], а количество многоножек как [latex]M[/latex]. Внесем имеющиеся данные в таблицу для удобства построения решения.

Дракон				Многоножка
Один		Несколько		Одна		Несколько
Голов	Ног	Голов	Ног	Голов	Ног	Голов	Ног
[latex]K[/latex]	[latex]N[/latex]	[latex]KD[/latex]	[latex]ND[/latex]	[latex]1[/latex]	[latex]S[/latex]	[latex]M[/latex]	[latex]SM[/latex]

Воспользуемся полученной таблицей и промоделируем сложившуюся ситуацию в виде системы уравнений:
[latex] \left\{\begin{matrix}
KD + M = A & \\
ND + SM = B &
\end{matrix}\right.[/latex]

Выразим из первого уравнения количество многоножек и подставим во второе уравнение:
[latex] \left\{\begin{matrix}
A — KD = M & \\
ND + S(A — KD) = B &
\end{matrix}\right.[/latex]

Раскрыв скобки, преобразуем выражение во втором уравнении:
[latex] \left\{\begin{matrix}

A — KD = M & \\
B — SA = D(N — SK) &
\end{matrix}\right.[/latex]

Теперь мы можем выразить количество драконов:
[latex] \left\{\begin{matrix}

A — KD = M & \\
\frac{B — SA}{N — SK} = D &
\end{matrix}\right.[/latex]

Учитывая тот факт, что мы работаем не просто с системой уравнений, а с величинами имеющими определенный логический смысл, проведем анализ полученного результата:

[latex]D[/latex] — количество драконов, следовательно, это положительное целое число.
Выполняя деление мы предполагаем, что [latex]N — SK[/latex] [latex]\neq[/latex] [latex]0[/latex]. Следует проверить имеет ли данный случай смысл и решение в контексте условия задачи.
Вернемся к системе считая, что [latex]N = SK[/latex]:
[latex] \left\{\begin{matrix}A — KD = M & \\
ND + S(A — KD) = B &
\end{matrix}\right.[/latex][latex] \left\{\begin{matrix}A — KD = M & \\
SKD + SA — SKD = B &
\end{matrix}\right.[/latex][latex] \left\{\begin{matrix}A — KD = M & \\
SA = B &
\end{matrix}\right.[/latex] Приходим к выводу, что, при условии [latex]SA = B[/latex], задача гарантировано имеет решение вида [latex]N = SK[/latex].
Теперь оценим знак полученного нами выражения:
[latex]\frac{B — SA}{N — SK}[/latex] [latex]> 0[/latex] [latex] \Rightarrow[/latex] [latex](B — SA > 0[/latex] [latex]\wedge[/latex] [latex]N — SK > 0)[/latex] [latex]\vee[/latex] [latex](B — SA < 0[/latex] [latex]\wedge[/latex] [latex]N — SK < 0)[/latex].
Оценим значение [latex]B — SA [/latex]:
[latex]B — SA = ND +SM — SA = ND +S(M — A) [/latex] [latex]M[/latex] — количество голов у одной многоножки, [latex]A[/latex] — общее количество голов [latex] \Rightarrow[/latex] [latex]M — A <= 0[/latex] , делаем вывод, что
[latex]B — SA <= 0[/latex] [latex]\forall[/latex] [latex]B, S, A[/latex] [latex] \Rightarrow[/latex] [latex]N — SK <= 0[/latex] [latex] \Rightarrow[/latex] [latex]N <= SK [/latex]

Анализ условия задачи окончен. Перейдем к реализации решения, принимая во внимание все условия и ограничения полученные в процессе размышлений.
Запустим цикл от [latex]0[/latex] до [latex]SK[/latex] (выполнять цикл далее не имеет смысла, так как там не будет найдено ни одного решения), который перебирает количество ног дракона. Объединим все получившиеся ограничения:

Прежде всего выполняем проверку для избежания деления на [latex]0[/latex]. (Условие проверки : [latex]SA = B[/latex] [latex] \Rightarrow[/latex] выводим результат [latex]N = SK [/latex] и заканчиваем работу программы).
Иначе выполняем ряд последовательных проверок для текущего [latex]N[/latex] в цикле:
- [latex]\frac{B — SA}{N — SK}[/latex] — целая величина. (Условие проверки : [latex]B — SA[/latex] делится нацело на [latex]N — SK[/latex])
- Количество ног драконов не превышает общее количество ног минус количество ног одной многоножки (имеется хотя бы одна многоножка, которая имеет [latex]S[/latex] ног). (Условие проверки: [latex]B — S >= DN[/latex])
- Количество голов драконов меньше чем общее количество голов (имеется хотя бы [latex]1[/latex] многоножка с [latex]1[/latex] головой). (Условие проверки: [latex]A > DK[/latex])

Как только выполняются все вышеописанные условия из пункта 2, выполняем вывод текущего количества ног дракона и заканчиваем работу программы, в противном случае выводим [latex]-1[/latex], так как данные противоречивы.

Примечание: в ходе решения выяснилось, что автор задачи предполагает существование 0 — ногих драконов, 0 — ногих многожек и т.д. Эти условия повлияли на вид некоторых неравенств.

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

#include <iostream>
using namespace std;

int main() {
	int s, k, a, b;// заданные величины в соответствующем условию порядке
	int n = 0;// текущее количество ног дракона
	int d;// текущее количество драконов
	cin >> s >> k >> a >> b;
	if (a * s == b){
	    cout << s * k;
	    return 0;
	}// отдельный случай, при a * s = b
	while (n < s * k) {
		if ((b - s * a) % (n - s * k) == 0) { 
		    d = (b - s * a) / (n - s * k);
		    if (b - s >= d * n && a > d * k) {
		       	cout << n;
		        return 0;
		    }// проверяем удовлетворяет ли текущее количество драконов и текущее количество ног все условия
		}// выполняем все проверки только для целых d
		n++;
    }// выполняем перебор только до s*k
	cout << -1;// выводим -1, если решений не нашлось(входные данные противоречивы)
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int s, k, a, b;// заданные величины в соответствующем условию порядке

int n = 0;// текущее количество ног дракона

int d;// текущее количество драконов

cin >> s >> k >> a >> b;

if (a * s == b){

cout << s * k;

return 0;

}// отдельный случай, при a * s = b

while (n < s * k) {

if ((b - s * a) % (n - s * k) == 0) {

d = (b - s * a) / (n - s * k);

if (b - s >= d * n && a > d * k) {

cout << n;

return 0;

}// проверяем удовлетворяет ли текущее количество драконов и текущее количество ног все условия

}// выполняем все проверки только для целых d

n++;

}// выполняем перебор только до s*k

cout << -1;// выводим -1, если решений не нашлось(входные данные противоречивы)

return 0;

}

Код программы
Засчитанное решение

Related Images:

e-olymp 248. Юный садовод

01/10/2015 by Кондратюк Настя

Задача взята с сайта www.e-olymp.com

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

Мама попросила Васю полить все молодые деревца в саду. Вася знает, что пока деревья маленькие, их надо очень хорошо поливать. А вот сколько поливать — неизвестно. Но Вася — очень умный мальчик. Он внимательно прочитал весь учебник ботаники для средней школы и выяснил, что полив прямо пропорционален количеству листьев на дереве. Для хорошего роста деревьев достаточно выливать под дерево ежедневно по одному литру воды на каждый лист.

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

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

Количество ярусов [latex]n (0 \leq n \leq 1000)[/latex] на дереве.

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

Вывести количество литров воды для полива этого дерева.

Тесты

	Входные данные	Выходные данные
1.	3	13
2.	0	1
3.	50	2551
4.	560	314161

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

#include <iostream>
using namespace std;

int main() {
    int n,a=0,sum=0;
    cin >> n;
    for(int i=0 ; i<n ; i++){
        a = a + 2;
        sum = sum + a;
    }
    cout << (sum+1) << endl;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n,a=0,sum=0;

cin >> n;

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

a = a + 2;

sum = sum + a;

}

cout << (sum+1) << endl;

return 0;

}

ideone.com

Решение

Для решения этой задачи необходимо найти сумму арифметической прогрессии, где [latex]N=n,[/latex] [latex]a_{1} = 2[/latex] и [latex]d = 2[/latex] и добавить к ней единицу (лист с верхушки). Для этого можно воспользоваться формулой суммы арифметической прогрессии [latex]Sn=\frac{2a_{1}+d\left(n-1 \right)}{2}n \rightarrow n^2+n[/latex], либо при помощи цикла [latex]n[/latex] раз прибавлять к [latex]a[/latex] двойку, получая при этом следующий член прогрессии и добавлять его к сумме.

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

Related Images:

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

30/09/2015 by Алина Гончарова

Задача

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

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

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

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

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

Решение

Для решения поставленной задачи нам нужно выделить отдельные цифры в записи данного числа, чтобы сосчитать их произведение и сумму. Для этого прочитаем это число из входного потока данных и реализуем разбиение числа на цифры с помощью цикла while. Благодаря остатку от деления числа на 10 получаем последнюю цифру текущего числа, затем делим это число на 10. Если полученное число не 0, повторяем все действия, постепенно накапливая произведение и сумму. Найденные значения произведения и суммы цифр данного числа разделим, предварительно воспользовавшись явным преобразованием к типу double. Это и будет ответом, но так как в задаче указано вывести ответ с тремя десятичными цифрами, я использовала функцию <code>setprecision(3)</code>. В итоге получаем решение этой задачи.

Код

#include <iostream>
#include <iomanip>
using namespace std;
 
int main() {
    int number, sumOfDigits = 0, multOfDigits = 1;
    cin >> number;
    while (number) {
        multOfDigits *= number % 10;
		sumOfDigits += number % 10;
        number /= 10;
    }
    cout << fixed << setprecision(3) << (double)multOfDigits / sumOfDigits << endl;
    return 0;
}

#include <iostream>

#include <iomanip>

using namespace std;

int main() {

int number, sumOfDigits = 0, multOfDigits = 1;

cin >> number;

while (number) {

multOfDigits *= number % 10;

sumOfDigits += number % 10;

number /= 10;

}

cout << fixed << setprecision(3) << (double)multOfDigits / sumOfDigits << endl;

return 0;

}

Тесты

Входные данные	Выходные данные
36	2.000
3456	20.000
1645	7.500

Задача взята отсюда.

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

Related Images:

e-olymp 7338. Постоянная сумма цифр

30/09/2015 by Максим Носов

Задача

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

В единственной строке задано целое одно цифровое число.

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

Количество чисел.

Код

#include <iostream>
using namespace std;

int main() {
    int n,a,b,c,k=0;  // задаем переменные
    cin>>n; //вводим число, на которое будут умножаться все двухзначные числа
    for (int i=10;i<=99;i++) {  //задаем цикл от 10 до 99(все двухзначные числа)
        c=i*n;  //для удобства задаем переменную с - произведение двухзначного числа и заданного нами одно цифрового
        a=i/10+i%10; //задаем переменную а - сума цифр двухзначного числа
        b=(c/10)%10+c%10+c/100;   // и вычисляем сумму цифр числа с
        if (a==b) k++;  //если  суммы чисел а и с равны то добавляем 1 на "счетчик"
    }
    cout<<k;  //выводим на экран количество чисел 
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n,a,b,c,k=0; // задаем переменные

cin>>n; //вводим число, на которое будут умножаться все двухзначные числа

for (int i=10;i<=99;i++) { //задаем цикл от 10 до 99(все двухзначные числа)

c=i*n; //для удобства задаем переменную с - произведение двухзначного числа и заданного нами одно цифрового

a=i/10+i%10; //задаем переменную а - сума цифр двухзначного числа

b=(c/10)%10+c%10+c/100; // и вычисляем сумму цифр числа с

if (a==b) k++; //если суммы чисел а и с равны то добавляем 1 на "счетчик"

}

cout<<k; //выводим на экран количество чисел

return 0;

}

Тесты

№	Входные данные	Выходные данные
1	2	10
2	0	0
3	1	90
4	9	6
5	5	10

Решение

Для начала задаем переменные и вводим с клавиатуры число, на которое будут умножаться все двухзначные числа. Задаем цикл от 10 до 99. Для удобства вводим переменную [latex]c[/latex], которая равна произведению двухзначного числа на входное число и переменную [latex]a[/latex], которая равна сумме цифр входного числа. Далее находим сумму цифр числа с — [latex](c/10)%10+c%10+c/100[/latex]. Если сумма цифр входного числа равна сумме цифр [latex]c[/latex], то добавляем 1 на «счетчик». В конце выводим на экран количество чисел, которые не меняют свою сумму цифр при умножении на число, которое мы ввели с клавиатуры.

Ссылку на код здесь.

Задача взята с сайта.

Related Images:

e-olymp 388. Превращение

30/09/2015 by Молоканов Юрий

Условие

Возьмем какое-нибудь натуральное число [latex]N[/latex]. Будем изменять его следующим образом: если число четное, то разделим его на [latex]2[/latex], если нечетное, прибавим [latex]1[/latex]. После нескольких таких изменений мы всегда получаем число [latex]1[/latex]. Например, из числа [latex]11[/latex] получается число [latex]12[/latex], затем [latex]6[/latex], [latex]3[/latex], [latex]4[/latex], [latex]2[/latex] и, наконец, [latex]1[/latex]. Таким образом, для получения [latex]1[/latex] из [latex]11[/latex] нужно проделать [latex]6[/latex] изменений.

Напишите программу, которая считывает натуральное число и выводит количество изменений данного числа до получения [latex]1[/latex].

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

№	Входные данные	Выходные данные
1	1	0
2	11	6
3	65	13
4	1024	10

Код

#include <iostream>
using namespace std;

int main() {
	int n, i;	// n для числа, i для счета преобразований
	cin >> n;
	for (i = 0; n > 1; i++) n = (n%2>0?n+1:n/2);	// Преобразовываем n, пока не получим 1
	cout << i;	// Выводим значение счетчика
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n, i; // n для числа, i для счета преобразований

cin >> n;

for (i = 0; n > 1; i++) n = (n%2>0?n+1:n/2); // Преобразовываем n, пока не получим 1

cout << i; // Выводим значение счетчика

return 0;

}

Решение

Так как в качестве ответа на задачу нам нужно вывести значение переменной-счетчика, которая отвечает за количество проделанных изменений, то объявлять ее нужно будет не в начальных условиях цикла for, а в пределах главной функции:

#include <iostream>
using namespace std;

int main() {
	int n, i;	// n для числа, i для счета преобразований

#include <iostream>

using namespace std;

int main() {

int n, i; // n для числа, i для счета преобразований

Теперь опишем, каким образом будет работать цикл:

Цикл начинается со значением счетчика 0, так как возможны случаи, когда операций над [latex]n[/latex] вообще не нужно будет производить (конкретно — при [latex]n=1[/latex]).
Поскольку нам гарантируют, что входное число [latex]n[/latex] — натуральное, то цикл будет работать до тех пор, пока [latex]n>1[/latex].
После каждой итерации значение счетчика будет увеличено на [latex]1[/latex].
Тело цикла состоит из единственного оператора присваивания переменной с числом [latex]n[/latex] нового значения. [latex]n[/latex] может быть преобразовано двумя способами, и для определения нужного используется проверка на его четность:
- если [latex]n[/latex] — нечетное, то значение [latex]n[/latex] увеличивается на [latex]1[/latex];
- в противном случае [latex]n[/latex] делится на [latex]2[/latex].

Реализуем описанный алгоритм, после которого отправляем на печать значение счетчика i:

for (i = 0; n > 1; i++) n = (n%2>0?n+1:n/2);
cout << i;

1 2	for (i = 0; n > 1; i++) n = (n%2>0?n+1:n/2); cout << i;

Ссылки

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

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

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

Related Images:

e-olymp 127. Баксы в банке

30/09/2015 by Александр Димитриев

Условие

Папа Карло подарил Буратино [latex]1[/latex] доллар в его первый день рождения, а экономный Буратино сложил подарок в банку. Каждый последующий год папа Карло удваивал свой предыдущий подарок и прибавлял к нему столько долларов, сколько лет исполнилось Буратино, а тот в свою очередь продолжал складывать баксы в банку. На какой [latex]N[/latex]-й день рождения в банке будет не менее чем [latex]S[/latex] долларов?

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

Единственное число — значение [latex]S[/latex]. [latex]1\le S \le 240[/latex].

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

Искомое значение [latex]N[/latex].

Задача взята с сайта e-olymp.

Тесты

Входные данные	Выходные данные
15	3
25	4
9	3
99	5
199	6
333	7
56	5
478	8
809	8

Код

#include <iostream>
using namespace std;

int main() {
    long long s,sum=1,p=1,n=1;
    cin >> s;
    while (sum<s){ 
        n++;
        p=p*2+n;
        sum += p;
    }
    cout << n;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long long s,sum=1,p=1,n=1;

cin >> s;

while (sum<s){

n++;

p=p*2+n;

sum += p;

}

cout << n;

return 0;

}

Решение

В данной задаче [latex]sum[/latex] — сколько долларов в банке, [latex]p[/latex] — сколько долларов Папа Карло подарил Буратино. Пока [latex]sum<s[/latex] мы увеличиваем [latex]N[/latex] на [latex]1[/latex] и считаем сколько Папа Карло подарит Буратино [latex]p=p\cdot 2+n[/latex] и суммируем его с тем что лежит в банке [latex]sum=sum+p[/latex] или же как у меня что одно и тоже [latex]sum += p[/latex]. После этого выводим [latex]N[/latex].
Код программы
Засчитанное решение

Related Images:

e-olymp 192. Просто Фибоначчи

30/09/2015 by Аня Шохина

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

Найти [latex]N[/latex]-е по порядку простое число Фибоначчи.

Во входном файле число [latex]N[/latex], [latex]\left(1\leq N\leq 10 \right)[/latex] В выходной файл следует записать [latex]N[/latex]-е по порядку простое число Фибоначчи.

Тесты

[latex]N[/latex]	Простое число Фибоначчи
3	5
5	89
7	1597
9	514229
10	433494437

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

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

int main() {
	int n;
	cin >> n;
	int a, b, c, d, k;
	a = 1;
	b = 1;
	c = 2;
	bool x;
	int counter = 0;
	while (counter < n){
		x = true;
		c = a + b;
		a = b;
		b = c;
		for (int j = 2; j <= sqrt(c) && x; j++) {
			if((c%j) == 0){
				x = false;
			}
		}
		if (x){
			counter ++;
		}
	}
	cout << c;
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int n;

cin >> n;

int a, b, c, d, k;

a = 1;

b = 1;

c = 2;

bool x;

int counter = 0;

while (counter < n){

x = true;

c = a + b;

a = b;

b = c;

for (int j = 2; j <= sqrt(c) && x; j++) {

if((c%j) == 0){

x = false;

}

if (x){

counter ++;

}

cout << c;

return 0;

}

Код на ideone.com

Выполненное задание на сайте e-olimp.com здесь.

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

Нам необходимо вычислить первые десять элементов последовательности Фибоначчи. Для этого будем использовать цикл. Пусть [latex] a<b<c [/latex] , где [latex] a, b, c [/latex] являются членами последовательности Фибоначчи. Обозначим, что элемент последовательности равен сумме двух ему предшествующих элементов. Далее присвоим переменным [latex]a, b[/latex] значения следующих элементов последовательности соответственно. Таким образом присваиваем переменной [latex] a [/latex] значение переменной [latex] b [/latex] , переменной [latex] b[/latex] — значение переменной [latex] c [/latex] , а переменной [latex] c [/latex] — значение равное [latex](a+b)[/latex].
Но не каждый элемент последовательности Фибоначчи является простым числом. Следовательно, нам необходимо проверить делится ли без остатка полученное нами число на какое-либо число, отличное от [latex] 0 [/latex] , [latex] 1 [/latex] и самого себя. Таким образом, если найденный элемент [latex] c [/latex] делится без остатка на целые числа, принадлежащие отрезку [latex]\left[2;\sqrt{c} \right][/latex] , то найденный элемент не является простым числом. Тогда необходимо рассмотреть следующий элемент последовательности Фибоначчи. Для этого введем логическую переменную [latex] (bool x) [/latex] , которая будет принимать значение истинны только тогда, когда число простое.
Когда логическая переменная принимает значение истины, то увеличим счетчик на единицу. А искать последующие значения элемента[latex] c [/latex] будем до тех пор, пока значение счетчика не станет равным числу [latex] N [/latex].