Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CSC3100 Data Structures Fall 2022

Programming Assignment I

1 02 Representaion (20% of this assignment)

1.1 Problem Description

Each positive integer n  corresponds to a unique binary representation  (specifying  that  binary numbers are written from right to left, in order of most significant digit to least significant digit).

For example: 10 = 8 + 2 = 2(3) + 2(1)

For ease of writing, “a(b)” is used in this question to denote“a to the power of b”, i.e., ab . Specifying the 02 representation of a number can be obtained by the following procedure:

1. substitute a number that is not 0 or 2 with its binary representation, additionally, using 2(0) instead of 1.

2. check whether the result contains only 0 and 2, and if it contains numbers other than 0 and 2, repeat the step 1 for these numbers

It can be proved that the representation is unique after the above steps.

Take 137 as an example:

• First round: 137 = 2(7) + 2(3) + 2(0), 7 and 3 do not meet the requirements

• Second round:

– Substitute 7 and 3 with their binary expressions: 7 = 2(2) + 2 + 2(0), 3 = 2 + 2(0)

– Thus, 137 = 2(2(2) + 2 + 2(0)) + 2(2 + 2(0)) + 2(0)

So the “02 representation” of 137 is 2(2(2) + 2 + 2(0)) + 2(2 + 2(0)) + 2(0), remember that binary numbers are written from right to left, in order of most significant digit to least significant digit

Your task is to write a program that reads a positive integer n and outputs the 02 representation of the given number

1.2 Problem Description

An integer n, the number to be represented in 02 form (ensure that 1 ≤ n ≤ 109 ).

Hint: For C/C++ and Java users, an int type stores integers range from -2,147,483,648 to 2,147,483,647. So it is possible to store n with an int type.

1.3 Output

One line, the 02 representation of n, (no spaces between characters).

Trailing spaces and newlines after the last character are ok.

Sample Input I

Sample Output I

7

Sample Input II Sample Output II

137

Problem Scale & Subtasks

For 30% of the testcases 1 n 200

For 100% of the testcases 1 n 109

Test Case No

Constraints

1 n = 7

2 n 200

3 n = 137

4-10 No additional constraints

2 Crossing (20% of this assignment)

2.1 Description

A terminal is a row of n equal segments numbered 1 to n in order. There are two parallel terminals, one above the other.

You are given an array a of length n.  For all i = 1, 2, , n, there should be a straight wire from some point on segment i of the top terminal to some point on segment ai  of the bottom terminal. You can’t select the endpoints of a segment.  For example, the following pictures show two possible wirings if n = 7 and a = [4, 1, 4, 6, 7, 7, 5].

Figure 1: A crossing occurs when two wires share a point in common. In the picture above, crossings are circled in red.

What is the maximum number of crossings there can be if you place the wires optimally?

2.2 Input

The first line contains an integer n (1 ≤ n ≤ 105 ), representing length of the array.          Then follows 1 line with n numbers, representing the array. It is guaranteed (1 ≤ ai  ≤ n)

2.3 Output

Output one integer representing the maximum number of crosses.

Hint (For C/C++ and Java users): The result may exceed the range of int type, you are recom- mended to use long long (in C/C++) or long (in Java) to store the result.

Sample Input I Sample Output I

7

4 1 4 6 7 7 5

6

Sample Input II Sample Output II

3

2 2 2

3

Problem Scale & Subtasks

For 30% of the testing data, n 1, 000

For 100% of the testing data, 1 ≤ n ≤ 100, 000

Test Case No

Constraints

1-4

5-8

9-10

n 1000

a is a a permutation, i.e.,

No additional constraints

a contains all integers from 1 to

n exactly once.

3 Sierpiński carpet (20% of this assignment)

3.1 Description

You are required to write a program to print out the Sierpiński carpet of size 3k  × 3k . Construction of Sierpiński carpet (quoted from wikipeadia):

The construction of the Sierpiński carpet begins with a square.  The square is cut into 9 congruent subsquares in a 3-by-3 grid, and the central subsquare is removed. The same procedure is then applied recursively to the remaining 8 subsquares, ad infinitum.

3.2 Input

A positive integer k, ensure that 1 ≤ k ≤ 7

