Category Archives: 3. Циклы

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

Циклы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Тесты:

n	m	answer
4	1	YES
6	3	NO

Решение:

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

Код:

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

#include <iostream>

using namespace std;

int main() {

int n, m, p;

while(cin >> n >> m) {

if (m > n) {

p = n;

n = m;

m = p;

}

while (m > 0) {

p = n % m;

if (p != 0) {

n = m;

m = p;

}

else break;

}

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

}

return 0;

}

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

Related Images:

e-olymp 2061. Юные программисты

30/09/2015 by Андрей Яроцкий

Задача

Известно, что в школе не менее чем [latex]k_1[/latex] учеников, но не более чем [latex]k_2[/latex] учеников. Также известно, что каждый мальчик дружит с [latex]n[/latex] девочками, а каждая девочка с [latex]m[/latex] мальчиками. Какое минимальное количество учеников может быть в школе, и сколько в школе мальчиков и девочек?

Тесты:

№	Ввод	Вывод
1	20 30 4 5	27 15 12
2	40 50 5 4	45 20 25

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

#include <iostream>
using namespace std;
 
int main() {
   int k1, k2, n, m;
   int b, g; //b-boys;g-girls
   cin >> k1 >> k2 >> n >> m;
   for (g = n; true; g++)
   {
      b = g * m / n;
      if (((g * m) % n) == 0 && b + g >= k1) break; // перебираем варианты пока количество мальчиков не станет целым а сумма всех учеников будет больше k1
   }
   cout << b + g << " " << b << " " << g << endl;
   return 0;
}

#include <iostream>

using namespace std;

int main() {

int k1, k2, n, m;

int b, g; //b-boys;g-girls

cin >> k1 >> k2 >> n >> m;

for (g = n; true; g++)

{

b = g * m / n;

if (((g * m) % n) == 0 && b + g >= k1) break; // перебираем варианты пока количество мальчиков не станет целым а сумма всех учеников будет больше k1

}

cout << b + g << " " << b << " " << g << endl;

return 0;

}

Решение:

Увеличиваем количество девочек на 1 пока количество мальчиков по формуле [latex]b = g \cdot m / n[/latex] не станет целочисельным значением и сумма мальчиков и девочек будет больше или равна минимальному возможному количеству учеников [latex]k_1[/latex].

Условие задачи можно найти на сайте e-olymp.
Ссылка на решение задачи на ideone.com здесь.
Ссылка на полностью решенную задачу здесь.

Related Images:

e-olymp 2. Цифры

30/09/2015 by Холодков Юрий

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

Условие

Вычислить количество цифр целого неотрицательного числа [latex]n[/latex].

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

Одно не отрицательное целое число [latex]n[/latex] [latex](0<=n<=2*10^9)[/latex].

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

Количество цифр в числе [latex]n[/latex].

Тесты

Число	Количество цифр
1	1
20	2
123	3

Код

#include <iostream>
using namespace std;

int main() {
	int x, n=1;
	cin >> x;
	while ((x/=10) > 0) n++;
	cout << n;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int x, n=1;

cin >> x;

while ((x/=10) > 0) n++;

cout << n;

return 0;

}

Решение

Сначала объявляем переменную [latex] n [/latex] для подсчета цифр в числе и присваиваем ей значение 1. Далее используем цикл while, проверкой которого ставим деление числа на 10 — так как тип числа int, это «отбрасывает» последнюю цифру в числе. Пока результат проверки истинный, инкриментируем n на 1.

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

Засчитанное решение

Альтернативное решение с помощью десятичного логарифма

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

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

int main() {
	int x;
	cin >> x;
	cout << (x==0? 1: int (log10 (x) + 1));
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int x;

cin >> x;

cout << (x==0? 1: int (log10 (x) + 1));

return 0;

}

Код решения

Related Images:

e-olimp 7365. Молоко и пирожок

30/09/2015 by Настя Ивасенко

Ученикам первого класса дополнительно дают стакан молока и пирожок, если вес первоклассника менее 30 кг. В первых классах школы учится [latex]n[/latex] учеников. Стакан молока имеет емкость 200 мл, а упаковки молока – 0.9 л. Определить количество дополнительных пакетов молока и пирожков, необходимых каждый день.

Тесты

Количество детей	Вес	Количество упаковок молока	Количество пирожков
3	30 29 30	1	1
5	25 41 56 20 20	1	3
4	30 30 30 30	0	0
7	25 26 27 28 29 23 24	2	7

Код

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

int main() {
    int p=0; //пирожки
    int n, k; //количество детей, вес и упаковки молока
    double m, u, w; 
    cin >> n;
    m=0.2; u=0.9;
    for(int i=0; i<n; i++) {
        cin >> w;
        if (w<30) p++;
        if(w>=30) p=p+0;
    }
    k= ceil(p*m/u);
    cout << k << " " << p;
    return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main() {

int p=0; //пирожки

int n, k; //количество детей, вес и упаковки молока

double m, u, w;

cin >> n;

m=0.2; u=0.9;

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

cin >> w;

if (w<30) p++;

if(w>=30) p=p+0;

}

k= ceil(p*m/u);

cout << k << " " << p;

return 0;

}

Решение

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

По количеству пирожков мы можем найти количество упаковок молока. При этом мы можем получить не целое число. Чтобы избежать этого, подключаем библиотеку <cmath> и используем округление вверх ceil .

Посмотреть код на ideone можна здесь.

Проверить правильность на e-olimp можна здесь.

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:

e-olymp 36. Змей Горыныч

29/09/2015 by Грешилов Константин

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

Условие:

В некотором царстве жил Змей Горыныч. У него было [latex]N[/latex] голов и [latex]M[/latex] хвостов. Иван-царевич решил уничтожить губителя человеческих душ, для чего ему его кума Баба Яга подарила волшебный меч, так как только им можно убить Змея Горыныча. Если отрубить одну голову, то на её месте вырастает новая, если отрубить хвост, то вместо него вырастет 2 хвоста. Если отрубить два хвоста, то вырастает 1 голова, и только когда отрубить 2 головы, то не вырастет ничего. Змей Горыныч гибнет только в том случае, когда ему отрубить все головы и все хвосты. Определить минимальное количество ударов мечом, нужное для уничтожения Змея Горыныча.

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

Два числа [latex]N[/latex], [latex]M[/latex] ([latex]0[/latex] [latex]<=[/latex][latex]N[/latex], [latex]M[/latex][latex]<=[/latex][latex]1000[/latex]).

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

Единственное число – минимальное количество ударов мечом, или -1, если уничтожить Змея Горыныча невозможно.

Тесты:

N	M	Количество ударов
3	3	9
3	0	-1
0	9	12
0	0	0
3	2	3
19	114	95

Решение

#include <iostream>
using namespace std;

