## 11385 - Da Vinci Code

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

Moderator: Board moderators

outsbook
New poster
Posts: 26
Joined: Fri Oct 28, 2011 2:42 am

### 11385 - Da Vinci Code

Try this
Input:

Code: Select all

``````10
5
1 2 3 5 8
A
5
8 5 3 2 1
A
5
8 5 3 2 1
abcd
5
8 5 3 2 1
ABCDEFG
5
5 4 3 2 1
ABCDE
5
5 4 3 2 1
A a B b C c D d E e
1
13
ABCD
1
1836311903
aaaaaaaaaabbbbbbbbbbcccccccccccDdddddddddddddddddddd
1
4
ABC
1
2
a``````
Output:

Code: Select all

``````A####
####A
#####
EDCBA
DCBA
DCBA
#####A
############################################D

##
Note: Here # means space character ' '``````
"Learning to love yourself is the greatest love of all" - Michael Masser and Linda Creed

Evan72
New poster
Posts: 11
Joined: Sat Apr 28, 2012 2:01 pm

### Re: 11385 - Da Vinci Code WHY WA?!?

SOMEBODY HELP PLZ......

Code: Select all

``````AC
``````
Last edited by Evan72 on Fri Jul 06, 2012 3:43 pm, edited 1 time in total.

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

### Re: 11385 - Da Vinci Code

Print a newline at the end of the last line.
Check input and AC output for thousands of problems on uDebug!

Evan72
New poster
Posts: 11
Joined: Sat Apr 28, 2012 2:01 pm

### Re: 11385 - Da Vinci Code

Thank u brianfry713

Sakibul Mowla
New poster
Posts: 2
Joined: Tue May 29, 2012 2:48 pm

### Wa: 11385 - Da Vinci Code

getting wrong answer !!!
kindly help , plz!!!

#include <stdio.h>
#include <string.h>

int main()
{
long long int a,b,fibo[100],num[1000];
int i,j,k,l,n,m,len,c;
char line[1000],code[1000],z;

fibo[0]=a=1;fibo[1]=b=2;
for(i=2;i<100;i++)
{
fibo=a+b;
a=b;
b=fibo;
}

scanf("%d",&n);
for(i=0;i<n;i++)
{
scanf("%d",&m);
l=0;
for(j=0;j<m;j++)
{
scanf("%lld",&num[j]);
if(num[j]>l)
l=num[j];
}
scanf("%c",&z);
gets(line);
len=strlen(line);
for(j=0;j<100;j++)
{
if(l==fibo[j])
{
c=j;
break;
}
}
for(k=0,l=0;k<len;k++)
{
if(line[k]>='A' && line[k]<='Z')
{
for(j=0;j<=c;j++)
{
if(fibo[j]==num[l])
{
code[j]=line[k];
l++;
break;
}
}
}
}
for(k=0;k<=c;k++)
{
if(!(code[k]>='A' && code[k]<='Z'))
code[k]=' ';
}
code[c+1]='\0';
printf("%s\n",code);
for(j=0;j<1000;j++)
code[j]='\0';
}

return 0;
}

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

### Re: 11385 - Da Vinci Code

Your code array is not initialized before the first test case, but you'll still get WA after you fix that.
Check input and AC output for thousands of problems on uDebug!

Sakibul Mowla
New poster
Posts: 2
Joined: Tue May 29, 2012 2:48 pm

### Re: 11385 - Da Vinci Code

Thanks brian !!!
made necessary changes & got AC !!!

uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Contact:

### Re: 11385 - Da Vinci Code

Please, help me, I am getting WA
Code:

Code: Select all

``````// Remove trailing space from output array
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <map>
#include <iterator>
using namespace std;

