Page 1 of 1

293 - Bits

Posted: Sun Jun 12, 2005 9:56 pm
by Dominik Michniewski
Could anyone help me and post some special I/O ?

I try with various self imagined inputs, but I think that I've got correct answers. But judge think somehing else and I got WA (after 0.084s). I have no more ideas about bug in my code.

Best regards and thanks for any help
DM

Posted: Tue Jun 14, 2005 5:07 pm
by stubbscroll
Here are the i/o I used for this problem:

input:

Code: Select all

12
year : [1970..2030]
team : {
        name : string(14)
        members : array [1..3] of {
                sex : ( male, female )
                name : string(20)
                age : [16..30]
        }
        position : [1..40]
}
jurynames : array [1..3] of string(20)
fish : array [1..2] of array [1..1] of array [63..66] of array [565..588] of string(14)
fisk : array [1..2] of array [1..2] of array [1..2] of array [1..2] of array [1..32] of array [1..9] of array [-1..9] of array [-77..-72] of string(4)
frosk : {
loff : string(55)
sopp : [-10000..-9999]
dings : ( dfsdf, dfgd, dfgdfg, dfgfdg, ghfhg )
}

year:[ 1970 . . 2030 ]
team:{name:string     (

14

)members :
array[1    ..3        ]of{sex:(male      ,female)
                name


 :string    (20          



)
                age :[16    .                
     .    
30


]}
        position 



: [   1          .

.40]

}jurynames :array[1..3]ofstring(20   
)fish:array[1..2]of array[1.     .1] of array[63..66] of array [565..588] of string(14)
fisk : array [1..2] of array [1..2] of array [1..2] of array [1..2] of array [1..32] of array [1..9] of array [-1..9] of array [-77..-72] of string(4)
frosk : {
loff : string(55)
sopp : [-10000..-9999]
dings : ( dfsdf, dfgd, dfgdfg, dfgfdg, ghfhg )
}
output:

Code: Select all

A "year" message requires 6 bits.
A "team" message requires 539 bits.
A "jurynames" message requires 420 bits.
A "fish" message requires 18816 bits.
A "fisk" message requires 8515584 bits.
A "frosk" message requires 389 bits.
A "year" message requires 6 bits.
A "team" message requires 539 bits.
A "jurynames" message requires 420 bits.
A "fish" message requires 18816 bits.
A "fisk" message requires 8515584 bits.
A "frosk" message requires 389 bits.
I'm not sure if this input is legal, though, but it helped me make a foolproof program.

I had some trouble with this problem for a while, it turned out that my parsing routine read "ofstring" as one word.

Posted: Wed Jun 15, 2005 7:56 am
by Dominik Michniewski
I think that your test cases with dots separated by spaces are incorrect.
Any two tokens may be separated by an arbitrary amount of white space (blanks, tabs an newlines). White space does not occur within tokens.
By other way, I found that nowhere is stated that minimum one white space must appear between tokens :) So I think it's my problem ;)

I try to modify my code as soon as possible and resubmit it :)

Best regards
DM

293 impossible WA!

Posted: Fri Nov 03, 2006 8:08 pm
by mpi
This problem is driving me crazy. I've sent it dozens of times and i always get WA (first times i got TLE :D). I think my program is very rigorous and correct with each posible input, and i don't know where is the trick.

These are some of the assumptions i made:

1) Number of elements in an array [a..b] is (b - a + 1)
2) No input line is longer than 1000000 characters
3) The total number of bits always fits in an (signed) integer
4) If a message is 1 bit length, print "...requires 1 bits."
5) Identifiers in an enum haven't to be all different, so i use a set (STL C++) to count them.
6) Input like [ a .<space>+. b] is not valid (i've seen it in some previous posts)

I'm really puzzled about this. I've even tried sample input provided in one of the previous posts, and my code gives the same output.

Anyone of this problem solvers can help me?

Posted: Fri Nov 03, 2006 8:50 pm
by mf
I've had a really hard time with this problem, too.
There is one dirty catch - adjacent tokens might not be separated by spaces. So, if you want to get accepted, make sure your program works with inputs like these:

Code: Select all

2
array:array[1..2]ofarray[1..2]ofstring(1)of:array[-1..-1]ofarray[0..0]of(array,
of,string,arrayofstring)
Output should be:

Code: Select all

A "array" message requires 28 bits.
A "of" message requires 2 bits.
And please, don't create new threads for a problem, when there is already one. Post in the existing thread.

Posted: Fri Nov 03, 2006 9:01 pm
by mpi
No problem with that kind of input. But thanks anyway!

Posted: Fri Nov 03, 2006 9:19 pm
by mf
Does your program works with this input:

Code: Select all

4
a : array[-42..42] of (justoneid)
b : string(0)
c : array[-42..42] of [42..42]
d : { a:[1..1] b:[2..2] c:(a) }
All these messages require 0 bits.

If it works, then I don't know what could be wrong. But you can post your code, I'll try to check.

Posted: Fri Nov 03, 2006 10:21 pm
by mpi
PERFECT! That was the problem. Now i get AC with 0.053s. I think that case is a bit tricky though. When i first read your last post i thought you were wrong, but soon i realized my mistake. I've always thought that at least 1 bit is needed to store some data :)

Thanks a lot! I really appreciate your help.

Re: 293 - Bits

Posted: Thu Jun 09, 2016 9:59 am
by metaphysis
The test data is tricky. Problem statement have no mention about handing with cases provided by mf.