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

dragon135
New poster
Posts: 2
Joined: Sat May 23, 2009 8:31 am

Re: 11385 - Da Vinci Code

Post by dragon135 » Sat Feb 06, 2010 12:04 pm

HI, can anyone please give me some input b'cos my below program is wrong answered..
don't know why..

Code: Select all

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

#define KEYLENMAX   100
int key[KEYLENMAX];
char teks[KEYLENMAX+1],res[KEYLENMAX+1];

int main(){
  int i,n,j,keylen,len,lastidx,max,idx;
  scanf("%d",&n);
  for(j=0;j<n;++j){
    scanf("%d",&keylen);
    for(i=0;i<keylen;++i)scanf("%d",key+i);
    gets(teks);
    gets(teks);    
    len=strlen(teks);
    lastidx=-1;
    for(i=0;i<len;++i)
      if(isupper(teks[i]))teks[++lastidx]=teks[i];
    ++lastidx;
    max=0;
    memset(res,' ',sizeof(res));
    if(keylen>lastidx)keylen=lastidx;
    for(i=0;i<keylen;++i){
      switch(key[i]){
        case 1: idx=1;break;
        case 2: idx=2;break;
        case 3: idx=3;break;
        case 5: idx=4;break;
        case 8: idx=5;break;
        case 13: idx=6;break;
        case 21: idx=7;break;
        case 34: idx=8;break;
        case 55: idx=9;break;
        case 89: idx=10;break;
        case 144: idx=11;break;
        case 233: idx=12;break;
        case 377: idx=13;break;
        case 610: idx=14;break;
        case 987: idx=15;break;
        case 1597: idx=16;break;
        case 2584: idx=17;break;
        case 4181: idx=18;break;
        case 6765: idx=19;break;
        case 10946: idx=20;break;
        case 17711: idx=21;break;
        case 28657: idx=22;break;
        case 46368: idx=23;break;
        case 75025: idx=24;break;
        case 121393: idx=25;break;
        case 196418: idx=26;break;
        case 317811: idx=27;break;
        case 514229: idx=28;break;
        case 832040: idx=29;break;
        case 1346269: idx=30;break;
        case 2178309: idx=31;break;
        case 3524578: idx=32;break;
        case 5702887: idx=33;break;
        case 9227465: idx=34;break;
        case 14930352: idx=35;break;
        case 24157817: idx=36;break;
        case 39088169: idx=37;break;
        case 63245986: idx=38;break;
        case 102334155: idx=39;break;
        case 165580141: idx=40;break;
        case 267914296: idx=41;break;
        case 433494437: idx=42;break;
        case 701408733: idx=43;break;
        case 1134903170: idx=44;break;
        case 1836311903: idx=45;break;
      }
      res[idx-1]=teks[i];
      if(idx>max)max=idx;
    }
    res[max]='\0';
    puts(res);
  }
  return 0;
}

aliahmed
New poster
Posts: 24
Joined: Fri Oct 24, 2008 8:37 pm
Location: CUET, Chittagong, Bangladesh
Contact:

Re: 11385 - Da Vinci Code

Post by aliahmed » Sat Mar 20, 2010 10:35 am

Remove after ACC
Last edited by aliahmed on Sun Mar 28, 2010 12:06 am, edited 1 time in total.

naseef_07cuet
Learning poster
Posts: 62
Joined: Sat Nov 21, 2009 10:17 pm
Location: CUET,Chittagong,Bangladesh

Re: 11385 - Da Vinci Code

Post by naseef_07cuet » Sat Mar 20, 2010 12:04 pm

Code: Select all

//code removed after AC
Last edited by naseef_07cuet on Sat Mar 20, 2010 10:06 pm, edited 2 times in total.
If you have determination, you can do anything you want....:)

naseef_07cuet
Learning poster
Posts: 62
Joined: Sat Nov 21, 2009 10:17 pm
Location: CUET,Chittagong,Bangladesh

Re: 11385 - Da Vinci Code

Post by naseef_07cuet » Sat Mar 20, 2010 6:53 pm

Still PE please help:(...
If you have determination, you can do anything you want....:)

naseef_07cuet
Learning poster
Posts: 62
Joined: Sat Nov 21, 2009 10:17 pm
Location: CUET,Chittagong,Bangladesh

