Задачи очного тура личного первенства

Расположите на игровом поле размером 10x10 клеток набор из 10 кораблей (1 флагман длиной 4 клетки, 2 корабля длиной 3, 3 корабля длиной 2 и 4 катера длиной 1). Некоторые клетки поля уже открыты. Цифры сбоку и снизу игрового поля показывает количество фрагментов кораблей, которое попало в эту строку или столбец. Корабли не могут касаться друг друга даже углами.

Ввод содержит 11 строк, в первых 10 строках содержится 10 символов и цифра от '0' до '8', в последней – 10 цифр от '0'до '8'. Первые 10 символов первых 10 строк содержат информацию об открытых клетках. Символ '.' означает клетку, о которой нет информации, символ '~' – клетку с водой, символ 'O' – клетку с катером, символ '#' – средний фрагмент большого корабля, символы '<', '>', 'v' и '^' – крайние фрагменты больших кораблей. Гарантируется, что для головоломки существует решение.

Выведите 10 строк по 10 символов, содержащие решение головоломки, используя аналогичные обозначения.

..........0
..........1
....v.....1
.......~..4
..........3
..........3
..........4
O.........1
..........1
..........2
4030421204

~~~~~~~~~~
~~~~^~~~~~
~~~~v~~~~~
^~^~~~O~~^
#~#~~~~~~#
v~v~~~~~~#
~~~~<>~O~v
O~~~~~~~~~
~~~~~~~O~~
~~~~<>~~~~