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

}

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

}

e-olymp 905. Какой треугольник?

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

Задача e-olymp 905
Задача Тест на tryHaxe

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

Определить вид треугольника (равносторонний, равнобедренный, разносторонний) по заданным длинам его сторон. Существование треугольника и корректность исходных данных гарантируется. Технические условия Входные данные В единственной строке задано 3 целых числа — длины сторон треугольника. Длины сторон не превышают 100. Выходные данные В единственной строке вывести 1, если треугольник равносторонний, 2 если равнобедренный и 3 если разносторонний.

Тесты:

Входные данные	Результат
5 5 5	1
1 2 2	2
3 4 5	3
3 5 5	такого треугольника не существует

class Test
{
  static function main() 
  {   
   var n;
   n = Std.parseInt(Sys.stdin().readLine());
   var a = new Array<Int>();
   for(i in 0...n)
   {
      a[i] = Std.parseInt(Sys.stdin().readLine());
   }

   if ( (a[1] + a[2]) >= a[3]) \\проверка на условие неравенство треугольника
   {
       if( a[0] == a[1] && a[1] == a[2] )\\равнобедренный треугольник 
       {
           trace("1");
       }
       else if( a[0] == a[1] || a[1]==a[2] || a[0]==a[2])\\ три стороны равны то есть треугольник равносторонний
       {
     	   trace("2");
       }
       else 
       {
           trace("3");
       }
    }	
   else trace("такого треугольника не существует");
  }
}

class Test

