We are given an array V with N positive integers. We want to split it into M sub
ID: 3903366 • Letter: W
Question
We are given an array V with N positive integers. We want to split it into M subarrays (contiguous), each of them of even length. The cost of one subarray equals the maximum between the sum of of the elements in first half of the subarray, on the one hand, and the sum of the elements in the second half of the array, on the other hand. The total cost of a split is the maximum of the costs if the subarrays defining that split.Compute the minimum total cost of a split of the array V.
Input: The file split2.in contains on the first line T, the number of tests. Each test contains 2 lines: on the first one we have N and M, on the second one the array V.
Output: Write in the output file split2.out (each on a line) the requested value for each of the T tests, respectively.
Constraints: 1 <= T <= 50 1 <= M <= N <= 1000 1 <= V[i] <= 10000 N is even.
For each test there will be a correct split.
Example:
split2.in 1 10 3 1 2 4 2 4 5 2 2 1 3
split2.out 6
== The split will be: 1 2 4 2 | 4 5 | 2 2 1 3
First subarray 1 2 4 2 has cost 6. Second subarray 4 5 has cost 5. Third subarray 2 2 1 3 has cost 4.
Please help me write a java or c++ code for this problem We are given an array V with N positive integers. We want to split it into M subarrays (contiguous), each of them of even length. The cost of one subarray equals the maximum between the sum of of the elements in first half of the subarray, on the one hand, and the sum of the elements in the second half of the array, on the other hand. The total cost of a split is the maximum of the costs if the subarrays defining that split.
Compute the minimum total cost of a split of the array V.
Input: The file split2.in contains on the first line T, the number of tests. Each test contains 2 lines: on the first one we have N and M, on the second one the array V.
Output: Write in the output file split2.out (each on a line) the requested value for each of the T tests, respectively.
Constraints: 1 <= T <= 50 1 <= M <= N <= 1000 1 <= V[i] <= 10000 N is even.
For each test there will be a correct split.
Example:
split2.in 1 10 3 1 2 4 2 4 5 2 2 1 3
split2.out 6
== The split will be: 1 2 4 2 | 4 5 | 2 2 1 3
First subarray 1 2 4 2 has cost 6. Second subarray 4 5 has cost 5. Third subarray 2 2 1 3 has cost 4.
Please help me write a java or c++ code for this problem
Compute the minimum total cost of a split of the array V.
Input: The file split2.in contains on the first line T, the number of tests. Each test contains 2 lines: on the first one we have N and M, on the second one the array V. Input: The file split2.in contains on the first line T, the number of tests. Each test contains 2 lines: on the first one we have N and M, on the second one the array V.
Output: Write in the output file split2.out (each on a line) the requested value for each of the T tests, respectively. Output: Write in the output file split2.out (each on a line) the requested value for each of the T tests, respectively.
Constraints: 1 <= T <= 50 1 <= M <= N <= 1000 1 <= V[i] <= 10000 N is even. Constraints: 1 <= T <= 50 1 <= M <= N <= 1000 1 <= V[i] <= 10000 N is even.
For each test there will be a correct split.
Example:
split2.in 1 10 3 1 2 4 2 4 5 2 2 1 3
split2.out 6
== The split will be: 1 2 4 2 | 4 5 | 2 2 1 3
First subarray 1 2 4 2 has cost 6. Second subarray 4 5 has cost 5. Third subarray 2 2 1 3 has cost 4. For each test there will be a correct split.
Example:
split2.in 1 10 3 1 2 4 2 4 5 2 2 1 3
split2.out 6
== The split will be: 1 2 4 2 | 4 5 | 2 2 1 3
First subarray 1 2 4 2 has cost 6. Second subarray 4 5 has cost 5. Third subarray 2 2 1 3 has cost 4.
Please help me write a java or c++ code for this problem
Explanation / Answer
import java.util.*;
import java.io.*;
public class SplitArray {
public static void main( String[] args ) throws FileNotFoundException {
File file_o = new File("split2.txt");
Scanner sc = new Scanner(file_o);
int T = 0, N = 0, M = 0;
int V[] = new int[1];
boolean is_data = false;
if (sc.hasNextLine()) {
String str = sc.nextLine();
T = Integer.parseInt(str);
if (sc.hasNextLine()) {
str = sc.nextLine();
String s[] = str.split(" ");
N = Integer.parseInt(s[0]);
M = Integer.parseInt(s[1]);
if (sc.hasNextLine()) {
V = new int[N];
str = sc.nextLine();
String st[] = str.split(" ");
for(int i=0; i<st.length; i++) {
V[i] = Integer.parseInt(st[i]);
}
if(T < 1 || T > 50) {
System.out.println("1 <= T <= 50");
} else if(N < 1 || N > 1000 || M > N){
System.out.println("1 <= M <= N <= 1000");
}
is_data = true;
}
}
}
if(!is_data) {
System.out.println("No proper input in file");
} else {
System.out.println(T + " " + N + " " + M + " " + V.length);
int start = 2;
for(int i=0; i<T; i++) {
int last_occurance = 0;
System.out.println("The split will be:");
for(int i_m=0; i_m<M; i_m++) {
if(i_m != 0)
System.out.print("| ");
int d = 0;
if(N % M > 0 && N / M >= M) {
d = (M % 2 == 0 ? M + 2 : M + 1);
} else {
d = (M % 2 == 0 ? M - 2 : M - 1);
}
for(int k=last_occurance; k<(last_occurance + d) && k<N; k++) {
System.out.print(V[k] + " ");
}
last_occurance = last_occurance + d ;
}
}
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.