Foregone Solution
問題
解法
与えられた整数Nを2つの整数（A+B）に分割する。この時、AとBのどの桁にも4が含まれ無いように分割するという問題。
Nの各桁を順次見ていき、4の場合は2と2、それ以外は0と元の数、のようにAとBに割り振る。
なお、答えを出力する際に、先頭の0は削除する必要がある点に注意する。
実装
N=gets.to_i
N.times do |i|
n=gets.chomp.split("")
a=[]
b=[]
n.each do |v|
if v == '4'
a << '2'
b << '2'
else
a << '0'
b << v
end
end
printf("Case #%d: %s %s\n", i+1, a.join.gsub(/^0*/, ""), b.join)
end
You Can Go Your Own Way
問題
解法
NxNのマス目を北西から南東に移動する。移動は南（S）、東（E）の組み合わせのみで後戻りは無し。
テストケースで与えられた移動方法に対して、経路が重ならないような移動方法を1通り出力するという問題。
これは、与えられた移動方法（SとEの並び）に対して対象な移動方法（SならE、EならS）を作れば良いです。
例えば、SEEESSESならESSSEESE。
このようにすると、移動経路はマス目の北西から南東への対角線に対して対象な移動経路になるので、絶対に重なりません。
実装
T=gets.to_i
T.times do |i|
n=gets
s = []
gets.chomp.split("").each do |v|
s << (v == 'E' ? 'S' : 'E')
end
printf("Case #%d: %s\n", i+1, s.join)
end
Cryptopangrams
問題
解法
テストケースとして与えられる整数列は、元の文字列が対応する素数の積になっています。
例えばテストケースの整数列をEi、元の文字列の対応する素数をPiとすると、E0はP0xP1、E1はP1xP2です。
よって、E0とE1の最大公約数をとればP1が求まり、それでE0とE1を割ることでP0とP2も求めることが出来ます。
ここで注意点ですが、E0とE1が等しい場合、つまり、P0〜P2が同じ素数（＝文字）の場合はこの方法では求めることが出来ません。（これに気づかずに最初WAをくらいました。。。）
よって、整数列を前から見ていき、隣り合う整数が最初に異なる場所に上記の方法を適用し、そこから前方、後方を見ていくことで全ての素数を求めることが出来ます。
素数が全て求まったらソートして小さい方からアルファベットを割り当てていき、元の文字列に戻すことが出来ます。
実装
def gcd(a,b)
return a if b == 0
gcd(b,a%b)
end
T=gets.to_i
T.times do |i|
n,l=gets.chomp.split.map(&:to_i)
enc = gets.chomp.split.map(&:to_i)
pn=Hash.new(0)
dec = Array.new(l+1)
pos = 0
0.upto(l-2) do |j|
if enc[j] != enc[j+1]
dec[j+1] = gcd(enc[j],enc[j+1])
pn[dec[j+1]] += 1
pos=j+1
break
end
end
(pos-1).downto(0) do |j|
dec[j] = enc[j] / dec[j+1]
pn[dec[j]] += 1
end
(pos+1).upto(l) do |j|
dec[j] = enc[j-1] / dec[j-1]
pn[dec[j]] += 1
end
m = {}
pn.keys.sort.each_with_index do |v, i|
m[v] = ('A'.ord+i).chr
end
ans=[]
dec.each do |v|
ans << m[v]
end
printf("Case #%d: %s\n",i+1,ans.join)
end
Dat Bae
問題
解法
N台のコンピュータのうちB台が壊れている。N個のビット列を与えたとき、壊れたコンピュータのビットは返ってこない。F回までビット列を投げることが出来る場合に、何台目のコンピュータが壊れているかを特定する方法を考えるという問題。
TestSet1のF=10の場合は結構簡単。というのも、Nの最大値が1024(=2^10)なので、0〜1023までの数字を各コンピュータに割り当てて、1回目の問い合わせは1ビット目、2回目の問い合わせは2ビット目、・・・というように10ビット目まで投げてやる。その結果、返ってきた回答を繋げて10進数に戻してやった場合に、欠けている数字が壊れているコンピュータの位置になります。
TestSet2のF=5の場合は少し工夫が必要です。2^5=32なので、5回の問い合わせで作れるビット列は0〜31になります。例えば、N=1024の場合、0台目から順にサイクリックに0〜31を割り当てます。すると、0〜31、0〜31、・・・、0〜31が32回繰り返されることになります。問題の制約として、壊れているコンピュータは最大15台までなので、抜けている数字の位置によってどのコンピュータが壊れているか一意に特定することが出来ます。
より厳密にはBが最大31までであれば大丈夫だと思います。32以上になると、例えば連続する0〜31が抜けていた場合に何番目の0〜31が抜けているのかが特定できない、ということになります。
実装
T=gets.to_i
def solve
n,b,f=gets.chomp.split.map(&:to_i)
r = Array.new(n-b).map { Array.new }
f.times do |i|
q = []
j = 0
n.times do
t = j >> i
q << (t & 1)
j += 1
j = 0 if j == 16
end
puts q.join
STDOUT.flush
gets.chomp.split("").each_with_index do |v, i|
r[i] << v
end
end
i = 0
j = 0
ans = []
r.each do |v|
if i == v.reverse.join.to_i(2)
else
while(i != v.reverse.join.to_i(2))
ans << j
j += 1
i += 1
i = 0 if i == 16
end
end
i += 1
i = 0 if i == 16
j += 1
end
while(j != n)
ans << j
j += 1
end
puts ans.join(" ")
STDOUT.flush
gets.to_i
end
T.times do
solve
end