int main() {
	int N, M, count = 0;
	cin>>N>>M;
	if ((N%2!=0)&&(M==0)) //здесь проверяется, возможно ли убить Горыныча
	{
		cout<<"-1"<<endl;// вывод "-1" в противном случае
	}
	else 
	{
		while ((N>0)||(M>0)) //цикл будет выполняться до тех пор, пока существует хоть одна голова или хвост
		{
			if (M%2==1) //если хвостов нечетное количество, то посредством отрубания одного хвоста увеличиваем число их на 1
			{
				count++;// здесь и далее таким образом будет увеличиваться счетчик надрезов
				M++;
			}
			if ((N%2==1)&&(M>=2)) //если голов нечетное количество, то отрубая два хвоста увеличиваем количество голов на 1
			{
				M-=2;
				N++;
				count++;
			}
			if ((M%2==0)&&(N%2==0)&&((N+(M/2))%2==0)) //если число голов и хвостов четное, и если количество хвостов при делении на два дает четное число
			{
				count=count+M/2+((N+M/2)/2);//то увеличиваем счетчик надрезов
				N=0;
				M=0;//и обнуляем количество голов и хвостов для выхода их цикла
			}
			else  //если не выполняется какое-либо из условий прошлого ветвления, то увеличиваем количество хвостов на 1
			{
				M++;
				count++;
			}
		}
		cout<<count<<endl;//выводим количество ударов
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int N, M, count = 0;

cin>>N>>M;

if ((N%2!=0)&&(M==0)) //здесь проверяется, возможно ли убить Горыныча

{

cout<<"-1"<<endl;// вывод "-1" в противном случае

}

else

{

while ((N>0)||(M>0)) //цикл будет выполняться до тех пор, пока существует хоть одна голова или хвост

{

if (M%2==1) //если хвостов нечетное количество, то посредством отрубания одного хвоста увеличиваем число их на 1

{

count++;// здесь и далее таким образом будет увеличиваться счетчик надрезов

M++;

}

if ((N%2==1)&&(M>=2)) //если голов нечетное количество, то отрубая два хвоста увеличиваем количество голов на 1

{

M-=2;

N++;

count++;

}

if ((M%2==0)&&(N%2==0)&&((N+(M/2))%2==0)) //если число голов и хвостов четное, и если количество хвостов при делении на два дает четное число

{

count=count+M/2+((N+M/2)/2);//то увеличиваем счетчик надрезов

N=0;

M=0;//и обнуляем количество голов и хвостов для выхода их цикла

}

else //если не выполняется какое-либо из условий прошлого ветвления, то увеличиваем количество хвостов на 1

{

M++;

count++;

}

cout<<count<<endl;//выводим количество ударов

}

return 0;

}

Описание решения:

При решении данной задачи было рассмотрено несколько случаев.

Змея Горыныча убить невозможно. Это возможно только в том случае, когда у него нечетное количество голов, и нет ни одного хвоста, так как при наличии хотя бы одного хвоста становится возможным увеличение количества хвостов и голов до необходимого, путем отрубания одного, или двух хвостов соответственно. Чтобы определить возможность уничтожения Змея, делаем проверку: если количество голов нечетное и хвостов нет, то выводим «-1». Если эти условия не выполняются, то переходим ко второму пункту решения.

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

while ((N>0)||(M>0)) //цикл будет выполняться до тех пор, пока существует хоть одна голова или хвост

13	while ((N>0)\|\|(M>0)) //цикл будет выполняться до тех пор, пока существует хоть одна голова или хвост

Горыныча можно убить тогда и только тогда, когда при отрубании всех хвостов получается четное количество голов. Отсюда, необходимо, чтобы у Змея было четное количество хвостов, и сумма голов и количества хвостов, деленного на два, была четным числом. Поэтому будем работать по простому алгоритму:

Если количество хвостов [latex]M[/latex] нечетное, то отрубаем один хвост, на месте которого вырастает два новых, и увеличиваем счетчик ударов [latex]count[/latex] на один.
Если количество голов нечетное, и хвостов больше одного, то отрубаем два хвоста, тем самым увеличивая количество голов на 1, и увеличиваем счетчик.
Если количество голов и хвостов четное, и если количество хвостов при делении на два дает четное число, то мы увеличиваем счетчик на [latex]M/2+((N+M/2)/2)[/latex], и приравниваем количество голов и хвостов нулю.
Если какое-то из условий пункта 3 не выполняется, то увеличиваем количество хвостов на 1, и увеличиваем счетчик ударов.
Повторяем алгоритм до тех пор, пока не убьем Горыныча.

После выхода из цикла в счетчике [latex]count[/latex] находится минимальное число ударов, необходимое для уничтожения Змея Горыныча. Выводим его на экран, и переходим на новую строку с помощью команды [latex]endl[/latex].

Здесь код программы на сайте ideone.com.

Для перехода к странице на e-olimp с полностью выполненным данным заданием щелкните здесь.

Related Images:

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

27/09/2015 by Таня Корнилова

Задача e-olimp.com №388

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

Условие

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

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

Число N (1 ≤ N ≤ 10⁹).

Тесты

Входные данные(N)	Выходные данные
11	6
43	9
1	0

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

#include <iostream>
using namespace std;

int main() {
	int N, counter=0;
	cin >> N;
	while(N!=1){
		counter++;
		if(N%2==0){ 
			N = N/2;
		} 
		else{
			N++;
		}
	}		
	cout << counter << endl;
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int N, counter=0;

cin >> N;

while(N!=1){

counter++;

if(N%2==0){

N = N/2;

}

else{

N++;

}

cout << counter << endl;

return 0;

}

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

Решение

Пусть [latex]N[/latex] — это число, которое мы будем изменять, а [latex]counter[/latex] — количество превращений. Цикл должен выполняться до того момента, пока [latex]N \neq 1[/latex]. Чтоб проверить число на чётность/нечётность, делим его по модулю и сравниваем остаток с нулём. Если число — чётное, то делим его на 2, в противном случае — добавляем единицу, и при выполнении каждого действия, увеличиваем количество превращений на 1.

Related Images:

e-olymp 11. Большая точность

24/09/2015 by Катя Писова

Задача. Дана рациональная дробь [latex]\frac{m}{n}[/latex]. Запишите её в виде десятичной дроби с точностью [latex] k[/latex] знаков после запятой.

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

В одной строке записано 3 числа [latex]m,n,k[/latex]. [latex]{{0}<{m,n}\leq{100}}[/latex], [latex]{{0}\leq{k}\leq{1000}}[/latex].

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

Вывести [latex]k[/latex] точных значащих цифр после десятичной точки искомого числа.

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

Деление уголком

Разделим [latex]m[/latex] на [latex]n[/latex] в столбик. Определим, сколько раз [latex]n[/latex] помещается в [latex]m[/latex]. Это будет целая часть частного. Умножим ее на [latex]n[/latex] и отнимем от [latex]m[/latex]. Таким образом получим остаток от деления. Будем умножать его на [latex]10[/latex] (эквиваленто сноске [latex]0[/latex]) и проводить такую же операцию, как при нахождении целой части пока не закончится цикл. Так мы определим все цифрs после запятой.

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

#include <iostream>
int main() {
    int m, n, k;
    std::cin >> m >> n >> k;
    std::cout << m / n << ".";
    for (int i = 0; i < k; ++i) {
       m = (m % n) * 10;
       std::cout << m / n;
    }
}

#include <iostream>

int main() {

int m, n, k;

std::cin >> m >> n >> k;

std::cout << m / n << ".";

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

m = (m % n) * 10;

std::cout << m / n;

}

Проверка

(По условию задачи):

Ввод:	#	Вывод:
m	1	0.500
n	2
k	3

Ввод:	#	Вывод:
m	2	0.66666666666666666666
n	3
k	20

Ввод:	#	Вывод:
m	9	1.000000000
n	9
k	9

Ввод:	#
m	1	0.33333333333333333333
n	3
k	20

Здесь можно посмотреть решение на ideone.com

Здесь можно посмотреть условие задачи на e-olymp.com

Related Images:

e-olymp 22. «Зеркально простые» числа

22/09/2015 by Таран Таня

Назовем число «зеркально простым», если само число является простым, и простым является число, записанное теми же цифрами в обратном порядке.

Найти количество «зеркально простых» чисел на промежутке от [latex]a[/latex] до [latex]b[/latex].

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

Два числа [latex]a[/latex] и [latex]b[/latex] ( [latex]1[/latex][latex]\le[/latex] [latex]a[/latex], [latex]b[/latex] [latex]\le[/latex] [latex]10000[/latex]).

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

Вывести количество «зеркально простых» чисел на промежутке от [latex]a[/latex] до [latex]b[/latex] включительно.

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

Тесты

Границы промежутка	Количество «зеркально простых» чисел
1 10	4
100 200	12
1008 1230	19
3340 3950	31
9900 10000	4

Алгоритм

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

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

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

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

#include <iostream>
using namespace std;

int main() {
    int a, b;
    int number1, number2;// переменные для хранения текущего числа из промежутка и "зеркального" соответственно
    int counter = 0;// счетчик количества "зеркально простых" чисел
    cin >> a >> b;
    if(a > b){
       a += b;
       b = a - b;
       a -= b;
    }// меняем местами границы промежутка, если они введены в неправильном порядке
    if (a == 1) 
        counter--;// декрементируем счетчик, если в промежуток попадает число 1, которое не является простым
    for (int i = a; i <= b; i++){
         number1 = i; 
         bool f1 = true;// флаг выполнения условия для number1
         bool f2 = true;// флаг выполнения условия для number2
         for (int j = 2; j*j <= number1; j++){
              f1 = number1%j;
              if (!f1) 
                  break;
         }// проверяем является ли number1 простым
         if (f1){
             number2 = 0;
             while (number1 > 0){
                    number2 = number2*10 + number1%10;
                    number1 /= 10;
             }// собираем число "зеркальное" текущему
             for (int j = 2; j*j <= number2; j++){
                  f2 = number2%j;
                  if (!f2) 
                      break; 
             }// проверяем является ли number2 простым 
             if (f2) 
                 counter++;// инкрементируем счетчик 
         }
    }
    cout << counter;
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int a, b;

int number1, number2;// переменные для хранения текущего числа из промежутка и "зеркального" соответственно

int counter = 0;// счетчик количества "зеркально простых" чисел

cin >> a >> b;

if(a > b){

a += b;

b = a - b;

a -= b;

}// меняем местами границы промежутка, если они введены в неправильном порядке

if (a == 1)

counter--;// декрементируем счетчик, если в промежуток попадает число 1, которое не является простым

for (int i = a; i <= b; i++){

number1 = i;

bool f1 = true;// флаг выполнения условия для number1

bool f2 = true;// флаг выполнения условия для number2

for (int j = 2; j*j <= number1; j++){

f1 = number1%j;

if (!f1)

break;

}// проверяем является ли number1 простым

if (f1){

number2 = 0;

while (number1 > 0){

number2 = number2*10 + number1%10;

number1 /= 10;

}// собираем число "зеркальное" текущему

for (int j = 2; j*j <= number2; j++){

f2 = number2%j;

if (!f2)

break;

}// проверяем является ли number2 простым

if (f2)

counter++;// инкрементируем счетчик

}

cout << counter;

return 0;

}

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

Засчитанное решение

Related Images:

e-olymp 109. Нумерация

22/09/2015 by Сплошнов Кирилл

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

Условие

Для нумерации [latex]M[/latex] страниц книги использовали [latex]N[/latex] цифр. По заданному [latex]N[/latex] вывести [latex]M[/latex] или [latex]0[/latex], если решения не существует. Нумерация начинается с первой страницы.

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

Единственное число [latex]N[/latex]. В книге не более [latex]1001[/latex] страницы.

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

Искомое количество страниц.

Тесты :

N	8	21	22	113	999	1001
M	8	15	0	61	369	0

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

#include <iostream>
using namespace std;

int main()
{
	int N;
	cin >> N;
	for (int i = 1; true; i++) // i - номер страницы, будем отнимать от N количество цифр в i
    {
		if (i < 10) // в i одна цифра
			N --;
		else if (i >= 10 && i < 100) // 2 цифры
			N -= 2;
		else if (i >= 100 && i < 1000) // 3 цифры
			N -= 3;
		else  // 4 цифры
			N -= 4;
		if (N == 0) // если лишних цифр у нас не осталось
		{
			cout << i << endl;
			break;
		}
		else if (N < 0) // иначе выводим "0"
		{
			cout << 0 << endl;
			break;
		}
    }
	return 0;
}

#include <iostream>

using namespace std;

int main()

{

int N;

cin >> N;

for (int i = 1; true; i++) // i - номер страницы, будем отнимать от N количество цифр в i

{

if (i < 10) // в i одна цифра

N --;

else if (i >= 10 && i < 100) // 2 цифры

N -= 2;

else if (i >= 100 && i < 1000) // 3 цифры

N -= 3;

else // 4 цифры

N -= 4;

if (N == 0) // если лишних цифр у нас не осталось

{

cout << i << endl;

break;

}

else if (N < 0) // иначе выводим "0"

{

cout << 0 << endl;

break;

}

return 0;

}

Примечание

Общее (и более компактное) решение можно написать, подключив библиотеку <cmath> и воспользовавшись функцией логарифма с основанием 10.

Код программы (вторая версия)

#include <iostream>
#include <cmath>
using namespace std;
 
int main()
{
	int N;
	cin >> N;
	for (int i = 1; true; i++) // i - номер страницы, будем отнимать от N количество цифр в i
    {
		N -= floor(log10(i) + 1);
		if (N == 0) // если лишних цифр у нас не осталось
		{
			cout << i << endl;
			break;
		}
		else if (N < 0) // иначе выводим "0"
		{
			cout << 0 << endl;
			break;
		}
    }
	return 0;
}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

int N;

cin >> N;

for (int i = 1; true; i++) // i - номер страницы, будем отнимать от N количество цифр в i

{

N -= floor(log10(i) + 1);

if (N == 0) // если лишних цифр у нас не осталось

{

cout << i << endl;

break;

}

else if (N < 0) // иначе выводим "0"

{

cout << 0 << endl;

break;

}

return 0;

}

Ссылки

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

Рабочий код на Ideone.com .

Related Images:

e-olymp 128. Счастливые билеты

21/09/2015 by Женя Максимова

Задача. Подсчитайте количество счастливых билетов, у которых сума первых трёх цифр равна [latex]N(N \leq 27)[/latex].

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

Тесты

Число [latex]N[/latex]	3	27	26	1	10
Количество билетов	100	1	9	9	3969

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

#include <iostream>
using namespace std;
int main() 
{
  int N, c = 0;
  cin >> N;
  for ( int i = 0; i < 10; i++ ) //цикл, перебирающий все варианты первой цифры трехзначного числа
  {
     for ( int j = 0; j < 10; j++ ) //вложенный цикл, перебирающий все варианты второй цифры
     {
        if ( N - i - j >= 0 && N - i - j < 10 ) //условие для третьей цифры
        { c++; } //подсчет подходящих номеров
     }
  }
  cout << c*c; //увеличение количества в c раз для шестизначного числа
  return 0;
}

#include <iostream>

using namespace std;

int main()

{

int N, c = 0;

cin >> N;

for ( int i = 0; i < 10; i++ ) //цикл, перебирающий все варианты первой цифры трехзначного числа

{

for ( int j = 0; j < 10; j++ ) //вложенный цикл, перебирающий все варианты второй цифры

{

if ( N - i - j >= 0 && N - i - j < 10 ) //условие для третьей цифры

{ c++; } //подсчет подходящих номеров

}

cout << c*c; //увеличение количества в c раз для шестизначного числа

return 0;

}

Алгоритм

Любой шестизначный номер мы можем представить как 2 трехзначных номера.

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

Когда в цикле встречается подходящая комбинация, мы увеличиваем счетчик [latex]c[/latex] на 1. Поскольку на самом деле номер шестизначный, то каждой удачной комбинации в первой его половине будет соответствовать [latex]c[/latex] комбинаций во второй. Следовательно, искомое число счастливых билетов будет равно [latex]c \cdot c[/latex].

Решение

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

Related Images:

e-olymp 29. Уровень палиндромности

15/09/2015 by Таран Таня

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

Найти уровень палиндромности заданного числа [latex]M[/latex].

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

Единственное число [latex]M[/latex] ([latex]0[/latex] [latex] <[/latex] [latex]M[/latex] [latex] <[/latex] [latex]10000[/latex]).

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

Единственное число – уровень палиндромности.

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

Тесты

Входные данные	Выходные данные
1	0
79	6
101	0
198	5
865	2
9998	6

Алгоритм

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

Для начала инициализируем счетчик, который хранит в себе текущее значение уровня палиндромности, и логическую переменную, значение которой ложно до тех пор пока палиндром не найден. Данное условие и будет критерием для выполнения тела основного цикла.
Присвоив значения переменным в цикле, выполняем последовательный разбор введенного числа на цифры и сборку «зеркального» числа.
Проверяем равенство числа и ему обратного.
Выполнение условного оператора сигнализирует о том, что палиндром найден, следовательно выводим «уровень», изменяем значение логической переменной на противоположное и выходим из цикла.
В противном случае суммируем текущее число и «зеркальное», инкрементируем счетчик.
Повторяем пункты 2, 3, 5 до истинности пункта 3 и перехода к 4.

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

#include <iostream>
using namespace std;

int main() {
	long x, x1, x2;// переменные для хранения числа, его копии и числа записанного в обратном порядке соответственно
	int c;
	int k = 0;// счетчик "уровня палиндромности"
	cin >> x;
	bool f = false;// флаг выполнения условия палиндромности числа
	while(!f){
		 x1 = x;
		 x2 = 0;
		 while (x1 > 0){
		        c = x1%10;
		        x1 /= 10;
		        x2 = x2*10 + c;// собираем число записанное в обратном порядке
	     }
	if (x == x2){
		cout << k;// выводим счетчик, если число палиндром
		f = true; 
		break;// выход из цикла, при условии, что палиндром найден
	} else { 
			x += x2;// суммируем значение числа и обратно записанного, если оно не является палиндромом
			k++; 
	}
	}
	return 0;
}

#include <iostream>

using namespace std;

int main() {

long x, x1, x2;// переменные для хранения числа, его копии и числа записанного в обратном порядке соответственно

int c;

int k = 0;// счетчик "уровня палиндромности"

cin >> x;

bool f = false;// флаг выполнения условия палиндромности числа

while(!f){

x1 = x;

x2 = 0;

while (x1 > 0){

c = x1%10;

x1 /= 10;

x2 = x2*10 + c;// собираем число записанное в обратном порядке

}

if (x == x2){

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

f = true;

break;// выход из цикла, при условии, что палиндром найден

} else {

x += x2;// суммируем значение числа и обратно записанного, если оно не является палиндромом

k++;

}

return 0;

}

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

Засчитанное решение

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;
}

#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;

}

Related Images:

А1035

28/06/2015 by Ковальський Олександр Дмитрович

Задача. Указать маршрут коня. Начинающегося на одном заданном поле шахматной доски и оканчивающемся на другом. Никакое поле не должно встречаться в маршруте дважды.

Пример

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

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

a1
b3
d2
b1

a1
h8

a1
c2
e3
g2
h4
g6
h8

Решение

#include <iostream>
#include <math.h>
using namespace std;

struct coord
	{
		int x,y;
	};
const int n=8;
int main()
	{
		int chessboard[n][n];
		bool k;
		string s0,s1;
		int step=0;
		coord start, finish;
		cin>>s0>>s1;
		start.x=(int)s0[0]-97;
		start.y=s0[1]-49;
		finish.x=(int)s1[0]-97;
		finish.y=s1[1]-49;
		for(int i=0;i<n;i++)
			for(int j=0;j<n;j++)
				chessboard[i][j]=-1;
		chessboard[start.x][start.y]=0;
		k=true;
		while(chessboard[finish.x][finish.y]==-1)
			{
				k=false;
				for(int i=0;i<n;i++)
					for(int j=0;j<n;j++)
						if(chessboard[i][j]==step)
							{
								for(int a=fmax(0,i-2);a<=fmin(n-1,i+2);a++)
									for(int b=fmax(0,j-2);b<=fmin(n-1,j+2);b++)
										if((chessboard[a][b]==-1)&&(((abs(i-a)==2)&&(abs(j-b)==1))||((abs(i-a)==1)&&(abs(j-b)==2))))
											{
              									chessboard[a][b]=step+1;
              									k=true;
											}
							}
					if(!k) chessboard[finish.x][finish.y]=0;
					else step++;
			}
		if (chessboard[finish.x][finish.y]==0) cout<<"start=finish"<<endl;
		else
			{
				coord path[8];
				path[0].x=finish.x;
				path[0].y=finish.y;
				for(int i=0;i<step;i++)
					{
						int x=path[i].x;
						int y=path[i].y;
						for(int a=fmax(0,x-2);a<=fmin(n-1,x+2);a++)
							for(int b=fmax(0,y-2);b<=fmin(n-1,y+2);b++)
								if((chessboard[a][b]==chessboard[x][y]-1)&&(((abs(x-a)==2)&&(abs(y-b)==1))||((abs(x-a)==1)&&(abs(y-b)==2))))
									{
										path[i+1].x=a;
										path[i+1].y=b;
									}
					}
				for(int i=step;i>=0;i--)
				cout<<(char)(path[i].x+97)<<path[i].y+1<<endl;
			}
		return 0;
	}

#include <iostream>

#include <math.h>

using namespace std;

struct coord

{

int x,y;

};

const int n=8;

int main()

{

int chessboard[n][n];

bool k;

string s0,s1;

int step=0;

coord start, finish;

cin>>s0>>s1;

start.x=(int)s0[0]-97;

start.y=s0[1]-49;

finish.x=(int)s1[0]-97;

finish.y=s1[1]-49;

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

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

chessboard[i][j]=-1;

chessboard[start.x][start.y]=0;

k=true;

while(chessboard[finish.x][finish.y]==-1)

{

k=false;

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

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

if(chessboard[i][j]==step)

{

for(int a=fmax(0,i-2);a<=fmin(n-1,i+2);a++)

for(int b=fmax(0,j-2);b<=fmin(n-1,j+2);b++)

if((chessboard[a][b]==-1)&&(((abs(i-a)==2)&&(abs(j-b)==1))||((abs(i-a)==1)&&(abs(j-b)==2))))

{

chessboard[a][b]=step+1;

k=true;

}

if(!k) chessboard[finish.x][finish.y]=0;

else step++;

}

if (chessboard[finish.x][finish.y]==0) cout<<"start=finish"<<endl;

else

{

coord path[8];

path[0].x=finish.x;

path[0].y=finish.y;

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

{

int x=path[i].x;

int y=path[i].y;

for(int a=fmax(0,x-2);a<=fmin(n-1,x+2);a++)

for(int b=fmax(0,y-2);b<=fmin(n-1,y+2);b++)

if((chessboard[a][b]==chessboard[x][y]-1)&&(((abs(x-a)==2)&&(abs(y-b)==1))||((abs(x-a)==1)&&(abs(y-b)==2))))

{

path[i+1].x=a;

path[i+1].y=b;

}

for(int i=step;i>=0;i--)

cout<<(char)(path[i].x+97)<<path[i].y+1<<endl;

}

return 0;

}

Читаем входные данные. Преобразуем их в координаты начального и финального поля на шахматной доске. Массив chessboard сначала заполняем -1 (не пройденные поля), затем значение в поле с начальными координатами присваиваем 0. Затем будем отмечать все доступные ходы коня до тех пор пока не изменится значение в финальном поле. Затем, если у нас не совпали начальное и финальное поле будем восстанавливать путь коня. Создаем массив в котором и будет путь коня. Первое значение которое мы заносим в массив будет наше финальное поле. Затем с этого поля будем рассматривать все возможные ходы которые пройдут по уже помеченным клеткам. Если в финальное поле можно было попасть несколькими путями одинаковой длины то нам не имеет значение каким из них возвращаться в начальное поле. Затем выводим массив пути в обратном порядке.

Код на ideone.

Related Images:

А1033

17/06/2015 by Марченко Філіп Олександрович

Условие

Получить все размещения из [latex]9[/latex] элементов [latex]\left\{1,2, \ldots, 9\right\}[/latex] по [latex]5[/latex] элементов в каждом.

Код на С++

#include <iostream>
#include <algorithm>
#include <math.h>

using namespace std;


int a1[6]; int a2[6]; int cnt=0;


//генерация перестановок
void permut (int m){
	for (int j=1; j<=m; j++) a2[j]=a1[j];
	int i = 1;
	int j;
	while (i != 0){
		for (int i=1; i<=m; i++) cout << a2[i];
		cout << endl;
		i=m-1;
		while (a2[i]>a2[i+1]) i--;
		j=m;
		while (a2[j]<a2[i]) j--;
		swap (a2[j],a2[i]);
		int k=i+1;
		int kk=i+floor((m-i)/2);
		while (k<=kk){
			swap(a2[k],a2[m-k+i+1]);
			k++;
		}
		cnt++;
	}
}

int main() {
    int n=9, k=5;
	int p=k;
        //генерация размещений
	for (int i=1; i<=k; i++) a1[i]=i;
	while(p>=1){
        permut(k);
		if (a1[k]==n)
			p-=1;
		else
			p=k;
		if (p>=1)
			for (int i=k; i>=p; i--) a1[i]=a1[p]+i-p+1;
	}
        //проверка количества размещений
	cout << cnt << endl;
	return 0;
}

#include <iostream>

#include <algorithm>

#include <math.h>

using namespace std;

int a1[6]; int a2[6]; int cnt=0;

//генерация перестановок

void permut (int m){

for (int j=1; j<=m; j++) a2[j]=a1[j];

int i = 1;

int j;

while (i != 0){

for (int i=1; i<=m; i++) cout << a2[i];

cout << endl;

i=m-1;

while (a2[i]>a2[i+1]) i--;

j=m;

while (a2[j]<a2[i]) j--;

swap (a2[j],a2[i]);

int k=i+1;

int kk=i+floor((m-i)/2);

while (k<=kk){

swap(a2[k],a2[m-k+i+1]);

k++;

}

cnt++;

}

int main() {

int n=9, k=5;

int p=k;

//генерация размещений

for (int i=1; i<=k; i++) a1[i]=i;

while(p>=1){

permut(k);

if (a1[k]==n)

p-=1;

else

p=k;

if (p>=1)

for (int i=k; i>=p; i--) a1[i]=a1[p]+i-p+1;

}

//проверка количества размещений

cout << cnt << endl;

return 0;

}

Код на Java:

import java.util.*;
import java.lang.*;
import java.io.*;
 
class A {
	public static int cnt = 0;
	public static void Permutation (int m, int[] a1, int[] a2){
		for (int j=1; j<=m; j++) a2[j] = a1[j];
		int j;
		int i = 1;
		while (i != 0){
			//for (i=1; i<=m; i++) System.out.print(a2[i]);
			//System.out.print("\n");
			i=m-1;
			while (a2[i]>a2[i+1]) i--;
			j=m;
			while (a2[j]<a2[i]) j--;
			int tmp = a2[j];
			a2[j] = a2[i];
			a2[i] = tmp;
			int k=i+1;
			int kk=i + (m-i)/2;
			while (k<=kk){
				tmp = a2[k];
				a2[k] = a2[m-k+1+i];
				a2[m-k+1+i] = tmp;
				k++;
			}
			cnt++;
		}
	}
	public static void main (String[] args) {
		int[] a1; int[] a2;
		a1 = new int [6];
		a2 = new int [6];
		int n=9, k=5;
		int p=k;
		for (int i=1; i<=k; i++) a1[i]=i;
		while(p>=1){
	        Permutation(k, a1, a2);
			if (a1[k]==n)
				p-=1;
			else
				p=k;
			if (p>=1)
				for (int i=k; i>=p; i--) a1[i]=a1[p]+i-p+1;
		}
		System.out.println(cnt);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class A {

public static int cnt = 0;

public static void Permutation (int m, int[] a1, int[] a2){

for (int j=1; j<=m; j++) a2[j] = a1[j];

int j;

int i = 1;

while (i != 0){

//for (i=1; i<=m; i++) System.out.print(a2[i]);

//System.out.print("\n");

i=m-1;

while (a2[i]>a2[i+1]) i--;

j=m;

while (a2[j]<a2[i]) j--;

int tmp = a2[j];

a2[j] = a2[i];

a2[i] = tmp;

int k=i+1;

int kk=i + (m-i)/2;

while (k<=kk){

tmp = a2[k];

a2[k] = a2[m-k+1+i];

a2[m-k+1+i] = tmp;

k++;

}

cnt++;

}

public static void main (String[] args) {

int[] a1; int[] a2;

a1 = new int [6];

a2 = new int [6];

int n=9, k=5;

int p=k;

for (int i=1; i<=k; i++) a1[i]=i;

while(p>=1){

Permutation(k, a1, a2);

if (a1[k]==n)

p-=1;

else

p=k;

if (p>=1)

for (int i=k; i>=p; i--) a1[i]=a1[p]+i-p+1;

}

System.out.println(cnt);

}

Решение

При решении этой задачи мне понадобились 2 источника информации:

Там были приведены алгоритмы генерирования перестановок («Комбинаторные алгоритмы», стр. 27-29) и генерирования сочетаний («Комбинаторика для программистов», стр. 39-41).
Размещения я получал следующим образом:

Посчитал кол-во всевозможных размещений по формуле [latex]A^{k}_{n}=\frac{n!}{(n-k)!}=\frac{9!}{4!}=15120[/latex];
Заметил, что размещения — это перестановки всех уникальных комбинаций из 5 чисел (т.е сочетаний);
Поскольку кол-во перестановок [latex]P_{k}=k![/latex], а кол-во сочетаний — [latex]C_{n}^{k}=\frac{n!}{k!(n-k)!}[/latex], то кол-во размещений [latex]A_{n}^{k}=P_{k}\times{C_{n}^{k}}=\frac{n!k!}{k!(n-k)!}=\frac{n!}{(n-k)!}=15120[/latex];

Таким образом, генерируя вначале сочетание, я генерировал перестановки этого сочетания. В результате вышло 15120 размещений.

Related Images:

e-olymp 5072. Подсчет количества ребер (ОГ)

28/05/2015 by Царев Николай Александрович

Задача

Ориентированный граф задан матрицей смежности.
Найдите количество ребер в графе.

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

Входной файл содержит число n (1 ≤ n ≤ 100) — число вершин в графе, и затем n строк по n чисел, каждое из которых равно 0 или 1 — его матрицу смежности.

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

Выведите в выходной файл количество ребер заданного графа.

Решение

Задача на E-Olimp.

30 1 11 0 1

0 1 1

50 1 1 1 11 0 0 0 0

1 0 0 0 0

0 0 1 0 1

1 0 0 0 0

21 11 1

#include <iostream>

using namespace std;

int main()
{
    int n;
    cin >> n;
    int k, l=0;
    for(int i=0;i<n;i++){
        for(int j=0; j<n; j++){
            cin >> k;
            if(k)
            l++;
        }
    }
    cout << l << endl;

    return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

int k, l=0;

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

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

cin >> k;

if(k)

l++;

}

cout << l << endl;

return 0;

}

Алгоритм решения прост. Количество ребер ориентированного графа равно количеству единиц в его матрице смежности. Поэтому просто считываем, суммируем если 1, и выводим ответ.

Задача на ideone

Related Images:

А714

19/05/2015 by Ковальський Олександр Дмитрович

Задача

Комплексная матрица [latex]Z[/latex] представляется парой [latex]X[/latex], [latex]Y[/latex] действительных матриц так, что [latex]Z=X+iY[/latex]. Даны действительные квадратные матрицы [latex]A[/latex], [latex]B[/latex], [latex]C[/latex] и [latex]D[/latex] порядка [latex]m[/latex]. Найти произведение двух комплексных матриц [latex]A+iB[/latex] и [latex]C+iD[/latex], т. е. найти действительные квадратные матрицы [latex]X[/latex] и [latex]Y[/latex] порядка [latex]m[/latex] такие, что [latex]X+iY=(A+iB)(C+iD)[/latex].

Пример

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

Вывод

9 5 4 8 5 2 6 1 3

1 4 6 5 3 1 9 8 7

4 2 8 3 9 5 1 2 7

5 6 7 4 1 9 3 8 2

16 13 70

9 24 39

-68 -91 -75

99 141 186

96 108 167

110 165 218

Решение

#include <iostream>
using namespace std;

int main()
	{
		int m;
		cin>>m;
		int A[m][m], B[m][m], C[m][m], D[m][m];
		int X[m][m], Y[m][m];
		int el;
		for(int i=0;i<m;i++)
			for(int j=0;j<m;j++)
				cin>>A[i][j];
		for(int i=0;i<m;i++)
			for(int j=0;j<m;j++)
				cin>>B[i][j];
		for(int i=0;i<m;i++)
			for(int j=0;j<m;j++)
				cin>>C[i][j];
		for(int i=0;i<m;i++)
			for(int j=0;j<m;j++)
				cin>>D[i][j];
		
		for(int i=0;i<m;i++)
			{
				for(int j=0;j<m;j++)
					{
						el=0;
						for(int l=0;l<m;l++)
							{
								el=el+A[i][l]*C[l][j]-B[i][l]*D[l][j];
							}
						X[i][j]=el;
					}
			}
		for(int i=0;i<m;i++)
			{
				for(int j=0;j<m;j++)
					{
						el=0;
						for(int l=0;l<m;l++)
							{
								el=el+A[i][l]*D[l][j]+B[i][l]*C[l][j];
							}
						Y[i][j]=el;
					}
			}
		cout<<"X:"<<endl;
		for(int i=0;i<m;i++)
			{
				for(int j=0;j<m;j++)
					{
						cout<<X[i][j]<<" ";
					}
				cout<<endl;
			}
		cout<<endl;
		cout<<"Y:"<<endl;
		for(int i=0;i<m;i++)
			{
				for(int j=0;j<m;j++)
					{
						cout<<Y[i][j]<<" ";
					}
				cout<<endl;
			}
		return 0;
	}

#include <iostream>

using namespace std;

int main()

{

int m;

cin>>m;

int A[m][m], B[m][m], C[m][m], D[m][m];

int X[m][m], Y[m][m];

int el;

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

for(int j=0;j<m;j++)

cin>>A[i][j];

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

for(int j=0;j<m;j++)

cin>>B[i][j];

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

for(int j=0;j<m;j++)

cin>>C[i][j];

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

for(int j=0;j<m;j++)

cin>>D[i][j];

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

{

for(int j=0;j<m;j++)

{

el=0;

for(int l=0;l<m;l++)

{

el=el+A[i][l]*C[l][j]-B[i][l]*D[l][j];

}

X[i][j]=el;

}

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

{

for(int j=0;j<m;j++)

{

el=0;

for(int l=0;l<m;l++)

{

el=el+A[i][l]*D[l][j]+B[i][l]*C[l][j];

}

Y[i][j]=el;

}

cout<<"X:"<<endl;

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

{

for(int j=0;j<m;j++)

{

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

}

cout<<endl;

}

cout<<endl;

cout<<"Y:"<<endl;

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

{

for(int j=0;j<m;j++)

{

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

}

cout<<endl;

}

return 0;

}

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
	public static void main (String[] args)
	{
		Scanner in = new Scanner(System.in);
        int m = in.nextInt(), el;
		int[][] A = new int[m][m], B = new int[m][m], C = new int[m][m], D = new int[m][m],X = new int[m][m], Y = new int[m][m];
		for(int i = 0; i < m; i++)
			for(int j = 0; j < m; j++)
				A[i][j] = in.nextInt();
		for(int i = 0; i < m; i++)
			for(int j = 0; j < m; j++)
				B[i][j] = in.nextInt();
		for(int i = 0; i < m; i++)
			for(int j = 0; j < m; j++)
				C[i][j] = in.nextInt();
		for(int i = 0; i < m; i++)
			for(int j = 0; j < m;j++)
				D[i][j] = in.nextInt();
		for(int i = 0; i < m; i++)
			{
				for(int j = 0; j < m; j++)
					{
						el = 0;
						for(int l = 0;l < m; l++)
							{
								el += A[i][l] * C[l][j] - B[i][l] * D[l][j];
							}
						X[i][j] = el;
					}
			}
		for(int i = 0; i < m; i++)
			{
				for(int j = 0; j < m; j++)
					{
						el = 0;
						for(int l = 0; l < m; l++)
							{
								el += A[i][l] * D[l][j] + B[i][l] * C[l][j];
							}
						Y[i][j] = el;
					}
			}
		System.out.println("X:");
		for(int i = 0; i < m; i++)
			{
				for(int j = 0; j < m; j++)
					{
						System.out.printf(X[i][j] + " ");
					}
				System.out.println();
			}
		System.out.println();
		System.out.println("Y:");
		for(int i = 0; i < m; i++)
			{
				for(int j = 0; j < m; j++)
					{
						System.out.printf(Y[i][j] + " ");
					}
				System.out.println();
			}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

int m = in.nextInt(), el;

int[][] A = new int[m][m], B = new int[m][m], C = new int[m][m], D = new int[m][m],X = new int[m][m], Y = new int[m][m];

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

for(int j = 0; j < m; j++)

A[i][j] = in.nextInt();

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

for(int j = 0; j < m; j++)

B[i][j] = in.nextInt();

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

for(int j = 0; j < m; j++)

C[i][j] = in.nextInt();

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

for(int j = 0; j < m;j++)

D[i][j] = in.nextInt();

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

{

for(int j = 0; j < m; j++)

{

el = 0;

for(int l = 0;l < m; l++)

{

el += A[i][l] * C[l][j] - B[i][l] * D[l][j];

}

X[i][j] = el;

}

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

{

for(int j = 0; j < m; j++)

{

el = 0;

for(int l = 0; l < m; l++)

{

el += A[i][l] * D[l][j] + B[i][l] * C[l][j];

}

Y[i][j] = el;

}

System.out.println("X:");

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

{

for(int j = 0; j < m; j++)

{

System.out.printf(X[i][j] + " ");

}

System.out.println();

}

System.out.println();

System.out.println("Y:");

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

{

for(int j = 0; j < m; j++)

{

System.out.printf(Y[i][j] + " ");

}

System.out.println();

}

[latex]X+iY=(A+iB)(C+iD)=(AC-BD)+i(AD+BC)[/latex], т. е. [latex]X=AC-BD[/latex], [latex]Y=AD+BC[/latex].

Код на ideone.

Related Images:

e-olimp 4000. Обход в глубину

30/04/2015 by Ковальський Олександр Дмитрович

Задача e-olimp 4000

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

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

В первой строке содержится два целых числа [latex]n[/latex] и [latex]s[/latex] [latex](1\leq s\leq n\leq 100)[/latex], где [latex]n[/latex] — количество вершин графа, а [latex]s[/latex] — выделенная вершина. В следующих [latex]n[/latex] строках записано по [latex]n[/latex] чисел — матрица смежности графа, в которой цифра «0» означает отсутствие ребра между вершинами, а цифра «1» — его наличие. Гарантируется, что на главной диагонали матрицы всегда стоят нули.

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

Выведите одно число — искомое количество вершин.

Пример:

Входные данные	Выходные данные
5 1	3
0 1 1 0 0
1 0 1 0 0
1 1 0 0 0
0 0 0 0 1
0 0 0 1 0

Решение

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

int main()
	{
		int n;
		int s;
		cin>>n>>s;
		s--;
		int matrix[n][n];
		stack<int> st;
		int counter=1;
		for(int i=0;i<n;i++)
			{
				for(int j=0;j<n;j++)
					{
						cin>>matrix[i][j];
					}
			}
		for(int j=0;j<n;j++)
			{
				if(matrix[s][j] == 1) st.push(j);
			}
		matrix[s][s]=1;
		while(!st.empty())
			{
				int a=st.top();
				st.pop();
				if(matrix[a][a]!=1)
					{
						for(int j=0;j<n;j++)
							{
								if(matrix[a][j] == 1) st.push(j);
							}
						counter++;
						matrix[a][a]=1;
					}
				
			}
		cout<<counter<<endl;
	}

#include <iostream>

#include <stack>

using namespace std;

int main()

{

int n;

int s;

cin>>n>>s;

s--;

int matrix[n][n];

stack<int> st;

int counter=1;

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

{

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

{

cin>>matrix[i][j];

}

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

{

if(matrix[s][j] == 1) st.push(j);

}

matrix[s][s]=1;

while(!st.empty())

{

int a=st.top();

st.pop();

if(matrix[a][a]!=1)

{

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

{

if(matrix[a][j] == 1) st.push(j);

}

counter++;

matrix[a][a]=1;

}

cout<<counter<<endl;

}

import java.util.*;
import java.lang.*;
import java.io.*;

class Ideone
{
	public static void main (String[] args)
	{
		Scanner in = new Scanner(System.in);
        int n = in.nextInt(), s = in.nextInt()-1, counter = 1;
		int[][] matrix = new int[n][n];
		Stack st = new Stack();
		for(int i = 0;i < n; i++)
			{
				for(int j = 0;j < n; j++)
					{
						matrix[i][j] = in.nextInt();
					}
			}
		for(int j = 0; j < n; j++)
			{
				if(matrix[s][j] == 1) st.push(j);
			}
		matrix[s][s] = 1;
		while(!st.empty())
			{
				int a = (int) st.peek();
				st.pop();
				if(matrix[a][a] != 1)
					{
						for(int j = 0; j < n; j++)
							{
								if(matrix[a][j] == 1) st.push(j);
							}
						counter++;
						matrix[a][a] = 1;
					}
				
			}
		System.out.println(counter);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

int n = in.nextInt(), s = in.nextInt()-1, counter = 1;

int[][] matrix = new int[n][n];

Stack st = new Stack();

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

{

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

{

matrix[i][j] = in.nextInt();

}

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

{

if(matrix[s][j] == 1) st.push(j);

}

matrix[s][s] = 1;

while(!st.empty())

{

int a = (int) st.peek();

st.pop();

if(matrix[a][a] != 1)

{

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

{

if(matrix[a][j] == 1) st.push(j);

}

counter++;

matrix[a][a] = 1;

}

System.out.println(counter);

}

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

Код на ideone.

Засчитанное решение.

Related Images:

А136о

30/01/2015 by Сабиров Ильдар

Даны натуральное число [latex]n,[/latex] действительные числа [latex]a_{1},\ldots,a_{n}[/latex].
Вычислить: [latex]\sqrt{10+a_{1}^{2}}+\ldots+\sqrt{10+a_{n}^{2}}[/latex]

n	[latex]a_{1}[/latex]	[latex]a_{2}[/latex]	[latex]a_{3}[/latex]	[latex]a_{4}[/latex]	[latex]a_{5}[/latex]	[latex]a_{6}[/latex]	sum	Комментарий
6	1	0.5	7	19	-9	8	51.6024	Пройден.
5	16	14.3	2	27	19	—	81.1426	Пройден.
2	61	-5	—	—	—	—	66.998	Пройден.
3	28.8	0.34	20.9	31.5	—	—	53.2915	Пройден.
1	-65.9242	—	—	—	—	—	66	Пройден.

#include <iostream>
#include <math.h>
using namespace std;

int main()
{
    int i;
    int n;
    double sum=0;
    cin>>n;
    double a;
    for(i=1;i<=n;++i)
    {
        cin>>a;
        sum+=sqrt(10+a*a);
    }
    cout<<sum;
    return 0;
}

#include <iostream>

#include <math.h>

using namespace std;

int main()

{

int i;

int n;

double sum=0;

cin>>n;

double a;

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

{

cin>>a;

sum+=sqrt(10+a*a);

}

cout<<sum;

return 0;

}

Вводим числа( n, [latex]a_{1},\ldots,a_{k}.[/latex])
Подсчитываем указанную сумму([latex]\sqrt{10+a_{1}^{2}}[/latex]+…+[latex]\sqrt{10+a_{n}^{2}}.[/latex])
Выводим сумму.

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

Related Images:

А410е

25/12/2014 by Носуленко Марк

Дана целочисленная матрица [latex][a_{ij}], ij=1,\ldots,n.[/latex] Получить [latex]b_{1},\ldots,b_{n}[/latex], где [latex]b_{i}[/latex] — это: [latex]\underset{1\leq j\leq n}{\max a_{ij}}\cdot \underset{1\leq j\leq n}{\min a_{ji}}[/latex].

Исходя из задачи ясно, что из данной матрицы надо взять максимальный элемент [latex]i[/latex]-й строки и умножить его на минимальный элемент [latex]i[/latex]-го столбца. Так например, если нам дана матрица 2-го порядка [latex]\begin{Vmatrix}1&2\\4&1\end{Vmatrix}[/latex] то [latex]b_{1}= 2[/latex], [latex]b_{2}= 4[/latex].

Для нахождения максимума [latex]a_{ij}[/latex], введем переменную и будем придавать ей начальное значение 1-го элемента [latex]i[/latex]-й строки. Дабы при расчете максимума проходя по элементам строки мы не сравнивали каждый [latex]i[/latex]-й элемент с 1-м, придавать начальное значение максимуму мы будем в цикле по [latex]i[/latex]. Аналогично с минимумом [latex]a_{ji}[/latex], одно единственное но, начальное значение минимума будет равно первому элементу [latex]i[/latex]-го столбца.

Тесты:

Матрица порядка [latex]n[/latex], где [latex]n[/latex]:	[latex]a[i][j][/latex]:	Результат:	Комментарий:
2	[latex]\begin{Vmatrix}1&2\\4&1\end{Vmatrix}[/latex]	2 4	Пройден.
3	[latex]\begin{Vmatrix}1&2&3\\4&1&-6\\1&-2&-1\end{Vmatrix}[/latex]	3 -8 -6	Пройден.

#include <iostream>
using namespace std;
int main() {
    int n,maxa,mina;
    cin >>n;
    int a[n][n];
    for(int i=0; i<n;++i){
        for(int j=0;j<n;++j){
            cin >>a[i][j];
        }
    }
    int b[n];
    for(int i=0;i<n;++i){
        maxa=a[i][0]; //Придаем максимуму значение первого элемента i-й строки.
        mina=a[0][i]; //Минимуму же придаем значение первого элемента i-го столбца.
        for(int j=0;j<n;++j){
            maxa=(maxa>a[i][j]?maxa:a[i][j]); //Вычисляем максимум i-й строки.
            mina=(mina<a[j][i]?mina:a[j][i]); //Минимум i-го столбца.
        }
        b[i]=maxa*mina; //Наш результат.
    }   for(int i=0;i<n;++i){
        cout <<b[i]<<" ";
    }
    return 0;
}