{

static function main()

{

var n;

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

var a = new Array<Int>();

for(i in 0...n)

{

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

}

if ( (a[1] + a[2]) >= a[3]) \\проверка на условие неравенство треугольника

{

if( a[0] == a[1] && a[1] == a[2] )\\равнобедренный треугольник

{

trace("1");

}

else if( a[0] == a[1] || a[1]==a[2] || a[0]==a[2])\\ три стороны равны то есть треугольник равносторонний

{

trace("2");

}

else

{

trace("3");

}

else trace("такого треугольника не существует");

}

e-olymp 506. Новый компилятор

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

Задача e-olymp 506.

Оригинальное решение.

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

Задача. Вам необходимо преобразовать множество старых программ для новой версии компилятора. Для этого необходимо заменить «->» на «.» везде, кроме комментариев. Комментарии в данном языке программирования начинаются с символов «//» и продолжаются до конца строки. Напишите программу, выполняющую такое преобразование.

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

Входной файл содержит от 1 до 500 строк длиной не более 50 символов с ASCII-кодами от 32 до 127 – текст программы, которую нужно преобразовать.

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

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

Тесты:

Входные данные	Результат
test program —> int main();	test program -. int main();
coments write like // not ->	coments write like // not ->
coment you can wtite -> // not -> \\	coment you can wtite . // not -> \\

Код

class Main
{
	static function main() 
	{        
		var str = new Array < String > ();
        var new_str = "";
        var arrowFlag: Bool;
        var commentFlag: Bool;
        var commentFullFlag: Bool;
        var i = 0;
		
        while ((new_str = Sys.stdin().readLine()) != "")
        {
            str[i] = "";
            var arrowFlag = false;
            var commentFlag = false;
            var commentFullFlag = false;
            for (j in 0...new_str.length)
            {
                var symb = new_str.charAt(j);
                if (!commentFullFlag)
                {
                    if (symb == "/")
                    {
						commentFullFlag = commentFlag;
                        commentFlag = true;
                        str[i] += symb;
                    }
                    else if (symb == "-" && !arrowFlag)
                    {
                        arrowFlag = true;
                    }
                    else if (symb == ">" && arrowFlag)
                    {
						str[i] += ".";
						arrowFlag = false;
                    }
                    else
                    {
                        str[i] += symb;
                    }
                }
                else
                {
                    str[i] += symb;
                }
            }
            i++;
        }
		
        var output = Sys.stdout();
        for (i in 0...str.length)
        {
            output.writeString(str[i] + "\n");
        }
	}
}

class Main

{

static function main()

{

var str = new Array < String > ();

var new_str = "";

var arrowFlag: Bool;

var commentFlag: Bool;

var commentFullFlag: Bool;

var i = 0;

while ((new_str = Sys.stdin().readLine()) != "")

{

str[i] = "";

var arrowFlag = false;

var commentFlag = false;

var commentFullFlag = false;

for (j in 0...new_str.length)

{

var symb = new_str.charAt(j);

if (!commentFullFlag)

{

if (symb == "/")

{

commentFullFlag = commentFlag;

commentFlag = true;

str[i] += symb;

}

else if (symb == "-" && !arrowFlag)

{

arrowFlag = true;

}

else if (symb == ">" && arrowFlag)

{

str[i] += ".";

arrowFlag = false;

}

else

{

str[i] += symb;

}

else

{

str[i] += symb;

}

i++;

}

var output = Sys.stdout();

for (i in 0...str.length)

{

output.writeString(str[i] + "\n");

}

Ю4.21

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

Задача.

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

Решение.

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

Тесты:

n = 4 \begin{pmatrix}0 & 1 & 0&1 \\1 & 0 & 1&0 \\0 & 1 & 0&1 \\1 & 0& 1&0\end{pmatrix}
n = 2 \begin{pmatrix}
0 & 1 \\
1 & 0
\end{pmatrix}

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

class Test

{

static function main()

{

var n;

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

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

for(i in 0...n )

{

for(j in 0...n )

{

if((i+j)%2==0)

{

a[i][j] = 1;

}

else

{

a[i][j] = 0;

}

Задача взята с источник

А137а

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

Задача:

Даны натуральное число n и действительные числа [latex] a_1, \cdots ,a_n [/latex]

Вычислить:

[latex] a_1, a_1 + a_2, \cdots, a_1 + a_2 + \cdots + a_n [/latex]

Решение:

Для подсчёта суммы в данной задаче надо было организовать цикл for (поскольку указано количество элементов в ряду), и с каждой итерацией прибавлять к результату result (которому предварительно придано значение 0) введённое с клавиатуры значение, потом выводить результат на экран.

Тесты:

Кол-во элементов	[latex] a_1, \cdots ,a_n [/latex]	Результат
7	1, 2, 3, 4, 5, 6, 7	1, 3, 6, 10, 15, 21, 28
10	10, 12, 14, 16, 18, 20, 21, 23, 25, 27	10, 22, 36, 52, 70, 90, 111, 134, 159, 186
5	0.1, 0.2, 0.3, 0.4, 0.5	0.1, 0.3, 0.6, 1.0, 1.5

class Test
{
  static function main()
  {
      var result : Float;
      var a : Float; // заводим переменные для считывания числа и подсчёта суммы
      var n;  //кол-во элементов в ряду
      n = Std.parseInt(Sys.stdin().readLine());        
      for (i in 0...n)
      {
        a = Std.parseInt(Sys.stdin().readLine()); //вводим число
        result+=a; //прибавляем к результату
        trace (result + "\n"); //выводим на экран результат сложения
      }
  }
}

class Test

{

static function main()

{

var result : Float;

var a : Float; // заводим переменные для считывания числа и подсчёта суммы

var n; //кол-во элементов в ряду

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

for (i in 0...n)

{

a = Std.parseInt(Sys.stdin().readLine()); //вводим число

result+=a; //прибавляем к результату

trace (result + "\n"); //выводим на экран результат сложения

}

Тест на tryHaxe
Задача взята с источника

e-olymp 60. Площадь многоугольника

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

Задача e-olymp 60.
Тест на tryHaxe.

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

Заданы координаты [latex] n [/latex] последовательных вершин многоугольника. Определить его площадь.

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

Первая строка содержит количество вершин многоугольника [latex] n [/latex]. В следующих [latex] n [/latex] строках через пробел заданы целочисленные координаты его последовательных вершин [latex] x_i, y_i. [/latex] Известно, что [latex] 3≤n≤1000,−1000≤x[i],y[i]≤1000.[/latex]

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

Площадь многоугольника [latex] S [/latex].

Тесты

Входные данные	Выходные данные
3, (0, 0), (0, 2), (2, 0)	2
4, (-1000, 500), (-500, 1000), (2, 10), (35, 60)	339865
5, (13, -92), (44, 0), (-800, 30), (27, 2), (1, 2)	1446.000

class Test {
    static function main() {
        var n, n1, x1, x2, y1, y2, x, y;
        var sum = 0.0;
        n = Std.parseInt(Sys.stdin().readLine());
        x = Std.parseInt(Sys.stdin().readLine());
        y = Std.parseInt(Sys.stdin().readLine());
        x1 = x;
        y1 = y;
        for (i in 0...n) {
            x2 = Std.parseInt(Sys.stdin().readLine());
            y2 = Std.parseInt(Sys.stdin().readLine());
            sum = sum + (x1 + x2) * (y2 - y1);
            x1 = x2;
            y1 = y2;
        }
        sum = sum + (x + x2) * (y - y2);
        trace(Math.abs(sum) / 2);
    }
}

class Test {

static function main() {

var n, n1, x1, x2, y1, y2, x, y;

var sum = 0.0;

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

x = Std.parseInt(Sys.stdin().readLine());

y = Std.parseInt(Sys.stdin().readLine());

x1 = x;

y1 = y;

for (i in 0...n) {

x2 = Std.parseInt(Sys.stdin().readLine());

y2 = Std.parseInt(Sys.stdin().readLine());

sum = sum + (x1 + x2) * (y2 - y1);

x1 = x2;

y1 = y2;

}

sum = sum + (x + x2) * (y - y2);

trace(Math.abs(sum) / 2);

}

Для подсчёта площади необходима специальная формула которую можно найти тут а так же некоторое её обоснование.

ML5

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

Оригинал задачи тут
Тесты задачи на TryHaxe

Условие:

Даны два действительных числа. Найти среднее арифметическое этих чисел и среднее геометрическое их модулей.

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

Нам необходимо найти среднее арифметическое чисел, которое представляет собой сумму всех зафиксированных значений, делённую на их количество. Для нашей задачи формула приобретает следующий вид: [latex] A = \frac{a+b}{2}.[/latex]
Для нахождения среднего геометрического модулей двух чисел воспользуемся формулой [latex] G = \sqrt{|a×b|}.[/latex]

class Test
{
    static function main()
    {
	    var a : Float;
        var b : Float;   
    	var a : Float = std.parsefloat(sys.stdin.readline());
    	var b : Float = std.parsefloat(sys.stdin.readline());
      	trace((a + b) / 2 + "среднее арифметическое чисел\n");
      	trace(Math.sqrt(Math.abs(a * b)) + "среднее геометрическое чисел\n");
    }
}

class Test

{

static function main()

{

var a : Float;

var b : Float;

var a : Float = std.parsefloat(sys.stdin.readline());

var b : Float = std.parsefloat(sys.stdin.readline());

trace((a + b) / 2 + "среднее арифметическое чисел\n");

trace(Math.sqrt(Math.abs(a * b)) + "среднее геометрическое чисел\n");

}

Тесты:

Первое число	Второе число	Среднее арифметическое	Среднее геометрическое
3	9	6	5.19615
156	82	119	113.102
-544.59	-12	-278.295	80.8398

e-olymp 918. Какая четверть?

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

Задача e-olymp 918
Тесты задачи на TryHaxe

Задача

Задана точка с координатами x и y. Определить, в какой координатной четверти она расположена.

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

В единственной строке через пробел заданы 2 вещественных числа — координаты точки, значения координат по модулю не превышают 100.

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

Единственное число — номер соответствующей четверти, либо 0, если однозначно определить четверть невозможно.

class Test
{
    static function main()
    {
        var x: Int;
        var y: Int;
        //var x : Int = std.parsefloat(sys.stdin.readline());
        //var y : Int = std.parsefloat(sys.stdin.readline());
        x = 3;
        y = 2;
        if (x == 0 && y == 0)
        {
            trace("0");
        }
        else if (x > 0 && y > 0)
        {
            trace("1");
        }
        else if (x > 0 && y < 0)
        {
            trace("4");
        }
        else if (x < 0 && y > 0)
        {
            trace("2");
        }
        else
        {
            trace("3");
        }
    }
}

class Test

{

static function main()

{

var x: Int;

var y: Int;

//var x : Int = std.parsefloat(sys.stdin.readline());

//var y : Int = std.parsefloat(sys.stdin.readline());

x = 3;

y = 2;

if (x == 0 && y == 0)

{

trace("0");

}

else if (x > 0 && y > 0)

{

trace("1");

}

else if (x > 0 && y < 0)

{

trace("4");

}

else if (x < 0 && y > 0)

{

trace("2");

}

else

{

trace("3");

}

Тесты:

[latex] x [/latex]	[latex] y [/latex]	Четверть
2	-2	4
8	10	1
-3	5	2
-3	-9	3

Сначала мы проверяем, не равна ли хотя бы одна переменная нулю. Если да — выводим 0, если нет — проверяем, больше ли [latex] x [/latex] нуля. Если да — это будет первая или четвертая четверть, если нет — вторая или третья. Если [latex] y [/latex] больше нуля — это первая или вторая четверть, если меньше — вторая или третья.

2.1.4 Type Bool

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

2.1.4 Bool учебник по Haxe 3.

Bool — базовый тип, представляющий собой значение типа true или false.

Значения типа Bool обычно используют в условиях if и while.
Значения типа Bool могут возвращать такие операторы как:

&& (и)
|| (или)
! (не).

Haxe гарантирует что сложные логические выражения вычисляются слева направо и при том только при необходимости в момент выполнения. Например, для выражения типа А && B программа первое что проверит это верно ли А, и проверит В только в том случае если проверка для А верна. Для выражения А || B не будет вычисляться В если А == true поскольку значение В уже не будет иметь значения. Это важно в таких случаях как например это:

if (object != null && object.field == 1) { . . . }

В этом случае, доступ в object.field приведет к ошибке во время исполнения, если поле object пусто, то есть null, но проверка object != null защитит от этой ошибки. Другой пример:

class Test 
{
    static function main() 
    {
        var a = 1;
		var b = 6;
        if (a > 0 || b < 0 )
        {
           trace("true");
        }
        else trace ("false");
    }
}

class Test

{

static function main()

{

var a = 1;

var b = 6;

if (a > 0 || b < 0 )

{

trace("true");

}

else trace ("false");

}

В этом случае на выходе будет true. При этом если a > 0 && b < 0, то будет выведена строка «false».

Ссылка на Try Haxe!

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

haxe

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

Author Archives: Алексей Маслеев

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

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

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

Реализация:

Тесты:

Код:

А400

e-olymp 905. Какой треугольник?

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

Тесты:

e-olymp 506. Новый компилятор

Задача e-olymp 506.

Оригинальное решение.

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

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

Тесты:

Ю4.21

Задача.

Решение.

Тесты:

А137а

e-olymp 60. Площадь многоугольника

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

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

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

Тесты

ML5

Условие:

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

Тесты:

e-olymp 918. Какая четверть?

Задача

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

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

2.1.4 Type Bool