e-olymp 128. Счастливые билеты

22.06.2017 by Алёна Ищук

Задача взята с сайта e-olymp.com.

Задача

Подсчитайте количество счастливых билетов, у которых сума первых трёх цифр равна [latex]N[/latex].

Счастливым билетом называется билет с шестизначным номером, у которого сумма первых трёх цифр равна сумме трёх последних.

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

В единственной строке задано натуральное число [latex] N (N ≤ 27). [/latex]

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

Единственное число — количество счастливых билетов.

Тесты

№	Входные данные (число [latex] N [/latex])	Выходные данные (число билетов)
1.	1	9
2.	27	1
3.	0	1
4.	10	3969
5.	3	100

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

class Test {
    static function main() {
       	var N = 10;
        var c = 0;
        for ( i in 0...10 ) { 	 // цикл, перебирает все варианты первой цифры трехзначного числа
            for ( j in 0...10 ) {  // внутренний цикл, перебирает все варианты второй цифры
                if ( N - i - j >= 0 && N - i - j < 10 ) {  //условие для третьей цифры
                    c++;  //подсчет подходящих номеров
                }
            }
        }
    	trace(c * c); //увеличение количества в c раз для шестизначного числа
    }
}

class Test {

static function main() {

var N = 10;

var c = 0;

for ( i in 0...10 ) { // цикл, перебирает все варианты первой цифры трехзначного числа

for ( j in 0...10 ) { // внутренний цикл, перебирает все варианты второй цифры

if ( N - i - j >= 0 && N - i - j < 10 ) { //условие для третьей цифры

c++; //подсчет подходящих номеров

}

trace(c * c); //увеличение количества в c раз для шестизначного числа

}

Решение
Любой шестизначный номер можно представить как 2 трехзначных номера.

Для решения задачи рассмотрим все варианты трехзначных номеров. Две первые цифры такого номера могут быть любыми. Переберем все их комбинации с помощью двух циклов. А для определения третьей цифры будем использовать специальное условие. Она должна быть результатом вычитания двух первых цифр из [latex]N[/latex], и быть именно цифрой, то есть меньше 10.

Когда в цикле встречается подходящая комбинация, счетчик [latex]c[/latex] увеличивается на 1. Так как номер шестизначный, а счетчик [latex]c[/latex] подсчитывает удачные комбинации для трехзначного числа первой части, то и для трехзначного числа второй части он будет соответствовать. Следовательно, окончательное число комбинаций будет равно [latex]c \cdot c[/latex].

Оригинальное решение: cpp.mazurok.com.
Рабочий код для тестирования на try.haxe.org: Try Haxe !

e-olymp 974. Флойд-1

13.06.2017 by Сергей Завада

Ссылка на оригинальную статью.

Условие:

Полный ориентированный взвешенный граф задан матрицей смежности. Постройте матрицу кратчайших путей между его вершинами. Гарантируется, что в графе нет циклов отрицательного веса.

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

В первой строке записано количество вершин графа [latex]n (1 ≤ n ≤ 100)[/latex]. В следующих [latex]n[/latex] строках записано по [latex]n[/latex] чисел — матрица смежности графа ([latex]j[/latex]-ое число в [latex]i[/latex]-ой строке соответствует весу ребра из вершины [latex]i[/latex] в вершину [latex]j[/latex]). Все числа по модулю не превышают [latex]100[/latex]. На главной диагонали матрицы — всегда нули.

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

Выведите [latex]n[/latex] строк по [latex]n[/latex] чисел — матрицу кратчайших расстояний между парами вершин. [latex]j[/latex]-ое число в [latex]i[/latex]-ой строке должно равняться весу кратчайшего пути из вершины [latex]i[/latex] в вершину [latex]j[/latex].

Решение:

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

Тесты:

Input

Output

4
0 5 9 100
100 0 2 8
100 100 0 7
4 100 100 0

0 5 7 13

12 0 2 8

11 16 0 7

4 9 11 0

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

import neko.Lib;
/**
 * ...
 * @author Zavada Sergey
 */
class Main 
{
	static function main() 
	{
		var n:Int = Std.parseInt(Sys.stdin().readLine());
		var w:Array<Array<Float>> = [for (x in 0...n) [for (y in 0...n) 0]];
		for (i in 0...n)
		{
			for (j in 0...n)
			{
				w[i][j] = Std.parseFloat(Sys.stdin().readLine());
			}
		}
		for (k in 0...n)
		{
			for (i in 0...n)
			{
				for (j in 0...n)
				{
					w[i][j] = Math.min(w[i][j], w[i][k]+w[k][j]);
				}
			}
		}
		var output = Sys.stdout();
		for (i in 0...n)
		{
			for (y in 0...n)
			{
				output.writeString(Std.string(w[i][y]) + " ");
			}
			output.writeString("\n");
		}	
	}
}

import neko.Lib;

/**

* ...

* @author Zavada Sergey

class Main

{

static function main()

{

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

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

for (i in 0...n)

{

for (j in 0...n)

{

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

}

for (k in 0...n)

{

for (i in 0...n)

{

for (j in 0...n)

{

w[i][j] = Math.min(w[i][j], w[i][k]+w[k][j]);

}

var output = Sys.stdout();

for (i in 0...n)

{

for (y in 0...n)

{

output.writeString(Std.string(w[i][y]) + " ");

}

output.writeString("\n");

}

А412г

22.05.2017 by Лена Наумова

Ссылка на оригинальное решение

Задача:

Даны две целочисленные квадратные матрицы порядка $ 6 $. Найти последовательность из нулей и единиц $ b_1, \dots , b_6 $ такую, что $ b_i = 1 $, когда количество отрицательных и неотрицательных элементов $ i $-й строки первой матрицы совпадает соответственно с количеством отрицательных и неотрицательных элементов $ i $-й строки второй матрицы.

Тесты:

№	Матрица $ A $	Матрица $ B $	Выходные данные
1	1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1	1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1	1 1 1 1 1 1
2	1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1	-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1	0 0 0 0 0 0
3	1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 1 1 1 1 1 1 1 1 1 1 1 1 -1 -1 -1 -1 -1 -1 1 1 1 1 1 1	-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1	0 1 0 0 1 0
4	0 2 2 3 4 4 1 3 3 4 5 5 2 4 4 5 6 6 3 5 5 6 7 7 4 6 6 7 8 8 5 7 7 8 9 9	0 2 2 3 4 4 -1 3 1 4 3 5 -2 4 0 5 2 6 -3 5 -1 6 1 7 -4 6 -2 7 0 8 -5 7 -3 8 -1 9	1 0 0 0 0 0

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

class Test {
    static function main() {
        var A = 
        [
        	[0, 2, 2, 3, 4, 4],
			[1, 3, 3, 4, 5, 5],
			[2, 4, 4, 5, 6, 6],
			[3, 5, 5, 6, 7, 7],
			[4, 6, 6, 7, 8, 8],
			[5, 7, 7, 8, 9, 9]
        ];
        var B =
        [
        	[0, 2, 2, 3, 4, 4],
			[-1, 3, 1, 4, 3, 5],
			[-2, 4, 0, 5, 2, 6],	
			[-3, 5, -1, 6, 1, 7],
			[-4, 6, -2, 7, 0, 8],
			[-5, 7, -3, 8, -1, 9]
        ];
        
        var ans = [];
        
        for(i in 0 ... 6) {
            
            var a_positive = 0,
                b_positive = 0;
            
            for(j in 0 ... 6) {
                
                if(A[i][j] >= 0) {
                    a_positive += 1;
                }
                    
                if(B[i][j] >= 0) {
                    b_positive += 1;
                }
                    
            }
                
            if(a_positive == b_positive) {
                ans.push(1);
            }
            else {
                ans.push(0);
            }
        }
        trace(ans);
    }
}

class Test {

static function main() {

var A =

[

[0, 2, 2, 3, 4, 4],

[1, 3, 3, 4, 5, 5],

[2, 4, 4, 5, 6, 6],

[3, 5, 5, 6, 7, 7],

[4, 6, 6, 7, 8, 8],

[5, 7, 7, 8, 9, 9]

];

var B =

[

[0, 2, 2, 3, 4, 4],

[-1, 3, 1, 4, 3, 5],

[-2, 4, 0, 5, 2, 6],

[-3, 5, -1, 6, 1, 7],

[-4, 6, -2, 7, 0, 8],

[-5, 7, -3, 8, -1, 9]

];

var ans = [];

for(i in 0 ... 6) {

var a_positive = 0,

b_positive = 0;

for(j in 0 ... 6) {

if(A[i][j] >= 0) {

a_positive += 1;

}

if(B[i][j] >= 0) {

b_positive += 1;

}

if(a_positive == b_positive) {

ans.push(1);

}

else {

ans.push(0);

}

trace(ans);

}

Ссылка на tryhaxe

Решение:

Заведем массив ans , в который будем дописывать $ 1 $, если количество неотрицательных элементов матрицы $ A $ в текущей строке совпадает с количеством неотрицательных элементов матрицы $ B $ в текущей строке, и $ 0 $ в противном случае. Проверять совпадение количества отрицательных элементов отдельно не нужно, потому как строки в матрицах одинаковой длины, т. е. количество отрицательных элементов всегда равно $ 6 — $ (количество_неотрицательных).

В цикле по переменной i проходимся по каждой из шести строк матриц, каждый раз заводя счетчики на количество неотрицательных элементов. Цикл по j идет по столбцам матриц, проверяя каждый элемент. Если встретили неотрицательный элемент в матрице $ A $, увеличиваем счетик a_positive . Если неотрицательный элемент попался в $ B $, увеличиваем b_positive .

По истечении прохода по текущей строке проверяем, совпадает ли количество неотрицательных элементов в строке $ i $ для обеих матриц. Если да, дописываем в ответ единицу, иначе — ноль.

Ю 4.33

13.05.2017 by Анастасия Улановская

Решённую задачу на C++ можно просмотреть здесь

Задача
Для заданной матрицы [latex] A(m,n) [/latex] найти её норму: [latex] \left \| A \right \|_{1} = \max\limits_{i=1,m} \sum\limits_{k=1}^{n} \left | a_{ik} \right |[/latex].

Входные данные
$m$ и $n$ — размеры матрицы, $x$ — временная переменная для хранения следующего значения из входного потока

Выходные данные
$norm$ — норма матрицы

Тесты

Матрица	Построчные суммы	Вывод
[latex] \begin{pmatrix} 1 & -3 & 2 & 4 & 0 \\ -3 & -7.5 & 2.3 & -3.1 & 2.8 \\ 3.4 & -4.5 & 0 & 0 & 2 \\ 3.2 & 4.7 & 2.8 & -3.1 & -4.3 \end{pmatrix} [/latex]	[latex] \begin{matrix} 10 \\ 18.7 \\ 14.4 \\ 18.1 \end{matrix}[/latex]	18.7

Код

class Main 
{
	
	static function main() 
	{
		var m, n, norm:Float = 0;
		
		m = Std.parseInt(Sys.stdin().readLine());
		n = Std.parseInt(Sys.stdin().readLine());
		
		for (i in 0...m) 
		{
			var s:Float = 0;
			for (j in 0...n) 
			{
				var x:Float = Std.parseFloat(Sys.stdin().readLine());
				s += Math.abs(x);
			}
			
			if (s > norm)
			{
				norm = s;	
			}
		}
		
		Sys.stdout().writeString(Std.string(norm));
	}
}

class Main

{

static function main()

{

var m, n, norm:Float = 0;

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

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

for (i in 0...m)

{

var s:Float = 0;

for (j in 0...n)

{

var x:Float = Std.parseFloat(Sys.stdin().readLine());

s += Math.abs(x);

}

if (s > norm)

{

norm = s;

}

Sys.stdout().writeString(Std.string(norm));

}

Решение
Нам понадобятся два цикла: во внешнем будем искать максимум, пробегая по всем строкам матрицы; во внутреннем будем для фиксированной строки вычислять сумму абсолютных величин её элементов. Если эта сумма превосходит текущую максимальную, обновляем последнюю. Поскольку все наши суммы будут неотрицательными числами, изначально присвоим переменной max значение 0.

e-olymp 5072. Подсчет количества ребер

13.05.2017 by Денис Швецов

Задача

Ориентированный граф задан матрицей смежности.
Найдите количество ребер в графе.

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

Входной файл содержит число n (1 ≤ n ≤ 100) — число вершин в графе, и затем n строк по n чисел, каждое из которых равно 0 или 1 — его матрицу смежности.

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

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

Решение

30 1 11 0 1

0 1 1

50 1 1 1 11 0 0 0 0

1 0 0 0 0

0 0 1 0 1

1 0 0 0 0

21 11 1

class Test 
{
    static function main() 
    {
        // Считываем входные данные
    	var n:Int = Std.parseFloat(Sys.stdin().readline());
    	var k:Int = 0;
        var count:Int = 0;
        
        for(i in 1...n) 
        {
            for(j in 1...n) 
            {
            	k = Std.parseInt(Sys.stdin().readline());
            	if(k == 1)
            	    count++;
            }
        }
        
        trace(count);
    }
}

class Test

{

static function main()

{

// Считываем входные данные

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

var k:Int = 0;

var count:Int = 0;

for(i in 1...n)

{

for(j in 1...n)

{

k = Std.parseInt(Sys.stdin().readline());

if(k == 1)

count++;

}

trace(count);

}

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

Количество ребер ориентированного графа равно количеству единиц в его матрице смежности. Поэтому просто считываем, суммируем найденные 1-цы, и выводим ответ.

Выполнение кода на Try Haxe !
Решение задачи на С++.

e-olymp 1154. Кружок хорового пения

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

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

В некотором учебном заведении функционирует кружок хорового пения. Начало кружка всегда происходит единообразно: по сигналу руководителя кружка все [latex]N[/latex] участников становятся в круг и каждый [latex]M[/latex] -й для распевки поёт гамму.

Руководитель кружка заметил, что размять голосовые связки не всегда удаётся всем участникам кружка. По заданным [latex]M[/latex] и [latex]N[/latex] помогите ему определить, или в очередной раз в разминке примут участие все участники хора.

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

Входные данные состоят из нескольких тестовых случаев. Каждый тестовый случай расположен в отдельной строке и содержит два целых числа [latex]M[/latex] и [latex]N[/latex].

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

Для каждого тестового случая в отдельной строке выведите «Yes», если в разминке примут участие все участники хора, в противном случае выведите «No».

Тесты:

n	m	answer
4	1	Yes
6	3	No

Код:

class Main 
{
	
	static function main() 
	{
		var n, m, p;
		
		n = getNextInt();
		
		while ((m = getNextInt()) > 0) 
		{
			while ((p = n % m) != 0)
			{
				n = m;
				m = p;
			}
			
			var result = m == 1 ? "Yes" : "No";
			
			var output = Sys.stdout();
			output.writeString(result + "\n");
		}
	}
	
	static function getNextInt()
	{
		var number = Sys.stdin().readLine();
		return Std.parseInt(number);
	}
}

class Main

{

static function main()

{

var n, m, p;

n = getNextInt();

while ((m = getNextInt()) > 0)

{

while ((p = n % m) != 0)

{

n = m;

m = p;

}

var result = m == 1 ? "Yes" : "No";

var output = Sys.stdout();

output.writeString(result + "\n");

}

static function getNextInt()

{

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

return Std.parseInt(number);

}

Ход решения:

Для начала нам надо найти наибольший общий делитель (НОД). Для этого хорошо подойдет алгоритм Евклида и если НОД равен единице, то все ученики распоются и на выходе подаётся «Yes», иначе «No».

Ю3.45

09.04.2017 by Артур Тарасов

Условие

Ю3.45. Гуси и кролики. У гусей и кроликов вместе $2n$ лап. Сколько может быть гусей и кроликов (вывести все возможные сочетания)?

Тесты

n	Кроликов	Гусей	Комментарий
4	0, 2, 4	2, 1, 0	Тест пройден
3	1, 3	1, 0	Тест пройден
0	0	0	Тест пройден
7	1, 3, 5, 7	3, 2, 1, 0	Тест пройден

Код

class Test {
	static function main() {
		var g:Int=0; // гусей
		var k:Int=0; //кроликов
		var n:Int = 5; 
		while (k <= n/2) {
			g = (2*n-4*k) >> 1;
 			trace("Гусей - " + g + " Кроликов - " + k);
			k++;
		}
	}
}

class Test {

static function main() {

var g:Int=0; // гусей

var k:Int=0; //кроликов

var n:Int = 5;

while (k <= n/2) {

g = (2*n-4*k) >> 1;

trace("Гусей - " + g + " Кроликов - " + k);

k++;

}

Решение

По условию задачи необходимо вывести все возможные варианты сочетаний количества кроликов и гусей.

Для того, чтобы это сделать используется 1 цикл. В нем проверяется условие (количество кроликов не превышает [latex]\frac{n}{2}[/latex]) — количество кроликов не может превышать $n/2$. Изначально переменным $k$ и $g$ присваивается значение 0. В теле цикла считаем количество гусей по формуле $(2n — 4k)/2$.

Если условие выполнено успешно, то на экран выводится один из вариантов сочетаний. После чего цикл повторяется с заданным инкрементом и выводится следующий вариант сочетаний.

Ссылка на условие задания: cpp.mazurok.com
Try Haxe

A334(а). Вложенная сумма

31.03.2017 by Кирилл Автомонов

Ссылка на оригинальную статью.

Задача

Вычислить:[latex]\sum \limits_{i=1}^{m}\sum \limits_{j=1}^{n}\frac{1}{i+j^2}[/latex] где [latex]m,n[/latex] — вводимые нами числа.

Тесты

Вход([latex]m,n[/latex])	Выход([latex]S[/latex])
40 20	13.6458
100 50	24.6458
200 25	31.7764
1000 282	89.8078

Код

class Main 
{
	
	static function main() { 
    var S:Float;
	S = 0;
	var m:Int = Std.parseInt(Sys.stdin().readLine());
	var N:Int = Std.parseInt(Sys.stdin().readLine());
    for(i in 1...m) {
        for(j in 1...N) {
            S+=1.0/(i+j*j);
            
        }
		
    }
	trace(S);
   }
	
 }

class Main

{

static function main() {

var S:Float;

S = 0;

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

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

for(i in 1...m) {

for(j in 1...N) {

S+=1.0/(i+j*j);

}

trace(S);

}

Решение

Вводим два оператор цикла for, один вложенный в другой.
Задаем наше выражение, а затем суммируем его,
согласно циклу.

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

haxe

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

Tag Archives: Вложенные циклы

e-olymp 128. Счастливые билеты

e-olymp 974. Флойд-1

Условие:

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

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

Решение:

Тесты:

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

А412г

Ю 4.33

e-olymp 5072. Подсчет количества ребер

Задача

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

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

Решение

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

e-olymp 1154. Кружок хорового пения

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

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

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

Тесты:

Код:

Ход решения:

Ю3.45

Условие

Тесты

Код

Решение

A334(а). Вложенная сумма

Задача

Тесты

Код

Решение