Задание 12. ЕГЭ (Инф.)

# УСЛОВИЕ: На ленте записано двоичное число 800. Пустые ячейки — «λ» (пробел).
# Начало: каретка в ближайшей ПРАВОЙ пустой ячейке.
# ТАБЛИЦА:
#      |    λ     |    0     |    1     |
# ----------------------------------------
#  q0  | λ, L, q1 |          |          |
#  q1  | λ, R, q2 | 0, L, q1 | 1, L, q1 |
#  q2  |          | 0, R, q2 | 1, R, q3 |
#  q3  | λ, R, q4 | 0, R, q3 | 0, R, q4 |
#  q4  | λ, S, q4 | 0, R, q4 | 1, R, q4 |

b = bin(800)[2:]
t = dict(enumerate(b))  # Лента
s, i = 0, len(b)  # Старт справа (для старта слева i = -1)

# Состояния: q0..q4 -> 0..4 | L=-1, R=1, S=0 | Остановка = -1
p = {
    (0, ' '): (' ', -1, 1),
    (1, ' '): (' ', 1, 2), (1, '0'): ('0', -1, 1), (1, '1'): ('1', -1, 1),
    (2, '0'): ('0', 1, 2), (2, '1'): ('1', 1, 3),
    (3, ' '): (' ', 1, 4), (3, '0'): ('0', 1, 3), (3, '1'): ('0', 1, 4),
    (4, ' '): (' ', 0, -1), (4, '0'): ('0', 1, 4), (4, '1'): ('1', 1, 4)
}

while s != -1:
    t[i], d, s = p[(s, t.get(i, ' '))]
    i += d

print(int(''.join(map(t.get, sorted(t))).replace(' ', ''), 2))

# УСЛОВИЕ (Пример 1): 1000 нулей и 1000 единиц. Каретка справа.
# Найти МАКСИМАЛЬНО возможное число нулей в конце.
# ТАБЛИЦА:
#      |    λ     |    1     |    0     |
# ----------------------------------------
#  q0  | λ, L, q1 |          |          |
#  q1  | λ, S, q1 | 0, S, q1 | 1, L, q1 |

# Для макс. результата в этой задаче выгодно, чтобы 1 стояла в самом конце
b = '0' * 1000+ '1' * 1000
t = dict(enumerate(b))
s, i = 0, len(b)  # Старт справа

# Состояния: q0=0, q1=1 | L=-1, R=1, S=0 | Остановка = -1
p = {
    (0, ' '): (' ', -1, 1),
    (1, ' '): (' ', 0, -1),
    (1, '0'): ('1', -1, 1),
    (1, '1'): ('0', 0, -1)
}

while s != -1:
    t[i], d, s = p[(s, t.get(i, ' '))]
    i += d

# Считаем количество нулей на всей ленте
print(''.join(map(t.get, sorted(t))).replace(' ', '').count('0'))

# УСЛОВИЕ (Демо 2026): Длина 1000 символов. Старт СПРАВА. 
# Итог: ровно 343 нуля. Найти МАКСИММУМ нулей в исходной строке.
#
# ТАБЛИЦА:
#      |    λ     |    0     |    1     |
# ----------------------------------------
#  q0  | λ, L, q1 |          |          |
#  q1  | λ, S, q1 | 1, L, q1 | 0, S, q1 |


# Подбираем строку вручную (например: 342 нуля, одна 1, 657 нулей = 1000 символов)
b = '0' * 500 + '1' +'0'*499


t = dict(enumerate(b)) 
s, i = 0, len(b) # len(b) - Старт справа; -1 - Cтарт слева


# Состояния: q0=0, q1=1 | L=-1, R=1, S=0 | Остановка = -1
p = {
    (0, ' '): (' ', -1, 1),
    (1, ' '): (' ', 0, -1),
    (1, '0'): ('1', -1, 1),  # 0 -> 1, L, q1
    (1, '1'): ('0', 0, -1)   # 1 -> 0, S, q1
}


while s != -1:
    t[i], d, s = p[(s, t.get(i, ' '))]
    i += d
    
print("Было нулей в начале:", b.count('0'))
print(''.join(map(t.get, sorted(t))).replace(' ', '').count('0'))
"""
УСЛОВИЕ:
На ленте в соседних ячейках записано двоичное представление числа 2026 без ведущих нулей. 
Ячейки справа и слева от последовательности заполнены пустыми символами «λ». 
В начальный момент времени головка расположена в ближайшей ячейке слева от последовательности.


Программа работы исполнителя:
     |    λ     |    0     |    1     |
----------------------------------------
  q0 | λ, R, q1 |          |          |
  q1 | 0, R, q2 | 0, R, q1 | 1, R, q1 |
  q2 | 0, R, q3 |          |          |
  q3 | λ, S, q3 |          |          |


Определите результат работы программы. В ответе запишите получившееся на ленте число в десятичной системе счисления.
"""
b = bin(2026)[2:]
t = dict(enumerate(b))
s, i = 0, -1  # Старт в ближайшей ячейке слева


# Состояния: q0..q3 -> 0..3 | L=-1, R=1, S=0 | Остановка = -1
p = {
    (0, ' '): (' ', 1, 1),
    (1, '0'): ('0', 1, 1),
    (1, '1'): ('1', 1, 1),
    (1, ' '): ('0', 1, 2),
    (2, ' '): ('0', 1, 3),
    (3, ' '): (' ', 0, -1)
}


while s != -1:
    t[i], d, s = p[(s, t.get(i, ' '))]
    i += d


print(int(''.join(map(t.get, sorted(t))).replace(' ', ''), 2))