Обсуждение @ 1435. Финансовая ошибка @ Timus Online Judge

Показать все сообщения Спрятать все сообщения

I think it's the fastest, but TLE - ??? KAV 4 мар 2006 10:56

I use such an algorithm:
SumNeed - the last number in the input, what it's need to have
sum - the physical sum of all numbers
If ( SumNeed - sum ) does not divide by 9 - unrecoverable error.
Else ( SumNeed - sum ) / 9 is the difference between swapped digits. So I look through all the numbers, and if there are digits with difference ( SumNeed-sum )/9 - it is the mixed number.
On my computer when N=1500000 it works nearly 0.1 sec, and how it gets TLE - I can't even imagine. :(

[code cut]

Edited by moderator 16.03.2009 01:25

Re: I think it's the fastest, but TLE - ??? Burmistrov Ivan (USU) 4 мар 2006 21:58

Use scanf()!
I had same problem. But now I have WA #45 :( Any hints? :)

Re: I think it's the fastest, but TLE - ??? Burunduk1 5 мар 2006 01:36

The fastest one:
Don't read numbers as integers!
Read it as string or char[]
This way brings AC 0.18 sec

PS:
In such problems (input data is large and TL is small)
don't use scanf or cin to read integer numbers.

Re: I think it's the fastest, but TLE - ??? KAV 5 мар 2006 15:53

So, you think that the algorithm is good, but reading input takes all the time? Well, I will try to change, to read strings. Thanks!

Re: I think it's the fastest, but TLE - ??? KAV 9 мар 2006 09:17

Thanks to all, I have converted the algorithm into strings, now it is about 0.25 sec.
But - WA 45 :( I can't guess why. Is unsigned __int64 enough?
Burmistrov Ivan (USU), you told that you also had WA 45. Have you overcome this problem?

Have you read updated problem statement? Vladimir Yakovlev (USU) 9 мар 2006 12:32

Re: Have you read updated problem statement? KAV 9 мар 2006 17:11

It's very strange!!!
Statement: "Each of the next N lines contains a corresponding non-negative integer summand (not exceeding 2^31-1)."
2^31 is 2147483648 - 10 symbols.
All input numbers I kept in char[11] and got WA.
When I changed the type into char[12] - I got Accepted!!!
How to explain it? ;)

!!! No question. My stupid fault :(

YES, AC 0.171 8-)

Edited by author 09.03.2006 17:22

Re: I think it's the fastest, but TLE - ??? Burmistrov Ivan (USU) 9 мар 2006 16:21

Now I have WA #46 :( In 45-th test correct number more than 2^31-1, I think. But what is 46-th test?

Re: I think it's the fastest, but TLE - ??? Dr.Korbin 10 мар 2006 03:11

I have WA #46 :( What's the problem??!

AC Dr.Korbin 10 мар 2006 03:21

O, I think I undestood, what was wrong.
I had an array "long int a[1500000]", and other variables were __int64. When I corrected "__int64 a[1500000]", my program began to eat 12MB of memory instead of 6MB, but I got AC!!!!

Edited by author 10.03.2006 03:22

Re: AC Dan.hu 25 фев 2007 23:09

u are quite right!
i got AC this way,too! Thx u for ur hints!
but does it mean the judge writer use number greater than 2^31-1? if yes, i have a feeling of being fooled!

Re: I think it's the fastest, but TLE - ??? Igor E. Tuphanov 9 мар 2006 16:27

int64 is quite enough...

Обсуждение задачи 1435. Финансовая ошибка