G - Gray Code
Time Limit: 20 Sec

Memory Limit: 256 MB

Topic linking

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=87643#problem/G

Description

Denis, Vanya and Fedya gathered at their first team training. Fedya told them that he knew the algorithm for constructing a  Gray code.
  1. Create a 2-bit list: {0, 1}.
  2. Reflect this list and concatenate it with the original list: {0, 1, 1, 0}.
  3. Prefix old entries with 0, and prefix new entries with 1: {00, 01, 11, 10}.
  4. Repeat steps 2 and 3 until the length of all elements is equal to n.

The number n is a length of a Gray code. For example, the code of length 3 is: {000, 001, 011, 010, 110, 111, 101, 100}.

Denis ran the Fedya's algorithm and obtained a binary number  x at position  k (positions are numbered starting from zero). Vanya wrote down the numbers  k and  x in binary system. This story happened many years ago and now you hold the paper sheet with these numbers in your hands. Unfortunately, some digits are unreadable now. Could you determine the values of these digits using the readable digits?

Input

The first line contains a number k written in the binary system. Unreadable digits are denoted with symbol “?”. The second line contains a number x in the same format. The lengths of these numbers are equal and don't exceed 10 5. The numbers may contain leading zeroes.

Output

If there is a unique way to restore the numbers k and x, output them, replacing the symbols “?” with “0” or “1”. If there are multiple ways to restore them, output “Ambiguity”. If Denis or Vanya certainly made a mistake in these numbers, output “Impossible”.

Sample Input

0?1
0?0

Sample Output

011
010

HINT

The question

The title gives a way to construct a sequence

And then I'll give you a k, Judgment No. k Is the number given x

Answer key

Find the rules , Pay attention to the flip = =

Code :

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <vector>
#include <stack>
#include <map>
#include <set>
#include <queue>
#include <iomanip>
#include <string>
#include <ctime>
#include <list>
#include <bitset>
typedef unsigned char byte;
#define pb push_back
#define input_fast std::ios::sync_with_stdio(false);std::cin.tie(0)
#define local freopen("in.txt","r",stdin)
#define pi acos(-1) const char * fail = "Impossible";
const char * more = "Ambiguity";
using namespace std;
const int maxn = 1e5 + ;
int dp[maxn][];
char s1[maxn] , s2[maxn]; int main(int argc,char *argv[])
{
scanf("%s%s",s1+,s2+);
int Length = strlen(s1+);
s1[] = '';
for(int i = Length ; i > ; -- i)
{
if (s2[i] == '')
{
// Same number
if (s1[i] == '' && s1[i-] == '') continue;
if (s1[i] == '' && s1[i-] == '')
{
printf("%s\n",fail);
return ;
}
if(s1[i] == '' && s1[i-] == '?')
{
s1[i-] = '';
continue;
}
if (s1[i] == '' && s1[i-] == '')
{
printf("%s\n",fail);
return ;
}
if (s1[i] == '' && s1[i-] == '') continue;
if (s1[i] == '' && s1[i-] == '?')
{
s1[i-] = '';
continue;
}
if (s1[i] == '?' && s1[i-] == '')
{
s1[i] = '';
continue;
}
if (s1[i] == '?' && s1[i-] == '')
{
s1[i] = '';
continue;
}
if (s1[i] == '?' && s1[i-] == '?') continue;
}
if (s2[i] == '')
{
// Different sign
if (s1[i] == '' && s1[i-] == '') continue;
if (s1[i] == '' && s1[i-] == '')
{
printf("%s\n",fail);
return ;
}
if(s1[i] == '' && s1[i-] == '?')
{
s1[i-] = '';
continue;
}
if (s1[i] == '' && s1[i-] == '') continue;
if (s1[i] == '' && s1[i-] == '')
{
printf("%s\n",fail);
return ;
}
if(s1[i] == '' && s1[i-] == '?')
{
s1[i-] = '';
continue;
}
if(s1[i] == '?' && s1[i-] == '')
{
s1[i] = '';
continue;
}
if(s1[i] == '?' && s1[i-] == '')
{
s1[i] = '';
continue;
}
if(s1[i] == '?' && s1[i-] == '?') continue;
}
}
for(int i=;i<=Length;i++)
if(s1[i]=='?')
{
if(s2[i]!='?')
{
if(s2[i]=='') s1[i]=s1[i-];else s1[i]=''+-(s1[i-]-'');
continue;
}
printf("%s\n",more);
return ;
}
for(int i=;i<Length;i++)
if(s1[i]!=s1[i+])
{
s2[i+]='';
}
else s2[i+]='';
printf("%s\n%s\n",s1+,s2+);
return ;
}

