А 1041

29/06/2015

Задача. Найти такую расстановку восьми слонов на шахматной доске, при которой каждое поле будет находиться под ударом одного из них. Предполагается, что используется обычная шахматная доска размером 8х8, а слоны могут бить по обоим частичным диагоналям на пересечении которых они находятся. Если на той же диагонали находится ещё один слон, то он перекрывает линию боя. … Continue reading →

А404

29/06/2015

Задача: Даны натуральные числа [latex]{i}, {j}[/latex], действительная матрица размера [latex]{18}\times{24}[/latex] [latex](1\leq i\leq j\leq 24)[/latex]. Поменять местами в матрице [latex]{i}[/latex]-й и [latex]{j}[/latex]-й столбцы. Тест: Вводим матрицу (размером [latex]{18}[/latex] — строк, [latex]{24}[/latex] — столбцов) в [latex]{input}[/latex], в следующей строке вписываем номера столбцов которые хотим поменять. Пример: 0 1 2 3 4 5 6 7 8 9 10 … Continue reading →

e-olymp 1454. Лабиринт знаний

28/06/2015

Задача В Летней Компьютерной Школе (ЛКШ) построили аттракцион «Лабиринт знаний». Лабиринт представляет собой n комнат, занумерованных от 1 до n, между некоторыми из которых есть двери. Когда человек проходит через дверь, показатель его знаний изменяется на определенную величину, фиксированную для данной двери. Вход в лабиринт находится в комнате 1, выход — в комнате n. Каждый … Continue reading →

А136и

28/06/2015

Задача. Даны натуральное число n, действительные числа [latex]a_{1}, a_{2}, \dots, a_{n}[/latex] Вычислить [latex] \frac{a_{1}}{0!} + \frac{a_{2}}{1!} + \cdots + \frac{a_{n}}{(n-1)!} [/latex] Тест Число-n Действительные числа Результат 5 4 5 6 7 8 13,5 7 5 4 7 9 2 8 3 14,1542 3 6 9 3 16,5 Программа:

#include <iostream>
using namespace std;
 
int main() {
    int n; 
    double a;
    cin >> n;
    double s = 0.0;
    for (int  i = 0; i < n; i++){
        cin >> a;
        for(int j = 1; j<=i; j++){
            a/= j*1.0;
        }
        s+=a;
    }
    cout << s <<"\n";
    return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

double a;

cin >> n;

double s = 0.0;

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

cin >> a;

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

a/= j*1.0;

}

s+=a;

}

cout << s <<"\n";

return 0;

}

Вводим n, a (действительные числа); Вычисляем … Continue reading →

А1035

28/06/2015

Задача. Указать маршрут коня. Начинающегося на одном заданном поле шахматной доски и оканчивающемся на другом. Никакое поле не должно встречаться в маршруте дважды. Пример Входные данные Выходные данные a1 b1 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;

}

Читаем входные данные. Преобразуем их в координаты начального и … Continue reading →

Ю4.8

27/06/2015

Задача: В массиве C(m) заменить каждый третий элемент полусуммой двух предыдущих, а стоящий перед ним — полусуммой соседних с ним элементов. Тест: Количество элементов Элементы Результат 3 5 9 1 5 3 7 6 8 7 6 9 4 0 8 7 7,5 9 4,5 6,5 9 2 5 7 3 6 9 4 6 … Continue reading →

А787

27/06/2015

Задача Вернемся к сортам гороха с желтыми (аллель [latex]R[/latex]) и зелеными (аллель [latex]r[/latex]) семядолями ( смотри предыдущую задачу). Были подвергнуты скрещиванию два растения, одно из которых имело зеленые семядоли. В результате скрещивания получили [latex]m[/latex] растений [latex]F_{1}[/latex] (смотри задачу 785) с желтыми семядолями и [latex]n[/latex]- с зелеными [latex]m\geq 0,n\geq 0 [/latex]. Используя законы Менделя, указать наиболее … Continue reading →

e-olymp 4514. Сортировка вагонов — А

26/06/2015

Задача К тупику со стороны пути 1 (см. рисунок) подъехал поезд. Разрешается отцепить от поезда один или сразу несколько первых вагонов и завезти их в тупик (при желании, можно даже завезти в тупик сразу весь поезд). После этого часть из этих вагонов вывезти в сторону пути 2. После этого можно завезти в тупик еще несколько … Continue reading →

e-olymp 975

26/06/2015

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

А702а

24/06/2015