map<unsigned long, unsigned long> fib;
map<unsigned long, unsigned long>::iterator it;
unsigned long fb[1000];
int main()
{
fib[0]=0; fib[1]=1; fib[2]=2;
fb[0]=0;  fb[1]=1;  fb[2]=2;
unsigned long i, j, pos;
for(i=3 ; i<=50 ; i++){
fib[i] = fib[i-2] + fib[i-1];
fb[i] = fib[i];
}
int T;
unsigned long n, ln, k=1, maxx=0, p=0, tm, ctxt[1112]={0};
char ch, in[1111]={'\0'}, tmp[1112]={'\0'}, pr[1112]={'\0'};
//freopen("in-11385.txt","r",stdin);
//freopen("out-11385.txt","w",stdout);
scanf("%d",&T);
while(T){
scanf("%lu",&n);
for(i=1 ; i<=n ; i++){
scanf("%lu",&ctxt[i]);
if(maxx < ctxt[i]){
maxx = ctxt[i];
}
}

gets(in);
ln=strlen(in);
if(n>0 && ln>0){
for(i = 0 ; i < ln ; i++){
if(in[i]>='A' && in[i]<='Z'){
tmp[k] = in[i];
k++;
}
}
for(i = 1 ; i < 50 ; i++){
if(maxx == fb[i]) {pos=i; }
}
int fnf=1;
for(i=1 ; i<=pos ; i++ ){
tm = fb[i];
int fag=0, pss;
for(j=1 ; j<=n ; j++){
if(tm == ctxt[j]){
fag=1;
pss=j;
break;
}
}
if(fag==1){
if(tmp[pss]>='A' && tmp[pss]<='Z'){
pr[i] = tmp[pss];
}
}
else pr[i]=' ';
fnf++;
}
fnf -= 1;
if(fnf==pos){
for(i = 1 ; i <= pos ; i++){
if( (pr[i]>='A' && pr[i]<='Z') || pr[i]==' '){
printf("%c",pr[i]);
if(i==pos) {T--; fnf=0;}
}
}
printf("\n");
}

memset(in,'\0',sizeof(in));
memset(tmp,'\0',sizeof(tmp));
memset(pr,'\0',sizeof(pr));
memset(ctxt,0,sizeof(ctxt));

}
}
return 0;
}

``````

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

### Re: 11385 - Da Vinci Code

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

uvasarker
Learning poster
Posts: 96
Joined: Tue Jul 19, 2011 12:19 pm
Contact:

### Re: 11385 - Da Vinci Code

Still WA.........Guru
Code:

Code: Select all

``````// Remove trailing space from output array
#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <map>
#include <iterator>
using namespace std;

map<unsigned long, unsigned long> fib;
map<unsigned long, unsigned long>::iterator it;
unsigned long fb[1000];

char in[1111]={'\0'}, tmp[1112]={'\0'}, pr[1112]={'\0'};
unsigned long ctxt[1112]={0};

int main()
{
fib[0]=0; fib[1]=1; fib[2]=2;
fb[0]=0;  fb[1]=1;  fb[2]=2;
unsigned long i, j, pos;
for(i=3 ; i<=50 ; i++){
fib[i] = fib[i-2] + fib[i-1];
fb[i] = fib[i];
}
int T;
unsigned long n, ln, k=1, maxx=0, p=0, tm;
char ch;

//freopen("in-11385.txt","r",stdin);
//freopen("out-11385.txt","w",stdout);
scanf("%d",&T);
while(T){
k=1;
scanf("%lu",&n);
for(i=1 ; i<=n ; i++){
scanf("%lu",&ctxt[i]);
if(maxx < ctxt[i]){
maxx = ctxt[i];
}
}

gets(in);
ln=strlen(in);
if(n>0 && ln>0){
for(i = 0 ; i < ln ; i++){
if(in[i]>='A' && in[i]<='Z'){
tmp[k] = in[i];
k++;
}
}
int fg=0;
for(i = 1 ; i < 50 ; i++){
if(maxx == fb[i]){
pos=i;
fg=1;
}
}
if (fg==0) pos=49;
int fnf=1;
for(i=1 ; i<=pos ; i++ ){
tm = fb[i];
int fag=0, pss;
for(j=1 ; j<=n ; j++){
if(tm == ctxt[j]){
fag=1;
pss=j;
break;
}
}
if(fag==1){
if(tmp[pss]>='A' && tmp[pss]<='Z'){
pr[i] = tmp[pss];
}
}
else pr[i]=' ';
fnf++;
}
fnf -= 1;
if(fnf==pos){
for(i = 1 ; i <= pos ; i++){
if( (pr[i]>='A' && pr[i]<='Z') || pr[i]==' '){
printf("%c",pr[i]);
if(i==pos) {T--; fnf=0;}
}
}
printf("\n");
}

memset(in,'\0',sizeof(in));
memset(tmp,'\0',sizeof(tmp));
memset(pr,'\0',sizeof(pr));
memset(ctxt,0,sizeof(ctxt));

}
}
return 0;
}

