## Problem H. Walaweh

Problem Author: Felix Halim

Soal ini cukup merepotkan, bukan karena algoritmanya yang susah, melainkan karena implementasi program rekursi/simulasinya yang harus dibuat dengan hati-hati (mudah salah). Hanya dua tim yang mencoba menyelesaikan soal ini, namun tidak ada yang berhasil.

Solusi C/C++
oleh Felix Halim
```#include <stdlib.h>
#include <string.h>
#include <string>
#include <time.h>
#include <stdlib.h>
using namespace std;

string walaweh(long long L, long long N){
string left = "", right = "";
while (L-- > 1){
long long len = 1LL << L;
switch ((L-1)%8){
case 0: if (N < len){ right = "0" + right; } else { right = "1" + right; N -= len; } break;
case 1: if (N < len){ left = left + "0";   } else { left = left + "1"; N -= len;   } break;
case 2: if (N < len){ right = "1" + right; } else { right = "0" + right; N -= len; } break;
case 3: if (N < len){ left = left + "1";   } else { left = left + "0"; N -= len;   } break;
case 4: if (N < len){ right = "0" + right; } else { right = "1" + right; N = len - (N-len) - 1; } break;
case 5: if (N < len){ left = left + "0";   } else { left = left + "1"; N = len - (N-len) - 1;   } break;
case 6: if (N < len){ right = "1" + right; } else { right = "0" + right; N = len - (N-len) - 1; } break;
case 7: if (N < len){ left = left + "1";   } else { left = left + "0"; N = len - (N-len) - 1;  } break;
}
}
return left + (N?"1":"0") + right;
}

long long seq(char *w, int left, int right){
if (left == right) return w[left] - '0' + 1;

long long L = right-left, len = 1LL << L;
switch ((L-1)%8){
case 0: return seq(w,left,right-1) + ((w[right]=='1')? len : 0);
case 1: return seq(w,left+1,right) + ((w[left]=='1')? len : 0);
case 2: return seq(w,left,right-1) + ((w[right]=='0')? len : 0);
case 3: return seq(w,left+1,right) + ((w[left]=='0')? len : 0);
case 4: return (w[right]=='1')? (2*len - seq(w,left,right-1) + 1) : seq(w,left,right-1);
case 5: return (w[left]=='1')? (2*len - seq(w,left+1,right) + 1) : seq(w,left+1,right);
case 6: return (w[right]=='0')? (2*len - seq(w,left,right-1) + 1) : seq(w,left,right-1);
case 7: return (w[left]=='0')? (2*len - seq(w,left+1,right) + 1) : seq(w,left+1,right);
}
}

int main(){
char s[100];
long long L,N;

while (scanf("%s",s)!=EOF){
if (s[0]=='W'){
scanf("%I64d %I64d",&L,&N);
printf("%s\n",walaweh(L,N-1).c_str());
} else {
scanf("%s",s);
printf("%I64d\n",seq(s,0,strlen(s)-1));
}
}
}
```

Solusi JAVA
oleh Felix Halim
```import java.util.*;
import java.io.*;

public class Walaweh {
String wal(int L, long N){
if (L==1) return ""+N;
long H = 1L << (L-1);
switch ((L-2)%8){
case 0: return (N<H)? (wal(L-1,N)+"0") : (wal(L-1,N-H)+"1");
case 1: return (N<H)? ("0"+wal(L-1,N)) : ("1"+wal(L-1,N-H));
case 2: return (N<H)? (wal(L-1,N)+"1") : (wal(L-1,N-H)+"0");
case 3: return (N<H)? ("1"+wal(L-1,N)) : ("0"+wal(L-1,N-H));
case 4: return (N<H)? (wal(L-1,N)+"0") : (wal(L-1,H-(N-H)-1)+"1");
case 5: return (N<H)? ("0"+wal(L-1,N)) : ("1"+wal(L-1,H-(N-H)-1));
case 6: return (N<H)? (wal(L-1,N)+"1") : (wal(L-1,H-(N-H)-1)+"0");
case 7: return (N<H)? ("1"+wal(L-1,N)) : ("0"+wal(L-1,H-(N-H)-1));
}
return "error";
}

long seq(String S, int i, int j){
if (i==j) return S.charAt(i)-'0';
long N = 1L << (j-i), ret = 0, add = 0;
switch ((j-i-1)%8){
case 0 : return (S.charAt(j)=='0')? seq(S,i,j-1) : (N + seq(S,i,j-1));
case 1 : return (S.charAt(i)=='0')? seq(S,i+1,j) : (N + seq(S,i+1,j));
case 2 : return (S.charAt(j)=='1')? seq(S,i,j-1) : (N + seq(S,i,j-1));
case 3 : return (S.charAt(i)=='1')? seq(S,i+1,j) : (N + seq(S,i+1,j));
case 4 : ret = seq(S,i,j-1); if (S.charAt(j)=='1') ret = N-ret-1 + N; break;
case 5 : ret = seq(S,i+1,j); if (S.charAt(i)=='1') ret = N-ret-1 + N; break;
case 6 : ret = seq(S,i,j-1); if (S.charAt(j)=='0') ret = N-ret-1 + N; break;
case 7 : ret = seq(S,i+1,j); if (S.charAt(i)=='0') ret = N-ret-1 + N; break;
}
return ret;
}

void solve() throws Exception {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
for (String line; (line = br.readLine())!=null; ){
String[] s = line.split(" ");
if (s[0].charAt(0)=='W'){
int L = Integer.parseInt(s[1]);
long N = Long.parseLong(s[2]);
bw.write(wal(L, N-1) + "\n");
} else {
bw.write((seq(s[1],0,s[1].length()-1)+1) + "\n");
}
}
br.close();
bw.close();
}

public static void main(String[] args) throws Exception {
new Walaweh().solve();
}
}```