a406

18.05.2017 by Дарья Пиндус

Задача. С помощью [latex]x_{ij}, i=1,2; j=1,…,n[/latex] — действительной матрицы на плоскости задано [latex]n[/latex] точек так, что [latex]x_{1j},x_{2j} [/latex] — координаты [latex]j [/latex]— точки. Точки попарно соединены отрезками. Найти длину наибольшего отрезка.

Тест

n	Матрица [latex]x_{ij}, i=1,2[/latex]	Длина наибольшего отрезка	Комментарий
3	2 8 4 9 1 5	10	Пройдено
4	6 14 2 1 9 3 8 0	13.3417	Пройдено
5	1 8 4 3 7 2 9 5 0 11	11.7047	Пройдено

Код программы

class Point {
   public var x:Int; 
   public var y:Int;
   public function new(x,y) {
    this.x = x;
    this.y = y;
  }
}

class Test {
    static function distance(a:Point, b:Point):Float{
            return Math.sqrt((b.x-a.x)*(b.x-a.x) + (b.y - a.y)* (b.y - a.y));
    }
    
    static function main() {
        var n = Std.parseInt(Sys.stdin().readLine()); 
        
        var coords:Array<Array<Int>> = new Array<Array<Int>>();
        var max:Float = 0;
        var curr:Float;
        
        for (i in 0...n){
            for (j in 0...1) {
            	coords[i][j] = Std.parseInt(Sys.stdin().readInt32());
        	}
        }
        
        var a:Point, b:Point;
        for (i in 0...n){
            a = new Point(coords[0][i], coords[1][i]);
        	b = i < n ? new Point(coords[0][i+1], coords[1][i+1]) : new Point(coords[0][0], coords[1][0]);
            curr = distance(a, b);
            if (max < curr) {
                max = curr;
            }
        }
        trace(max);
    }
}

