e-olimp 4650. Граф-Турнир

26.06.2017 by Алексей Маслеев

Задача на e-olimp

Оригинал решения

Тесты на Try Haxe!

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

Построить на [latex]n[/latex] вершинах турнир, расстояние между любой парой вершин в котором не превышает двух рёбер.

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

Условию удовлетворяет любая тройка вершин, принадлежащих циклу длины три, следовательно, искомый граф сильно связен. Уместно взять за основу полный неориентированный граф [latex]K_n[/latex] (не ограничивая общности рассуждений, будем представлять граф на плоскости как правильный n-угольник) и задать на нём ориентацию рёбер согласно набору правил:

Контур графа (рёбра вида [latex](k,k+1)[/latex]) ориентирован по часовой стрелке.
В дальнейших построениях будем отталкиваться от контура: каждая вершина графа должна находиться в хотя бы в одном цикле длины три с данной. Опишем процедуру построения такого орграфа: начиная с вершины под номером 1 будем просматривать все остальные вершины. Если на некотором шаге ребро, связывающее вершины, не ориентировано, то ориентируем его образом, противоположным ориентации ребра, соединяющего текущую вершину-исток и предыдущую по номеру вершину в обходе. Более конструктивно процедура формулируется так: обойти все вершины в порядке их следования в контуре. Пусть номер стартовой вершины для исходной итерации — [latex]V_i[/latex], рассматриваемой на данном шаге — [latex]V_k[/latex] Если ребро [latex](V_i,V_k)[/latex] не ориентировано, и номера обеих вершин (не)чётны — задать ориентацию [latex][V_i,V_k][/latex], иначе — [latex][V_k,V_i][/latex].

Исключение — граф [latex]K_4[/latex]: степень каждой вершины равна трём, следовательно, одно ребро каждой вершины не принадлежит контуру. Но таких рёбер всего два, следовательно, невозможно задать чередование ориентаций рёбер и получить четыре цикла длины 3. Для всех графов на большем числе вершин построение всегда возможно.

Реализация:

Для решения задачи достаточно хранить граф в форме матрицы смежности.

Тесты:

n = 5 \begin{pmatrix}0 & 1 & 1&0&0 \\0 & 0 & 1&1&0 \\0 & 0 &0&1&1\\1 & 0& 0&0&1\\1 & 1 & 0&0&0\end{pmatrix}
n = 3 \begin{pmatrix}0 & 1 & 0 \\0 & 0 & 1 \\1 & 0 & 0 \end{pmatrix}

Код:

class Test{
    static function main(){
        var n = Std.parseInt(Sys.stdin().readLine());
        var a:Array<Array<Int>> = [for (i in 0...n) [for (j in 0...n) 0]];        
		if (n == 4){
        	trace("-1");     
        }            
        for(i in 0...n){
        	a[i][(i+1)%n] = 1;  
        }    	
    	for(i in 0...n){
         	for(j in 0...n){
                if((a[i][j] + a[j][i] == 0) && (i != j)){
                    if(i % 2 == j % 2){
                        a[i][j] = 1;
                    }
                    else a[j][i] = 1;                    
                }
            }
        }
		for(i in 0...n){
        	for(j in 0...n){
                trace(a[j][i]);
            }
            trace(" ");
        }
    }
}

