Problem 265 przysporzył mi trochę trudności, najpierw myślałem, żeby przeiterować przez wszystkie możliwośći
potem pomyslalem ze wystarczy przejsc przez wszystkie liczby od 000001000…000 do 000001111111…11111 jednak taki program po pol godziniie przeszukal jakis 1% zadania;)
potem doszedlem do wniosku, ze zamiast sprawdzac wszystkie liczby mozna je wygenerowac i oto moje rozwiazanie:)
[code=ruby]#prosta funkcja sprowadzajaca liczby do postaci binarnej
def decimal_to_binar(x,significant_bits)
z = []
while x >= 1
z << x % 2
x /= 2
end
suffix = z.reverse.join("")
prefix = “0”*(significant_bits-suffix.length)
prefix + suffix
end
class String
#tutaj sprawdzamy, czy liczba nie ma powtarzajacego sie podciagu
def distinct?(n)
collected = []
s = self + self
for i in 0…31
sub = s[i…(i+(n-1))]
return false if collected.include?(sub)
collected << sub
end
return true
end
end
#generujamy podciagi od 00001 do 11111 (pomijamy 00000 bo jak troche pomyslec to zadanie od nas tego wymaga -> kazdy wygenerowany ciąg mozna tak przesunac zeby 00000 bylo z przodu)
collection = []
for i in 1…31
v = decimal_to_binar(i,5)
collection << {:v => v, :pre => v[0…3]}
end
#kazde slowo zacznie sie od 00000
root = “00000”
#jakas funkcja z netu po prostu sprowadza liczby binarne do decymalnych;)
def bin2dec(number)
ret_dec = 0;
number.split(//).each{|digit|
ret_dec = (Integer(digit) + ret_dec) * 2;
}
return ret_dec/2;
end
#klasa z implementacja algorytmu
class Collector
#kolekcja wygenerowanych ciągów
attr_accessor :collected
def initialize
@collected = []
end
#startujac od 00000 sprawdzamy co moze byc dalej.
# stad 00000 -> 000001
# 000001 -> 0000011 albo 0000010
# i tak dalej
def compute(bits,collection)
ends_with = bits[-4..-1]
if bits.length==32
@collected << bits
return
end
collection.each do |v|
if ends_with == v[:pre]
new_collection = collection.clone
new_collection.delete(v)
compute(bits+v[:v][4..4],new_collection)
end
end
return
end
end
c = Collector.new
c.compute(root,collection)
sum = 0
c.collected.each do |v|
# Collector nie zapewnia ze liczba jest distinct
if v.distinct?(5)
sum += bin2dec(v)
end
end
#wynik 
puts sum[/code]
czas trwania około sekundy