Re: 11385 - Da Vinci Code

Post by naseef_07cuet » Sat Mar 20, 2010 10:05 pm

Got it.....Accepted....thanks... :D
If you have determination, you can do anything you want....:)

RehabReda
New poster
Posts: 5
Joined: Thu Dec 03, 2009 8:25 pm

Re: 11385 - Da Vinci Code

Post by RehabReda » Sat Aug 28, 2010 6:47 pm

hi all
i get wrong answer and don't know why ?
is there any test cases ?

Code: Select all


#include<iostream>
using namespace std;
char output[101];
int inputPositions[100];
char inputCharacters[101];
int main()
{
	freopen("acm.txt","r",stdin);
	int noOfTestCases;
	cin>>noOfTestCases;

	for(int i=0;i<noOfTestCases;i++)
	{
		memset(output,' ',100);
		int noOfCharacters;
		cin>>noOfCharacters;
		for(int j=0;j<noOfCharacters;j++)
		{
			cin>>inputPositions[j];
		}
		char c;
		int counter=0;
		while(cin>>c && counter<noOfCharacters)
		{
			if(c>='A'+0&&c<='Z'+0)
			{
				inputCharacters[counter]=c;
				counter++;
			}

		}
		int found=0;
		int firstNumber=1;
		int secondNumber=1;
		int count=0;
		while(found<noOfCharacters)
		{
			int temp=secondNumber;
			secondNumber=secondNumber+firstNumber;
			firstNumber=temp;
			for(int m=0;m<noOfCharacters;m++)
			{
				if(inputPositions[m]==firstNumber)
				{

					output[count]=inputCharacters[m];
					found++;
					break;
				}
			}
			count++;
		}
		int l=0;
			int counter1=0;
		while(l<noOfCharacters)
		{
			if(output[counter1]>='A'+0&&output[counter1]<='Z'+0)
				l++;
			if(output[counter1]==' ')
				cout<<"#";
			else 
				cout<<output[counter1];

			counter1++;
		}
		cout<<endl;

	}


}

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

Re: 11385 - Da Vinci Code

Post by sazzadcsedu » Tue Aug 31, 2010 8:54 pm

Your program has logical error.Try this-

Code: Select all

input:

1
2
2
5
AxB

output:
<space>A<space>B
your program does not show correct output.
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

Eather
New poster
Posts: 28
Joined: Thu Jan 28, 2010 2:23 pm

11385 - Da Vinci Code

Post by Eather » Fri Oct 29, 2010 10:41 pm

deleted after AC
Last edited by Eather on Fri May 06, 2011 7:10 pm, edited 1 time in total.

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

Re: 11385 - Da Vinci Code

Post by Imti » Fri May 06, 2011 5:33 pm

Can anyone plz help me get rid of this problem??I got WA more than 20 times..I checked closely my code for all input found here..
i)Precomputed all the fibonacci number from 1 to 45.
2)By using binary search I recorded all the position in a array.In
the mean time I also found out maxpos.
3)Initialized an array of char which will be outputted say,"out[]" to blank spaces upto maxpos
4)Then by filtering input string,placed all the upper-case into corresponding position.In the mean time I also found out curmaxpos,which records max value
yet assigned to "out[]",array to set out[curmaxpos+1]='\0'
That's the way I worked out..But couldn't figure out why WA?

Code: Select all

#include<stdio.h>
long memo[100];
long pos(long n)
{
     long s,e,m;
     s=1;e=45;
     while(s<=e)
     {
       m=(s+e)/2;
       if(memo[m]==n)
         return m-1;
       else if(memo[m]>n)
         e=m-1;
       else
         s=m+1;
     }
}
int main()
{
    long kase,n,i,j,maxpos,curmaxpos,a[1000], t;
    char out[1000],str[1000];
    memo[1]=1;memo[2]=2;
    for(i=3;i<=45;i++)
     memo[i]=memo[i-1]+memo[i-2];
    scanf("%ld",&kase);
    while(kase--)
    {
       scanf("%ld",&n);
       maxpos=0;
       for(i=0;i<n;i++)
       {
            scanf("%ld",&t);
            a[i]=pos(t);
            if(a[i]>maxpos)
             maxpos=a[i];
       }
       out[maxpos+1]='\0';
       for(i=0;i<=maxpos;i++)
        out[i]=' ';
       getchar();
       gets(str);
       j=0;
       curmaxpos=-1;
       for(i=0;str[i]!='\0'&&j<=maxpos;i++)
       {
         if(str[i]>='A'&&str[i]<='Z')
         {
             out[a[j++]]=str[i];
             if(a[j-1]>curmaxpos)
              curmaxpos=a[j-1];
         }
       }
       out[curmaxpos+1]='\0';
       printf("%s\n",out);
    }
     return 0;
}

