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

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

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

Пример

Входные данные	Выходные данные
2 2 1 2 5 1 2 -5	5
5 5 1 2 5 2 4 5 4 5 5 3 3 5 2 3 5	15
3 3 1 2 5 1 2 -5 2 2 6	🙁
3 3 1 2 2 2 3 3 3 1 4	🙂

Решение

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

struct edge
	{
		int start,finish,cost;
	};
	
int main()
	{
		int n,m;
		cin>>n>>m;
		vector<edge>e;
		for (int i=0;i<m;i++)
			{
				edge a;
				cin>>a.start>>a.finish>>a.cost;
				a.start--;
				a.finish--;
				e.push_back(a);
			}
		vector<int> length (n, INT_MIN);
		vector<int> p (n, -1);
		length[0] = 0;
		int x;
		for (int i=0;i<n;i++)
			{
				x = -1;
				for (int j=0;j<m;j++)
					if ((length[e[j].start]>INT_MIN)&&(length[e[j].finish]<length[e[j].start] + e[j].cost))
							{
								length[e[j].finish]=length[e[j].start] + e[j].cost;
								p[e[j].finish]=e[j].start;
								x=1;
							}
			}
		vector<int> path;
		int k=0;
		for (int i=n-1;i!=-1;i=p[i])
			{
				k++;
				path.push_back (i);
				if(k>n) break;
			}
		if(length[n-1]==INT_MIN) cout<<":("<<endl;
		else 
			 if((x!=-1)&&((path.back()!=0)||(path.front()!=n-1)||(k>n))) cout<<":)"<<endl;
			 else cout<<length[n-1]<<endl;
		return 0;
	}

#include <iostream>

#include <vector>

#include <climits>

using namespace std;

struct edge

{

int start,finish,cost;

};

int main()

