## 11385 - Da Vinci Code

Moderator: Board moderators

ashdboss
New poster
Posts: 16
Joined: Fri May 17, 2013 8:59 am

### Re: 11385 - Da Vinci Code

this input sets consider almost all kind of input for this problem.thanks for the inputs

helli3papa
New poster
Posts: 8
Joined: Wed Apr 11, 2012 5:48 pm

### Re: 11385 - Da Vinci Code

Hi all
I got TLE for this problem
Some Body Help me plz
TY

Code: Select all

#include <iostream>
#include <string>

using namespace std;

typedef long long ll;

ll fib(ll n)
{
if(n == 0)
return 1;
if(n == 1)
return 1;
if(n == 2)
return 2;
return fib(n - 1) + fib(n - 2);
}
#define isnaleph(ch) if(!((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')))
bool check(string s)
{
for (int i = 0; i < s.size(); i++)
{
isnaleph(s[i])
return false;
}
return true;
}
string back_shift (string s)
{
bool flag = false;
while(flag == false)
{
for (int i = 0; i < s.size(); i++)
{
isnaleph(s[i])
{
for (int j = i; j < s.size() - 1; j++)
s[j] = s[j + 1];
s.resize(s.size() - 1);
}
}
flag = check(s);
}
return s;
}
ll spaces (string s)
{
ll k = 0;
for (int i = 0; i < s.size(); i++)
isnaleph(s[i])
k++;
return k;
}

string getallup (string s)
{
for (int i = 0; i < s.size(); i++)
if(s[i] >= 'a' && s[i] <= 'z')
s[i] = char(int(s[i]) - 32);
return s;
}
int main()
{
int n;
cin >> n;
ll a[110] = {0};
string s;
for (int i = 0; i < n; i++)
{
int r;
cin >> r;
for (int j = 0; j < r; j++)
cin >> a[j];
string str = "";
getline(cin, s);
getline(cin, s);
ll sp = spaces(s);
s = back_shift(s);
for (int j = 0; j < r + sp; j++)
{
bool flag = false, flag2 = false;
int no = 0, l = 0;
for (int k = 0; k < r; k++)
{
if(fib(j + 1) == a[k])
{
str += s[k];
flag = true;
break;
}
}
if(flag == false)
str += ' ';
}
str = getallup(str);
cout << str << endl;
}
}

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

### Re: 11385 - Da Vinci Code

Don't print spaces at the end of a line.
C I/O is faster than C++ I/O.
Check input and AC output for thousands of problems on uDebug!

helli3papa
New poster
Posts: 8
Joined: Wed Apr 11, 2012 5:48 pm

### Re: 11385 - Da Vinci Code

Thank You brainfry
But Where I put space?
and I don't know about string in scanf

ijabir
New poster
Posts: 3
Joined: Thu Sep 26, 2013 5:42 pm

### Getting WA - 11385 - Da Vinci Code

anyone pls help me out
here is my code

Code: Select all

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

using namespace std;

int fbn[100];

void fibon(void)
{
fbn[0]=1, fbn[1]=2;
for(int r=2; r<41; r++)
fbn[r] = fbn[r-1] + fbn[r-2];
}

int main()
{
//    freopen("in.txt", "r", stdin);
int t, cs=0; cin>>t;
int n, i, j, r, nm[100], mx;
char s[100], f[100], res[100];
fibon();
//    for(int r=0; r<41; r++)
//    cout<<fbn[r]<<" ";
while(t--)
{
memset(s, 0, sizeof(s));
memset(f, 0, sizeof(f));
memset(res, 0, sizeof(res));
mx=0;
cin>>n;
for(i=0; i<n; i++)
{
cin>>nm[i];
}
getchar();
gets(s);
for(i=0, j=0; s[i]!='\0'; i++)
if('A'<=s[i] && s[i]<='Z') f[j++]=s[i];
f[j]='\0';
//puts(f);
for(i=0; i<n; i++)
{
for(r=0; r<41; r++)
{
if(nm[i]==fbn[r])
{
res[r]=f[i];
if(r>mx)mx=r;
break;
}
}
}
for(i=0; i<mx; i++)
if('A'>res[i] || res[i]>'Z') res[i]=' ';
res[mx+1]='\0';
if(cs++!=0) cout<<endl;
for(i=0; res[i]!='\0'; i++)
cout<<res[i];
}
return 0;
}

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

