A1029

17/06/2015

Условие Получить все расстановки [latex]8[/latex] ладей на шахматной доске, при которых ни одна ладья не угрожает другой. Решение Для начала, выясним, а сколько существует таких расстановок, при условии, что рассматривается стандартная шахматная доска [latex]8 \times 8[/latex]. Ладья находится под боем, если другая ладья находится с ней на одной строке или в одном … Continue reading →

А1033

17/06/2015

Условие Получить все размещения из [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) и … Continue reading →

e-olymp 4850. Шайтан-машинка

17/06/2015

Условие У Ибрагима есть магическая чёрная шайтан-машинка. На ней есть три кнопки и табло. Табло может показывать не более чем четырёхзначные числа. Каждая из кнопок меняет число некоторым образом: первая домножает его на [latex]3[/latex], вторая прибавляет к нему сумму его цифр, а третья вычитает из него [latex]2[/latex]. В случае, если число становится отрицательным или превосходит … Continue reading →

А719б

17/06/2015

Условие Симметричные квадратные матрицы [latex]A[/latex] и [latex]B[/latex] порядка [latex]n[/latex] заданы последовательностями из [latex]\frac{n(n+1)}{2}[/latex] чисел аналогично правым треугольным матрицам. Получить в аналогичном виде матрицу [latex]A^{2}-B^{2}[/latex]. Решение Безусловно, по входным данным можно восстановить матрицы, тривиальным образом их перемножить и вывести результат в заданном виде. Как пример плохого стиля программирования: наивный алгоритм приводит к почти двукратному перерасходу потребляемой … Continue reading →

А712

16/06/2015

Задача Дана квадратная матрица [latex]A[/latex] порядка [latex]n[/latex]. Получить матрицы [latex]\frac{1}{2}(A+A^{*}) (1)[/latex] и [latex]\frac{1}{2}(A-A^{*}) (2)[/latex]. Тесты: Ввод Вывод (1) Вывод (2) 3 1 2 3 2 4 6 1 4 8 1 2 2 2 4 5 2 5 8 0 0 1 0 0 1 -1 -1 0 Код:

    #include <iostream>
    using namespace std;
     
    int main() 
    {
	    int n;
	    cin >> n;
	    double a[n][n], result1[n][n], result2[n][n];
	    for (int i = 0; i < n; i++)
	    {
			for (int j = 0; j < n; j++)
			{
				cin >> a[i][j];
			}
	    }
	    for (int i = 0; i < n; i ++)
	    {
	    	for (int j = 0; j < n; j ++)
	    	{
	    		result1[i][j] = 0.5 * ( a[i][j] + a[j][i] );
	    		result2[i][j] = 0.5 * ( a[i][j] - a[j][i] );
	    	}
	    }
	     for (int i = 0; i < n; i++)
	     {
		     for (int j = 0; j < n; j++)
		     {
			     cout << result1[i][j] << ' ';
		     }
		     cout << endl;
	     }
	     cout << endl;
	     for (int i = 0; i < n; i ++)
	     {
		     for (int j = 0; j < n; j ++)
		     {
			     cout << result2[i][j] << ' ';
		     }
		     cout << endl;
	     }
		return 0;
}

#include <iostream>

using namespace std;

int main()

