Programming Assignment 1 Queue Disorder

CSC3100 Data Structures 
Programming Assignment 1
Assignment Link: http://oj.cuhk.edu.cn/contest/csc310023falla1
Access Code: 9v7Dxqet
1 Queue Disorder (40% of this assignment)
1.1 Description
In a queue, people are supposed to stand in ascending order of their heights. However, due to some
confusion, the order of the queue gets disrupted. Your task is to determine the number of disorder
pairs in the queue.
A disorder pair is defined as a pair of people (pi
, pj ) such that i < j and pi
is taller than pj in the
queue, which means their order is reversed.
For example, consider a queue with 5 people: [180, 160, 175, 170, 170]. In this case, there are 6 disorder
pairs: (180, 160), (180, 175), (180, 170), (180, 170), (175, 170) and (175, 170). Please note that (170,
170) is not considered as a disorder pair.
Write a program to calculate the number of disorder pairs in a given queue.
1.2 Input
The first line of input contains an integer N (1 ≤ N ≤ 106
), representing the number of people in the
queue.
The second line contains N space-separated integers p1, p2, . . . , pN (1 ≤ pi ≤ 109
), representing the
heights of people in the queue.
1.3 Output
Output a single integer, the number of disorder pairs in the queue.
Sample Input 1
6
1 2 3 4 5 6
Sample Output 1
0
Sample Input 2
5
180 160 175 170 170
Sample Output 2
6
4
Problem Scale & Subtasks
Test Case No. Constraints
1-4 N ≤ 1000
5-8 N ≤ 10000
9-10 N ≤ 106
Hint
For C/C++ and Java users, an int type stores integers range from -2,147,483,648 to 2,147,483,647. It
may be too small for this problem. You need other data types, such as long long for C/C++ and long
for Java. They store integers ranging from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807.
Use scanf("%lld",&n) for C, cin>>n for C++ and n = scanner.nextLong() for Java to get the
input n. And the other operations for long and long long are quite same as int.
2 Star Sequence (50% of this assignment)
2.1 Description
Renko Usami observes space through a telescope when she notices a fantastic phenomenon – the
number of stars in the fields follows a mathematical pattern.
Specifically, let’s denote the number of stars in the Nth field by fN , then fN satisfies the following
expression, and a, b are given positive integers.
fN = afN−1 + bfN−2 (N ≥ 2)
Now Renko Usami is curious about how many stars in the nth field, but the nth field is too far away
to be observed through her cheap astronomical telescope. Since there are so many stars, she only cares
about the value of the number of stars modulo m. In other words, she want to know fn mod m.
Fortunately, Renko Usami is able to observe the two closest star fields to her, and the numbers of stars
in fields are f0 and f1. Unfortunately, she is going to be late again for her appointment with Merry.
Can you write a program for her to calculate fn mod m?
2.2 Input
The only line of the input contains 6 integers n(1 ≤ n ≤ 1018), a, b, f0, f1(1 ≤ a, b, f0, f1 ≤ 100),
m(1 ≤ m ≤ 2 × 109
). – the meanings of these numbers are shown in the problem description.
2.3 Output
Output a single integer – fn mod m.
Sample Input 1
4 1 1 1 1 1000
Sample Output 1
5
Sample Input 2
468908 34 29 33 30 998244353
Sample Output 2
829261643
5
Problem Scale & Subtasks
For 100% of the test cases, 1 ≤ n ≤ 1018, 1 ≤ a, b, f0, f1 ≤ 100, 1 ≤ m ≤ 2 × 109
.
Test Case No. Constraints
1-2 n ≤ 10
3-5 n ≤ 106
6-10 No additional constraints
Hint
Hint1 : For C/C++ and Java users, an int type stores integers range from -2,147,483,648 to 2,147,483,647.
It may be too small for this problem. You need other data types, such as long long for C/C++ and
long for Java. They store integers ranging from -9,223,372,036,854,775,808 to 9,223,372,036,854,775,807.
Use scanf("%lld",&n) for C, cin>>n for C++ and n = scanner.nextLong() for Java to get the input
n. And the other operations for long and long long are quite same as int.
Hint2 : Here’s a simple definition of the modulo operation. Your output should be the remainder of
the Euclidean division of fn by m, where fn is the dividend and m is the divisor. And for the modulo
operation the following equation holds:
(x + y) mod m = ((x mod m) + (y mod m)) mod m
Hint3 : When a and b are 1, fn is Fibonacci Sequence. Here is a way to compute the Fibonacci
Sequence by using matrices:

1 1
1 0 f1
f0

=

f2
f1

The Matrix 
1 1
1 0
is called transition matrix. Also, note that matrix multiplication is associative.
By multiplying the transition matrix n − 1 times, we can get the fn.
6