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

huffman Batch , stdin/stdout

Registered Users Only

Please login to utilize this feature.

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

huffman.html

Problem Description

While Rar the Cat is teaching huffman encoding, he wondered if its possible to use Huffman Encoding on non-binary strings.

After some Googling, Rar the Cat found that it is actually possible. Hence, he wants you to implement Huffman Encoding for strings where each encoded digit is between 0 and K-1.

Rar the Cat's string has N characters, each with frequency Fi.

To perform Huffman Encoding, you are to assign a K-ary string to each of the N characters. Assume character i is assigned to a K-ary string with length Li. To encode the string, Rar the Cat will replace every character i in the string with the K-ary string that is assigned. Hence, the total length of the encoded message would be the sum of Li multiplied by Fi. Rar the Cat wants the shortest possible encoded string by asking you to minimize this sum.

In addition, to ensure that the message can be decoded properly, each encoded string must be unique. In addition, no encoded string can be a prefix of another encoded string.

For example, there cannot be a set of assigned binary strings {0, 1, 01} as '0' is a prefix of '01'. However, the set {0, 10, 11} is valid.

Input

The first line of input contains 2 integers N and K.

N lines of integers follow, the ith line describes Fi.

Output

You are to output a single integer on the first line, the minimum length of the encoded string.

Subsequently, you are to output N lines containing 1 integer each. On the ith line should be Li, the length of the encoded string you have assigned for character i.

Limits

For all testcases, 0 ≤ Fi ≤ 1012. However, it is guaranteed that the answer will fit into a 64-bit signed integer.

Subtask 1 (20%): 1 ≤ N ≤ 100000, K = 2.

Subtask 2 (35%): 1 ≤ N ≤ 2000. 2 ≤ K ≤ 9.

Subtask 3 (45%): 1 ≤ N ≤ 100000. 2 ≤ K ≤ 9.

Subtask 4 (0%): Sample Testcases.

Sample Testcase 1

Input

4 2
1
1
2
2

Output

12
2
2
2
2

Explanation

The encoded string of abccdd is 00 01 10 10 11 11.

Sample Testcase 2

Input

4 3
1
1
2
2

Output

8
2
2
1
1

Explanation

The encoded string of abccdd is 00 01 1 1 2 2.

Sample Testcase 3

Input

3 2
1
2
3

Output

9
2
2
1

Explanation

The encoded string of abbccc is 00 01 01 1 1 1.

Tags

Greedy

Subtasks and Limits

Subtask Score #TC Time Memory Scoring
12091s256MBMinimum
235111s256MBMinimum
345221s256MBMinimum
4021s256MBMinimum

Judge Compile Command

g++-8 ans.cpp -o huffman -Wall -Wshadow -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512

Accepted Submissions

subIDUserTimeMax Time

Past Submissions

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