eolymp
bolt
Try our new interface for solving problems
Məsələlər

Уравниватель битов

Уравниватель битов

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Даны две непустые строки S и T одинаковой длинны. S содержит символы '0', '1' и '?', в то время как T содержит только '0' и '1'. Вам следует преобразовать S в T за минимальное количество ходов. За каждый ход можно:

  1. изменить '0' в S на '1'

  2. изменить '?' в S на '0' или '1'

  3. поменять местами любые два символа в S

Например, пусть S = "01??00" и T = "001010". Можно преобразовать S в T за 3 хода:

  • Изначально S = "01??00"

  • Ход 1 – изменить S[2] на '1'. S станет "011?00"

  • Ход 2 – изменить S[3] на '0'. S станет "011000"

  • Ход 3 – поменять S[1] с S[4]. S станет "001010"

  • S теперь равно T

Giriş verilənləri

Первая строка содержит количество тестов t (t 200). Каждый тест состоит из двух строк. Первой является строка S, состоящая из '0', '1' и '?'. Второй является строка T, состоящая из '0' и '1'. Длины строк не превосходят 100.

Çıxış verilənləri

Для каждого теста вывести его номер и наименьшее количество ходов, необходимых для преобразования S в T. Если преобразование невозможно, вывести -1.

Nümunə

Giriş verilənləri #1
3
01??00
001010
01
10
110001
000000
Çıxış verilənləri #1
Case 1: 3
Case 2: 1
Case 3: -1
Mənbə 2012 ACM Southwestern European Regional Programming Contest (SWERC), Problem B