### Re: Getting WA - 11385 - Da Vinci Code

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

damihen
New poster
Posts: 1
Joined: Fri Nov 22, 2013 8:16 pm

### Re: Getting WA - 11385 - Da Vinci Code

Could anyone help me please.. im stuck on it...
Thx

Code: Select all

#include <iostream>
#include <stdio.h>
#include <cstdlib>
#include <cstring>

using namespace std;

int main(){

long long int fib[47];
fib[0]=1;
fib[1]=2;
for(int i=2;i<=46;i++)
fib[i]=fib[i-1]+fib[i-2];

///////////////////// FIB

int n, qt, c, maior, menor;
long long int v[1000];
char word[1002], nova[1002];
bool foi[1000];

scanf("%d",&n);

for(int j=0;j<n;j++){
c=0;
maior=0;
menor=100;
scanf("%d",&qt);

for(int i=0;i<qt;i++)
scanf("%lld",&v[i]);

for(int i=0;i<100;i++)
foi[i]=false;

memset(nova,'0', sizeof(nova));

getchar();
gets(word);

for(int i=0;i<strlen(word);i++){
if(isalpha(word[i])){
for(int k=0;k<46;k++){
if(fib[k]==v[c]){
foi[k]=true;
if(k>maior) maior=k;
if(k<menor) menor=k;
nova[k]=word[i];
c++;
k=48;
}
}
}
}

for(int i=menor;i<maior;i++){
if(!foi[i])
nova[i]=' ';
}

nova[maior+1]='\0';

for(int i=0;nova[i]!='\0';i++)
cout<<nova[i];

printf("\n");

}

return 0;
}

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

### Re: Getting WA - 11385 - Da Vinci Code

Input:

Code: Select all

1
1
8
A
Output should be:

Code: Select all

A
Check input and AC output for thousands of problems on uDebug!

techbd123
New poster
Posts: 14
Joined: Tue Aug 06, 2013 3:42 pm

### Re: 11385 - Da Vinci Code

Why wa???

[Removed as it was AC then]
Last edited by techbd123 on Wed Dec 04, 2013 5:33 am, 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

Line 34: use %d to read an int.
Why is str unsigned?
Check input and AC output for thousands of problems on uDebug!

techbd123
New poster
Posts: 14
Joined: Tue Aug 06, 2013 3:42 pm

### Re: 11385 - Da Vinci Code

Guru! Thanks.

And I made unsigned char for str though it was unnecessary, it could be only char type too.

Kenpachi24
New poster
Posts: 20
Joined: Wed Oct 30, 2013 7:06 pm

### Re: 11385 - Da Vinci Code

Code: Select all

AC; THANKS brianfry713
My problem in this exercise was the input of numbers separated by several blank spaces; as I work with java I Solve the problem with StringTokenizer.

Example:
Input

Code: Select all

2
11
13    2      89         377        8         3 233 34    144    21      1
OH, LAME SAINT!
15
34   21   13    144 1597 3 987 610 8 5 89        2 377 2584            1
O, DRACONIAN DEVIL!

Before:

Code: Select all

String arreglo[]=numeros.split(" ");

//ERROR
After:

Code: Select all

StringTokenizer tk= new StringTokenizer(numeros);
int cont=0;
while(tk.hasMoreTokens()){
int arreglo[cont]=tk.nextToken();
cont++;
}
//GOOD
Last edited by Kenpachi24 on Wed Feb 12, 2014 10:26 am, 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

Try input:

Code: Select all

2
11
13    2 89 377 8 3 233 34  144 21 1
OH, LAME SAINT!
15
34 21 13 144 1597 3 987 610 8 5 89 2 377 2584 1
O, DRACONIAN DEVIL!
Check input and AC output for thousands of problems on uDebug!

Kenpachi24
New poster
Posts: 20
Joined: Wed Oct 30, 2013 7:06 pm

### Re: 11385 - Da Vinci Code

Code: Select all

AC, THANKS brianfry713
Last edited by Kenpachi24 on Wed Feb 12, 2014 10:28 am, 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

Try fixing your code to work on the input I posted, it's the same as the sample input with some extra spaces.
Check input and AC output for thousands of problems on uDebug!