## 11598 - Optimal Segments

All about problems in Volume 115. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

ravael
New poster
Posts: 2
Joined: Wed Sep 02, 2009 8:24 pm

### 11598 - Optimal Segments

Hi, i am really curious about this problem. i manage to solve this using some kind of DP similar to partitioning problem but with additional upper-bounding rule. But still, i got WA from time to time. Is there something i am missing? or is there any crucial or tricky cases, or perhaps, "dirty" string input data?
Please help me , i have checked my solution using many many cases, but still i can't find any mistake.... maybe those who have solved this one can share their ideas? Thx before   sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### Re: 11598 - Optimal Segments

Try this case

Code: Select all

``````Input
30 5
16 X 25 X 2 9 22 X 19 10 15 X 1 11 11 X 16 3 9 10 12 13 25 3 4 21 X 24 X X

Output
Case 1: 17179869184 (16 X 25 X 2)(9 22 X 19)(10 15 X 1 11 11)(X 16 3 9 10 12 13)(25 3 4 21 X 24 X X)
``````

ravael
New poster
Posts: 2
Joined: Wed Sep 02, 2009 8:24 pm

### Re: 11598 - Optimal Segments

thx for the case. But my solution still produce the correct one. is there any special case or any tips?
btw here is my code :

Code: Select all

``````#include<cstdio>
#include<algorithm>
using namespace std;
#define INF -9999
char ch,*ptr;
int v,ok,pos,b,n,k,f,ts,i,j,p,kk,sum,id,r,jum,mini,lim,par,res,ans,mm,ar;
char s;
int go(int x,int y){
int ada,sum=0;
if(x==n && y==k){
ok=1;
return -INF;
}
if(x==n) return INF;
if(y==k) return INF;
if(v[x][y]!=-1) return v[x][y];
v[x][y]=INF;
ada=0;
for(int i=x;i<n;i++){
sum+=b[i];
if(sum>lim) break;
if(b[i]==0) ada=1;
if(ada){
if(go(i+1,y+1)==INF) continue;
int xx=min(sum,go(i+1,y+1));
if(v[x][y]<=xx){
v[x][y]=xx;
pos[x][y]=i;
}
}
}
if(ada) return v[x][y];
return INF;
}

bool gt(){
for(int i=0;i<kk;i++)
if(par[i+1]-par[i]>res[i+1]-res[i]) return true;
else if(par[i+1]-par[i]<res[i+1]-res[i]) return false;
return false;
}

int main(){
scanf("%d",&ts);
while(ts--){
scanf("%d %d",&n,&k);
scanf("%c",&ch);
gets(s);
while(strcmp(s,"")==0) gets(s);
ptr=strtok(s," ");
n=sum=0;
int total=0;
while(ptr!=NULL){
if(strcmp(ptr,"X")==0) b[n++]=0;
else b[n++]=atoi(ptr);
total+=b[n-1];
ptr=strtok(NULL," ");
}
memset(mm,0,sizeof(mm));
for(i=0;i<n;i++){
sum=b[i];
mm[sum]=1;
for(j=i+1;j<n;j++){
sum+=b[j];
mm[sum]=1;
}
}
int num=0;
for(i=0;i<=total;i++) if(mm[i]) ar[num++]=i;
r=-INF;
f=0;
//printf("sum %d\n",total);
for(int x=total;x>=0;x--){
ans=x;
//printf("%d\n",ans);
ok=0;
lim=ans;
memset(v,-1,sizeof(v));
mini=go(0,0);
//printf("hm %d\n",ans);
if(!ok) continue;
f=1;
if(r<ans-mini) continue;
p=0;
kk=0;
par=0;
while(p<n){
p=pos[p][kk]+1;
kk++;
par[kk]=p;
}
if(r>ans-mini || gt()){
//printf("%d %d %d\n",r,ans,go(0,0));
r=ans-mini;
for(i=0;i<=kk;i++) res[i]=par[i];
}
}
id++;
printf("Case %d: ",id);
if(!f){
printf("not possible!\n");
continue;
}
if(r>49) printf("overflow\n");
else{
printf("%lld ",(1LL<<(long long)r));
for(i=0;i<kk;i++){
for(j=res[i];j<res[i+1];j++){
if(j==res[i]) printf("(");
else printf(" ");
if(b[j]==0) printf("X");
else printf("%d",b[j]);
}
printf(")");
}
printf("\n");
}
}
}
``````
can someone please point out what's wrong with it thx again serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

### Re: 11598 - Optimal Segments

