## 11385 - Da Vinci Code

Moderator: Board moderators

joshi13
New poster
Posts: 9
Joined: Sun Jan 06, 2008 3:18 am

### 11385 - Da Vinci Code

Hi, i'm trying to solve this problem.
I do the following:

- Precompute all fibonacci numbers up to fib(46).
- For each character of cypher, if is apha, then look for its correct position
in the output string.
- Output string.

But i am getting WA.

Code: Select all

`````` ACC

``````
Last edited by joshi13 on Mon Jan 14, 2008 6:33 am, edited 2 times in total.

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
From description:

Code: Select all

``````Note that only uppercase letters conveys the message; other characters are simply garbage.
``````
I think it means you should consider only upper case letters in the chiper.
-----
Rio

joshi13
New poster
Posts: 9
Joined: Sun Jan 06, 2008 3:18 am
Well i changed the line:

Code: Select all

``if(isalpha(line[k])``
to

Code: Select all

``if(isupper(line[k]))``
but this still gives WA. dont know why.

Thanks.

sonyckson
New poster
Posts: 49
Joined: Tue Feb 06, 2007 9:29 pm
Location: Cordoba, Argentina
Hi joshi!, im not sure, but i think there may be leading blank spaces. gl! Eric.

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
This is not written in the description clearly, but there could be cases like:

Code: Select all

``````3
2 3 1
ABCDEFG
``````
The fibonacci series ends up before the chiper ends. I got AC outputing:

Code: Select all

``````CAB
``````
And you don't need this line.

Code: Select all

``````while(out[i] == ' ') i++;
``````
Just trim trailing spaces.
-----
Rio

mpi
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm
I agree with Rio. That's the last error I had to fix before getting AC. Please, don't assume that the number of uppercase letters in the cypher text is always equal to the number of uppercase letters in the plain text!

Mata
New poster
Posts: 18
Joined: Mon Dec 17, 2007 11:35 pm
Location: Queretaro
Contact:
Hi
I try this problem, but I get wa, can you post some input.
here is my code

Code: Select all

``````Got Ac!
``````
Last edited by Mata on Thu Jan 17, 2008 8:05 pm, edited 3 times in total.

rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan
Input:

Code: Select all

``````2
1
5
A
3
3 2 1
aBc
``````
Output:

Code: Select all

``````   A
B
``````
-----
Rio

Mata
New poster
Posts: 18
Joined: Mon Dec 17, 2007 11:35 pm
Location: Queretaro
Contact:
thanks, i changed my code, i got Ac.

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Contact:

Code: Select all

``````#include <iostream>
#include <cstdio>
#include <cstring>
#include <cctype>
#include <cstdlib>
#include <assert.h>

using namespace std;

int fib[47];
int fibind(int n){
int left = 1;
int right = 45;
int mid;
while(left<right){
mid=(left+right)/2;
if(fib[mid]==n)return mid;
else if(fib[mid]<n)left=mid+1;
else right=mid-1;
}
return left;
}

int main (void){
int i;
fib[0]=fib[1]=1;
for(i=2;i<=46;++i){fib[i]=fib[i-1]+fib[i-2];}

char s[200], buff[1000];
char *p;
int c[200], T, N, k, mxpos;
//freopen("input.txt","r",stdin);
gets(buff);
sscanf(buff,"%d",&T);

while(T--){
gets(buff);
sscanf(buff,"%d",&N);
gets(buff);
for(i=0,p=strtok(buff," ");i<N;++i,p=strtok(NULL," ")){
sscanf(p,"%d",&c[i]);
}

for(i=0;i<200;++i)s[i]=' ';s[i]='\0';
gets(buff);
int len = strlen(buff), pos;
k=0;mxpos=0;
for(i=0;i<len && k<N;++i){
if(buff[i]>='A' && buff[i]<='Z'){
pos = fibind(c[k]);
s[pos-1]=buff[i];
if(pos>mxpos)mxpos=pos;
k++;
}
}
s[mxpos]='\0';
printf("%s\n",s);
}

return 0;
}``````
I tried to avoid trailing spaces using mxpos variable. mxpos contains the the position after the last index where an uppercase letter is placed.

samin
New poster
Posts: 6
Joined: Fri Jul 18, 2008 9:29 pm

### 11385 - Da Vinci Code

#include<stdio.h>
int main()
{
unsigned long int a[72],b[52];
int i,n,m,j,max;
char cat[101];
unsigned long int c[52];
char str[101];
a[1]=1,a[2]=2;
for(i=3;i<=50;i++)
{
a = a[i-1]+a[i-2];
}
scanf("%d",&m);
while(m-- > 0)
{
max = 0;
scanf("%d",&n);
for(i=0;i<n;i++)
scanf("%d",&b);
fflush(stdin );
gets(str);
for(j=0;j<n;j++)
{
for(i=1;i<=45;i++)
{
if(a==b[j])
{
c[j] = i;
if(max < i)
max = i;
break;

}
}
}

for(i=0;i<=max;i++)
cat = ' ';
for(i=0,j=0;i<n && str[j];j++)
{
if(str[j] >= 'A' && str[j] <= 'Z')
{
cat[c-1] = str[j];
i++;
}
}
cat[max]='\0';
printf("%s\n",cat);
}
return 0;
}

plz help me.

rajib_sust
New poster
Posts: 16
Joined: Sun Mar 02, 2008 10:34 am

### help :: 11385 - Da Vinci Code

Code: Select all

``````ACC
``````

Rajib, sust
life is beautiful like coding

raj_bd
New poster
Posts: 1
Joined: Wed Feb 11, 2009 8:16 pm

### Re:help me i m getting WA 11385 - Da Vinci Code

here is my code.i hv tried all input..bt still getting WA.

Code: Select all

``````#include<stdio.h>
#include<string.h>
int main()
{

long long a,b,c,i,d=0;
a=0;
b=1;
long long flist[60];
for(i=0;;i++){
c=a+b;
//printf("c=%d\n",c);
flist[d]=c;
if(d==50)
{

break;
}
d++;
b=a;
a=c;
}

long long t1;
scanf("%lld",&t1);

for(i=0;i<t1;i++)
{
long long t2,j=0,ni,k=0,count=0,length=0,len=0,m=0;
long long numlist[500];
char str1[110],str2[110];

scanf("%lld",&t2);

for(j=0;j<t2;j++)
{
scanf("%lld",&ni);
numlist[j]=ni;
}
scanf(" %[^\n]",&str1);
len=strlen(str1);
for(k=0;k<len;k++)
{
if((str1[k]>=65)&&(str1[k]<=90))
{ str2[m]=str1[k];
m++;

}
}
j=0,k=0;
char os[110];
for(j=0;j<m;j++)
{
for(k=1;k<50;k++)
{
if(numlist[j]==flist[k])
{
os[k-1]=str2[count];

count++;
length++;
break;
}
}
}

j=0;
for(j=0;;j++)
{
if(j==length)
{
break;
}
if((os[j]>=65)&&(os[j]<=122))
{

printf("%c",os[j]);
os[j]='\0';
}
else
{
printf(" ");
length=length+1;

}

}

printf("\n");
}
return 0;
}``````

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

### Re: 11385 - Da Vinci Code

Code: Select all

``char os[110];``
Check this line. After declaring it, since you haven't initialized it, so, garbage values will be there. Now, you are assigning some uppercase characters in the array and assuming that the rest don't contain any uppercase character. But since garbage values are there, there can be uppercase characters, too. So, initialize the array with spaces, or use

Code: Select all

``char os[110] = {0};``
Hope it helps.
Ami ekhono shopno dekhi...
HomePage