All submissions for this problem are available.
Argo-natia is a linear, street-like Illusion land of traps set up by Stoneman for Captain America. By linear, we mean all the cages in the street-like Illusion land are placed on a single straight line i.e. the x-axis. Thus every cage’s position can be defined by a single coordinate, the distance from the left borderline of the street like structure. All cages can be treated as single points.
When Captain America comes to know that the Avengers have been lured into these traps, he decides to help them. When he comes to Argo-natia , he realizes that all of them are not trapped in the same cage but are randomly distributed. He gets very sad as he could think of no plan at that moment and he is running out of time. Seeing his misery, Stoneman’s stone heart melts and he informs him that he knew that he would not be able to help them all. So to be fair, he devised a system of networking between each of the cages. But, because his brain has turned into a stone, he wasn’t able to remember any concept of networking or any of its model. So he made a new concept in which if Ki avengers are trapped in cage i, then there should be atleast Ki cables from cage i to every other cage of the Illusion land.
So, now Captain America needs to find out how much cable he needs to get all the avengers in different cages connected, given the no. of avengers in each cage.The connection between the cages can be shared. Once he get them all connected they can together fight the Stoneman and save themselves.
A number T is given in the first line and then comes T blocks, each representing a scenario. Each scenario consists of three lines. The first line indicates the number of cages (N). The second line indicates the coordinates of the N cages. The third line contains the no of avengers in each of the cages. The cages needn't be in increasing order in the input.
For each scenario of the input, write the length of cable needed in a single line modulo 1,000,000,007.
Border to border length of the cages<=1000,000,000
Input: 2 3 1 3 6 10 20 30 5 5 55 555 55555 555555 3333 333 333 33 35 Output: 280 463055586
Example case 1.For the first test case, having 3 cages requires 3 sets of cable connections. Between cage 1 and 2, which has a population of 10 and 20, respectively Captain America realizes that at least 10 cables should come out of city 1 for this connection, and at least 20 cables should come out of city 2 for this connection.
Thus, the connection between city 1 and city 2 will require 20 cables, each crossing a distance of 3-1=2 km. Applying this funny logic to connection 2,3 and 1,3, we have [1,2]=> 20 connections* 2 km=40 km of cable. [2,3]=> 30 connections*3 km=90 km of cable. [1,3]=>50 connections*3 km=150km of cable. For a total of 280 , Output is 280 km of cable.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, CS2, PAS fpc, PAS gpc, GO, NODEJS, HASK, D, PERL, FORT, ADA, CAML, ICK, BF, ASM, CLPS, ICON, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, JS, ERL, kotlin, PERL6, CLOJ, COB, FS|
Fetching successful submissions