My algo is:
value is 0, if the i-th cell is special, otherwise it is given in the input;
sm = sm[i-1] + value, thus the weight of the segment [i,j] is calculated as follows: (1ULL << sm[j]-sm[i-1]);
pref = pref[i-1] + (is_special ? 1 : 0);
Now suppose (j,k) be such a state that we have optimally divided the first 1..j part into k segments,
DP: z[j][k].x = the sum of the values of the heaviest segment,
z[j][k].y = the sum of the values of the lightest segment;
So the optimal ratio is (1ULL << z[j][k].x-z[j][k].y);
Although n >= 2 and k >= 2, it does make sense to initialize z[j].x = z[j].y = sm[j],
so long as pref[j] >= 1.
To go on with our initialization, if pref[j] < k, then we mark the state (j,k) as "impossible",
otherwise we assign z[j][k].x = 63, z[j][k].y = 0 (overflow).
Now we do DP:

Code: Select all

``````for k =2 to K:
for j = k to n:
if pref[j] < k:
continue //impossible
for i = j downto k:
if state z[i-1][k-1] is impossible:
continue
w = sm[j]-sm[i-1]
p = max( w, z[i-1][k-1].x )
q = min( w, z[i-1][k-1].y )
if ( p-q < z[j][k].x-z[j][k].y ):
z[j][k].x = p
z[j][k].y = q
parent[j][k] = (i-1,k-1)
else if p-q == z[j][k].x-z[j][k].y:
u = getSolution(j,k)
v = getSolution(i-1,k-1), v.append(j-i+1)
if v is "better" than u:
parent[j][k] = (i-1,k-1)
``````
"better" means this: u and v are the sequences of lengths of the corresponding divisions,
u is "better" than v iff for some i u > v, and for all j < i u[j] == v[j]

My code is getting WA. What do you say?
If there is ever a war between men and machines, it is easy to guess who will start it (c) Arthur Clarke

red_apricot
New poster
Posts: 48
Joined: Sun Jun 22, 2014 6:14 am

### Re: 11598 - Optimal Segments

OK, I seem to pass all the cases I can think of, but still WA. Any ccomments on the below code?

Code: Select all

``Spoiler deleted``
EDIT: Accepted now, thanks Brian for pointing out nasty cases such as

Code: Select all

``````1
12 6
(3 2 X X) (X) (X 1) (1 X 1) (X) (X)
``````
Good problem with good data.
Last edited by red_apricot on Sun Dec 07, 2014 1:05 pm, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11598 - Optimal Segments

Input:

Code: Select all

