WEIRDFN - Weird Function
Let us define:
- F[1] = 1
- F[i] = (a × M[i] + b × i + c) % 1000000007 for i > 1
where M[i] is the median of the array {F[1], F[2] ... F[i-1]}.
The median of an array is the middle element of that array when it is sorted. If there are an even number of elements in the array, we choose the first of the middle two elements to be the median.
Given a, b, c and n, calculate the sum F[1] + F[2] + ... + F[n].
Input
The first line contains T the number of test cases. Each of the next T lines contain 4 integers : a, b, c and n.
Output
Output T lines, one for each test case, containing the required sum.
Constraints
1 ≤ T ≤ 100
0 ≤ a, b, c < 1000000007
1 ≤ n ≤ 200000
Example
Input: 2 1 0 0 3 3 1 2 6 Output: 3 103
hide comments
|
wingman__7:
2019-10-04 10:05:48
maintain two priority queues, and alternate between those two for storing F[i] |
|
itachi_2016:
2019-09-24 00:14:12
Any corner test cases we need to take care of?
|
|
baddu609:
2019-05-29 22:50:26
Be careful, Take mod of terms only, not the mod for the final answer. |
|
Aditya:
2019-04-18 20:54:52
The same solution got accepted in c++ but gave tle in Java. Last edit: 2019-04-18 20:55:16 |
|
tanmay2904:
2019-03-24 20:53:50
@hp1999 bcoz clearing them using priority_queue.clear() takes O(n) time
|
|
hp1999:
2019-03-10 13:09:31
I can't get it. I got TLE when I declared the priority queues outside the 't' while loop (the one I used for test cases) and was emptying them after each iteration. But when I declared them inside it, I got AC. What could be the reason? |
|
masterchef2209:
2019-01-17 11:38:02
LESSON LEARNED=priority_queue is faster than multiset
|
|
tan_sourabh:
2019-01-16 18:09:54
Nice problem, can be done using priority_queue. Choose priority_queue over set, if you are using STL. |
|
taponidhi:
2018-05-21 12:57:32
It's a really gud question with nice STL implementation.Just remember to not take modulus of ∑F(i).If you take modulus,it will give wrong answer.I was kinda stuck there :( . |
|
shahianshu:
2018-02-13 12:22:38
question can be solved in c++ by using priority queue stl by making two priority queue left and right and taking the middle as integer and forming logic based on the question. |
| Added by: | Varun Jalan |
| Date: | 2010-01-25 |
| Time limit: | 1.116s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: NODEJS OBJC PERL6 SQLITE VB.NET |
| Resource: | own problem used for Codechef Snackdown Onsite |
RSS