class Point {

public var x:Int;

public var y:Int;

public function new(x,y) {

this.x = x;

this.y = y;

}

class Test {

static function distance(a:Point, b:Point):Float{

return Math.sqrt((b.x-a.x)*(b.x-a.x) + (b.y - a.y)* (b.y - a.y));

}

static function main() {

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

var coords:Array<Array<Int>> = new Array<Array<Int>>();

var max:Float = 0;

var curr:Float;

for (i in 0...n){

for (j in 0...1) {

coords[i][j] = Std.parseInt(Sys.stdin().readInt32());

}

var a:Point, b:Point;

for (i in 0...n){

a = new Point(coords[0][i], coords[1][i]);

b = i < n ? new Point(coords[0][i+1], coords[1][i+1]) : new Point(coords[0][0], coords[1][0]);

curr = distance(a, b);

if (max < curr) {

max = curr;

}

trace(max);

}

Ход решения:

Вводим матрицу построчно (не очень удобно).
Находим длину наибольшего отрезка.
С помощью вложенных циклов мы находим длины всех отрезков по формуле
По алгоритму нахождения максимума находим длину наибольшего отрезка.
Выводим матрицу.
Выводим длину наибольшего отрезка.

Пример выполнения

Ю 4.31

18.05.2017 by Дарья Пиндус

Задача

Циклический сдвиг. Осуществить циклический сдвиг элементов массива [latex]T(n)[/latex] на [latex]m[/latex] позиций влево, то есть получить массив: [latex]t_{m+1},…,t_{n},t_{1},…,t_{m}[/latex].
При этом необязательно [latex]m<n[/latex].

Тесты:

изначальный массив	сдвиг (m)	результат	комментарий
1 2 3 4 5 6 7	2	3 4 5 6 7 1 2	пройден
1 2 3 4 5 6 7	0	1 2 3 4 5 6 7	пройден
1 2 3 4 5 6 7	10	4 5 6 7 1 2 3	пройден

Код программы

class Test {
    static function main() {
        var a:Array<Int> = [];
        var n = Std.parseInt(Sys.stdin().readLine()); 
        var m = Std.parseInt(Sys.stdin().readLine()); 
        for (i in 0...n){
             a[i] = Std.parseInt(Sys.stdin().readLine()); 
        }
        a = shiftArray(a, m);
        trace(a);
    }
    
    static function shiftArray(a:Array<Int>, m:Int):Array<Int>{
        if (m < 0) {
            throw "Illegal argument exception";
        }
        var shifted:Array<Int> = [];
        var length = a.length;
        if (m > length) {
            m = m % length;
            trace(m);
        }
        for (i in 0...a.length){
        	shifted[i] = i + m < length ? a[i+m] : a[(i+m)%length];    
		}
        return shifted;
    }
   
}

class Test {

static function main() {

var a:Array<Int> = [];

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

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

for (i in 0...n){

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

}

a = shiftArray(a, m);

trace(a);

}

static function shiftArray(a:Array<Int>, m:Int):Array<Int>{

if (m < 0) {

throw "Illegal argument exception";

}

var shifted:Array<Int> = [];

var length = a.length;

if (m > length) {

m = m % length;

trace(m);

}

for (i in 0...a.length){

shifted[i] = i + m < length ? a[i+m] : a[(i+m)%length];

}

return shifted;

}

Пример выполнения

A299

18.04.2017 by Дарья Пиндус

Условие

Дана последовательность действительных чисел [latex]a_{1},a_{2},…,a_{n}[/latex]. Требуется домножить все члены последовательности на квадрат её наименьшего члена, если [latex]<a_{1} \geq 0[/latex], в противном случае — на квадрат наибольшего.

Решение

Для решения воспользуемся классом Array для инициализации массива. Далее заполним его числами со входного потока. Далее, в зависимости от первого (нулевого) элемента массива, воспользуемся функцией getMin() или getMax() . Далее умножим каждый элемент на (соответственно) минимум/максимум и выведем последовательность.

Тесты

№	Входные данные	Выходные данные
1	-2 2 43 5 -10 12 0 -1	-3698 3698 79507 9245 -18490 22188 0 -1849
2	0 100 99 0 -1 1	0 100 99 0 -1 1
3	42 1 1 1 0 -1 24 -24 -42	74088 1764 1764 1764 0 -1764 42336 -42336 -74088

Код

class Test {
    static function getMin(a:Array<Int>) {
        var min:Int = a[0];
        for (v in a) {
        	if (v < min)
            	min = v;
        }
    	return min;
    }

	static function getMax(a:Array<Int>) {
        var max:Int = a[0];
        for (v in a){
        	if (v > max)
            	max = v;
        }
    	return max;
    }

    static function main() {
        var a:Array<Int> = new Array<Int>();
        while(true) {
            var b:Int = Std.parseInt(Sys.stdin().readLine());
            a.push(b);
        }
        var factor = a[0] >= 0 ? getMin(a) : getMax(a);     
       
        for (i in 0...a.length) {
        	a[i] *= factor*factor;
        }
        trace (a);
    }
}

class Test {

static function getMin(a:Array<Int>) {

var min:Int = a[0];

for (v in a) {

if (v < min)

min = v;

}

return min;

}

static function getMax(a:Array<Int>) {

var max:Int = a[0];

for (v in a){

if (v > max)

max = v;

}

return max;

}

static function main() {

var a:Array<Int> = new Array<Int>();

while(true) {

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

a.push(b);

}

var factor = a[0] >= 0 ? getMin(a) : getMax(a);

for (i in 0...a.length) {

a[i] *= factor*factor;

}

trace (a);

}

Ссылка на решение

e-olymp 141. Минимальная сумма цифр

26.03.2017 by Дарья Пиндус

Задача. Сколько натуральных чисел из промежутка имеют наименьшую сумму цифр ?

Задачу также можно найти здесь.

Входные данные:
Во входном файле два числа [latex]\textrm{M}[/latex] и [latex]\textrm{N}[/latex] ([latex]1\leq \textrm{M}\leq \textrm{N}\leq 1000000[/latex]) .

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

В выходной файл нужно записать ответ — одно число.

Тесты

№	M	N	Вывод
1	1	100	3
2	2	17	1
3	32	1024	2
4	1	1000000	7
5	10	10	1

Код программы

class Test {
    static function DigitsSum(val:Int):Int{
        var res:Int = 0;
        while (val!=0) {
            res +=val%10;
            val = Std.int(val/10);
        }
        return res;
    }

    static function main() {
        var m: Int = Std.int(Sys.stdin().readline());
        var n: Int = Std.int(Sys.stdin().readline());
        var count:Int;
        count = 1;
        var min:Int;
        min = DigitsSum(m);
        while (++m <= n) {
            if (min == DigitsSum(m)) {
                count++;
            }
            else if (min > DigitsSum(m)) {
                min = DigitsSum(m);
                count = 1;
            }
        }
        trace("Result " + count);
    }
}

class Test {

static function DigitsSum(val:Int):Int{

var res:Int = 0;

while (val!=0) {

res +=val%10;

val = Std.int(val/10);

}

return res;

}

static function main() {

var m: Int = Std.int(Sys.stdin().readline());

var n: Int = Std.int(Sys.stdin().readline());

var count:Int;

count = 1;

var min:Int;

min = DigitsSum(m);

while (++m <= n) {

if (min == DigitsSum(m)) {

count++;

}

else if (min > DigitsSum(m)) {

min = DigitsSum(m);

count = 1;

}

trace("Result " + count);

}

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

Для решения данной задачи зададим функцию, которая возвращает сумму чисел вводимого нами числа. После ввода границ необходимого промежутка присваиваем минимальную сумму[latex]\textrm{M}[/latex]. Теперь задаём цикл со счётчиком i от [latex]\textrm{M + 1}[/latex] до [latex]\leq \textrm{N}[/latex]. В случае, когда сумма чисел счётчика меньше сумме цифр числа [latex]\textrm{M}[/latex], присваиваем ей (сумме цифр счётчика i) минимальную сумму цифр и выводим единицу. В противном случае увеличиваем счётчик на единицу и выводим полученный результат. Выводимое число и будет количеством натуральных чисел на промежутке, имеющих наименьшую сумму цифр.

Код программы можно найти здесь.

6.7. Итераторы

26.03.2017 by Дарья Пиндус

С Haxe очень легко определить пользовательские итераторы и итерируемые типы данных. Эти понятия представлены типами Iterator и Iterable <T> соответственно:

typedef Iterator<T> = {
  function hasNext() : Bool;
  function next() : T;
}

typedef Iterable<T> = {
  function iterator() : Iterator<T>;
}

typedef Iterator<T> = {

function hasNext() : Bool;

function next() : T;

}

typedef Iterable<T> = {

function iterator() : Iterator<T>;

}

Любой класс, который структурно согласуется с одним из этих типов, может быть проитерирован с помощью цикла for-loop. То есть, если класс определяет методы hasNext и next с соответствующими возвращаемыми типами, он считается итератором, а если он определяет итератор метода, возвращающий Iterator <T>, он считается итерируемым типом.

class BoundsArrayIterator<T> { 
    var min:Int; 
    var max:Int; 
    var a:Array<T>;

    public function new(a:Array<T>, min:Int, max:Int) { 
        this.a = a; 
        this.min = min; 
        this.max = max; 
    } 

    public function hasNext(){ 
    	return max > min; 
    } 

    public function next(){ 
        return a[min++]; 
        } 
    } 

class BoundsArrayWrap<T> { 
    var min:Int; 
    var max:Int; 
    var a:Array<T>; 

    public function new(a:Array<T>, min:Int, max:Int) { 
        this.a = a;
        this.min = min;
        this.max = max;
    } 

    public function iterator(){ 
    	return new BoundsArrayIterator<T>(a, min, max); 
    } 
}

class Test {
    static function main() {
        var a = ['not', 'very', 'important', 'text', 'at', 'all'];
          var bounded = new BoundsArrayWrap<String>(a, 1, 4);
          for (str in bounded) {
               trace(str);
          }
    }
}

class BoundsArrayIterator<T> {

var min:Int;

var max:Int;

var a:Array<T>;

public function new(a:Array<T>, min:Int, max:Int) {

this.a = a;

this.min = min;

this.max = max;

}

public function hasNext(){

return max > min;

}

public function next(){

return a[min++];

}

class BoundsArrayWrap<T> {

var min:Int;

var max:Int;

var a:Array<T>;

public function new(a:Array<T>, min:Int, max:Int) {

this.a = a;

this.min = min;

this.max = max;

}

public function iterator(){

return new BoundsArrayIterator<T>(a, min, max);

}

class Test {

static function main() {

var a = ['not', 'very', 'important', 'text', 'at', 'all'];

var bounded = new BoundsArrayWrap<String>(a, 1, 4);

for (str in bounded) {

trace(str);

}

Выполнение кода можно посмотреть здесь

Тип BoundsArrayIterator<T> в данном примере является итератором. Он реализует методы hasNext, проверяющий достигнут ли конец диапазона, и next, возвращающий объект из массива. Данный итератор используется в классе BoundsArrayWrap<T> в методе iterator, который и определяет данный класс как итерируемый.

Ссылка на источник

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

haxe

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

Author Archives: Дарья Пиндус

a406

Ю 4.31

Задача

A299

e-olymp 141. Минимальная сумма цифр

6.7. Итераторы