{

int n;

cin >> n;

double a[n][n], result1[n][n], result2[n][n];

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

{

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

{

cin >> a[i][j];

}

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

{

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

{

result1[i][j] = 0.5 * ( a[i][j] + a[j][i] );

result2[i][j] = 0.5 * ( a[i][j] - a[j][i] );

}

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

{

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

{

cout << result1[i][j] << ' ';

}

cout << endl;

}

cout << endl;

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

{

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

{

cout << result2[i][j] << ' ';

}

cout << endl;

}

return 0;

}

Ссылка на ideone. Сначала, вводим размер матрицы и саму … Continue reading →

e-olymp 5073. Проверка на наличие параллельных ребер (ОГ)

16/06/2015

Ориентированный граф задан списком ребер. Проверьте, содержит ли он параллельные ребра. Входные данные Входной файл содержит числа [latex]n(1\leq n\leq 100)[/latex] — число вершин в графе и [latex]m(1\leq m\leq 10000)[/latex] — число ребер. Затем следует [latex]m[/latex] пар чисел — ребра графа. Выходные данные Выведите в выходной файл YES если граф содержит параллельные ребра и NO в противном случае. Задача на … Continue reading →

A713

16/06/2015

Задача Следом квадратной матрицы называется сумма элементов, расположенных на главной диагонали. Даны квадратная матрица порядка m, натуральное число n. Вычислить следы матриц [latex]A, A^{2}, … , A^{n}[/latex]. Тесты [latex]m[/latex] [latex]n[/latex] [latex]A[/latex] следы [latex]A, A^{2}, … , A^{n}[/latex] Комментарий 3 4 [latex]\begin{pmatrix} 1 & 2 & 3\\ 1 & 2& 3 \\ 1 & 2 & 3 \end{pmatrix}[/latex] 6 36 216 1296 Пройден 2 5 [latex]\begin{pmatrix} 1 & 2\\ 3 & 4 \end{pmatrix}[/latex] 5 29 … Continue reading →

А701б

13/06/2015

Условие Даны квадратная матрица [latex]A[/latex] порядка [latex]n[/latex] и вектор [latex]b[/latex] c [latex]n[/latex] элементами. Получить вектор [latex]{ A }^{ 2 }b[/latex] Тесты n A b Результат 3 1 1 11 1 1 1 1 1 5 5 5 45 45 45 5 1 0 0 0 00 2 0 0 0 0 0 3 0 0 0 0 0 4 0 0 0 0 0 5 8 1 8 … Continue reading →

e-olymp 2479. Баланс скобок

13/06/2015

Условие (Ссылка на задачу в e-olymp) Имеется строка, содержащая скобки () и []. Скобочное выражение считается правильным, если: оно является пустым если A и B правильны, то AB правильно если A правильно, то (A) и [A] правильны Напишите программу, которая по входной строке, содержащей скобочное выражение, определит корректно ли оно. Длина строки не больше 128 … Continue reading →

A1048

11/06/2015

Задача. Одним из наиболее часто встречающихся видов списка является стек-список, в котором все включения и исключения элементов делаются только на одном его конце — вершине стека. Механизм функционирования стека хорошо отражен в другом его названии — список типа «LIFO» (last in first out) -«последним вошел — первым вышел»). При работе со стеком предполагаются две операции: … Continue reading →

A1031

06/06/2015

Задача. Получить все перестановки элементов 1, …, 6. Решение Все перестановки считаются и выводятся с помощью рекурсивной функции perestanovka(). Когда в ней складывается новый набор элементов, проверяем что бы в нем не было повторяющихся значений (считаем факториал и сумму, они должны совпадать со стандартом (6! = 720, 1+2+3+4+5+6 = 21) и тогда выводим. Что бы … Continue reading →

А1042

01/06/2015

Условие: В данной последовательности действительных чисел [latex]a_{1},…,a_{20}[/latex] выбрать возрастающую подпоследовательность наибольшей длинны. Тесты: Число элементов в заданной последовательности Заданная последовательность Найденная подпоследовательность 20 1 44 3 66 2 6 55 2 4 9 50 3 4 12 45 8 15 5 18 48 3 6 9 12 15 18 20 1 9 17 25 90 … Continue reading →

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

28/05/2015

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

А709

24/05/2015

Условие: Дана квадратная матрица [latex]A[/latex], порядка [latex]m[/latex], натуральное число [latex]n[/latex], действительные числа [latex]p_{n},p_{n-1},\ldots,p_{0}[/latex]. Получить матрицу [latex]p_{n}A^{n}+p_{n-1}A^{n-1}+\ldots p_{1}A+p_{0}E[/latex], где [latex]E[/latex]- единичная матрица порядка [latex]m[/latex]. Тесты: Ввод количества p Ввод размерности матрицы А и одновременно Е 6 3 Ввод коэффициентов 5 4 3 2 1 0 Матрица А: 1 2 3 3 2 1 2 1 … Continue reading →

А717б

24/05/2015

Условие Две правые треугольные матрицы [latex] A [/latex] и [latex] B [/latex] порядка [latex] n [/latex] заданы в виде последовательности [latex] \frac{\left( n + 1 \right) n}{2}[/latex] чисел: сначала идёт [latex] n [/latex] элементов первой строки, затем [latex] n-1 [/latex] элемент второй строки, и т.д. (из последней, [latex] n [/latex] -ой строки берётся только [latex] … Continue reading →

А1043

21/05/2015

Задача Построить все правильные скобочные выражения длины 10, то есть, которые содержат по 5 левых и по 5 правых скобок. Код на языке С++:

#include <iostream>
#include <string>
using namespace std;
 
void f(int x, string s){
	if(s.size() == 10){cout << s << endl; return;}
	if(x>0){f(x-1,s+")");}
	if(10-s.size() > x){f(x+1,s+"(");}
}
 
int main() {
	f(0,"");
	return 0;
}

#include <iostream>

#include <string>

using namespace std;

void f(int x, string s){

if(s.size() == 10){cout << s << endl; return;}

if(x>0){f(x-1,s+")");}

if(10-s.size() > x){f(x+1,s+"(");}

}

int main() {

f(0,"");

return 0;

}

Посмотреть программу можно здесь Код на языке Java:

import java.util.*;
import java.lang.*;
import java.io.*;
class Ideone {
	public static void f (int x, String s) {
		if(s.length() == 10) {
			System.out.println(s) ;
			return;
		}
		if(x>0) f(x-1,s+")");
		if(10-s.length() > x) f(x+1,s+"(");
	}
	public static void main (String[] args) {
		f(0, "");
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static void f (int x, String s) {

if(s.length() == 10) {

System.out.println(s) ;

return;

}

if(x>0) f(x-1,s+")");

if(10-s.length() > x) f(x+1,s+"(");

}

public static void main (String[] args) {

f(0, "");

}

Ссылка на программу: http://ideone.com/9MjHSA Решение: В переменной [latex]x[/latex] мы будем хранить количество открытых ([latex]»(«[/latex]) скобок. Далее проверяем условие, что если [latex]x>0[/latex], то … Continue reading →

А700а

21/05/2015

Задача: Дана квадратная матрица [latex]A[/latex] порядка [latex]n[/latex]. Получить матрицу [latex]AB[/latex]; элементы матрицы [latex]B[/latex] вычисляются по формуле : [latex]b_{ij} = \frac{1}{i+j-1}[/latex], при [latex]i,j=1,2,\dotsb n[/latex]. Тесты: [latex]n[/latex] [latex]A[/latex] [latex]AB[/latex] Комментарий 2 [latex] \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix} [/latex] [latex] \begin{pmatrix} 1 & 0.5 \\ 0.5 & 0.33 \end{pmatrix} [/latex] Пройден 3 [latex]\begin{pmatrix}2 & 16 & -3 \\ 4 … Continue reading →

A711a

20/05/2015

Задача: Дана матрица [latex]A [/latex] размера [latex]m\times m [/latex]. Получить матрицу [latex]AA^{*} [/latex] (ее размер [latex]m\times m [/latex]). Входные данные: 4 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 Выходные данные: 30 70 20 50 70 174 68 122 20 68 86 44 50 122 44 86 … Continue reading →

e-olymp 432. Подземелье

20/05/2015

Подземелье Вы попали в 3D подземный лабиринт и необходимо найти быстрый выход! Карта подземелья составлена из единичных кубических комнат, по которым можно или нельзя передвигаться. Нужно всего одну минуту, чтобы переместиться она одну единицу на север, юг, восток, запад, вверх или вниз. Вы не можете двигаться по диагонали, и лабиринт окружен твердой скальной породой … Continue reading →

А717а

20/05/2015

Задача Две правые треугольные матрицы [latex]A[/latex] и [latex]B[/latex] порядка [latex]n[/latex] заданы в виде последовательности [latex]\frac{\left(n+1\right)*n}{2}[/latex] чисел: сначала идет [latex]n[/latex] элементов первой строки, затем [latex]n-1[/latex] элемент второй строки, начиная со второго элемента, и т. д. (из последней, [latex]n[/latex]-й строки берется только [latex]n[/latex]-й элемент). Получить матрицу [latex]A*B[/latex]. Тесты n матрица A матрица B результат (матрица A*B) комментарий 2 1 2 3 4 5 … Continue reading →