10887  Concatenation of Languages
Moderator: Board moderators

 Learning poster
 Posts: 70
 Joined: Sat Feb 05, 2005 9:38 am
 Location: Gurukul
10887  Concatenation of Languages
Hi all,
I want to know how i solve this problem by using Hash. Without hashing is it solvable ? Thanks in advance.
I want to know how i solve this problem by using Hash. Without hashing is it solvable ? Thanks in advance.
Some Love Stories Live Forever ....
any tricky cases?
Are there any tricky cases? I'm getting WA after ~2.2s rather than TLE.
Here are my current test cases, which are fairly trivial to verify by hand:
input:
output:
Here are my current test cases, which are fairly trivial to verify by hand:
input:
Code: Select all
7
3 2
cat
dog
mouse
rat
bat
1 1
abc
cab
5 5
a
aa
aab
abc
ad
a
ab
b
bc
cd
3 3
a
b
a
b
0 0
1 1
a
b
10 0
a
b
c
d
e
f
g
h
i
j
Code: Select all
Case 1: 6
Case 2: 1
Case 3: 24
Case 4: 7
Case 5: 0
Case 6: 1
Case 7: 0
My output is as follow:
Code: Select all
Case 1: 6
Case 2: 1
Case 3: 24
Case 4: 7
Case 5: 0
Case 6: 1
Case 7: 0
how fast?
Someone who got AC, how fast does your program run on the input produced by this program?
Code: Select all
#include <stdio.h>
main() {
int i, j;
char sz[11] = "aaaaaaaaaa";
puts("1\n1500 1500");
for (i = 0; i < 3000; i++) {
puts(sz);
j = 9;
while (sz[j] == 'z') sz[j] = 'a';
sz[j]++;
}
}
I keep getting WA. I do the following
I assume first tht theere are no extra blank lines in input.
then I just consider each test case, and find the mxn possible strings and store them in a set.
I consider empty strings and I use gets to parse the input.
finally I output the size of this set. I don't know where I am wrong.
I don't see why someone needs to use the stl map. stl set is good enough for this problem I think.
I assume first tht theere are no extra blank lines in input.
then I just consider each test case, and find the mxn possible strings and store them in a set.
I consider empty strings and I use gets to parse the input.
finally I output the size of this set. I don't know where I am wrong.
I don't see why someone needs to use the stl map. stl set is good enough for this problem I think.
Try the input output set...
Input:
Output:
Hope it helps.
Input:
Code: Select all
1
3 2
cat
c
ca
at
t
Code: Select all
Case 1: 5
Ami ekhono shopno dekhi...
HomePage
HomePage
Ok, as it gets WA and would be too slow otherwise, I will.mf wrote:Could you show your code?
Code: Select all
#include <cstdio>
#include <vector>
#include <string>
#include <set>
using namespace std;
main() {
char sz[11];
int T, cs = 0;
scanf("%d ", &T);
while (T) {
int m, n;
vector<string> a, b;
scanf("%d %d ", &m, &n);
for (int i = 0; i < m; i++) {
gets(sz);
a.push_back(sz);
}
for (int i = 0; i < n; i++) {
gets(sz);
b.push_back(sz);
}
set<string> st;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
st.insert(a[i]+b[j]);
}
printf("Case %d: %d\n", ++cs, st.size());
}
}
Almost similar code.
Code: Select all
#include <stdio.h>
#include <string>
#include <set>
#include <iostream>
using namespace std;
set<string> first;
set<string> final;
int main()
{
int t, cano=0;
scanf("%d\n", &t);
while(t)
{
int m, n;
string inp;
scanf("%d %d\n", &m, &n);
first.clear();
final.clear();
for(int i=0; i<m; i++)
{
getline(cin, inp);
first.insert(inp);
}
set<string>::iterator st, en;
for(int j=0; j<n; j++)
{
getline(cin, inp);
for(st=first.begin(), en=first.end(); st!=en; st++)
{
final.insert(*st+inp);
}
}
printf("Case %d: %d\n", ++cano, final.size());
}
return 0;
}