``````200
28 8
15 6 X 15 12 X 6 1 21 X X 11 16 X X 15 22 25 X 16 X X 14 X 25 X X 21
15 8
8 X X 15 X 1 X 4 7 24 21 24 X 10 X
19 6
12 3 X 13 11 13 20 X X X X X X 20 22 X 3 X X
4 14
5 14 X X
20 13
1 8 24 X 2 9 X 4 X X X X X 24 X 5 X 20 1 X
9 14
X 5 X 4 X 23 X X X
14 10
X 23 20 X X 3 24 23 X X X X 10 17
11 13
X X 4 21 X 24 X X X X X
19 8
X X X X 11 X X X X 11 X X 2 X 5 X 13 20 23
10 4
5 16 X X X X X 14 17 7
28 15
15 25 X 21 1 X X X 1 14 X X X 24 9 24 X 25 19 10 X 12 8 X X 1 10 X
22 12
X 16 X 15 X X 6 8 3 X 15 11 21 X X 3 2 20 X 20 X X
18 9
X X 16 X 23 X 3 6 14 X X 17 X 3 X 22 2 22
29 8
11 X 1 13 9 X 12 20 16 10 X X X 12 9 X 1 X 13 X 1 8 X 8 X X X 10 21
17 14
10 X X X 14 X 9 X X 20 8 X 16 X X X 12
3 10
24 X 18
5 5
16 13 8 X 15
29 13
X 1 15 X X 18 X 8 15 X X X 19 X 9 X X 11 7 9 10 X X X 20 X 14 21 4
5 9
2 X X 6 X
16 15
X 15 12 7 X X 16 X X 10 X 7 X X X 11
30 13
18 23 X X 6 X X 16 X 1 X X X 16 11 X X 20 14 X 14 X 20 3 X X 10 3 X X
18 9
X X 23 2 X 2 X 21 11 X X X X X 19 X X X
3 13
12 1 8
12 3
X 25 11 X X X 23 X X X 24 25
29 9
X X X 2 16 6 9 X X 4 X X 24 6 17 X X X 24 10 X X X 15 X 7 X X X
10 4
X X X 5 9 17 9 13 X 11
27 10
X 15 X 1 9 X X X 3 22 X 1 X 19 X 4 X X X X X 1 7 X X X X
21 3
X 13 X 16 X X 19 1 X X 17 X 3 23 X 7 14 16 14 X X
23 3
X 16 14 X 18 9 X 3 19 7 X X 24 20 X 3 X X X X 3 5 X
19 12
X X 16 21 20 X 1 X X X X X 23 X 2 22 X 1 X
10 9
16 X X 7 X X 18 X 19 24
10 5
X X 17 18 X 19 X 17 X 1
13 11
X X X X X X 4 X 12 25 X X X
19 6
X X X X X 17 X X X X 9 12 X X X 4 X X 4
7 12
16 X 3 19 2 4 2
20 8
10 18 X 18 9 6 24 20 X 12 23 X 16 X X 21 X X X X
3 14
17 X 9
10 4
14 5 4 18 12 X X 8 3 20
14 8
6 11 15 X 23 13 8 X X 1 X 16 X X
8 7
21 5 1 2 X 12 X X
8 7
13 X 20 4 X 19 X X
11 5
3 X X X X X 8 X X 17 4
6 11
24 14 15 21 X 23
30 3
X 12 9 22 13 18 X 11 X 24 12 X X X X 21 25 X X X 8 10 X X 22 25 X X 19 20
16 10
1 14 X X X X 23 6 10 X 19 3 X X X 16
8 11
18 X 3 X 12 X 16 10
23 5
X 19 5 X X 10 X X 10 2 11 3 23 X 12 22 16 X X X X X 16
12 11
X 16 13 12 13 24 X X 5 25 X 24
7 9
7 13 X X X 22 23
25 6
23 X 10 X 19 X 1 X X 12 14 X 22 X 7 10 10 X 23 X X 5 X X 7
7 11
3 2 X 9 X X 7
22 8
12 X 23 16 16 X 22 X X X X X 13 17 X 19 15 X 23 6 X X
11 7
25 4 1 16 2 X X X 25 X X
22 7
17 X X X 6 X 17 X X X 5 X X X X X X 4 X X 8 X
15 14
6 5 X X 22 X 15 7 X 14 2 21 17 X X
30 9
X 6 X 20 X X 8 23 X X 20 X X 7 2 X 24 9 X X 21 17 24 X 16 23 X X 6 18
21 8
10 19 X X X 7 X X 1 X X 13 18 25 11 17 X 9 X 25 X
18 12
9 X X 14 9 X X X 21 X X 20 5 X 22 8 14 X
11 7
4 X 10 16 13 10 18 10 X X 20
5 4
X X 13 9 13
7 11
X 1 X 16 X 6 10
2 14
X 5
13 4
X 12 17 X 13 X 25 8 X 10 8 4 X
29 10
X 18 10 X X 24 X X 7 12 17 X 7 X 14 14 19 8 X 3 3 X 1 10 X X 25 9 X
24 11
14 X 11 X 25 X X X X X 6 X 21 X 20 11 X 10 X 22 X 12 6 X
27 8
X X X X X 5 X 25 X 10 X 7 X X X 17 21 8 12 X X X X 22 11 X X
14 2
X 19 X X X X 5 X X X 12 23 X 12
17 5
4 X 22 X 16 5 15 19 16 X 20 1 X 15 X X 25
18 15
5 19 23 X 13 X X 15 X 8 X X 24 12 X 1 X X
20 8
X 19 X X X 7 25 X X X X 24 X 25 1 6 X 24 14 25
26 14
3 X X X X 10 23 X X 12 4 X X 5 X 18 X X X 17 X 1 X 20 18 X
15 5
X 6 11 X X 20 23 X X 19 X 24 X 8 X
12 14
8 11 19 X X X 10 X X X X 3
10 4
17 X X 1 X 11 9 X 18 17
18 9
22 2 X X X 20 16 5 18 X X 9 3 X X 3 X 21
25 2
13 X 14 X X X X 1 X X X X X 15 22 X 15 25 X X X 9 X 21 2
30 13
15 X 17 3 16 X 5 X X 2 5 19 5 19 10 X X X 6 X X X X 16 X 6 18 21 2 25
12 3
X X 4 5 1 25 16 20 22 X X 11
19 10
16 X 17 6 X X X 1 X X 19 19 11 X 8 X X X 12
6 6
6 14 X X 19 7
21 13
23 18 3 X 14 8 X X 8 12 X 2 25 1 1 22 X X X 15 X
17 3
22 X X X 25 2 9 17 X 6 8 2 X 23 X X 13
22 9
16 X 11 15 15 15 X 6 X X X X X 5 X X 16 4 22 X X X
30 15
15 X X X 9 18 2 8 X X X X X 22 X 6 14 X 17 19 X 10 8 X 16 X X X X X
7 3
X 18 19 X X X X
5 13
21 X 17 1 X
3 15
12 6 X
30 11
10 12 X 16 X 18 12 2 X X X X X 18 X X X X 25 X X 8 23 25 16 X X 8 19 X
20 8
X X 11 X 25 17 X X 21 6 22 X 22 X 14 17 9 6 19 X
6 15
X X X X 4 9
5 8
X X 16 20 13
11 13
23 X 12 X X X 6 10 11 X 17
7 9
4 X 7 X 1 X 7
25 12
X X 18 X X 11 24 X X X 23 9 X X 19 X X X X 1 X 15 X X X
5 6
13 12 25 X X
14 4
14 X X X 24 25 13 17 X 6 9 16 X 6
8 12
12 18 12 X 3 X X X
26 5
X X X X X 7 21 7 X X 19 10 X X X 23 X X 1 24 19 X X 19 12 12
9 14
X X X 10 21 X X X 21
13 3
X 6 X 20 8 14 X 3 X X X X 9
26 6
X X 13 X X 6 25 X 5 X 25 X X 9 17 21 25 X X 4 X X X 16 19 X
22 5
19 16 X 17 X 10 X 3 X 7 25 19 X X 11 X 1 X X 17 18 2
14 13
2 X X 4 8 X X X 16 20 10 24 X X
11 14
X X 24 11 X X X 20 X 25 X
26 15
16 X X X X X 5 X X 12 16 22 10 2 X X 10 4 19 25 X X X 21 6 X
17 13
X X 14 11 X 20 X 10 X X 12 6 X 6 17 X X
3 13
X 1 25
28 8
8 2 X 24 6 5 X 3 2 X 9 X X 5 9 X 7 13 20 25 X X X 17 X X 2 X
16 6
1 17 20 22 X X 2 X 16 2 1 18 22 X X 9
21 7
X 13 8 2 17 16 24 X X 12 X 23 8 21 X 21 X 23 22 X X
26 12
6 3 X 18 X 13 X 8 X 6 14 X X X X X X 7 7 X 2 X X X X 16
4 15
8 X 17 18
22 8
X 8 24 X X 4 2 X 5 25 X 19 X 16 X 24 X X X 9 18 X
11 6
X X X X X X 1 9 X 15 X
19 13
X 9 X X 25 X 10 X 18 X 2 16 13 X X 1 X 12 X
26 11
X X 8 11 14 25 X X X X 6 22 2 13 X 13 X 1 14 X X X X X X 15
25 3
X 19 18 X X X X X 22 X X 5 1 X X 1 8 X 15 X 14 1 24 X 13
4 7
X X X X
26 13
X 9 X X 16 X X X 6 24 X 4 14 X X X X X 17 23 X X X 24 14 24
30 9
3 X X 8 20 1 X X X 4 15 X 12 5 3 2 X 2 X X X 12 16 X 13 X 20 X X X
12 3
25 24 X X X 13 X X 6 2 25 5
14 9
X 24 1 20 X X X X 14 13 13 X 19 7
16 8
X 11 X X X X X X 10 11 10 X X X X 10
13 7
X X X 7 18 X X 4 X 8 12 X 23
24 14
16 X 15 X 25 X X 11 X 19 X 12 X 17 18 X 6 4 X X 6 3 5 7
23 6
6 X X 11 13 X X X X X X X X X X X 9 X 1 X 7 X X
17 15
X X 8 13 9 X 25 X X X 23 3 16 5 X X X
12 2
3 X 3 22 X 9 12 4 1 X X X
19 13
23 10 X X 14 20 19 X 21 22 14 X 25 X 13 1 X X 3
25 13
X X 12 X 4 17 X X X 15 4 21 5 X 17 X X X X X 22 14 1 X X
22 9
X X X X 25 16 X 13 X 13 X X 14 19 25 19 X 20 21 X 23 1
27 10
1 4 X 11 X 20 8 X X X X X X 17 X X X X 8 21 7 X 9 14 X 24 1
6 15
X 21 4 X 1 14
19 2
19 X 14 4 X 15 X 23 X X X 12 16 5 X X X X X
16 7
X 18 25 21 X 5 8 X 8 X X X X X X 5
13 3
X 12 12 11 3 6 X 24 18 X X 5 X
13 3
1 14 5 1 X X 1 X 13 4 23 X X
27 13
X X X X 17 5 X 5 24 18 13 15 2 X 17 X X X 2 X 15 10 X 1 X 24 7
5 2
9 4 10 X X
29 3
X X 11 X 24 X 25 19 19 2 8 8 X 16 X X X 25 X 20 23 4 X 5 4 X X X X
10 2
X X 17 X X X 22 13 X 9
7 10
X X 5 2 X X X
13 12
19 X 2 15 X X 12 9 X 14 12 X 13
10 10
X X 3 7 2 14 X 15 X X
6 13
21 X X 16 14 12
10 8
13 X X X 17 6 X 20 22 X
10 2
X 8 24 22 18 X 5 7 16 21
25 4
5 X X 5 X X X 9 X X 24 22 21 X 14 X 23 X 13 7 4 2 X 8 19
8 2
9 X 9 16 7 12 2 17
15 14
18 25 17 6 X 12 X X X X X X X 24 6
17 14
1 X 20 X X X X X 3 4 13 X X 23 X X X
11 2
X X X 3 X 5 X X 23 1 22
18 15
X X 25 11 16 25 X 10 X X X X 19 X 3 21 3 6
19 9
X X 1 25 X 17 X 24 4 8 X X 18 21 X X 2 X X
30 9
17 X 18 X X X X X 11 5 X 15 1 10 X 9 2 20 X X X X X 22 X X X 11 19 3
16 10
12 12 X 1 X X X 6 X X 11 X 7 X X X
12 4
17 X 21 23 23 X X X X 12 X 4
17 11
14 21 X 5 18 X 7 5 X X 18 X 20 X X 10 20
7 15
6 3 X X 6 1 17
13 11
X 1 16 X 3 16 23 12 11 9 X 11 15
29 4
X X 24 17 X X X 23 13 1 X 23 X 19 X 2 22 X X 20 X X 14 10 X X X 15 X
14 7
X 6 X X 8 X X 5 25 X X 13 7 18
7 6
X X 24 X X 22 22
14 9
X X 9 24 X 24 12 X 18 X 13 X X 19
22 3
4 X 10 14 X X 20 2 25 X X 22 2 2 X X X 14 25 X 5 13
2 10
13 7
18 10
4 19 13 7 8 X X 2 X 17 3 X X X 7 9 20 5
11 2
X 21 19 17 X X 14 X 3 X X
21 12
X 13 X 11 15 24 X 24 14 15 X 6 5 X X 10 X 4 X 19 X
23 2
1 16 23 14 X 2 X X X X 1 22 X X 11 X X X X 18 25 X 23
13 7
X 18 X 21 22 X 13 X 9 16 21 3 9
30 11
10 5 3 X X 3 13 X X 5 X 9 X 20 X 17 X X X X X 23 19 9 13 24 X 14 15 X
16 10
X 19 X X X X 7 18 25 22 15 X 14 X 13 21
23 2
25 15 X 10 20 13 X 22 X 22 13 X X X X 24 19 3 X X X X X
23 10
X X 4 X X X 9 X 7 X 4 6 3 17 X X X 8 X 23 X 5 X
6 6
15 X 25 24 X X
14 8
X X X 2 X X X X X X 15 9 25 3
7 7
X X X X 6 3 14
20 5
23 X X 9 11 X 3 X 25 X 2 X X X X X 16 X X 6
20 3
X 4 22 7 1 17 X 9 11 X 20 3 10 7 X X X 19 X X
15 11
11 3 3 X X X X X X X 16 19 2 16 X
18 13
24 19 X X X X 11 17 X 6 19 X X 14 18 16 14 X
8 12
15 9 X 21 7 5 13 23
28 14
X X X 12 X 20 12 15 24 X 10 17 X X 4 X 11 9 X X X 8 25 X 18 X 6 X
14 10
3 X 16 X X 4 4 X X 5 9 X X X
16 13
X X 4 X 5 1 14 12 21 X 1 7 25 X 7 2
16 10
16 X 16 X X X 5 5 X 18 X X 1 16 16 X
21 2
X 17 2 X X X X 18 X X X X 25 3 15 6 16 21 14 23 X
16 13
X X 25 X 17 X X 14 12 2 8 X 13 X 10 X
9 5
8 14 X 20 12 X 6 X X
18 3
X X X X X X 24 X X 23 15 X 22 X X X X 15
26 15
X X 6 21 X X X 16 X 16 5 X 18 23 7 7 8 X X 17 16 X 22 X X 17
26 2
23 X 2 2 17 X 23 23 17 X X 4 3 X 1 X 1 21 16 X X 24 X X X X
16 3
X 11 X 23 12 8 X X X X 17 X 14 10 X X
11 7
X 6 2 17 X X 10 X X 5 X
26 2
7 X X 1 15 17 18 23 X X X X X X 11 X 15 16 20 X 21 21 13 X 4 X
23 13
18 22 X 21 7 X 7 X X X X X X 18 X X X X 14 X X X X
21 9
X X 18 X 2 22 23 2 10 19 24 17 17 X 23 25 13 9 X 3 13
9 9
24 7 13 6 X 5 X X 10
8 15
X X 3 21 X X X 12
``````
AC output:

