Ordering: insert, bubble; school tasks: Varienty union, Hair sell

Algo_training

def sum n
	return 1 if n == 1
	return n + sum(n - 1) 
end

def sort_buble arr
	arr.length.times do |n|
		(0..n).each do |x|
			if arr[x] > arr[n]
				arr[n], arr[x] = arr[x], arr[n]
			end
		end
	end
end

def sort_insert arr, revert=false
	arr.length.times do |n|
		(n..(arr.length - 1)).each do |k|
			order = revert ? arr[k] > arr[n] : arr[k] < arr[n]
			if order
				arr[k], arr[n] = arr[k], arr[n]
			end  
		end
	end
end

def quick_sort(arr, l, r)
	x = arr[(l+r) >> 1]
	i = l
	j = r
	while i <= j
		while arr[i] < x do i += 1; end
		while arr[j] > x do j -= 1; end
		if i <= j
			arr[i], arr[j] = arr[j], arr[i]
			i += 1
			j -= 1
		end
	end
	quick_sort(arr, l, j) if j > l
	quick_sort(arr, i, r) if r > i
end

def fact n
	return 1 if n == 1
	return n * fact(n - 1)
end


# Пересечение множеств
# (Время: 1 сек. Память: 16 Мб Сложность: 34%)
# Даны два неупорядоченных набора целых чисел (может быть, с повторениями). Выдать без повторений в порядке возрастания все те числа, которые встречаются в обоих наборах.
# Входные данные
# В первой строке входного файла INPUT.TXT записано через пробел два целых числа N и М (1 ≤ N, М ≤ 106) — количество элементов первого и второго наборов, соответственно. В следующих строках записано сначала N чисел первого набора, а затем M чисел второго набора. Числа разделены пробелами или символами конца строки. Каждое из этих чисел попадает в промежуток от 0 до 105.
# Выходные данные
# В выходной файл OUTPUT.TXT нужно записать в возрастающем порядке без повторений все числа, которые входят как в первый, так и во второй набор. Числа разделять одним пробелом. Если таких чисел нет, то выходной файл должен оставаться пустым.

#Входные данные, пример:
# 2 4 6 8 10 12 10 8 6 4 2
# 3 6 9 12 15 18
# ВЫход:
# 6 12
def varienty_union
	data = File.open('input.txt', 'r').readlines
	variety1 = data[1].split(' ')
	variety2 = data.last.split(' ')
	a = Array.new(10**5, 0)
	result = []
	
	variety1.each do |n|
		a[n.to_i] = 1	
	end

	variety2.each do |k|
		a[k.to_i] = 2 if a[k.to_i] == 1
	end

	a.length.times do |n|
		result.push(n) if a[n] == 2
	end
	result
end

# Одного неформала выгнали с работы, и теперь ему надо как-то зарабатывать себе на пиво и сигареты. Поразмыслив, он решил, что сможет иметь очень неплохие деньги на продаже собственных волос. Известно, что пункты приема покупают волосы произвольной длины стоимостью С у.е. за каждый сантиметр. Так как волосяной рынок является очень динамичным, то цена одного сантиметра волос меняется каждый день как и курс валют. Неформал является очень хорошим бизнес-аналитиком. Он смог вычислить, какой будет цена одного сантиметра волос в каждый из ближайших N дней (для удобства пронумеруем дни в хронологическом порядке от 0 до N-1). Теперь он хочет определить, в какие из этих дней ему следует продавать волосы, чтобы по истечению всех N дней заработать максимальное количество денег. Заметим, что волосы у неформала растут только ночью и вырастают на 1 сантиметр за ночь. Следует также учесть, что до 0-го дня неформал с горя подстригся наголо и к 0-му дню длина его волос составляла 1 сантиметр.
# Входные данные
# В первой строке входного файла INPUT.TXT записано целое число N (0 < N ≤ 100). Во второй строке через пробел заданы N натуральных чисел, не превосходящих 100, соответствующие стоимости C[i] 1 сантиметра волос за каждый i-й день.
# Выходные данные
# В единственную строку выходного файла OUTPUT.TXT нужно вывести максимальную денежную сумму, которую может заработать неформал за N дней.

# Входные данн пример:
# 1)	5	
# 	73 31 96 24 46
# 2)	10
# 	1 2 3 4 5 6 7 8 9 10
# 3)	10
# 	10 9 8 7 6 5 4 3 2 1
# Выходные:
# 1)	380
# 2) 	100
# 3) 	55
def hair_problem
	prices = File.open('input.txt', 'r').readlines.last.split(' ')	
	prices = prices.map(&:to_i)
	result = 0
	max_day = 0
	cut_day = 0
	while cut_day != prices.length
		max_price_ind = 0
		max_price = 0
		(cut_day..prices.length-1).each do |i|
			if prices[i] > max_price
				max_price = prices[i]
				max_price_ind = i
			end
		end
		result += max_price * (max_price_ind-(cut_day-1))
		cut_day = max_price_ind + 1
	end
	result
end


#Сортировка времени по текстовым данным из файла
def time_sort 
	data = open('input.txt').readlines.map {|n| n.split(' ').map(&:to_i) }
	hours = Array(0..23)
	minuts = Array(0..60)
	result = []
	hours.each do |hour|
		current = []
		data.each do |arr|
			current.push arr if arr[0] == hour
		end
		current_1 = []
		minuts.each do |minut|
			current.each do |arr|
				current_1.push arr if arr[1] == minut
			end
		end
		current_2 = []
		minuts.each do |second|
			current_1.each do |arr|
				current_2.push arr if arr[1] == second
			end
		end

		result.push current_2 if current_2.count > 0
	end
	result
end

