HowUnsorted
SRM 234 · 2005-03-16 · by AdminBrett
SRM 234 · 2005-03-16 · by AdminBrett · Sorting
Problem Statement
Problem Statement
The problem statement contains superscripts and subscripts that can be seen in the applet.
Given a randomly generated sequence, it can be useful to know how unsorted it is. The sequence
Given a randomly generated sequence, it can be useful to know how unsorted it is. The sequence
a1, a2, a3, a4, ... , angets 1 'unsortedness point' for every distinct pair (i,j) where i < j but ai > aj. The terms in the sequence are defined by the following formula:
a1 = 1 and ak = (m * ak-1 + c) % (231 - 1)Here % denotes the modulus or remainder operator. Return the number of unsortedness points scored by this n-element sequence.
Notes
- Make sure to use 64-bit types when generating the random values.
Constraints
- m will be between 1 and 2000000000 inclusive.
- c will be between 0 and 2^31-2 inclusive.
- n will be between 3 and 100000 inclusive.
Examples
0)
1234257123 123 100000 Returns: 2504702368
1)
1 1 10000 Returns: 0
2)
2 1 100000 Returns: 2418862875
3)
1 10000000 100000 Returns: 2496181732
4)
11 13 100000 Returns: 2503704581
19)
2 10 5 Returns: 0
The sequence used here is: 1, 12, 34, 78, 166 Since the values are sorted, the return is 0.
20)
1000 100 6 Returns: 3
The sequence here is: 1, 1100, 1100100, 1100100100, 588472836, 62316822 The 3 unsortedness points come from the pairs (4,6), (5,6), and (4,5).
Submissions are judged against all 37 archived test cases, of which 7 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class HowUnsorted with a public method long long howMany(int m, int c, int n) · 37 test cases · 2 s / 256 MB per case