{

int n,m;

cin>>n>>m;

vector<edge>e;

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

{

edge a;

cin>>a.start>>a.finish>>a.cost;

a.start--;

a.finish--;

e.push_back(a);

}

vector<int> length (n, INT_MIN);

vector<int> p (n, -1);

length[0] = 0;

int x;

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

{

x = -1;

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

if ((length[e[j].start]>INT_MIN)&&(length[e[j].finish]<length[e[j].start] + e[j].cost))

{

length[e[j].finish]=length[e[j].start] + e[j].cost;

p[e[j].finish]=e[j].start;

x=1;

}

vector<int> path;

int k=0;

for (int i=n-1;i!=-1;i=p[i])

{

k++;

path.push_back (i);

if(k>n) break;

}

if(length[n-1]==INT_MIN) cout<<":("<<endl;

else

if((x!=-1)&&((path.back()!=0)||(path.front()!=n-1)||(k>n))) cout<<":)"<<endl;

else cout<<length[n-1]<<endl;

return 0;

}

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

Код на ideone.

Создадим вектор расстояний length на n элементов. Все элементы кроме 0-го приравниваем к минимальному числу. Нулевой элемент приравниваем к 0. Также создадим вектор p в котором будем хранить номер вершины из которой мы попали в текущую. Затем в цикле проходим по всем вершинам и в вектор length записываем расстояние за которое мы дошли в эту вершину. n-1 элемент вектора и будет ответом задачи. Затем мы восстанавливаем путь из нулевой вершины в последнюю, но будем это делать не более n раз. Затем проверяем, если в последней вершине значение не изменилось то выводим :(. Затем проверяем был ли в пути цикл, если да то выводи :), в противном случае выводим значение length[n-1].

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:

А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:

AA8

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

Задача

Заданы две одинаковые по длине строки. Построить новую строку, в которой на четных местах расположены элементы первой строки, а на нечетных – элементы второй строки.

Тесты

Ввод

Вывод

abc

012

a0b1c2

0123

00112233

#include <iostream>
using namespace std;

int main() 
	{
		string s1;
		cin>>s1;
		string s2;
		cin>>s2;
		string s;
		for(int i=0;i<s1.length();i++)
			{
				s=s+s1[i]+s2[i];
			}
		cout<<s<<endl;
		return 0;
	}

#include <iostream>

using namespace std;

int main()

{

string s1;

cin>>s1;

string s2;

cin>>s2;

string s;

for(int i=0;i<s1.length();i++)

{

s=s+s1[i]+s2[i];

}

cout<<s<<endl;

return 0;

}

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:

Ю4.21

20/12/2014 by Ковальський Олександр Дмитрович

Задача.

Целочисленный массив K(n, n) заполнить нулями и единицами, расположив их в шахматном порядке.

Тесты.

Ввод

Вывод

1 0 1 
0 1 0 
1 0 1

1 0 1

0 1 0

1 0 1

1 0 1 0 1 0 
0 1 0 1 0 1 
1 0 1 0 1 0 
0 1 0 1 0 1 
1 0 1 0 1 0 
0 1 0 1 0 1

1 0 1 0 1 0

0 1 0 1 0 1

1 0 1 0 1 0

0 1 0 1 0 1

1 0 1 0 1 0

0 1 0 1 0 1

#include <iostream>
using namespace std;

int main() 
	{
		int n;
		scanf("%d",&n);
		int k[n][n];
		for(int i=0;i<n;i++)
			{
				for(int j=0;j<n;j++)
					{
						if((i+j)%2==0)printf("1 ");
						else printf("0 ");
					}
				printf("\n");
			}
		return 0;
	}

#include <iostream>

using namespace std;

int main()

{

int n;

scanf("%d",&n);

int k[n][n];

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

{

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

{

if((i+j)%2==0)printf("1 ");

else printf("0 ");

}

printf("\n");

}

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 n = in.nextInt();
		int[][] k = new int[n][n];
		for(int i = 0; i < n; i++)
			{
				for(int j = 0; j < n; j++)
					{
						if((i + j) % 2 == 0) System.out.printf("1 ");
						else System.out.printf("0 ");
					}
				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 n = in.nextInt();

int[][] k = new int[n][n];

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

{

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

{

if((i + j) % 2 == 0) System.out.printf("1 ");

else System.out.printf("0 ");

}

System.out.println();

}

Решение.

В цикле проверяем если сумма номеров элемента в массиве чётна, то печатаем единицу, в противном случае печатаем ноль.

Related Images:

А155

20/12/2014 by Ковальський Олександр Дмитрович

Задача.

Даны натуральное число $n$, действительные числа $x_1, \ldots, x_n, $ где [latex](n\geq 2).[/latex] Вычислить:

[latex]\left( \left( \frac{1}{|x_{1}|+1}+x_{2} \right)\left(\frac{1}{|x_{2}|+1}+x_{3} \right)\cdots\left(\frac{1}{|x_{n-1}|+1}+x_{n} \right)\right)[/latex]

Тесты.

Ввод		Вывод
$n$	$x_1, \ldots, x_n$	$k$
2	1 1	1.5
3	0.5 1 2	4.16667
3	-0.3 1 -0.5	0

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

int main() 
    {
        int n;
        double k=1;
        cin>>n;
        double x[n];
        for(int i=0;i<n;i++)
            {
                cin>>x[i];
            }
        for(int i=1;i<n;i++)
            {
                k*=((1/(fabs(x[i-1])+1))+x[i]);
            }
        cout<<k;
        return 0;
    }

#include <iostream>

#include <math.h>

using namespace std;

int main()

{

int n;

double k=1;

cin>>n;

double x[n];

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

{

cin>>x[i];

}

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

{

k*=((1/(fabs(x[i-1])+1))+x[i]);

}

cout<<k;

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 n = in.nextInt();
        double k = 1;
        double[] x = new double[n];
        for(int i = 0; i < n; i++)
            {
                x[i] = in.nextDouble();
            }
        for(int i = 1; i < n; i++)
            {
                k *= 1 / (Math.abs(x[i - 1]) + 1) + x[i];
            }
        System.out.println(k);
    }
}

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();

double k = 1;

double[] x = new double[n];

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

{

x[i] = in.nextDouble();

}

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

{

k *= 1 / (Math.abs(x[i - 1]) + 1) + x[i];

}

System.out.println(k);

}

Решение.
Задаем переменные $n, k$и массив действительных чисел с количеством элементов $n$. В первом цикле вводим числа в массив. Во втором умножаем переменную $k$ каждый раз на [latex]\left(\left(\frac{1}{|x_{n-1}|+1}+x_{n} \right)\right)[/latex]. После выводим значение $k$.

Related Images:

А812ж

20/12/2014 by Ковальський Олександр Дмитрович

Задача.

Дан текст, каждый символ которого может быть малой буквой, цифрой или одним из знаков +, -, *. Группой букв будем называть такую совокупность последовательно расположенных букв, которой непосредственно не предшествует и за которой непосредственно не следует буква. Аналогично определим группу цифр и группу знаков.

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

Тесты.

Ввод	Вывод
1aa2bb+-c2cc—**22	22
11aa2bb+-c2cc—**22	11
1aa2bb+-c23cc—**22	23
111aa2bb+-c2cc—**22	111
1aa2bb+-c234cc—**22	234
1aa221bb+-c234cc—**22	221

Код программы (string):

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

int main() 
	{
		string s;
		cin>>s;
		int k=0,n=0,a;
		for(int i=0;i<s.length()+1;i++)
			{
				if(n<k) n=k;
				if(isdigit(s[i])) k=k+1;
				else k=0;
			}
		for(int i=s.length();i>=-1;i--)
			{
				if(k==n) a=i+1;
				if(isdigit(s[i])) k=k+1;
				else k=0;
			}
		for(int i=a;i<a+n;i++)
			{
				cout<<s[i];
			}
		return 0;
	}

#include <iostream>

#include <string>

using namespace std;

int main()

{

string s;

cin>>s;

int k=0,n=0,a;

for(int i=0;i<s.length()+1;i++)

{

if(n<k) n=k;

if(isdigit(s[i])) k=k+1;

else k=0;

}

for(int i=s.length();i>=-1;i--)

{

if(k==n) a=i+1;

if(isdigit(s[i])) k=k+1;

else k=0;

}

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

{

cout<<s[i];

}

return 0;

}

Код программы (cstring):

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

int main() 
	{
		char *s;
		s=new char[100];
		cin>>s;
		int k=0,n=0,a;
		for(int i=0;i<strlen(s)+1;i++)
			{
				if(n<k) n=k;
				if(isdigit(s[i])) k=k+1;
				else k=0;
			}
		for(int i=strlen(s);i>=-1;i--)
			{
				if(k==n) a=i+1;
				if(isdigit(s[i])) k=k+1;
				else k=0;
			}
		for(int i=a;i<a+n;i++)
			{
				cout<<s[i];
			}
		return 0;
	}

#include <iostream>

#include <cstring>

using namespace std;

int main()

{

char *s;

s=new char[100];

cin>>s;

int k=0,n=0,a;

for(int i=0;i<strlen(s)+1;i++)

{

if(n<k) n=k;

if(isdigit(s[i])) k=k+1;

else k=0;

}

for(int i=strlen(s);i>=-1;i--)

{

if(k==n) a=i+1;

if(isdigit(s[i])) k=k+1;

else k=0;

}

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

{

cout<<s[i];

}

return 0;

}

Решение.

Вводим строку в переменную s. В первом цикле ищем наибольшую группу записывая значение в переменную n. В следующем цикле ищем номер первого символа в группе записывая значение в переменную a. В третьем цикле выводим символы с номерами с a-го по a+n.

Related Images:

Ю3.11

24/11/2014 by Ковальський Олександр Дмитрович

Задача.

Получить таблицу пересчета миль в километры и обратно (1 миля=1,609344 км) для расстояний,не превышающих k км, в следующем виде:

мили	км
0,6214	1,0000
1,0000	1,6093
1,2428	2,0000
1,8641	3,0000
2,0000	3,2187

Тесты.

Ввод	Вывод
k	Вывод
3	mile km 0.6214 1.0000 1.0000 1.6093 1.2427 2.0000 1.8641 3.0000
7	mile km 0.6214 1.0000 1.0000 1.6093 1.2427 2.0000 1.8641 3.0000 2.0000 3.2187 2.4855 4.0000 3.0000 4.8280 3.1069 5.0000 3.7282 6.0000 4.0000 6.4374 4.3496 7.0000
0	mile km
3.3	mile km 0.6214 1.0000 1.0000 1.6093 1.2427 2.0000 1.8641 3.0000 2.0000 3.2187

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

int main() 
	{
		double n=1,k;
		scanf("%lf ",&k);
		printf("mile     km\n");
		for(double i=1;i<=ceil(k);i++)
			{
				if(i/1.609344<n)printf("%.4f   %.4f\n",i/1.609344,i);
				else
					{
						if(n*1.609344<=k)printf("%.4f   %.4f\n",n,n*1.609344);
						if(i<=k)printf("%.4f   %.4f\n",i/1.609344,i);
						n++;
					}
			}
		return 0;
	}

#include <iostream>

#include <math.h>

using namespace std;

int main()

{

double n=1,k;

scanf("%lf ",&k);

printf("mile km\n");

for(double i=1;i<=ceil(k);i++)

{

if(i/1.609344<n)printf("%.4f %.4f\n",i/1.609344,i);

else

{

if(n*1.609344<=k)printf("%.4f %.4f\n",n,n*1.609344);

if(i<=k)printf("%.4f %.4f\n",i/1.609344,i);

n++;

}

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);
        double n = 1,k = in.nextDouble();
		System.out.println("mile     km");
		for(double i = 1;i <= Math.ceil(k);i++)
			{
				if(i / 1.609344 < n) System.out.format("%.4f   %.4f\n", i / 1.609344, i);
				else
					{
						if(n * 1.609344 <= k) System.out.format("%.4f   %.4f\n", n, n * 1.609344);
						if(i <= k) System.out.format("%.4f   %.4f\n", i / 1.609344, i);
						n++;
					}
			}
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

double n = 1,k = in.nextDouble();

System.out.println("mile km");

for(double i = 1;i <= Math.ceil(k);i++)

{

if(i / 1.609344 < n) System.out.format("%.4f %.4f\n", i / 1.609344, i);

else

{

if(n * 1.609344 <= k) System.out.format("%.4f %.4f\n", n, n * 1.609344);

if(i <= k) System.out.format("%.4f %.4f\n", i / 1.609344, i);

n++;

}

Решение.

Читаем значение k. В цикле имеем два значения n и i, значение i увеличиваем в каждом витке цикла, а значение n тогда, когда значение [latex]i/1.609344[/latex] превысит значение n. Пока этого не произошло печатаем значения соответствующие i км и [latex]i/1.609344[/latex] милям. Когда-же значение [latex]i/1.609344[/latex] превысило значение n проверяем, если значение [latex]n\times 1.609344[/latex] меньше или равно k печатаем строку, где значения миль равно n, а значение км [latex]n\times 1.609344[/latex], потом проверяем если значение i меньше или равно значению k, то печатаем строку, где значение миль равно[latex]i/1.609344[/latex], а значение км равно i. То есть для подсчёта целых значений миль используем параметр n, а для подсчёта целых значений км параметр i.

Related Images:

А60д

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

Задача.

Пусть D — заштрихованная часть плоскости и пусть u определяется по x и y следующим образом :

[latex]u=\begin{cases} \sqrt{|x^{2}-1|} & \text{ if } (x, y)\epsilon D \\ x+y & \end{cases}[/latex]

Даны действительные числа x и y. Определить u.

Тесты.

Ввод		Вывод
x	y	u
0	0	1
0	0.5	1
-0.3	0.6	0.953939
0.3	0.6	0.953939
-0.2	-0.1	-0.3
0.8	0.6	1.4
0.5	-0.5	0

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

int main() 
	{
		double x,y;
		cin>>x>>y;
		cout<< (((x*x+y*y<=1)&&(y>=fabs(x))) ? sqrt(abs(x*x-1)):x+y) <<endl;
		return 0;
	}

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

double x,y;

cin>>x>>y;

cout<< (((x*x+y*y<=1)&&(y>=fabs(x))) ? sqrt(abs(x*x-1)):x+y) <<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);
        double x = in.nextDouble(),y = in.nextDouble();
		System.out.println(((x * x + y * y <= 1) && (y >= Math.abs(x))) ? Math.sqrt(Math.abs(x * x - 1)) : x + y);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

Scanner in = new Scanner(System.in);

double x = in.nextDouble(),y = in.nextDouble();

System.out.println(((x * x + y * y <= 1) && (y >= Math.abs(x))) ? Math.sqrt(Math.abs(x * x - 1)) : x + y);

}

Решение.

Через переменные x, y обозначим координаты точки.

Мы имеем 3 графика функций:

[latex]y=-x[/latex]
[latex]y=x[/latex]
[latex]x^{2}+y^{2}=1[/latex]

Проверяем находится ли точка в заштрихованной области. Точка обязательно должна находиться над или на оси x.

Если точка принадлежит данной области то для расчёта u используем формулу:

[latex]\sqrt{|x^{2}-1|}[/latex]

В противном случае формулу:

[latex]u=x+y[/latex]

Related Images:

Ю1.1

18/09/2014 by Ковальський Олександр Дмитрович

Задача.

Из градусов в радианы. Угол α задан в градусах, минутах и секундах. Найти его величину в радианах(с максимально возможной точностью).

Тесты.

Ввод			Вывод
градусы(grad)	минуты(min)	Секунды(sec)	радианы(rad)
0	0	0	0
90	0	0	1.570796326794897
179	59	60	3.141592653589793
-270	0	0	-4.7123889803847

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

using namespace std;

int main() 
	{
	    int grad;	
        int min;	
        int sec;	
		scanf("%d %d %d",&grad,&min,&sec);	//вводим число градусов, минут, секунд
        long double rad;
        int k=round(grad/360);	//Проверяем число градусов больше 360 или нет
        if (k>=1 && grad>0) grad=grad-360*k;	
        if(grad>=0) rad=grad*M_PI/180+min*M_PI/60/180+sec*M_PI/180/3600;	
        else rad=grad*M_PI/180-min*M_PI/60/180-sec*M_PI/180/3600;
		printf("%.*Lf",LDBL_DIG,rad);
	    return 0;
	}

#include <iostream>

#include <math.h>

#include <float.h>

using namespace std;

int main()

{

int grad;

int min;

int sec;

scanf("%d %d %d",&grad,&min,&sec); //вводим число градусов, минут, секунд

long double rad;

int k=round(grad/360); //Проверяем число градусов больше 360 или нет

if (k>=1 && grad>0) grad=grad-360*k;

if(grad>=0) rad=grad*M_PI/180+min*M_PI/60/180+sec*M_PI/180/3600;

else rad=grad*M_PI/180-min*M_PI/60/180-sec*M_PI/180/3600;

printf("%.*Lf",LDBL_DIG,rad);

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);
	    double grad = in.nextInt(), min = in.nextInt(), sec = in.nextInt();	
        double rad;
        double k = Math.floor(grad / 360);
        if (k >= 1 && grad > 0) grad = grad - 360 * k;	
        if(grad >= 0) rad = (grad * Math.PI + min * Math.PI / 60 + sec * Math.PI / 3600) / 180;	
        else rad = (grad * Math.PI - min * Math.PI / 60 - sec * Math.PI / 3600) / 180;
		System.out.println(rad);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone

{

public static void main (String[] args)

{

Scanner in=new Scanner(System.in);

double grad = in.nextInt(), min = in.nextInt(), sec = in.nextInt();

double rad;

double k = Math.floor(grad / 360);

if (k >= 1 && grad > 0) grad = grad - 360 * k;

if(grad >= 0) rad = (grad * Math.PI + min * Math.PI / 60 + sec * Math.PI / 3600) / 180;

else rad = (grad * Math.PI - min * Math.PI / 60 - sec * Math.PI / 3600) / 180;

System.out.println(rad);

}

Решение.

Обозначим через переменные grad, min, sec число градусов, минут, секунд.

1 градус= 60 минут= 3600 секунд.

Сначала проверяем число градусов больше 360⁰ или нет. Если меньше то ничего не меняем, а если больше то от числа градусов отнимаем 360⁰ до тех пор пока оно не станет меньше 360. После используем формулы перевода градусов, минут и секунд в радианы:

[latex]\mathit{rad=grad\frac{\pi }{180}}[/latex]

[latex]\mathit{rad=min\frac{\pi }{180}/60}[/latex]

[latex]\mathit{rad=sec\frac{\pi }{180}/3600}[/latex]

Если число градусов положительно то используем конечную формулу:

[latex]\mathit{rad=grad\frac{\pi }{180}+min\frac{\pi }{180}/60+sec\frac{\pi }{180}/3600}[/latex]

Если же оно отрицательно то используем другую формулу:

[latex]\mathit{rad=grad\frac{\pi }{180}-min\frac{\pi }{180}/60-sec\frac{\pi }{180}/3600}[/latex]