293 - Bits

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

Moderator: Board moderators

Post Reply
Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

293 - Bits

Post by Dominik Michniewski » Sun Jun 12, 2005 9:56 pm

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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

stubbscroll
Experienced poster
Posts: 151
Joined: Tue Nov 16, 2004 7:23 pm
Location: Norway
Contact:

Post by stubbscroll » Tue Jun 14, 2005 5:07 pm

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.

Dominik Michniewski
Guru
Posts: 834
Joined: Wed May 29, 2002 4:11 pm
Location: Wroclaw, Poland
Contact:

Post by Dominik Michniewski » Wed Jun 15, 2005 7:56 am

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
If you really want to get Accepted, try to think about possible, and after that - about impossible ... and you'll get, what you want ....
Born from ashes - restarting counter of problems (800+ solved problems)

mpi
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm
Location: Madrid

293 impossible WA!

Post by mpi » Fri Nov 03, 2006 8:08 pm

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?

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Fri Nov 03, 2006 8:50 pm

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.

mpi
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm
Location: Madrid

Post by mpi » Fri Nov 03, 2006 9:01 pm

No problem with that kind of input. But thanks anyway!

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Fri Nov 03, 2006 9:19 pm

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.

mpi
New poster
Posts: 46
Joined: Fri Nov 03, 2006 7:53 pm
Location: Madrid

Post by mpi » Fri Nov 03, 2006 10:21 pm

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.

metaphysis
Experienced poster
Posts: 139
Joined: Wed May 18, 2011 3:04 pm

Re: 293 - Bits

Post by metaphysis » Thu Jun 09, 2016 9:59 am

The test data is tricky. Problem statement have no mention about handing with cases provided by mf.

Post Reply

Return to “Volume 2 (200-299)”