11385 - Da Vinci Code

[joshi13]

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.
Thanks in advance.

Code: Select all

 ACC      
         
        

[rio]

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]

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]

Hi joshi!, im not sure, but i think there may be leading blank spaces. gl! Eric.

[rio]

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]

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]

Hi
I try this problem, but I get wa, can you post some input.
here is my code

Code: Select all

Got Ac!

[rio]

Input:

Code: Select all

2
1
5
A
3
3 2 1
aBc

Output:

Code: Select all

   A
  B

-----
Rio

[Mata]

thanks, i changed my code, i got Ac.

[emotional blind]

Wrong Answer

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]

#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]

Code: Select all

ACC

Rajib, sust

[raj_bd]

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]

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.

[sazzadcsedu]

Acc.