``````

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

### Re: 11385 - Da Vinci Code

Add the line: while(getchar()!='\n'); before gets(), then you'll get PE.
Check input and AC output for thousands of problems on uDebug!

saiful_1105020
New poster
Posts: 1
Joined: Thu Mar 28, 2013 9:01 pm

### Re: 11385 - Da Vinci Code

Why getting WA???

#include <stdio.h>
#include <math.h>
#include <string.h>
long long int fib[777];
int fib_series(void)
{
fib[0]=1;
fib[1]=2;
int i=2;
while(fib[i-1]<pow(2,31))
{
fib=fib[i-1]+fib[i-2];
i++;
}
return i-1;
}
int main(void)
{
int a=0,n,t,r;
scanf("%d",&t);
while(a<t)
{
long long int num[111];
char str[1111],fin[111],res[111];
for(r=0;r<111;r++)
{
res[r]=' ';
}
scanf("%d",&n);
if(n==0)
{
a++;
continue;
}
int p,b,c=0,d;
for(p=0;p<n-1;p++)
{
scanf("%lld",&num[p]);
}
scanf("%lld %[^'\n']s",&num[p],str);
d=strlen(str);
for(b=0;b<d;b++)
{
if(('A'<=str)&&('Z'>=str))
{
fin[c]=str;
c++;
}
}
fin[c]='\0';
int f,g,h=fib_series(),maxg=-1;
for(f=0;f<n;f++)
{
for(g=0;g<h;g++)
{
if(num[f]==fib[g])
{
if(f<=c) res[g]=fin[f];

if(g>maxg) maxg=g;
}
}
}
res[maxg+1]='\0';
int l=strlen(res),m;
for(m=0;m<maxg;m++)
{
if(('A'>res[m])||(res[m]>'Z')) res[m]=' ';
}
printf("%s\n",res);
a++;
}
return 0;
}

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

### Re: 11385 - Da Vinci Code

Change the way you parse the input.
using:
gets(str)
scanf("%[^'\n']s",str)
will make your code AC.
Check input and AC output for thousands of problems on uDebug!

Leira
New poster
Posts: 1
Joined: Mon Apr 01, 2013 8:18 pm

### Re: 11385 - Da Vinci Code

hi there, I'm new to c and cpp but below is the solution i have using cpp. i have no idea why my string has some trailing characters at the end. I tried to null terminate the string as well but it does not seemed to have any effect. THANKS for your help in advance..

Code: Select all

``````#include <iostream>
#include <string>
#include <algorithm>

using namespace std;
int findpos(long a, long b[]) {
int i = 45;
while(i >= 0) {
if(b[i] == a) {
return i;
}
i--;
}
return i;
}

int main() {
long fib[46];
long next = 0;
long first = 1;
long second = 1;
int j = 0;
for (long c = 1 ; next < 1836311904 ; c++ ) {
if ( c <= 1 )
next = c;
else {
next = first + second;
first = second;
second = next;
}
fib[j] = next;
j++;
}

int T,N;
cin >> T;
for(int i = 0; i < T; i++) {
cin >> N;
long pos[N];
long m = 0;
for(int j = 0; j < N; j++) {
cin >> pos[j];
m = max(m, pos[j]);
}
string line;
getline(cin, line);
getline(cin, line);
int p = findpos(m, fib);
char ans[p+1];
int j = 0;
for(int k = 0; k < p+1; k++) {
ans[k] = ' ';
}
int k = 0;
int len = line.length();
while (k < len && j < N) {
if(isupper(line[k])) {
int p = findpos(pos[j], fib);
ans[p] = line[k];
j++;
}
k++;
}
cout << ans << endl;
}
}
``````

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

### Re: 11385 - Da Vinci Code

You need to increase the size of ans. For the first sample input your code is generating p=12, for the second p=16. Those aren't large enough to hold the output.
Check input and AC output for thousands of problems on uDebug!