ENG  RUSTimus Online Judge
Online Judge
Online contests
About Online Judge
Frequently asked questions
Site news
Problem set
Submit solution
Judge status
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests

Ural SU Team.GOV contest. Petrozavodsk training camp. Summer 2011

About     Problems     Submit solution     Judge status     Standings
Contest is over

A. GOV-internship

Time limit: 1.0 second
Memory limit: 64 MB
Hello Denis,

Your internship in Team.GOV is over. Unfortunately, we cannot make you a full-time offer. Don't be upset, because you are neither the first nor the last one. It was a great pleasure to work with you. We wish you best of luck.

Regards, Vadim Kantorov, the captain of Team.GOV

A freezing November night in the year of 2010. The dormitory of Department of Mathematics and Mechanics of Ural State University. Dim monitor light. That's how Den Mukhametianov (the 8th team member in succession) left Team.GOV.
At the beginning of September Den returned from hot summer vacations. He was calmly browsing the photos from a trip when he got an email “You are invited to an interview with Team.GOV”. A year before Den could only dream of this.
The picture emerges in the mind as if it all had been yesterday. It was a small cozy room, Vadik settled comfortably in a rocking chair. Den coughed awkwardly and shitfed his feet. Vadik looked up and smiled. “What experience have you got?”
“Half a year in Ural SU AirBug and half a year in Ural SU Quickov.”
“Hm, not bad. What's your favorite topic?”
“String algorithms.”
“Well, then straight to the point then,” Vadik interrupted Den. “Let's pick a problem. Do you know what is Hamming distance between two strings of equal lengths?”
“Yes, it's the number of positions on which the characters of the strings are not equal.”
“Exactly! Let's define the distance from a pattern p to a string s as the sum of Hamming distances from p to all substrings of s of length |p|. In the string and in the pattern some characters are erased. You need to recover the erased characters in such a way that the distance from p to s is minimal.”


The first line contains the string s, the second contains the pattern p. Both strings are not empty and their lengths don't exceed 1000. Strings are comprised of the following characters: “0”, “1” and “?”. Here, “?” stands for erased characters that you need to recover. Length of p doesn't exceed length of s.


The first line should contain the minimal distance from p to s after all erased characters are recovered. In the second and in the third line output s and p respectively where each character “?” is replaced with either “0” or “1”.


Problem Author: Mikhail Rubinchik
Problem Source: Ural SU Team.GOV Contest. Petrozavodsk Summer Session, August 2011
To submit the solution for this problem go to the Problem set: 1851. GOV-internship