A711a

02.05.2017 by Николай Яковлев

Задача.

Дана матрица $A$ размера $m\times m$. Получить матрицу $AA^{*}$ (ее размер $m\times m$).
Размер матрицы:

Матрица:

1	2	3	4
5	6	7	8
9	0	1	2
3	4	5	6

Результирующая матрица:

30	70	20	50
70	174	68	122
20	68	86	44
50	122	44	86

Ход решения:

На входе считываем $m$ — размер матрицы. После этого создаем два вложенных массива — $A$ для хранения вводимых значений и вычислений, $result$ — для результатов вычислений. Переменная $sum$ нужна для хранения временного результата суммы произведений $A[i,k]A[j,k]$.

Код:

class Main 
{
	
	static function main() 
	{
		var m = getNextInt();
		
		var A:Array<Array<Int>> = [for (x in 0...m) [for (y in 0...m) 0]];
		var result:Array<Array<Int>> = [for (x in 0...m) [for (y in 0...m) 0]];
		
		for (i in 0...m)
		{
			for (j in 0...m) 
			{
				A[i][j] = getNextInt();
			}
		}
		
		for (i in 0...m) 
		{
			for (j in 0...m) 
			{
				var sum = 0;
				for (k in 0...m) 
				{
					sum += A[i][k] * A[j][k];
				}
				result[i][j] = sum;
			}
		}
		
		var output = Sys.stdout();
		for (i in 0...m) 
		{
			for (j in 0...m)
			{
				output.writeString(Std.string(result[i][j]) + " ");
			}
			output.writeString("\n");
		}
	}
	
	static function getNextInt()
	{
		var number = Sys.stdin().readLine();
		return Std.parseInt(number);
	}
}

class Main

