Bertie recently bought a multimedia smartphone with a touch screen, to edit
his drum recordings while on the road. He bought an expensive mixer program
that was obviously optimized for much larger screens, resulting in all the little
knobs and switches being too small. Whenever he tries to operate the GUI with his
finger, he toggles a group of switches instead of a single switch. The
more switches are turned on, the higher the power consumption of the expensive
amplifiers is.
In this task, you will need to simulate Bertie's actions and estimate total power consumption by summing how many of the important switches were on during the simulation. Given n switches numbered from 0..n-1. Each switch is either turned on or off. Initially all of them are off. |
source: http://howtosmile.org/record/492 |
There are two operations Bertie can perform on the switches and each of them has two parameters, a and b:
operation | description |
---|---|
toggle(a,b) | toggle all switches in the closed interval [a,b] |
query(a,b) | query how many switches are turned on in the closed interval [a,b] (these are the important switches) |
Your task is to simulate a sequence of k operations and calculate the sum of all query results.
The simulation details are specified below using pseudo code.
function seed(s) { x := s } function rand() { x := (6364136223846793005*x + 1442695040888963407) mod 2^64 return x div 2^32 } function simulation(n, k, p, s) { seed(s) sum := 0 repeat k times len := rand() mod n a := rand() mod (n-len) b := a+len r := rand() if r < p then sum := sum + query(a, b) else toggle(a, b) end if end repeat print(sum) }
only one line: n k p s
only one number: the sum of all of the answers for the queries
10 10 2147483648 12345678987654321
8
Note: in this example the steps were
toggle(1, 6) toggle(2, 7) toggle(6, 6) toggle(1, 2) query(0, 6) toggle(0, 8) query(1, 7) query(1, 3) query(6, 7) toggle(1, 8)