Дана квадратная матрица порядка [latex]n[/latex]. Получить вектор [latex]Ab[/latex], где [latex]b[/latex]-вектор, элементы которого вычисляются по формуле: [latex]{b}_{i}={\frac{1}{{i}^{2}+2}}[/latex], где [latex]i=1,2,\dots,n[/latex]. 2 1 2 3 4 0.666667 1.66667 Пройдено 2 5 6 7 8 2.66667 3.66667 Пройдено При рассмотрении ряда квадратов чисел [latex](1, 4 , 9, \dots)[/latex], заметно, что числа следующей степени увеличиваются на четные числа, при этом … Continue reading →

А703

19/06/2015

Задача Даны квадратная матрица [latex]A[/latex] порядка [latex]n[/latex], векторы [latex]x[/latex] и [latex]y[/latex] с [latex]n[/latex] элементами. Получить вектор [latex]A(x+y)[/latex]. Примеры: Размерность матрицы Матрица Вектор x Вектор y Результирующий вектор A(x+y) 2 2 3 3 2 3 4 5 6 46 44 3 2 1 4 5 2 6 3 4 8 2 2 2 4 4 4 … Continue reading →

AA26.

19/06/2015

Задача В строке заменить последний и предпоследний символ, соответственно, на первый и второй. Если длина строки меньше четырех, то вывести, что это сделать невозможно. Тесты Input Output aabbcc ccbbaa input data atput dani Kalamabanga aglamabanaK

#include <iostream>
#include <string>

using namespace std;

int main(){
    string str;
    getline(cin,str);
    int l=str.length();
    if(l<4)
        cout << "False!" << endl;
    else{
        string s1;
        s1=str[l-1];
        s1+=str[l-2];
        for(int i=2; i<l-2; i++)
            s1+=str[i];
        s1+=str[1];
        s1+=str[0];
        cout<< s1 << endl;
    }
    return 0;
    }

#include <iostream>

#include <string>

using namespace std;

int main(){

string str;

getline(cin,str);

int l=str.length();

if(l<4)

cout << "False!" << endl;

else{

string s1;

s1=str[l-1];

s1+=str[l-2];

for(int i=2; i<l-2; i++)

s1+=str[i];

s1+=str[1];

s1+=str[0];

cout<< s1 << endl;

}

return 0;

}

Алгоритм Поскольку в условии задачи, количество слов не оговорено — для ввода строки используем функцию getline. Затем проверяем ее … Continue reading →

А700в

19/06/2015

Задача. Дана квадратная матрица А порядка n. Получить матрицу AB; элементы матрицы B вычисляются по формуле: [latex]b_{ij}=\left\{\begin{matrix}\frac{1}{i+j-1}&,if\: i<j\\ 0&,if\: i=j\\-\frac{1}{i+j-1}&other\: case\end{matrix}\right.[/latex] [latex](i,j=1,\cdots, n)[/latex] Тесты: Размер матрицы Входные данные Результат Комментарий n=2 [latex]\begin{pmatrix}1&7\\3&2\end{pmatrix}[/latex] [latex]\begin{pmatrix}-3,5&0,5\\-1&1,5\end{pmatrix}[/latex] Пройден n=3 [latex]\begin{pmatrix}1&2&3\\7&6&5\\4&8&9\end{pmatrix}[/latex] [latex]\begin{pmatrix}-2&-0,25&0,83333\\-4,66667&2,25&3,83333\\-7&-0,25&3,333\end{pmatrix}[/latex] Пройден Код программы:

#include <iostream>
 
using namespace std;
 
int main() {
	int n;
	cin >> n;
	double A[n][n];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cin >> A[i][j];
		}
	}
 
	double B[n][n];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			B[i][j] = 0;
			if (i < j){B[i][j] = 10 * 0.1 / ((i+1) + (j+1) -1);}
			else {
				if (i == j){B[i][j] = 0;}
				else {B[i][j] = -10 * 0.1 / ((i+1) + (j+1) -1);}
			}	
		}
	}
 
	double C[n][n];
	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			C[i][j] = 0;
			for(int k = 0; k < n; k++){
				C[i][j] += A[i][k] * B[k][j];
			}
		}
	}

	for(int i = 0; i < n; i++){
		for(int j = 0; j < n; j++){
			cout << C[i][j] << " ";
		}
		cout << endl;
	}
 
	return 0;
}

#include <iostream>

using namespace std;

int main() {

int n;

cin >> n;

double A[n][n];

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

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

cin >> A[i][j];

}

double B[n][n];

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

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

B[i][j] = 0;

if (i < j){B[i][j] = 10 * 0.1 / ((i+1) + (j+1) -1);}

else {

if (i == j){B[i][j] = 0;}

else {B[i][j] = -10 * 0.1 / ((i+1) + (j+1) -1);}

}