Code: Select all

``````Case 1: 524288 (15 6 X 15)(12 X 6 1 21 X X)(11 16 X)(X 15 22)(25 X)(16 X X 14 X)(25 X)(X 21)
Case 2: not possible!
Case 3: 549755813888 (12 3 X 13 11)(13 20 X X X X X)(X 20)(22 X 3)(X)(X)
Case 4: not possible!
Case 5: not possible!
Case 6: not possible!
Case 7: not possible!
Case 8: not possible!
Case 9: overflow
Case 10: 274877906944 (5 16 X X)(X)(X)(X 14 17 7)
Case 11: not possible!
Case 12: not possible!
Case 13: not possible!
Case 14: 16777216 (11 X 1 13 9)(X 12 20)(16 10 X X)(X 12)(9 X 1 X)(13 X 1)(8 X 8 X X)(X 10 21)
Case 15: not possible!
Case 16: not possible!
Case 17: not possible!
Case 18: 549755813888 (X 1 15 X)(X 18)(X 8 15)(X)(X)(X 19)(X 9)(X)(X 11 7 9 10)(X)(X)(X 20)(X 14 21 4)
Case 19: not possible!
Case 20: not possible!
Case 21: 2199023255552 (18 23 X X)(6 X X 16 X 1)(X)(X)(X 16 11)(X)(X 20 14)(X 14)(X 20 3)(X)(X 10 3)(X)(X)
Case 22: 8388608 (X X 23)(2 X 2)(X 21)(11 X X X)(X)(X 19)(X)(X)(X)
Case 23: not possible!
Case 24: 16777216 (X 25)(11 X X X 23 X X)(X 24 25)
Case 25: 1048576 (X X X 2 16 6)(9 X X)(4 X)(X 24)(6 17 X X)(X 24)(10 X X X)(15 X)(7 X X X)
Case 26: 8589934592 (X)(X)(X 5 9 17)(9 13 X 11)
Case 27: 2097152 (X 15)(X 1)(9 X X)(X 3)(22 X)(1 X)(19 X)(4 X X X X)(X 1)(7 X X X X)
Case 28: 64 (X 13 X 16 X X 19 1 X X)(17 X 3 23 X 7)(14 16 14 X X)
Case 29: 131072 (X 16 14 X 18)(9 X 3 19 7 X X)(24 20 X 3 X X X X 3 5 X)
Case 30: not possible!
Case 31: not possible!
Case 32: 524288 (X)(X 17)(18 X)(19 X)(17 X 1)
Case 33: not possible!
Case 34: 131072 (X X X X X 17 X X X)(X 9)(12 X X)(X 4)(X)(X 4)
Case 35: not possible!
Case 36: overflow
Case 37: not possible!
Case 38: not possible!
Case 39: not possible!
Case 40: not possible!
Case 41: not possible!
Case 42: 2097152 (3 X X X)(X)(X 8)(X)(X 17 4)
Case 43: not possible!
Case 44: 2048 (X 12 9 22 13 18 X 11 X)(24 12 X X X X 21 25 X X X 8)(10 X X 22 25 X X 19 20)
Case 45: not possible!
Case 46: not possible!
Case 47: 4194304 (X 19 5 X X 10 X)(X 10 2 11 3)(23 X 12)(22 16 X X X X)(X 16)
Case 48: not possible!
Case 49: not possible!
Case 50: 8192 (23 X)(10 X 19 X 1 X X)(12 14 X)(22 X)(7 10 10 X)(23 X X 5 X X 7)
Case 51: not possible!
Case 52: 34359738368 (12 X 23)(16 16 X)(22 X X X X)(X 13 17)(X 19 15)(X 23 6)(X)(X)
Case 53: not possible!
Case 54: 131072 (17 X X X)(6 X)(17 X X X)(5 X X X X X X 4)(X)(X 8)(X)
Case 55: not possible!
Case 56: 1073741824 (X 6 X 20 X X 8)(23 X X)(20 X X 7 2)(X 24)(9 X)(X 21 17)(24 X)(16 23 X)(X 6 18)
Case 57: overflow
Case 58: not possible!
Case 59: not possible!
Case 60: not possible!
Case 61: not possible!
Case 62: not possible!
Case 63: 131072 (X 12 17)(X 13)(X 25)(8 X 10 8 4 X)
Case 64: 524288 (X 18)(10 X X)(24 X)(X 7 12)(17 X 7)(X 14 14)(19 8 X)(3 3 X 1 10 X)(X 25)(9 X)
Case 65: 33554432 (14 X 11 X)(25 X X)(X)(X)(X 6)(X 21)(X 20)(11 X 10)(X 22)(X 12 6)(X)
Case 66: 8589934592 (X X X X X 5 X)(25 X)(10 X)(7 X X)(X 17 21)(8 12 X X X)(X 22)(11 X X)
Case 67: 2 (X 19 X X X X 5 X X X 12)(23 X 12)
Case 68: 2048 (4 X 22)(X 16 5 15)(19 16 X)(20 1 X 15 X)(X 25)
Case 69: not possible!
Case 70: overflow
Case 71: 8388608 (3 X X)(X)(X 10)(23 X)(X 12 4)(X)(X 5)(X 18)(X)(X)(X 17)(X 1)(X 20)(18 X)
Case 72: 32768 (X 6 11 X)(X 20)(23 X X)(19 X)(24 X 8 X)
Case 73: not possible!
Case 74: 17179869184 (17 X)(X 1)(X 11 9)(X 18 17)
Case 75: not possible!
Case 76: 128 (13 X 14 X X X X 1 X X X X X 15 22 X)(15 25 X X X 9 X 21 2)
Case 77: not possible!
Case 78: 1099511627776 (X X 4 5 1 25 16)(20 22 X)(X 11)
Case 79: 1073741824 (16 X)(17 6 X)(X)(X 1)(X)(X 19)(19 11 X)(8 X)(X)(X 12)
Case 80: not possible!
Case 81: not possible!
Case 82: 512 (22 X X X 25)(2 9 17 X 6 8)(2 X 23 X X 13)
Case 83: 4398046511104 (16 X 11 15)(15 15 X 6 X X X)(X)(X 5)(X)(X 16 4 22)(X)(X)(X)
Case 84: 134217728 (15 X X)(X 9 18)(2 8 X X)(X)(X)(X 22)(X 6 14)(X 17)(19 X)(10 8 X)(16 X)(X)(X)(X)(X)
Case 85: 524288 (X 18)(19 X X X)(X)
Case 86: not possible!
Case 87: not possible!
Case 88: 2199023255552 (10 12 X 16 X)(18 12 2 X X X X X)(18 X)(X)(X)(X 25)(X)(X 8 23)(25 16 X)(X 8 19)(X)
Case 89: 17592186044416 (X)(X 11)(X 25 17)(X)(X 21 6)(22 X 22)(X 14 17 9)(6 19 X)
Case 90: not possible!
Case 91: not possible!
Case 92: not possible!
Case 93: not possible!
Case 94: 16777216 (X X 18 X)(X 11)(24 X X)(X 23)(9 X X)(19 X X)(X)(X 1)(X 15)(X)(X)(X)
Case 95: not possible!
Case 96: 34359738368 (14 X X)(X 24 25)(13 17 X 6 9)(16 X 6)
Case 97: not possible!
Case 98: 131072 (X X X X X 7 21)(7 X X 19)(10 X X X 23 X X 1)(24 19 X)(X 19 12 12)
Case 99: not possible!
Case 100: 16384 (X 6 X 20)(8 14 X)(3 X X X X 9)
Case 101: 134217728 (X X 13 X X 6 25 X)(5 X 25 X)(X 9 17)(21 25 X X)(4 X X X 16)(19 X)
Case 102: 128 (19 16 X)(17 X 10 X 3)(X 7 25)(19 X X 11 X 1 X)(X 17 18 2)
Case 103: not possible!
Case 104: not possible!
Case 105: not possible!
Case 106: not possible!
Case 107: not possible!
Case 108: 34359738368 (8 2 X 24 6)(5 X)(3 2 X)(9 X)(X 5 9)(X 7 13 20)(25 X X X)(17 X X 2 X)
Case 109: not possible!
Case 110: 1073741824 (X 13 8 2 17)(16 24 X)(X 12)(X 23 8)(21 X 21)(X 23)(22 X X)
Case 111: 262144 (6 3 X)(18 X)(13 X)(8 X 6)(14 X X X X)(X)(X 7 7)(X 2)(X)(X)(X)(X 16)
Case 112: not possible!
Case 113: 524288 (X 8)(24 X X)(4 2 X 5)(25 X)(19 X)(16 X)(24 X X X)(9 18 X)
Case 114: 32768 (X X X)(X)(X)(X 1 9)(X 15)(X)
Case 115: not possible!
Case 116: 8589934592 (X X 8 11 14)(25 X X X)(X 6 22 2)(13 X 13)(X 1 14)(X)(X)(X)(X)(X)(X 15)
Case 117: 32768 (X 19 18 X X X X X)(22 X X 5 1 X X 1 8 X 15 X)(14 1 24 X 13)
Case 118: not possible!
Case 119: overflow
Case 120: 1024 (3 X X 8)(20 1 X X)(X 4 15)(X 12)(5 3 2 X 2 X X)(X 12)(16 X)(13 X)(20 X X X)
Case 121: 68719476736 (25 24 X X X)(13 X)(X 6 2 25 5)
Case 122: not possible!
Case 123: 2097152 (X 11 X X X)(X)(X)(X 10 11)(10 X)(X)(X)(X 10)
Case 124: 8388608 (X)(X)(X 7)(18 X)(X 4)(X 8 12)(X 23)
Case 125: not possible!
Case 126: 4096 (6 X)(X 11)(13 X X X X X X X X X X X)(9 X)(1 X)(7 X X)
Case 127: not possible!
Case 128: 4 (3 X 3 22 X)(9 12 4 1 X X X)
Case 129: not possible!
Case 130: 67108864 (X X 12)(X 4 17)(X)(X)(X 15 4)(21 5 X)(17 X)(X)(X)(X)(X 22)(14 1 X)(X)
Case 131: overflow
Case 132: 1073741824 (1 4 X 11 X)(20 8 X X X X)(X)(X 17)(X)(X)(X)(X 8 21)(7 X 9 14)(X 24 1)
Case 133: not possible!
Case 134: 16 (19 X 14 4 X 15 X)(23 X X X 12 16 5 X X X X X)
Case 135: 8796093022208 (X 18 25)(21 X 5 8 X 8 X)(X)(X)(X)(X)(X 5)
Case 136: 4096 (X 12 12 11)(3 6 X 24)(18 X X 5 X)
Case 137: 32 (1 14 5 1 X X)(1 X 13 4)(23 X X)
Case 138: not possible!
Case 139: 8388608 (9 4 10 X)(X)
Case 140: 2097152 (X X 11 X 24 X 25)(19 19 2 8 8 X 16 X X X)(25 X 20 23 4 X 5 4 X X X X)
Case 141: 131072 (X X 17 X X X 22)(13 X 9)
Case 142: not possible!
Case 143: not possible!
Case 144: not possible!
Case 145: not possible!
Case 146: not possible!
Case 147: 8192 (X 8 24 22)(18 X 5 7 16 21)
Case 148: 1024 (5 X X 5 X X X 9 X X 24)(22 21 X)(14 X 23 X 13)(7 4 2 X 8 19)
Case 149: not possible!
Case 150: not possible!
Case 151: not possible!
Case 152: 274877906944 (X X X 3 X 5 X)(X 23 1 22)
Case 153: not possible!
Case 154: 67108864 (X X 1 25)(X 17)(X 24)(4 8 X)(X 18)(21 X)(X 2)(X)(X)
Case 155: 8589934592 (17 X)(18 X X X X X 11)(5 X 15 1 10 X)(9 2 20 X X X)(X)(X 22)(X)(X)(X 11 19 3)
Case 156: 16777216 (12 12 X)(1 X)(X)(X 6)(X)(X 11)(X 7)(X)(X)(X)
Case 157: 4398046511104 (17 X 21)(23 23 X X X)(X 12)(X 4)
Case 158: not possible!
Case 159: not possible!
Case 160: not possible!
Case 161: 524288 (X X 24 17 X X X)(23 13 1 X 23 X)(19 X 2 22 X X)(20 X X 14 10 X X X 15 X)
Case 162: 274877906944 (X 6)(X)(X 8)(X)(X 5 25)(X)(X 13 7 18)
Case 163: not possible!
Case 164: not possible!
Case 165: 128 (4 X 10 14 X X 20 2)(25 X X 22 2 2 X X X)(14 25 X 5 13)
Case 166: not possible!
Case 167: not possible!
Case 168: 64 (X 21 19)(17 X X 14 X 3 X X)
Case 169: not possible!
Case 170: 4 (1 16 23 14 X 2 X X X X 1 22 X X)(11 X X X X 18 25 X 23)
Case 171: not possible!
Case 172: 70368744177664 (10 5 3 X X 3 13 X X 5)(X 9)(X 20)(X 17)(X)(X)(X)(X)(X 23 19)(9 13 24 X)(14 15 X)
Case 173: not possible!
Case 174: 1048576 (25 15 X 10 20 13 X)(22 X 22 13 X X X X 24 19 3 X X X X X)
Case 175: 8388608 (X X 4 X X)(X 9)(X 7)(X 4 6 3)(17 X)(X)(X 8)(X 23)(X 5)(X)
Case 176: not possible!
Case 177: overflow
Case 178: not possible!
Case 179: 65536 (23 X)(X 9)(11 X 3 X)(25 X)(2 X X X X X 16 X X 6)
Case 180: 4096 (X 4 22 7 1 17 X)(9 11 X 20)(3 10 7 X X X 19 X X)
Case 181: not possible!
Case 182: not possible!
Case 183: not possible!
Case 184: 549755813888 (X)(X)(X 12)(X 20 12)(15 24 X)(10 17 X)(X 4)(X 11 9)(X)(X)(X 8 25)(X 18)(X 6)(X)
Case 185: not possible!
Case 186: not possible!
Case 187: not possible!
Case 188: 1 (X 17 2 X X X X 18 X X X X 25 3 15)(6 16 21 14 23 X)
Case 189: not possible!
Case 190: not possible!
Case 191: 16384 (X X X X X X 24 X X)(23 15 X)(22 X X X X 15)
Case 192: not possible!
Case 193: 8 (23 X 2 2 17 X 23 23)(17 X X 4 3 X 1 X 1 21 16 X X 24 X X X X)
Case 194: 8192 (X 11 X 23)(12 8 X X X X 17 X)(14 10 X X)
Case 195: not possible!
Case 196: 4096 (7 X X 1 15 17 18 23 X X X X X X 11 X 15)(16 20 X 21 21 13 X 4 X)
Case 197: 1099511627776 (18 22 X)(21 7 X 7 X X X)(X)(X)(X 18)(X)(X)(X)(X 14)(X)(X)(X)(X)
Case 198: not possible!
Case 199: not possible!
Case 200: not possible!
``````
Check input and AC output for thousands of problems on uDebug!