olana.odessa
BAN USERHere is solution on D:
This can be tested on dpaste.dzfl.pl/61c4d824195f
import std.stdio;
import std.conv;
import std.typecons;
import std.algorithm;
import std.exception;
import std.c.math;
/*
(Bar Raiser Round)
Divide the array(+ve and -ve numbers) into two parts such that the average of both the parts is equal.
Input:
[1 7 15 29 11 9]
Output:
[15 9] [1 7 11 29]
Explanation:
The average of first two elements is (15+9)/2 = 12, average of remaining elements is (1 + 7 + 11 + 29)/4 = 12
*/
int calculateP(int S, size_t N, size_t K)
{
if (N <= 0 || K <= 0 || K >= N) return 0;
double intPart;
double doubleP = K * S / to!double(N);
bool isInt = (0.0 == modf(doubleP, &intPart));
return (S > doubleP && isInt) ? (to!int(doubleP)) : 0;
}
unittest
{
assert(calculateP(0,1,1) == 0);
assert(calculateP(1,0,1) == 0);
assert(calculateP(1,1,0) == 0);
assert(calculateP(10, 5, 2) == 4); /// 10 * 2 / 5
}
int[] findSubarray(int[]a, int P, size_t K)
{
/// This should return the subarray of the K items with total sum of P
if (K <= 0) throw new Exception("The 'K' should be positive.");
if (K >= a.length) throw new Exception("The 'K' should be less than 'a.length'.");
if (!isSorted(a))
{
int[] a_copy = a.dup;
sort(a_copy);
return findSubarray(a_copy, P, K);
}
switch(K)
{
case 1:
return findSplit(a, [P])[1];
case 2:
while (a.length > 1)
{
int S = a[0] + a[$-1];
if (P == S) return [a[0], a[$-1]];
a = (S > P) ? a[0..$-1] : a[1..$];
}
return [];
default:
foreach(i, item; a)
{
int[] res = findSubarray(a[0..i] ~ a[i+1..$], P - item, K - 1);
if (res.length) return [item] ~ res;
}
}
return [];
}
int SumOfArray(int[] a)
{
return reduce!"a+b"(0, a);
}
double AvgOfArray(int[] a)
{
return SumOfArray(a) / to!double(a.length);
}
unittest
{
int[] a = [-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, 6];
int[] Sub;
for (size_t K = 1; K < a.length; K += 2)
{
for(int P = -5; P <= 5; ++P)
{
Sub = findSubarray(a,P,K);
assert((P == SumOfArray(Sub) && Sub.length == K) || Sub.length == 0);
}
}
}
Tuple!(int[], int[]) divideByTemplate(int[]a, int[] templ)
{
Tuple!(int[], int[]) result;
foreach(elem; a)
{
if (templ.length == 0) break;
auto parts = findSplit(templ, [elem]);
if (parts[1].length > 0)
{
result[0] ~= parts[1];
templ = parts[0] ~ parts[2];
}
else
{
result[1] ~= elem;
}
}
return result;
}
unittest
{
int[] a = [1, 7, 15, 29, 11, 9];
int[] templ = [9, 15];
auto tuple = divideByTemplate(a, templ);
assert(tuple[0] == [15,9] && tuple[1] == [1, 7, 29, 11]);
}
Tuple!(int[], int[]) doSplit(int[] a)
{
size_t N = a.length;
int S = SumOfArray(a);
for(size_t K = 0; K <= N; ++K)
{
int P = calculateP(S, N, K);
int[] Sub = (P > 0) ? findSubarray(a,P,K) : [];
if (P == SumOfArray(Sub) && Sub.length == K && K > 0)
{
return divideByTemplate(a, Sub);
}
}
return tuple!(int[], int[])([],[]);
}
void doDemo(int[] a)
{
auto tuple = doSplit(a);
if (tuple[0] && tuple[1])
{
writeln("One of the possible division for this array ", a, " is " , tuple[0], " and ", tuple[1], ". Avg for this ", AvgOfArray(tuple[0]), " and ", AvgOfArray(tuple[1]) );
}
else
{
writeln("This array ", a, " could not be divided");
}
}
unittest
{
doDemo([1, 7, 15, 29, 11, 9]);
doDemo([1, 3, 5, 7, 13, 17]);
doDemo([1, -3, 2, -1, -1, 6]);
}
int main(string[] argv)
{
return 0;
}
Application output
One of the possible division for this array [1, 7, 15, 29, 11, 9] is [15, 9] and [1, 7, 29, 11]. Avg for this 12 and 12
One of the possible division for this array [1, 3, 5, 7, 13, 17] is [1, 5, 17] and [3, 7, 13]. Avg for this 7.66667 and 7.66667
One of the possible division for this array [1, -3, 2, -1, -1, 6] is [-3, -1, 6] and [1, 2, -1]. Avg for this 0.666667 and 0.666667
Output:
- olana.odessa May 08, 2015