Eather
New poster
Posts: 28
Joined: Thu Jan 28, 2010 2:23 pm

Re: 11385 - Da Vinci Code

Post by Eather » Fri May 06, 2011 7:10 pm

try with some test cases given here (in this discussion board).

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Location: Bangladesh
Contact:

Re: 11385 - Da Vinci Code

Post by Imti » Fri May 06, 2011 7:18 pm

I tried all the input I found here..But still WA..
BTW,can u verify the following case from ur acc code:

Code: Select all

1
2
3 5
jgj

What should be output for it?would it be a string with 4 blank or an empty string?

chengouxuan
New poster
Posts: 10
Joined: Wed Dec 15, 2010 12:32 pm

Re: 11385 - Da Vinci Code

Post by chengouxuan » Mon May 16, 2011 12:36 pm

i think it's a bad description.

sir. manuel
New poster
Posts: 18
Joined: Sat Nov 20, 2010 7:44 pm

Re: 11385 - Da Vinci Code

Post by sir. manuel » Fri May 27, 2011 7:45 am

I think that my solution it's fine but i get WA!!!...this is a stupid problem, have a bad description!!!...very bad!!!!

Code: Select all

#include<stdio.h>
#include<cstring>
#include<cctype>
#include<algorithm>
#include<vector>
#include<iostream>
#define max 109
using namespace std;

int main()
{
    long long int fibo[max];  fibo[1]=1; fibo[2]=2; fibo[0]=0;
       for(int i=3;i<46;i++){fibo[i]=fibo[i-1]+fibo[i-2]; printf("%lld\n",fibo[i]); }
         int casos,c;   scanf("%d",&casos);
         
            while(casos--){
                vector<long long int> nums;
                
                int t,p;  scanf("%d",&t); 
                    int vec[max]; memset(vec,0,sizeof(vec));
                   for(int i=1;i<=t;i++){scanf("%lld",&p); nums.push_back(p);
                   } 
                   string line,var;
                    getline(cin,var);
                   getline(cin,var);  
                  
                   for(int i=0;i<var.length();i++){
                     if(isupper(var[i])){line+=var[i]; }
                   }
                   
                  char vc[max]; memset(vc,' ',max);
                  
              int maximo=0;     
                for(int i=0;i<nums.size();i++){
                   long long int *index=lower_bound(fibo,fibo+47,nums[i]);
                   long long int id=(index-fibo);
                   if(id>maximo){maximo=id;}
                   vc[id-1]=line[i];
               }   
                for(int i=0;i<maximo;i++)printf("%c",vc[i]); puts("");
            }
return 0;    
}

sir. manuel
New poster
Posts: 18
Joined: Sat Nov 20, 2010 7:44 pm

Re: 11385 - Da Vinci Code

Post by sir. manuel » Fri May 27, 2011 8:54 pm

Solved!!!
I use binary search...
The worse error that i had was the "I consider all the nums as fibonaccis", you have to check if it's a fibo...

Eduardo790
New poster
Posts: 2
Joined: Wed Sep 07, 2011 2:02 pm

Re: 11385 - Da Vinci Code

Post by Eduardo790 » Thu Sep 08, 2011 9:53 am

Hi in here.
1. Display all Fibonacci numbers up to 99
2. Display all prime numbers up to 99
3. Display all Fibonacci numbers that are also prime numbers up to 99
4. Display 5 randomly generated prime numbers between 1 and 1000
I don't have the exact idea on how to get through my choices 1 - 4!How to display cell phone spy the fibonaccis until number entered, prime numbers etc
this is what i got so far.....

Post Reply

Return to “Volume 113 (11300-11399)”