oj mrJudge
Toggle navigation
  • Login
    • Forget Password
      Login
User Image

Hello, Stranger

Guest
  • Analysis Mode
  • Problems
    • All Problems
    • Latest Problems
  • Join Us Now
  • Registration
  • Contact Us
  • Infomation
  • About
    • Terms of Use
    • Technical Specifications
    • Credits

pandacompression Output Only

Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

pandacompression.html

Problem Description

Mr. Panda recently learnt about image compression and he learnt about a compression technique called run-length encoding. In it's simplest form, run-length encoding is used to compress files containing long strings of similar characters. For example "aaaaaaabbbbbccc" might be compressed to "a 7 b 5 c 3" and the compression is more effective when there are more such strings. Mr. Panda decides to use it to compress some images and since pandas are in black and white, so are his images. He converts the image into a rectangular grid of black and white pixels and turns the image into a text file going through all the pixels one by one and for clarity, he encodes each black pixel using '#' and each white pixel using '-'. He then performs run-length encoding on each row separately.

However, when he tries to open the compressed file, he realises that the file is corrupted and all the information on the '-' characters go missing. Hence, he is only left with the information on the '#' characters. For example, for the line "--##-###--#" is supposed to be compressed to "- 2 # 2 - 1 # 3 - 2 # 1" but instead all the '-' information is lost so what is left is "# 2 # 3 # 1" and the compression is lossy. Unsatisfied, he tries to perform run-length encoding on each column of text instead but when he opens the compressed file, he gets the same problem. However, he finds that given both of these lossy compressions, he is able to generate the original image and thus make the compression lossless. He decides to name his new found method "Panda Compression" and he needs your help to decompress his files.

Input

The files to decompress are under the "Attachments" tab and can be found inside the zip folder. The full score for each file is given in the first row. The compression of each row is given under "Rows:" and those of the columns are under "Columns:" and the format of the compression is as described above. Take note that each run-length represents a distinct block so "# 2 # 1" will never represent "-###-" since it would have been encoded as "# 3" instead. It is guaranteed that there is only one possible image that generates such a compression.

Output

Output the original text file consisting of '#' and '-' characters, refer to the sample output if there are doubts. There is an opportunity for partial scoring if you cannot find all the characters, refer to the "Scoring" section below for details. This is an output only problem so there is no need to submit any code. Hence, you may use any method you want to get the answer as long as the final correct answer is obtained.

Scoring

If you are unsure of any characters in your image, you may replace the characters with a '?' instead and those characters will not be graded. If the full score for that file is S, your score for the output will be (S*(Number of Correct Characters-(Number of Wrong Characters)2)/Total number of characters in original image) rounded down to the nearest integer. You will get 0 if the dimensions of the output image is wrong. Refer to sample outputs below for illustration.

Sample Input

Score: 10

Rows:
# 3
# 1 # 2
# 1 # 1
# 2
# 3

Columns:
# 3
# 1
# 1 # 1
# 1 # 2
# 4

Sample Outputs

###--
#--##
#---#
---##
--###

Score: 10. All characters are correct

##??-
#-??#
#?--?
--??#
-???#

Score: floor(10*14/25) = 5. Printed characters are correct

--??-
#-??#
#?--?
--??#
-???-

Score: floor(10*(14-2*2)/25) = 4. First two characters in the first row are wrong

Tags

Creative

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
110081s32MBCustom

Attachments

Attachment Filesize Last Updated
6.txt483B17 Dec 2013, 00:34:00
3.txt78B17 Dec 2013, 00:34:00
2.txt82B17 Dec 2013, 00:34:00
1.txt214B17 Dec 2013, 00:34:00
5.txt308B17 Dec 2013, 00:34:00
4.txt157B17 Dec 2013, 00:34:00
7.txt1.97KB17 Dec 2013, 00:34:00
8.txt3.07KB17 Dec 2013, 00:34:00

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

subIDUserTimeScore
mrJudge 09.05.20
Copyright © 2020 mrJudge. All rights reserved.