Scribd
Upload
23 views2 pages

Bit Stream Encoding in C++ Lab

The document describes a programming problem related to encoding bit streams using run-length encoding. It outlines the input and output formats, including how to calculate the number of bytes needed for both the original and encoded strings. An example is provided to illustrate the expected input and output for the problem.

Uploaded by

sheng.c.tan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
23 views2 pages

Bit Stream Encoding in C++ Lab

The document describes a programming problem related to encoding bit streams using run-length encoding. It outlines the input and output formats, including how to calculate the number of bytes needed for both the original and encoded strings. An example is provided to illustrate the expected input and output for the problem.

Uploaded by

sheng.c.tan
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Online Midterm: Fundamental Computer Programming- C++ Lab(I), Rung-Bin Lin

Nov.. 20, 2021, International Bachelor Program in Informatics, Yuan Ze University

Problem C: Bit Stream Encoding

(25%) (This problem related to Lab 4)

Problem Description
Given a string of 0’s and 1’s without containing any whitespaces, a run is a string’s substring that
contains only all 0’s or all 1’s. A run is not contained in any other runs. The length of a run is the
number of 0’s in the run or the number of 1’s in the run. For example, given a string
1111110000100111, This string has 5 runs, 3 runs of 1’s and 2 runs of 0’s. The lengths of these
runs are 6, 4, 1, 2, and 3. We can encode the above string into a sequence of numbers 1 6 4 1 2
3 using run length. The first integer 1 indicates that the starting bit of the string is 1. The second
integer 6 indicates that the first run is a run of 1’s and its run length is 6. Similarly, the third
integer 4 indicates that the second run is a run of 0’s and its run length is 4. If an integer takes 4
bytes and a space character takes one byte, encoding the above string into 1 6 4 1 2 3 take 29
bytes. However, the original string takes only two bytes. Here, you are asked to write a program
to calculate the number bytes needed for the original string and the encoded string.

Input Format
The first line gives the number of test cases. It is then followed by the input data of each test
case. The input of each test case is presented line-by-line where each line contains only 0’s and
1’s. The string on one line should join the string on the next line one after another to form a bit
string of 0’s and 1’s for a test case. The input of a test case ends with a line containing only a $.

Output Format
The output of a test case takes a line. Each line begins with a #, then a whitespace, and two
numbers. The first number is the number of bytes needed for the original string. The second
number is the number of bytes needed for the encoded string (i.e., a sequence of integers).

Example

Sample Input Sample Output


2 # 16 169
1111110000100111111111000010011111100001001111111110000100111 # 5 39
1111110000100111111111000010011111100001001111111110000100111
$
00111100001001111111111111111110000000
$
Online Midterm: Fundamental Computer Programming- C++ Lab(I), Rung-Bin Lin
Nov.. 20, 2021, International Bachelor Program in Informatics, Yuan Ze University

You might also like