Handling ambiguous encodings

Handling ambiguous encodings

akki的头像

Consider the input
1 2 1 1 0

One possible encoding is:
2 x 4
(1 2 1)(1)

This could mean:

1 2 1 1

OR

1 2 1 1

In such a case,

  1. is the same encoding expected to be listed twice?
  2. is it acceptable if the same encoding is listed twice?

Thanks.

5 帖子 / 0 new
最新文章
如需更全面地了解编译器优化,请参阅优化注意事项
gk4v07的头像
>One possible encoding is:
>2 x 4
>(1 2 1)(1)

It is not a possible encoding. The sequence 1 2 1 1 0 can not encode a rectangle according to the rules.
mdma的头像

Nice pictures! In both your examples, there is a (1) which is not a square, but a 1x2 rectangle. Rectangles are not allowed, so these are not valid encodings. A (1) should always correspond to a (1x1) square, (2) to (2x2) etc.

gk4v07的头像
Quoting mdma Nice pictures! In both your examples, there is a (1) which is not a square, but a 1x2 rectangle. Rectangles are not allowed, so these are not valid encodings. A (1) should always correspond to a (1x1) square, (2) to (2x2) etc.
Right, so the one necessary condition for the encoding
is that the area of the rectangle = the total area of the squares,
which is not true in this case: 2x4 = 8 while  1^2+2^2+1^2+1^2 = 7.
Also, while a sum of the squares is a prime, there could be a valid encodings 
only  if all squares are 1x1 in which case the two encodings should be found:  
1 x n 
(1 1 ... 1)
and 
n x 1
(1)(1)...(1)
 
    
akki的头像

Thanks for your replies, everyone. Silly question. Sorry. [embarassed]

That's what I get for not reading the problem carefully. Square tiles...

登陆并发表评论。