0

問題は次のとおりです。ある文字列の k 個の連結コピーとして表すことができる場合、文字列は k-string と呼ばれます。たとえば、「aabaabaabaab」という文字列は、同時に 1 弦、2 弦、4 弦ですが、3 弦、5 弦、6 弦などではありません。 . 明らかに、どの文字列も 1 文字列です。

小文字の英字と正の整数 k で構成される文字列 s が与えられます。あなたの仕事は、結果の文字列が k 文字列になるように、文字列 s の文字を並べ替えることです。

入力 最初の入力行には、整数 k (1 ≤ k ≤ 1000) が含まれます。2 行目には s が含まれており、s 内のすべての文字は小文字の英字です。文字列の長さ s は、不等式 1 ≤ |s| を満たします。≤ 1000、ここで |s| 文字列 s の長さです。

出力 文字列 s の文字を並べ替えて、結果が k-string になるようにします。結果を単一の出力行に出力します。複数の解決策がある場合は、それらのいずれかを印刷します。

解決策が存在しない場合は、"-1" (引用符なし) を出力します。

これが私のコードです：

k = gets.to_i
str = gets.chomp.split(//)
n = str.length/k
map = Hash.new(0)
map2 = Hash.new(0)
str.each { |i| map[i] += 1 }

x = str.uniq.permutation(n).map(&:join).each do |string|
  string.each_char { |c| map2[c] += k }
  if map2 == map
    puts string*k
    exit
  end
  map2 = Hash.new(0)
end

puts '-1'

私には、この解決策はうまくいくように思えますが、テストケースでは失敗します。誰でも理由を教えてもらえますか?

4

1 に答える 1

1

これが私の解決策です。

セグメントを 1 つ作成し、それを 1k回出力するだけです。文字が k 回 (またはその倍数) 出現しない場合は、早期に停止して -1 を出力します。

k = gets.to_i
str = gets.chomp.split(//)
counts = Hash.new(0)
str.each { |i| counts[i] += 1 }

out = ''
str.uniq.each do |c|
  if counts[c] % k != 0
    puts -1
    exit
  end
  out = out + c*(counts[c]/k)
end

puts out*k
于 2013-03-28T04:37:32.450 に答える