{

static function main()

{

var m = getNextInt();

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

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

for (i in 0...m)

{

for (j in 0...m)

{

A[i][j] = getNextInt();

}

for (i in 0...m)

{

for (j in 0...m)

{

var sum = 0;

for (k in 0...m)

{

sum += A[i][k] * A[j][k];

}

result[i][j] = sum;

}

var output = Sys.stdout();

for (i in 0...m)

{

for (j in 0...m)

{

output.writeString(Std.string(result[i][j]) + " ");

}

output.writeString("\n");

}

static function getNextInt()

{

var number = Sys.stdin().readLine();

return Std.parseInt(number);

}

e-olymp 138. Банкомат

10.04.2017 by Даша Тарабаева

Ссылка на условие задания: e-olymp.

Условие

В банкомате имеются в достаточном количестве купюры номиналом $10$, $20$, $50$, $100$, $200$, $500$. Найти минимальное количество купюр, которое необходимо использовать, чтобы выдать сумму в $n$ гривен или вывести $-1$, если указанную сумму выдать нельзя.

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

Одно число $n$ ([latex]1 \leq n \leq 1000000[/latex]).

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

Наименьшее количество купюр, которыми можно выдать $n$ гривен.

Тесты

Входные данные	Выходные данные
Сумма	Количество купюр
130	3
999	-1
7360	18
440	4
3	-1

Код.

class Test {
    static function f(n : Float) : Float {
        var M = [500,200,100,50,20,10];
        var k=0;//переменная для числа купюр
        if(n%10!=0) return (-1);
        for (i in 0...M.length)
            {
                k+=Math.floor(n/M[i]);
                n=n%M[i];
            }
            return k;
    }
    static function main() {
        var output = Sys.stdout();
        var n:Int = Std.parseFloat(Sys.stdin().readLine()); //необходимая сумма
        var k= f(n);    //переменная для числа купюр      
        output.writeString(k);
    }
}

class Test {

static function f(n : Float) : Float {

var M = [500,200,100,50,20,10];

var k=0;//переменная для числа купюр

if(n%10!=0) return (-1);

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

{

k+=Math.floor(n/M[i]);

n=n%M[i];

}

return k;

}

static function main() {

var output = Sys.stdout();

var n:Int = Std.parseFloat(Sys.stdin().readLine()); //необходимая сумма

var k= f(n); //переменная для числа купюр

output.writeString(k);

}

Решение.

Для выполнения задания была написана функция, параметром для которой служит сумма, которую должен выдать автомат.
Сама функция является реализацией жадного алгоритма.Он заключается в том, чтобы взять купюру наибольшего достоинства, и найти, сколько раз она входит в данную сумму. То, что мы можем выдать только с помощью этой купюры, отнять от исходной суммы. Затем повторить операцию для оставшегося количества денег и самой большой из купюр меньшего достоинства. Перебрав таким образом все купюры, мы получим наименьшее их количество для получения данной суммы, что от нас, собственно, и требуется.

Такой алгоритм подходит не для всех валютных систем, а только для канонических — таких, в которых каждая купюра большего достоинства превышает меньшую более чем в два раза. В нашем случае это условие соблюдается.

Следует учесть, что сумма может быть и такой, что банкомат не сможет ее выдать. Это будет происходить тогда, когда сумма содержит некоторую часть, меньшую самой меньшей купюры. Для проверки этого условия, до начала выполнения жадного алгоритма, выполняется проверка. Если указанная сумма делится на 10 без остатка, то функция начинает выполнение алгоритма, если же нет, то возвращает $-1$.

Ссылка на решение задачи на сайте Try Haxe!

А409

09.04.2017 by Артём Мисесин

Задача.

Дана действительная квадратная матрица порядка [latex]9[/latex]. Вычислить сумму тех из её элементов, расположенных на главной диагонали и выше неё, которые превосходят по величине все элементы, расположенные ниже главной диагонали. Если на главной диагонали и выше неё нету элементов с указанным свойством, то ответом должно служить сообщение об этом.

Решение.

Находим наибольший из нижних элементов (элементы, расположенные ниже главной диагонали).
Сравниваем каждый элемент верхнего множества (элементы, расположенные выше главной диагонали и на самой диагонали) с наибольшим элементом ( bottomMax ) из всех нижних элементов и если это число больше, то прибавляем это число к переменной totalSumm.

Код:

class Test {
    // функция определения максимального значения из двух данных
    static function max(x:Int, y: Int) {
    	return if (x > y) x else y;
    }
    
    static function main() {
        var i = 0;
        var n = 9;
        var maxValue = 100; // (maxValue - 1) - максимальное значение матрицы
        var totalSumm = 0;
        
        // генерация матрицы 9х9
	    var bigArray:Array<Array<Int>> = [
            for (x in 0...n) [
            	for (y in 0...n) Std.random(maxValue)]
        ];
        
        // вывод матрицы для наглядности
        for (x in 0...n) {
             var line = "";
             for (y in 0...n){
            	line += Std.string(bigArray[x][y]);
           		var addLine = "_|_";
            	if (bigArray[x][y] < 10) {
                    addLine = "__|_";
                }
                line += addLine;
        	 }
             trace(line);
        }
    	
        // поиск максимального значения элементов нижнего множества матрицы
    	var bottomMax = bigArray[0][1];
    	for (x in 0...n) {
             for (y in 0...n){
            	if (x > y){
                    bottomMax = max(bottomMax, bigArray[x][y]);
                }
        	 }
        }
    	trace(bottomMax);
		
        // поиск значений элементов верхнего множества матрицы, больших, чем максимальное 
        //значение элементов нижнего множества матрицы
	    for (x in 0...n) {
             for (y in 0...n){
            	if (y >= x){
            		if (bigArray[x][y] > bottomMax){
                    	totalSumm += bigArray[x][y];
                	}
                }
        	 }
        }
        // вывод результата
        if (totalSumm == 0){
            trace("В массиве нет элементов с таким свойством");
        } else {
        	trace(totalSumm);
        }
    }
}

class Test {

// функция определения максимального значения из двух данных

static function max(x:Int, y: Int) {

return if (x > y) x else y;

}

static function main() {

var i = 0;

var n = 9;

var maxValue = 100; // (maxValue - 1) - максимальное значение матрицы

var totalSumm = 0;

// генерация матрицы 9х9

var bigArray:Array<Array<Int>> = [

for (x in 0...n) [

for (y in 0...n) Std.random(maxValue)]

];

// вывод матрицы для наглядности

for (x in 0...n) {

var line = "";

for (y in 0...n){

line += Std.string(bigArray[x][y]);

var addLine = "_|_";

if (bigArray[x][y] < 10) {

addLine = "__|_";

}

line += addLine;

}

trace(line);

}

// поиск максимального значения элементов нижнего множества матрицы

var bottomMax = bigArray[0][1];

for (x in 0...n) {

for (y in 0...n){

if (x > y){

bottomMax = max(bottomMax, bigArray[x][y]);

}

trace(bottomMax);

// поиск значений элементов верхнего множества матрицы, больших, чем максимальное

//значение элементов нижнего множества матрицы

for (x in 0...n) {

for (y in 0...n){

if (y >= x){

if (bigArray[x][y] > bottomMax){

totalSumm += bigArray[x][y];

}

// вывод результата

if (totalSumm == 0){

trace("В массиве нет элементов с таким свойством");

} else {

trace(totalSumm);

}

Ссылка на решение задачи.

Cсылка на условие задачи.

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

haxe

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

Tag Archives: массивы

A711a

Задача.

Ход решения:

Код:

e-olymp 138. Банкомат

Условие

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

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

Тесты

Код.

Решение.

А409