Samosa (Puzzle)


Samosa Bhai got tired of the difficult tasks given by his owner along with meagre salary being paid to him. So he moves to Aloo uncle's village and opens a courier company there. In the village, everyone knows Aloo uncle and Kachori Aunty, so everyone sends their gifts using Samosa Bhai's courier company only. There are N houses in a row in the village. On New Year's Eve, each house sends a gift to all the other houses. The distance between two houses situated at positions x and y in the row is |x - y|. Samosa Bhai's courier company charges dk rupees for each delivery, where d is the distance between the 2 houses. Everyone chose Samosa Bhai's company because of Aloo uncle and Kachori aunty. So he decides to give them the amount of money earned by him modulo 1000000007 (109 + 7). You need to compute this amount. 
Input 
                   The first line of each test case contains 2 integers N and k denoting the number of houses and the exponent k, resepctively. The second line contains N space-separated integers A1, A2, ... AN denoting the positions of the houses. 
Output 
                   For each test case, output a single line with the amount given to Aloo uncle and Kachori aunty by Samosa Bhai. 
Constraints 
 2 <= N <= 105
 0 <= k <= 100
 0 <= Ai <= 1000000006 
 The sum of N over all test cases will be at most 100000 2 houses can be at the same position Example Input: 
2 2 
7 2 
2 3 
7 2 
3 2 
1 3 2 
10 2 
1 2 3 4 5 6 7 8 9 10 
10 10 
1 2 3 4 5 6 7 8 9 10 
Output: 
50 
250 
12 
1650 
558199159
Explanation 
Example 
case 1. House 1 sends a gift to House 2 with cost (|2 - 7|)2 and house 2 sends a gift to house 1 with cost (|7-2|)2, for a total cost of 50 
case 3. The cost for gift from house with index 1 to house with index 2 is 22 = 4, from houses 1 to 3 is 1, from houses 2 to 3 is 1. Taking into account the gifts sent the other way (from 2 to 1, 3 to 1 and 3 to 2), the total cost is 4 + 1 + 1 + 4 + 1 + 1 = 12

 CODE

Comments

Post a Comment

Popular posts from this blog

Female co passenger hack

The female co-passenger hack. I came across this trick on the internet. When you need to book a ticket on IRCTC (Indian Railways), book two seats instea of one, and cancel one after some days. One in your name and one in fake Female name to get a girls in the compartment. The IRCTC algorithm works that way.
Read more

C library function - qsort()

Image
Description               The C library function void qsort(void *base, size_t nitems, size_t size, int (*compar)(const void *, const void*)) sorts an array. Parameters base -- This is the pointer to the first element of the array to be sorted. nitems -- This is the number of elements in the array pointed by base. size -- This is the size in bytes of each element in the array. compar -- This is the function that compares two elements. Return Value This function does not return any value Code   #include <stdio.h> #include <stdlib.h> int values [] = { 88 , 56 , 100 , 2 , 25 }; int cmpfunc ( const void * a , const void * b ) { return ( *( int *) a - *( int *) b ); } int main () { int n ; printf ( "Before sorting the list is: \n" ); for ( n = 0 ; n < 5 ; n ++ ) { printf ( "%d " , values [ n ]); } qsort (...
Read more

Wildcard Pattern Matching (DP)

Given a text and a wildcard pattern, implement wildcard pattern matching algorithm that finds if wildcard pattern is matched with text. The matching should cover the entire text (not partial text). The wildcard pattern can include the characters ‘?’ and ‘*’ ‘?’ – matches any single character ‘*’ – Matches any sequence of characters (including the empty sequence) Text = "baaabab", Pattern = “*****ba*****ab", output : true Pattern = "baaa?ab", output : true Pattern = "ba*a?", output : true Pattern = "a*ab", output : false Each occurrence of ‘?’ character in wildcard pattern can be replaced with any other character and each occurrence of ‘*’ with a sequence of characters such that the wildcard pattern becomes identical to the input string after replacement. Let’s consider any character in the pattern. Case 1: The character is ‘*’ Here two cases arise We can ignore ‘*’ character and move to next character in the Pattern. ‘*’ cha...
Read more