10975 - Dueue's Quiz

[polone]

some words are reduplicate at the begining
these part shouldn't be done twice

tree can help you to solve

[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;
}

[Moha]

Read Character by character instead of reading line by line. It works OK!

[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

[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!

[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

[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;
}

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.

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.

[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.

[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.

[Tamagodzi]

My Guess is some input like:

Code: Select all

3 3
aaa
bbb
ccc

aaa
bbb
ccc

[Moha]

I read the entire input with cin, and had no problem.

[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;
}

[Martin Macko]

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.

[Martin Macko]

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.

[mf]

You can solve it, using a trie data structure to keep the words.
That's simpler to implement than Aho-Corasick.