10953 - Stochastic Digit Generator

All about problems in Volume 109. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

tywok
New poster
Posts: 32
Joined: Sun Oct 30, 2005 2:22 am

10953 - Stochastic Digit Generator

Post by tywok » Sun Oct 30, 2005 2:28 am

During the contest i spend 4 hours with this problem. I had a little error in the mod calculating part, but the funny thing is, that after i corrected, i still got WA. My last minute attemp was to change all the variables from long double to double. Curiously, i got accepted. Afterwards i checked if you just had to change the variables, and in the OJ i got WA with long double again when my code with double got AC. Should there be a little rejudging? I think it is unfair, since my results should theoretically be more precise!

If anyone wants my code, i can submit it via email
Impossible is nothing

waelsamy
New poster
Posts: 2
Joined: Sun Oct 30, 2005 2:39 am

Reply

Post by waelsamy » Sun Oct 30, 2005 2:40 am

Would u send me ur code plz

waelsamy@gmail.com

zhang
New poster
Posts: 11
Joined: Sun May 22, 2005 11:14 am

Post by zhang » Sun Oct 30, 2005 3:05 am

Maybe I want to ur code,can you send it to zhangfan555@tom.com.
Thanks.
If anyone wants my code, i can submit it via email

tywok
New poster
Posts: 32
Joined: Sun Oct 30, 2005 2:22 am

Post by tywok » Sun Oct 30, 2005 3:53 am

i mean, ill send it for viewing this issue, not for helping others to get WA. If you need help on this problem, ask for it and i will answer!
Impossible is nothing

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » Sun Oct 30, 2005 5:15 am

This problem had a special judge but may be it was not used by mistake.

zhang
New poster
Posts: 11
Joined: Sun May 22, 2005 11:14 am

Post by zhang » Sun Oct 30, 2005 10:30 am

How to solve this problem , I use brute search ,and get TLE.

Rostislav
New poster
Posts: 21
Joined: Sun Oct 05, 2003 11:19 am
Location: Bulgaria, Shoumen
Contact:

Post by Rostislav » Sun Oct 30, 2005 12:12 pm

I had the same problem during the contest.
If i use long double -> WA
but if it is only double -> AC.
And for me this is very strange.

Rostislav

zhang
New poster
Posts: 11
Joined: Sun May 22, 2005 11:14 am

Post by zhang » Sun Oct 30, 2005 1:54 pm

Could you tell me how to sovle this problem?
I get TLE.

tywok
New poster
Posts: 32
Joined: Sun Oct 30, 2005 2:22 am

Post by tywok » Sun Oct 30, 2005 2:13 pm

You have to use DP. Think about how you can use it! :wink:
Impossible is nothing

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sat Nov 05, 2005 12:11 am

I thought this was trivial DP, but maybe my precision is off somewhere.. I've tried double and long double but neither worked.. does anyone have any test cases? =)

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Sat Nov 05, 2005 2:42 am

This problem is easy, but it's also easy to make some silly mistakes (it took me over 30 minutes to figure all signs out, like when to add and when to subtract). I have AC with doubles, but not with long doubles. Some small cases:

Code: Select all

10
0 0.1
1 0.9
2 0
3 0
4 0
5 0
6 0
7 0
8 0
9 0
9
* 0
* 1
*0 10
*0 0
*4 7
*1 0
*** 1
*** 0
************************************************** 0
0
Output:

Code: Select all

Case 1:
0.10000000
0.90000000
0.90000000
0.10000000
0.00000000
0.90000000
0.74700000
0.16300000
0.19087903

Sanny
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:

Post by Sanny » Sat Nov 05, 2005 9:58 am

Krzysztof Duleba wrote:it took me over 30 minutes to figure all signs out, like when to add and when to subtract
Why do you need to subtract?

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Sat Nov 05, 2005 11:15 am

Modulo. Some digit positions contribute with negative signs towards the sum modulo 11, and some with positive. It would be much easier if I reversed the pattern first, but I was stubborn and parsed it from left to right :-)

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sat Nov 05, 2005 11:37 am

Well, you can use the other way of checking of a number is divisible by 11... though you can easily just DP the other way.

In any case, my output matches yours.. so maybe it's a harder case somewhere.. =/

Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry » Sat Nov 05, 2005 11:39 am

Nevermind, I've been making tons of silly mistakes lately.. if anyone's curious, my mistake was I had a < instead of <= in a loop somewhere.. sigh.

Post Reply

Return to “Volume 109 (10900-10999)”