1 second
256 megabytes
standard input
standard output
For each string s consisting of characters '0' and '1' one can define four integers a00, a01, a10 and a11, where axy is the number ofsubsequences of length 2 of the string s equal to the sequence {x, y}.
In these problem you are given four integers a00, a01, a10, a11 and have to find any non-empty string s that matches them, or determine that there is no such string. One can prove that if at least one answer exists, there exists an answer of length no more than1 000 000.
The only line of the input contains four non-negative integers a00, a01, a10 and a11. Each of them doesn't exceed 109.
If there exists a non-empty string that matches four integers from the input, print it in the only line of the output. Otherwise, print "Impossible". The length of your answer must not exceed 1 000 000.
1 2 3 4
Impossible
1 2 2 1
0110
思路：根据a[0]和a[3]，我们可以解出0，1的个数x1,x2，开始先按照前面全是0后面全是1来排列这个时候我们可以知道01的个数就是x1*x2,然后我们发现当0向右移位的时候，没超过一个1的时候01个数少1，10个数多1，那么我们知道，01和10的个数之和就是x1*x2,这样可以判断是否有解，然后就是到底咋移，因为可以一个一个增加，所以贪心，每次移一个，然后移动具体看代码；
1 #include<stdio.h>
2 #include<algorithm>
3 #include<iostream>
4 #include<string.h>
5 #include<stdlib.h>
6 #include<queue>
7 #include<set>
8 #include<math.h>
9 #include<vector>
10 using namespace std;
11 typedef long long LL;
12 LL a[5];
13 short int ans[1000005];
14 bool check(LL n);
15 int main(void)
16 {
17 while(scanf("%I64d",&a[0])!=EOF)
18 {
19 int i,j;
20 for(i = 1; i < 4; i++)
21 {
22 scanf("%I64d",&a[i]);
23 }
24 LL x1 = 1+8*a[0];
25 LL x2 = 1+8*a[3];
26 bool fla1 = check(x1);
27 bool fla2 = check(x2);
28 if(!fla1||!fla2)
29 {
30 //printf("1\n");
31 printf("Impossible\n");
32 }
33 else
34 {
35 if(a[0]==0&&a[1]==0&&a[2]==0&&a[3]==0)
36 {
37 printf("1\n");
38 }
39 else if(a[0]!=0&&a[1]==0&a[2]==0&&a[3]==0)
40 {
41 LL cnt = 1+sqrt(1+8*a[0]);
42 cnt/=2;
43 for(i = 0; i <cnt ; i++)
44 printf("0");
45 printf("\n");
46 }
47 else if(a[0]==0&&a[1]==0&&a[2]==0&&a[3]!=0)
48 {
49 LL cnt = sqrt(1+8*a[3])+1;
50 cnt/=2;
51 for(i = 0 ; i < cnt ; i++)
52 printf("1");
53 printf("\n");
54 }
55 else
56 {
57 x1 = 1 + sqrt(x1);
58 x1/=2;
59 x2 = 1 + sqrt(x2);
60 x2/=2;
61 fill(ans,ans+1000005,1);
62 LL sum1 = x1*x2;
63 LL sum2 = 0;
64 if(sum1 != a[1]+a[2])
65 printf("Impossible\n");
66 else
67 {
68 LL ac = a[2];
69 LL ak = ac/x2;
70 LL tt = ac%x2;
71 LL nn = x1 + x2;
72 if(tt) ak++;
73 for(i = 0; i < (x1-ak); i++)
74 {
75 printf("0");
76 }
77 if(tt == 0)
78 {
79 for(i = 0; i < x2 ; i++)
80 printf("1");
81 }
82 else
83 {
84 for(i = 0; i < x2 ; i++)
85 {
86 if(i == tt)
87 printf("0");
88 else printf("1");
89 }
90 printf("1");
91 }
92 if(tt)ak--;
93 for(i = 0 ; i < ak ; i++)
94 {
95 printf("0");
96 }
97 printf("\n");
98 }
99 }
100 }
101 }
102 return 0;
103 }
104 bool check(LL n)
105 {
106 LL ap = sqrt(1.0*n);
107 if(ap*ap == n)
108 return true;
109 return false ;
110 }