10887 - Concatenation of Languages

[[_TANG_]]

Hi,

Can anyone tell me why does the input:

Code: Select all

1
3 3
a

b
a

b

outputs:

Code: Select all

Case 1: 7

Think that's why I can't get AC ... ... My code output is 6

[mamun]

I should think the concatenated words are

• 1. aa
  2. a
  3. ab
  4.
  5. b
  6. ba
  7. bb

I couldn't get it accepted either, TLE.

[[_TANG_]]

Hello,

I've a strange problem, when I debug my code with an input containing empty strings (hardcoded) its output is correct but if I try to run my code at console like this:

code.exe < input.txt > output.txt

Doesn't recognize the empty string ... I think is because of this:

Code: Select all

cin >> A >> B;

		if(A && B)
		{
			count = 0;

			for(d = 0; d < A; d++)
				cin >> vectorA[d];

			for(d = 0; d < B; d++)
				cin >> vectorB[d];

...

I read from input and copy into an array the languages then I find the count of different words.

Is there other way to catch the input and recognize the empty string?

Thnx.

[mamun]

cin skips whitespaces unless skipws flag is off.

[Soarer]

Hi,

Can anyone tell me why does the input:

Code: Select all

1
3 3
a

b
a

b

outputs:

Code: Select all

Case 1: 7

Think that's why I can't get AC ... ... My code output is 6

why is this a valid input?

You can assume that the strings are formed by lower case letters (

[Soarer]

By the way, I need some i/o as well.. thanks.

[Martin Macko]

[quote="Soarer"]why is this a valid input?

You can assume that the strings are formed by lower case letters (

[Martin Macko]

By the way, I need some i/o as well.. thanks.

input:

Code: Select all

5
20 20
aaaaaaaaaa
aaaaaaaaa
aaaaaaaa
aaaaaaa
aaaaaa
aaaaa
aaaa
aaa
aa
a
baaaaaaaaa
baaaaaaaa
baaaaaaa
baaaaaa
baaaaa
baaaa
baaa
baa
ba
b
aaaaaaaaaa
aaaaaaaaa
aaaaaaaa
aaaaaaa
aaaaaa
aaaaa
aaaa
aaa
aa
a
aaaaaaaaab
aaaaaaaab
aaaaaaab
aaaaaab
aaaaab
aaaab
aaab
aab
ab
b
2 2
gas

gadf

1 1


1 1
a
a
5 1
gfegtwg
wgtwgtrweg
trwgtrwg
trwgrwg
trwgtgg
trwgtgg

output:

Code: Select all

Case 1: 76
Case 2: 4
Case 3: 1
Case 4: 1
Case 5: 5

[Jehad Uddin]

i have got ac,using set,bt its too slow,any faster idea??

[sazzadcsedu]

I submitted the following algorithm but got TLE. How can i improve running time .someone plz help.Is stl map not enough???
here my code

Code: Select all

 Acc.

Using set instead of using map got Acc.

[Shafaet_du]

getting tle after tle . I tried trie. I dont know how to write hash function yet.

[nymo]

As some posters said that it is possible to get AC with stl set. I am getting tle... I wonder how they did that...

[Karcher]

i got quite curious about this issue (getting AC with stl set), but found no exact answer. Is cell phone spy anybody in the know?

[plamplam]

I got Accepted with STL map, just don't use cin/getline, use gets() you should pass the Time Limit.

[hpjhc]

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <string>
#include <cstring>
using namespace std;

int hash(string );
int insert(int );
string st1[1510], st2[1510];
int head[1000003], next[2250010];
string queue[2250010];

int main(void)
{
int t, a, b, i, j, k, cnt = 0;
scanf("%d", &t);
while(t--)
{
scanf("%d%d", &a, &b);
for(i = 0; i < a; i++)
cin>>st1;
for(i = 0; i < b; i++)
cin>>st2;
k = 1;
memset(head, 0, sizeof(head));
memset(next, 0, sizeof(next));
for(i = 0; i < a; i++)
for(j = 0; j < b; j++)
{
queue[k] = st1+st2[j];
if(insert(k))
k++;
}
printf("Case %d: %d\n", ++cnt, k-1);
}
return 0;
}

int hash(string str)
{
int hash = 0, seed = 31;
for(int i = 0; i < str.size(); i++)
hash = hash*seed+str;
return (hash & 0x7fffffff) % 1000003;
}

int insert(int s)
{
int h = hash(queue[s]);
int u = head[h];
while(u)
{
if(queue == queue[s])
return 0;
u = next;
}
next[s] = head[h];
head[h] = s;
return 1;
}