Page 2 of 3
Posted: Wed Nov 23, 2005 4:03 pm
by polone
some words are reduplicate at the begining
these part shouldn't be done twice
tree can help you to solve
Posted: Wed Nov 23, 2005 8:10 pm
by Tamagodzi
Dont know whats wrong with input yet. But this simple input checker gets tle
Code: Select all
#include <iostream>
#include <string>
using namespace std;
string s;
char c;
int t,d,q,m,n,i,j;
int main()
{
cin >> t;
while(t--)
{
cin >> d;
while(d--)
{
cin >> s;
}
cin >> q;
while(q--)
{
cin >> m >> n;
cin.get();
while(m--)
{
getline(cin,s);
}
}
}
return 0;
}
Posted: Thu Nov 24, 2005 11:55 am
by Moha
Read Character by character instead of reading line by line. It works OK!
Posted: Wed Nov 30, 2005 10:20 pm
by Emilio
Hello all!
I was getting strange WAs, and then decided to make some input checkers. In the next lines I expose these input checkers and what are the OJ's replies.
input_checker_1
Code: Select all
int main ()
{
int T, D, Q, M, N, i, j, k;
char s[2005];
cin >> T;
assert(T>=1 && T<=10);
for (k=1; k<=T; k++)
{
cin >> D;
assert(D>=1 && D<=15000);
for (i=0; i<D; i++) cin >> s;
cin >> Q;
assert(Q>=1 && Q<=100);
for (j=1; j<=Q; j++)
{
cin >> M >> N;
assert(M>=1 && M<=100 && N>=1 && N<=100);
for (i=0; i<M; i++) cin >> s;
}
}
return 0;
}
The reply is WA in 0.002
input_checker_2
Code: Select all
int main ()
{
int T, D, Q, M, N, i, j, k;
char s[2005];
cin >> T;
assert(T>=1 && T<=10);
while (T--)
{
cin >> D;
assert(D>=1 && D<=15000);
while (D--) cin >> s;
cin >> Q;
assert(Q>=1 && Q<=100);
while (Q--)
{
cin >> M >> N;
assert(M>=1 && M<=100 && N>=1 && N<=100);
while (M--) cin >> s;
}
}
return 0;
}
The reply is RE in 0.002
input_checker_3
Code: Select all
int main ()
{
int T, D, Q, M, N, i, j, k;
char s[2005];
cin >> T;
while (T--)
{
cin >> D;
while (D--) cin >> s;
cin >> Q;
while (Q--)
{
cin >> M >> N;
while (M--) cin >> s;
}
}
return 0;
}
The reply is TLE
Well, Could anyone say me what is the reason?
And by other hand, what is correct manner to make a good parse input?
Thanks!
I'm waitting some interesting reply
Posted: Wed Nov 30, 2005 10:31 pm
by Moha
As is said before, For reading the input matrix for this problem, you should read it, character by character, so, instead of reading m line, read m*n character!
Posted: Thu Dec 01, 2005 2:43 am
by Emilio
To Moha:
Ok! The matrix m*n chars? I think m*(n+1) with '\n', or do you refer to valid chars only(lower case)?
And how do you read the rest of the input?
for ints -> scanf, cin, char by char?
for the words -> scanf, cin, char by char?
The size of your matrix is 101x101?
Thanks a lot of, in advance!
I have got about 35 WAs, REs, TLEs.
I have tested a lot of different methods, char by char, line by line, cin, gets, getc, getchar.
Is something wrong in the input specification?
Is the file input corrupted?
What is the reason why the AC rate is so slow?
Why my previous input checker codes give different answers when they must give the same?
If someone want to post his/her entire parse input method, or someone want describe it detailedly I think will give a lot of joy
Posted: Thu Dec 01, 2005 6:50 am
by Cho
Here is my input code:
Code: Select all
char buf[100000], sq[128][128];
int main()
{
int D, Q, M, N, T, t, k;
for(scanf("%d", &T), t=1; t<=T; t++)
{
scanf("%d", &D);
for(k=0; k<D; k++)
scanf("%s", buf);
scanf("%d", &Q);
for(k=1; k<=Q; k++)
{
scanf("%d %d", &M, &N);
for(i=0; i<M; scanf("%s", sq[i++]));
}
}
return 0;
}
Emilio wrote:Is something wrong in the input specification?
Is the file input corrupted?
I don't think so. I don't get any problem for reading input.
Emilio wrote:What is the reason why the AC rate is so slow?
Maybe, it is because the problem looks quite easy. At least everyone should know how to solve it with a brute-force method. But then, submitting the trivial solution will surely result in TLE.
Posted: Thu Dec 01, 2005 6:08 pm
by Emilio
Thanks Cho!
But I don't know why doesn't work with cin.
Now I have got MLE, I used trie. Well, this is another task, now I can think about other stuffs in this problem.
Posted: Sat Dec 03, 2005 2:53 am
by Tamagodzi
Try to read m and n with cin >> m >> n and surprisingly u will get wa.
Does anyone know whats the difference between cin and scanf("%d.. in reading integers?
There is definitly something wrong around some inputs for m and n which scanf can handle somehow and cin not.
Posted: Sat Dec 03, 2005 3:27 am
by Tamagodzi
My Guess is some input like:
Posted: Sat Dec 03, 2005 11:44 pm
by Moha
I read the entire input with cin, and had no problem.
Reading input wich cin
Posted: Sun Dec 04, 2005 11:55 pm
by Moha
This is my code for reading input:
Code: Select all
main()
{
int tn,ct=0;
string tmp;
for (fin>>tn;tn--;)
{
for(fin>>t;t--; )
fin>>tmp;
int ttn;
fin>>ttn;
for (int tc=0;tc<ttn;tc++)
{
fin>>m>>n;
for(int i=0;i<m;i++)
for (int j=0;j<n;j++)
fin>>table[i][j];
}
}
return 0;
}
Posted: Sat Dec 10, 2005 8:25 pm
by Martin Macko
Tamagodzi wrote:Try to read m and n with cin >> m >> n and surprisingly u will get wa.
Does anyone know whats the difference between cin and scanf("%d.. in reading integers?
There is definitly something wrong around some inputs for m and n which scanf can handle somehow and cin not.
Afaik there is no difference (except that cin>> is much more slower). How do you use it? You probably have a bug in your code.
Re: 10975 TLE
Posted: Sat Dec 10, 2005 9:05 pm
by Martin Macko
Wei-Ming Chen wrote:My code got TLE in this question.
And my method was find the first word, and checked the eight side of it. I thought it was too slow to solve this question. Can someone give me some hints to solve it?
Search for Aho-Corasick algorithm. It's based on KMP algorithm, but searches many patterns in a string at once.
Posted: Sun Dec 11, 2005 1:11 pm
by mf
You can solve it, using a trie data structure to keep the words.
That's simpler to implement than Aho-Corasick.