def real_time_sort
	require 'time'
	data = open('input.txt').readlines.map {|n| n.split(' ').map(&:to_i) }
	seconds_array = data.map { |n| n[0]*60*60 + n[1]*60 + n[2] }
	quick_sort(seconds_array, 0, seconds_array.length-1)
	seconds_array.map { |n| Time.at(n).gmtime.strftime('%R:%S')  }
end



# Свадьба
# (Время: 1 сек. Память: 16 Мб Сложность: 32%)
# Одна предприимчивая и очень симпатичная дамочка с прелестнейшим именем Горгона решила заработать себе денег на роскошную жизнь. N молодых людей так влюблены в нее, что предложили руку и сердце. К несчастью для них, Горгона видит в них только мешок с деньгами. Она планирует выйти замуж и почти сразу же развестись с некоторыми из молодых людей ради денежной выгоды. Все, что ей нужно, это подзаработать как можно больше денег (и уж, конечно, остаться незамужней). По законам этой прекрасной страны при разводе каждый из супругов получает половину всего имущества.
# Вы планируете опубликовать статью, в которой опишете всю подлость и меркантильность этой особы. Для того чтобы статья получилась особенно красочной, нужно указать максимальную сумму денег, которую сможет получить Горгона.
# Входные данные
# В первой строке входного файла INPUT.TXT записано целое число N — количество молодых людей, без памяти влюбленных в Горгону (1 < N <= 40). Далее следует N чисел — сумма денег на счету каждого молодого человека. В последней строке записано целое число А — сумма денег на счету Горгоны. Суммы денег на счету — целые неотрицательные числа, не превосходящие 109.
# Выходные данные
# В выходной файл OUTPUT.TXT выведите единственное число — максимальную сумму денег, которой сможет обладать Горгона после своей махинации. Ответ выводите с точностью до шести знаков ровно в формате без мантиссы.
# Примеры
# №	INPUT.TXT	OUTPUT.TXT
# 2
# 5 10
# 5				7.500000

# 3
# 1 3 2
# 0				2.125000

def wedding
	data = open('input.txt').readlines.map {|n| n.split(' ').map(&:to_f) }
	money_mans = data.first
	money_bride = data.last.first
	sort_insert( money_mans )
	money_mans.each do |mon|
		money_bride = (mon + money_bride)/2
	end
	money_bride
end

# В этой задаче нужно отсортировать целочисленный массив, но сложность ее в том, что массив может содержать 
# очень большое количество элементов (до миллиона). Решить данную задачу возможно с использованием стандартного
# алгоритма быстрой сортировки, но несмотря на это существует более эффективное решение, основанное на использовании 
# так называемой сортировки подсчетом (CountSort).
# Дело в том, что диапазон возможных значений элементов массива ограничен и поэтому вовсе не обязательно хранить
# весь массив в памяти, достаточно считывая его поэлементно вычислять для каждого возможного элемента x количество
# таких элементов в массиве. Для этого определяется некоторый массив d[x], в котором каждый элемент - это счетчик
# количества элементов исходного массива a[i], т.е в итоге в d[x] мы предполагаем получить количество элементов 
# массива a[i], которые равны x. Достичь этого можно следующим образом: при чтении очередного элемента a[i] увеличивать
# значение d[a[i]] на единицу. По завершении этого процесса достаточно вывести d[x] раз в порядке увеличения x 
# (по всему возможному диапазону) значение x. Данный алгоритм имеет порядок сложности O(N).
def count_sort
	data = open('input.txt').read.map {|n| n.split(' ').map(&:to_i) }.first
	dublicates_count = {}
	(-100..100).each do |n|
		dublicates_count[n] = 0
	end	
	data.each do |n|
		dublicates_count[n] += 1
	end
	result = ''
	(-100..100).each do |n|
		result.concat("#{n} "* dublicates_count[n])
	end
	result
end


def elections
	data = open('input.txt').read.split(' ').map(&:to_i)
	sort_insert( data )
	result = 0
	(0..data.length >> 1).each do |i|
		result += (data[i] >> 1) + 1
	end
	result
end

# Вычислить значение суммы
# S = 1/1! + 1/2! + ... + 1/k!
def fact_sum n
	return 1.00 if n == 1.00
	return 1.00/fact(n) + fact_sum(n-1.00)
end

def ariphmetic_progress
	data = [ 80, 50, 10, 30, 70, 40, 20, 60, 90 ]
	sort_insert(data)
	step = data[1] - data.first 
	prev = data.first
	ariphmetic = true
	data[1..data.length-1].each do |n|
		ariphmetic = false if n - prev != step
		prev = n
	end
	ariphmetic ? "Yes" : "No"
end

def year_balance
	data = [18, 10]
	profit = data.first.to_s.split('').map(&:to_i)
	manus = data.last.to_s.split('').map(&:to_i)
	sort_insert profit, true
	sort_insert manus
	manus.push(0) if manus.first == 0
	profit.join('').to_i  - manus.join('').to_i 
end


def pritty_square
	data = open("input.txt", 'r').readlines
	
	matrices = []
		current = [] 
	data.shift.first.to_i.times do |n|
		p current
			current = []
		data.shift.first.split(' ').first.to_i.times do |i|
			current.push(data.shift.split(' '))
		end
		matrices.push(current)
	end
	result = []
	matrices.each do |matrix|
		result.push(true)
		matrix.length.times do |row|
			matrix[row].length.times do |column|
				if !matrix[row][column-1].nil? && matrix[row][column-1] == matrix[row][column]
					if !matrix[row+1].nil? && matrix[row+1][column] == matrix[row+1][column-1]
						result.pop
						result.push(false)
						break
					end
				end
			end
			unless result.last
				break
			end
		end
	end
	result.each {|n| if n then p "YES" else p "NO" end }
end
pritty_square()