class Test{

static function main(){

var n = Std.parseInt(Sys.stdin().readLine());

var a:Array<Array<Int>> = [for (i in 0...n) [for (j in 0...n) 0]];

if (n == 4){

trace("-1");

}

for(i in 0...n){

a[i][(i+1)%n] = 1;

}

for(i in 0...n){

for(j in 0...n){

if((a[i][j] + a[j][i] == 0) && (i != j)){

if(i % 2 == j % 2){

a[i][j] = 1;

}

else a[j][i] = 1;

}

for(i in 0...n){

for(j in 0...n){

trace(a[j][i]);

}

trace(" ");

}

A703

08.06.2017 by Евгений Кравчук

Условие
Даны квадратная матрица $A$ порядка $n$, векторы $x$ и $y$ с $n$ элементами каждый. Получить вектор $A(x+y)$.

Входные данные
Число $n$, матрица $A$, вектор $x$, вектор $y$.

Выходные данные
Результирующий вектор $A(x+y)$.

Тесты

Число $n$	Матрица $A$	Вектор $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	3 3 3	42 78 90
4	1 2 3 4 3 4 1 6 2 3 8 1 4 5 0 8	1 2 3 4	5 4 3 2	60 84 84 102

class Main 
{
	
	static function main() 
	{
		var n:Int = Std.parseInt(Sys.stdin().readLine());
		
		var A:Array<Array<Int>> = [for (x in 0...n) [for (y in 0...n) 0]];
		var x:Array<Int> = [for (x in 0...n) 0];
		var y:Array<Int> = [for (x in 0...n) 0];
		var res:Array<Int> = [for (x in 0...n) 0];
		
		for (i in 0...n) {
			for (j in 0...n) {
				A[i][j] = Std.parseInt(Sys.stdin().readLine());
			}
		}
		for (i in 0...n) {
			x[i] = Std.parseInt(Sys.stdin().readLine());
		}
		for (i in 0...n) {
			y[i] = Std.parseInt(Sys.stdin().readLine());
		}
		
		for (i in 0...n) {
			x[i] += y[i];
		}
		
		for (i in 0...n) {
			for (j in 0...n) {
				res[i] += A[i][j] * x[j];
			} 
		}
		
		Sys.println(res);
	}
	
}

class Main

{

static function main()

{

var n:Int = Std.parseInt(Sys.stdin().readLine());

var A:Array<Array<Int>> = [for (x in 0...n) [for (y in 0...n) 0]];

var x:Array<Int> = [for (x in 0...n) 0];

var y:Array<Int> = [for (x in 0...n) 0];

var res:Array<Int> = [for (x in 0...n) 0];

for (i in 0...n) {

for (j in 0...n) {

A[i][j] = Std.parseInt(Sys.stdin().readLine());

}

for (i in 0...n) {

x[i] = Std.parseInt(Sys.stdin().readLine());

}

for (i in 0...n) {

y[i] = Std.parseInt(Sys.stdin().readLine());

}

for (i in 0...n) {

x[i] += y[i];

}

for (i in 0...n) {

for (j in 0...n) {

res[i] += A[i][j] * x[j];

}

Sys.println(res);

}

Решение
Вводим число $n$, матрицу $A$, вектора $x$ и $y$. Заходим в цикл в котором считаем сумму векторов $x$ и $y$. В следующем цикле считаем произведение матрицы $A$ на результат сложения векторов $x$ и $y$. Выводим результирующий вектор $res = A(x+y)$.

Try Haxe !

Ю4.12

07.06.2017 by Евгений Кравчук

Условие
Задача: Все ненулевые элементы матрицы $D\left(k,l\right)$ расположить в начале массива $E\left(k \times l\right)$ и подсчитать их количество..

Входные данные
Два натуральных числа $k$ и $l$. А так же $k \times l$ элементов массива.

Выходные данные
Матрица $D$, ненулевые элементы массива $E$, количество ненулевых элементов

Тесты

$k$	$l$	Матрица $D$	Ненулевые элементы матрицы $E$	Количество ненулевых элементов
2	3	2 7 0 1 4 9	2 7 1 4 9	5
3	4	6 7 4 2 9 0 1 3 0 8 0 19	6 7 4 2 9 1 3 8 19	9
4	2	8 9 0 1 5 2 7 26	8 9 1 5 2 7 26	7

class Main 
{
	
	static function main() 
	{
		var K:Int = Std.parseInt(Sys.stdin().readLine());
		var L:Int = Std.parseInt(Sys.stdin().readLine());
		
		var M:Int = K * L;
		
		var D:Array<Array<Int>> = [for (x in 0...K) [for (y in 0...L) 0]];
		var E:Array<Int> = [for (x in 0...M) 0];
		
		var count:Int = 0;
		
		for (i in 0...K) {
			for (j in 0...L) {
				D[i][j] = Std.parseInt(Sys.stdin().readLine());
				if (D[i][j] != 0) {
					E[count++] = D[i][j];
				}	
			} 
		}
		
		for (i in 0...M) {
			if (E[i] == 0) {
				E.splice(i, E.length - i);
			}
		}
		
		Sys.println(E);		
		Sys.println("Количество ненулевых элементов матрицы E = " + count);
		
		for (u in 0...K) {
			for (y in 0...L) {
				Sys.print(D[u][y] + " ");
			}
			Sys.println("");
		}
	}
	
}

class Main

{

static function main()

{

var K:Int = Std.parseInt(Sys.stdin().readLine());

var L:Int = Std.parseInt(Sys.stdin().readLine());

var M:Int = K * L;

var D:Array<Array<Int>> = [for (x in 0...K) [for (y in 0...L) 0]];

var E:Array<Int> = [for (x in 0...M) 0];

var count:Int = 0;

for (i in 0...K) {

for (j in 0...L) {

D[i][j] = Std.parseInt(Sys.stdin().readLine());

if (D[i][j] != 0) {

E[count++] = D[i][j];

}

for (i in 0...M) {

if (E[i] == 0) {

E.splice(i, E.length - i);

}

Sys.println(E);

Sys.println("Количество ненулевых элементов матрицы E = " + count);

for (u in 0...K) {

for (y in 0...L) {

Sys.print(D[u][y] + " ");

}

Sys.println("");

}

Решение
Вводим числа $k$ и $l$. Получаем размерность массива $E$ — $M = k * l$. Заходим в цикл в котором вводим все элементы матрицы $D$ и считаем количество ненулевых элементов и перегоняем их в массив $E$. Потом удаляем нулевые элементы из матрицы $E$.

Try Haxe !

А400

13.05.2017 by Алексей Маслеев

Задача. Дана действительная квадратная матрица порядка [latex]n[/latex]. Получить [latex]x_{1}x_{n} + x_{2}x_{n-1}+ \cdots + x_{n}x_{1} [/latex], где[latex] x_k[/latex] — наибольшее значение элементов [latex]k[/latex]-й строки данной матрицы.

Суть задачи. Происходит заполнение многомерного массива. После этого в силу коммутативности умножения первая сумма полностью совпадает с последней, вторая — с предпоследней и т.д. Т.е. все слагаемые берутся дважды, кроме середины для нечётного [latex]n[/latex]. Это означает, что каждый максимум при вычислении суммы потребуется ровно один раз и никакой массив максимумов не нужен.

Оригинал решения

Решение на Try Haxe!

Тесты

[latex]n[/latex]	Элементы	Результат
2	1 2 3 4	16
3	1 2 3 4 5 6 7 8 9	1146

Код

	static function main() 
	{
		var n = Std.parseInt(Sys.stdin().readLine());
		var array = new Array<Array<Float>>();
		
		var sum:Float = 0;
		
		for (i in 0...n) 
		{
			array[i] = new Array<Float>();
			for (j in 0...n) 
			{
				array[i][j] = Std.parseFloat(Sys.stdin().readLine());
			}
		}
		
		for (i in 0...Std.int(((n + 1) / 2)))
		{
			sum += 2 * max(array[i]) * max(array[Std.int(n - i - 1)]);
		}
		
		trace(sum);
	}
	
	static function max(x:Array<Float>) : Float
	{
		var max:Float = x[0];
		
		x[0] = 91;
		for (i in 1...x.length)
		{
			max = (max > x[i]) ? max : x[i];
		}
		
		return max;
	}

static function main()

{

var n = Std.parseInt(Sys.stdin().readLine());

var array = new Array<Array<Float>>();

var sum:Float = 0;

for (i in 0...n)

{

array[i] = new Array<Float>();

for (j in 0...n)

{

array[i][j] = Std.parseFloat(Sys.stdin().readLine());

}

for (i in 0...Std.int(((n + 1) / 2)))

{

sum += 2 * max(array[i]) * max(array[Std.int(n - i - 1)]);

}

trace(sum);

}

static function max(x:Array<Float>) : Float

{

var max:Float = x[0];

x[0] = 91;

for (i in 1...x.length)

{

max = (max > x[i]) ? max : x[i];

}

return max;

}

Сергей Завада	Алексей Маслеев	Анастасия Улановская
Владислав Козачков	Николай Яковлев	Даша Тарабаева
Денис Швецов	Лена Наумова	Артур Тарасов
Евгений Кравчук	Артём Мисесин	Даша Кивганова
Иоанна Васильева	Дарья Пиндус	Алёна Ищук
Кирилл Автомонов	Маша Лукьянова	Александр Зайченко
Игорь Варламов	Геннадий Муржи

haxe

Учебные материалы по программированию

Tag Archives: многомерный массив

e-olimp 4650. Граф-Турнир

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

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

Реализация:

Тесты:

Код:

A703

Ю4.12

А400