Highway Construction
You are planning the next FIFA World Cup and you are counting the number of highways that need to be built to connect the cities with the venue.
Your country has cities and all cities lie on a single straight road called “Highway Road”. If you want to go from City to City ( where ), you need to go through city .
The requirements for the highways are as follows:
- All games will be held in the city.
- New bidirectional roads, called "Super Highways", need to be built such that it is possible to visit the city from any other city directly.
You also have the cost to fulfil the second condition. The engineering team knows that if the length of a Super Highway is , then it will cost , where is an integer constant.The length of Super Highway between city and is .
For this problem, you need to find only a rough estimation of the cost, hence, find Total Cost Modulo .
Input Format
First line will contain a single positive integer denoting the number of queries. Then for each case there will be two positive integers, and .
Constraints
Output Format
For each case find the cost to build Super Highways such that it is possible to visit city from any other city directly. You have to print this value Modulo .
Sample Input 0
1
4 2
Sample Output 0
13
Explanation 0
There are four cities. We need to build Super Highways that connect city to city and city to city . No need to connect city 3 with city since they are adjacent on “Highway Road”. So cost is .
xxxxxxxxxx
char* readline();
char* ltrim(char*);
char* rtrim(char*);
char** split_string(char*);
int parse_int(char*);
long parse_long(char*);
/*
* Complete the 'highwayConstruction' function below.
*
* The function is expected to return an INTEGER.
* The function accepts following parameters:
* 1. LONG_INTEGER n
* 2. INTEGER k
*/
int highwayConstruction(long n, int k) {
}
int main()
{
FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");
int q = parse_int(ltrim(rtrim(readline())));
for (int q_itr = 0; q_itr < q; q_itr++) {
char** first_multiple_input = split_string(rtrim(readline()));
long n = parse_long(*(first_multiple_input + 0));
int k = parse_int(*(first_multiple_input + 1));
int result = highwayConstruction(n, k);
fprintf(fptr, "%d\n", result);
}
fclose(fptr);
return 0;
}
char* readline() {
size_t alloc_length = 1024;
size_t data_length = 0;
char* data = malloc(alloc_length);
while (true) {
char* cursor = data + data_length;
char* line = fgets(cursor, alloc_length - data_length, stdin);
if (!line) {
break;
}
data_length += strlen(cursor);
if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') {
break;
}
alloc_length <<= 1;
data = realloc(data, alloc_length);
if (!data) {
data = '\0';
break;
}
}
if (data[data_length - 1] == '\n') {
data[data_length - 1] = '\0';
data = realloc(data, data_length);
if (!data) {
data = '\0';
}
} else {
data = realloc(data, data_length + 1);
if (!data) {
data = '\0';
} else {
data[data_length] = '\0';
}
}
return data;
}
char* ltrim(char* str) {
if (!str) {
return '\0';
}
if (!*str) {
return str;
}
while (*str != '\0' && isspace(*str)) {
str++;
}
return str;
}
char* rtrim(char* str) {
if (!str) {
return '\0';
}
if (!*str) {
return str;
}
char* end = str + strlen(str) - 1;
while (end >= str && isspace(*end)) {
end--;
}
*(end + 1) = '\0';
return str;
}
char** split_string(char* str) {
char** splits = NULL;
char* token = strtok(str, " ");
int spaces = 0;
while (token) {
splits = realloc(splits, sizeof(char*) * ++spaces);
if (!splits) {
return splits;
}
splits[spaces - 1] = token;
token = strtok(NULL, " ");
}
return splits;
}
int parse_int(char* str) {
char* endptr;
int value = strtol(str, &endptr, 10);
if (endptr == str || *endptr != '\0') {
exit(EXIT_FAILURE);
}
return value;
}
long parse_long(char* str) {
char* endptr;
long value = strtol(str, &endptr, 10);
if (endptr == str || *endptr != '\0') {
exit(EXIT_FAILURE);
}
return value;
}