URAL 1780 G - Gray Code Find more articles about the rules

  1. BZOJ 1228 E&amp;G(sg function + Looking for a regular )

    Take a pair of stones and see a sub game . Play a sub game sg Looking for the law in the table .. I can't find this rule ... about i,j, If (i-1)%pow(2,k+1) < pow(2,k) (j-1)%pow(2,k+ ...

  2. Niuke Xiaobai moon race G Exclusive or Looking for a regular

    link :https://www.nowcoder.com/acm/contest/135/G source : Cattle from Title Description Once upon a time ,Apojacsleam In the aquarium at home , Raised a bunch of tropical fish . In these tropical fish ,Apoj ...

  3. POJ 1850 Code( Looking for a regular )

    Code Time Limit: 1000MS   Memory Limit: 30000K Total Submissions: 7913   Accepted: 3709 Description ...

  4. 2018 Nanjing regional competition G topic Pyramid—— Looking for a regular &amp;&amp; Recurrence

    Before you manually push out 10 term , And then on BM The board works out the recurrence formula $A_n = 5A_{n-1} - 10A_{n-2} + 10A_{n-3} - 5A_{n-4} + A_{n-5}$, According to the characteristic root theory, the characteristic equation can be obtained $ ...

  5. Ural 1780 Gray Code Violence

    Original link :http://acm.timus.ru/problem.aspx?space=1&num=1780 1780. Gray Code Time limit: 0.5 secondMem ...

  6. Niuke Xiaobai moon race 5 G Exclusive or (xor) 【 Looking for a regular 】

    Topic link : https://www.nowcoder.com/acm/contest/135/g Title Description Once upon a time ,Apojacsleam In the aquarium at home , Raised a bunch of tropical fish . In these tropical fish ,Apojacs ...

  7. ACM-ICPC 2018 Jiaozuo competition area network preliminary competition G. Give Candies ( Beat the watch to find the rules + Fast power )

    Topic link :https://nanti.jisuanke.com/t/31716 The main idea of the topic : Yes n A child and n A candy , Now let n A line of children , Send candy one by one , Each child randomly selects x Give him a candy ,x>=1, straight ...

  8. Ural 2045. Richness of words Beat the watch to find the rules

    2045. Richness of words Topic linking : http://acm.timus.ru/problem.aspx?space=1&num=2045 Description For ...

  9. Ural 2037. Richness of binary words Beat the watch to find the rules structure

    2037. Richness of binary words Topic linking : http://acm.timus.ru/problem.aspx?space=1&num=2037 Descripti ...

Random recommendation

  1. Aliju security is invited to attend SFDC Safety assembly , Share Internet business problems and security innovation practices

    Today, , Technology led business change has seamlessly penetrated into our daily life ,「 Technology changes life 」 We're pushing our developers to the top of the innovation wave . Well known developer technology community in China SegmentFault It has been more than four years , Since the technical Q & A , They have developed ...

  2. SQL Pass Beijing held the second 10 Offline activities , Welcome to sign up

    Activity theme : Explore replication in the real world ( Season two ) And Windows Azure SQL Database insider place : Beijing Microsoft ( China ) Co., LTD. [ Wangjing lixingxing ], Three layers 308 room Time :2013 year 9 month 28 Japan 13: ...

  3. Can't create SSL Connect

    In the use of wget In the process of using tools , When URL Use HTTPS When the agreement , The following errors are common :“ Can't create SSL Connect ”. This is because wget In the use of HTTPS When the agreement , By default, the certificate of the website will be verified , And this certificate verification often fails . add &q ...

  4. TextView------ Put a line at the bottom or in the middle of the text

    promotionLinkText = (TextView) this .findViewById(R.id. text_promotion_link ); Add a line in the middle promotionLinkTe ...

  5. [ original ]Devexpress XtraReports series 8 establish Drill-Through report form

    Ah , The company has been busy all day today , There has been no time to write . So I had to work overtime last night . It's hard ...... It was published yesterday Devexpress XtraReports Chapter seven of the series [ original ]Devexpress XtraRe ...

  6. C51 The programming specification of

    Now the programming of single chip microcomputer ,C51 It has been widely promoted and applied , It is the mainstream design program of MCU , It can even be said that as a microcontroller developers must master a language . As a tool , The ultimate goal is to achieve the function . Under the premise that , We hope ...

  7. Java And HashMap.values() Method misuse

    1. error Today, when testing the code, I found that the program reported an error , Only by looking at the code can we know that it is to use HashMap.values() There was an error in the method . Because the project needs to get Map And then iterate through it , So it's natural to call HashMap.val ...

  8. How to make celery Accept customized parameters

    Background introduction A recent project uses celery Settle orders , Use celery It's really convenient . But the complex internal framework leads to the need to transfer a large number of parameters, such as database configuration files, etc . Now let's take a look at the code I copied from the official website . All the code goes to githu ...

  9. Task scheduling tool :Celery

    http://www.liaoxuefeng.com/article/00137760323922531a8582c08814fb09e9930cede45e3cc000 Celery yes Python open ...

  10. Spring boot Integrate Mybatis

    How does it feel to write a blog after two months , Only use “ Great ” To describe the . Gossip , Go straight to the point , It was said in previous blogs that , take spring And mybatis The whole post development will be better , Based on now springboot It has become the developer of the whole industry ...