3.3 Output

Sierpiński carpet of size 3k  × 3k .‘  ’(SPACE) indicates the area is removed, and‘#’indicates the area remains.

Trailing spaces and newlines after the last character are ok.

Sample Input I Sample Output I

1

Sample Input II Sample Output II

#########

# ## ## #

#########

###

# #

###

#########

# ## ## #

#########

Problem Scale & Subtasks

For 100% of the test cases, 1 k 7

Test Case No

Constraints

1-3

4-7

k 3

No additional constraints

4 Array Maintenance (30% of this assignment)

4.1 Description

You are required to maintenance an array, which can do the following operations.

1. insert an element with value x after position k . (After this operation, element with value x will be the k + 1-th element in the array and k + 1-th element will be moved to position k + 2 and so on).

2. delete the k-th element in the array. (After this operation, the k-th element will be removed and k + 1-th element will be moved to position k and so on).

3. Calculate the sum from the l-th element to the r-th element.

In this problem, it is guaranteed that all the number k is randomly generated with equal possibility from all legal values.

(Hint: For a tree structure with n vertex whose root is vertex 1, if vertex i’s parent is randomly chosen form [1, i − 1], then the expected height of the tree is O(log n)).

4.2 Input

The first line contains an integer n (1 ≤ n ≤ 2 × 105 ), representing the number of operations.

Then follows n lines, with each line contains several integers. The first integer is the type of operation.

• If it is 1, then follows two integers k (0 ≤ k ≤ len(array)), x (1 ≤ x ≤ 109 ).

• If it is 2, then follows one integer k (1 ≤ k ≤ len(array)).

• If it is 3, then follows two integers l , r (1 ≤ l ≤ r ≤ len(array)).

Note:  In operation of type 1, if k  = 0, the new element x is inserted at the very beginning of the array, i.e., after the insertion, x should be the first element of the array.

4.3 Output

For each operation with type 3 output one integer in one line representing the answer of this operation. Hint (For C/C++ and Java users): The result may exceed the range of int type, you are recom- mended to use long long (in C/C++) or long (in Java) to store the result.

Sample Input I Sample Output I

6

1 0 1

1 0 2

1 1 4

3 1 1

3 2 2

3 1 3

Sample Input II Sample Output II

10

1 0 2

1 1 5

1 1 4

1 1 1

3 1 3

2 3

3 1 3

1 2 9

2 1

3 1 3

Problem Scale & Subtasks

For 100% of the testing data, 1 ≤ n ≤ 2 × 105

Test Case No

Constraints

1-3

4-6

7-10

n 2, 000

theres no operation with type

No additional constraints

2.

A. Requirements

Code (90%)

You can write your code in Java, Python, C, or C++.  The time limit may vary among different languages, depending on the performance of the language.  Your code must be a complete runnable program instead of only a function. We guarantee test data strictly compliance with the requirements

in the description, and you do not need to deal with cases where the input data is invalid. We provide a example problem to better illustrate the information above.

Report (10%)

You also need to write a report to explain the following:

• What are the possible solutions for the proble?

• How do you solve this problem?

• Why is your solution better than others?

Please note that the maximum number of pages allowed for your report is 5 pages.

Remember that the report is to illustrate your thinking process Keep in mind that your report is supposed to show your ideas and thinking process.  We expect clear and precise textual descriptions in your report, and we do not recommend that you over-format your report.

B. Example Problem: A + B Problem

Description

Given 2 integers A and B, compute and print A + B

Input

Two integers in one line: A, and B

Output

One integer: A + B

Sample Input I Sample Output I

1 2

Problem Scale & Subtasks

For 100% of the test cases, 0 A, B 106

Solutions

Java

import java .util .*;

public class Example {

public static void main(String [] args) {

int a, b;

Scanner scanner = new Scanner(System .in);

a = scanner .nextInt ();

b = scanner .nextInt ();

scanner .close ();

System .out .println(a + b);

}

}

Python

AB = input () .split ()

A, B = int (AB[0]) , int (AB [1])

print (A + B)

C

#include <stdio .h>

int main(int argc , char *argv [])

{

int A, B;

scanf("%d%d" , &A, &B);

printf("%d\n" , A + B);

return 0;