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

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

11385 - Da Vinci Code

Post by joshi13 » Mon Jan 14, 2008 5:21 am

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      
         
        
Last edited by joshi13 on Mon Jan 14, 2008 6:33 am, edited 2 times in total.

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

Post by rio » Mon Jan 14, 2008 5:32 am

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

Post by joshi13 » Mon Jan 14, 2008 5:36 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

Post by sonyckson » Mon Jan 14, 2008 5:49 am

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

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

Post by rio » Mon Jan 14, 2008 5:55 am

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
Location: Madrid

Post by mpi » Mon Jan 14, 2008 11:55 am

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!

User avatar
Mata
New poster
Posts: 18
Joined: Mon Dec 17, 2007 11:35 pm
Location: Queretaro
Contact:

Post by Mata » Wed Jan 16, 2008 5:17 pm

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.

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

Post by rio » Thu Jan 17, 2008 4:06 am

Input:

Code: Select all

2
1
5
A
3
3 2 1
aBc
Output:

Code: Select all

   A
  B
-----
Rio

User avatar
Mata
New poster
Posts: 18
Joined: Mon Dec 17, 2007 11:35 pm
Location: Queretaro
Contact:

Post by Mata » Thu Jan 17, 2008 6:15 am

thanks, i changed my code, i got Ac.

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

Post by emotional blind » Sat Mar 01, 2008 3:25 am

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
New poster
Posts: 6
Joined: Fri Jul 18, 2008 9:29 pm

11385 - Da Vinci Code

Post by samin » Tue Jul 22, 2008 11:13 pm

#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
Location: SUST , Sylhet, Bangladesh

help :: 11385 - Da Vinci Code

Post by rajib_sust » Sun Aug 17, 2008 11:29 pm

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

Post by raj_bd » Wed Feb 11, 2009 10:11 pm

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
Location: Dhaka, Bangladesh
Contact:

Re: 11385 - Da Vinci Code

Post by Jan » Mon Feb 16, 2009 12:50 pm

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

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

11385 - Da Vinci Code

Post by sazzadcsedu » Tue Jun 30, 2009 10:19 pm

Acc.
Last edited by sazzadcsedu on Tue Aug 31, 2010 8:55 pm, edited 1 time in total.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

Post Reply

Return to “Volume 113 (11300-11399)”