double C[n][n];

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

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

C[i][j] = 0;

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

C[i][j] += A[i][k] * B[k][j];

}

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

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

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

}

cout << endl;

}

return 0;

}

После ввода матрицы A, мы должны найти элементы матрицы B. Из условия … Continue reading →

A841

18/06/2015

Задача. «Исправление ошибок». Пусть по некоторому каналу связи передается сообщение, имеющее вид последовательностей нулей и единиц (или, аналагично, точек и тире). Из-за помех, возможен ошибочный прием некоторых сигналов: нуль может быть воспринят как единица и наоборот. Можно передавать каждый сигнал трижды, заменяя, например, последовательность 1, 0, 1 последовательностью 1, 1, 1, 0, 0, 0, 1, … Continue reading →

e-olymp 1266. CD

18/06/2015

Вам предстоит длительное путешествие на автомобиле. К сожалению, у Вас в машине есть только магнитофон, а лучшая музыка записана на компакт дисках. У Вас есть чистая магнитофонная лента с длительностью звучания [latex]N[/latex] минут. Вам нужно выбрать песни для записи на магнитофонную ленту таким образом, чтобы не используемое на ней место было минимально. Предположения: количество треков на … Continue reading →

e-olymp 4. Две окружности

18/06/2015

Две окружности Ссылка на засчитанное решение. Определить количество точек пересечения двух окружностей. Входные данные 6 чисел x1, y1, r1, x2, y2, r2, где x1, y1, x2, y2 — координаты центров окружностей, а r1, r2 – их радиусы. Все числа — действительные, не превышают по модулю 1000000000, заданы не более чем с 3-мя знаками после запятой. … Continue reading →

e-olymp 1872. Снеговики

18/06/2015

Задача: Зима. 2012 год. На фоне грядущего Апокалипсиса и конца света незамеченной прошла новость об очередном прорыве в областях клонирования и снеговиков: клонирования снеговиков. Вы конечно знаете, но мы вам напомним, что снеговик состоит из нуля или более вертикально поставленных друг на друга шаров, а клонирование — это процесс создания идентичной копии (клона). В местечке … Continue reading →

А704

18/06/2015

Задача: Даны квадратные матрицы A, B и C порядка n. Получить матрицу (A+B)C. Решение: В первом цикле читаем матрицу A. Во втором цикле читаем матрицу B и сразу прибавляем ее к матрице A, получаем сумму матриц. В третьем цикле умножаем сумму матриц A и B на матрицу C и выводим результат. Код:

#include <iostream>
#include <cstdlib>
 
using namespace std;
int main(){
	int n;
	cin >> n;
	int a[n][n], b[n][n], c[n][n], d[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++ ){
			cin >> b[i][j];
			a[i][j] += b[i][j];
		}
	}
	for( int i=0 ; i<n ; i++ ){
		for( int j=0 ; j<n ; j++ ){
			cin >> c[i][j];
		}
	}
	for( int i=0 ; i<n ; i++ ){		
		for( int j=0 ; j<n ; j++,d[i][j]=0 ){			
			for( int k=0 ; k<n ; k++ ){			
				d[i][j] += a[i][k] * c[k][j];
			}
			cout << d[i][j] << (j+1 == n? '\n' : ' ' );
		}
	}
}

#include <iostream>

#include <cstdlib>

using namespace std;

int main(){

int n;

cin >> n;

int a[n][n], b[n][n], c[n][n], d[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++ ){

cin >> b[i][j];

a[i][j] += b[i][j];

}

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

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

cin >> c[i][j];

}

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

for( int j=0 ; j<n ; j++,d[i][j]=0 ){

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

d[i][j] += a[i][k] * c[k][j];

}

cout << d[i][j] << (j+1 == n? '\n' : ' ' );

}

Тесты: n A B C Output 3 1 2 3 4 5 6 7 … Continue reading →

e-olymp 974. Флойд-1

17/06/2015

974. Флойд-1 Ссылка на засчитанное решение. Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса. Входные данные В первой строке записано количество вершин графа n (1 ≤ n ≤ 100). В следующих n строках записано по n чисел — матрица смежности графа … Continue reading →

e-olymp 625. Расстояние между вершинами

17/06/2015

Задача с сайта e-olimp № 625. Ссылка на засчитанное решение. РАССТОЯНИЕ МЕЖДУ ВЕРШИНАМИ Дан неориентированный взвешенный граф. Найти вес минимального пути между двумя вершинами. Входные данные Первая строка входного файла содержит натуральные числа N, M, S и F (N ≤ 5000, M ≤ 100000, 1 ≤ S, F ≤ N, S ≠ F) — количество … Continue reading →