Physical Address
304 North Cardinal St.
Dorchester Center, MA 02124
Ciel and Eggs CodeChef Solution
Problem -Ciel and Eggs CodeChef Solution
This website is dedicated for CodeChef solution where we will publish right solution of all your favourite CodeChef problems along with detailed explanatory of different competitive programming concepts and languages.
Ciel and Eggs CodeChef Solution in C++14
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
ll n,k;
ll dp[505][505];
ll arr[505];
ll rec(ll level,ll cnt)
{
if(level<cnt)
return 1e13;
if(level==0 || cnt ==0)
return 0;
if(dp[level][cnt]!=-1)
return dp[level][cnt];
ll ans = 1e18,store=0;
for(ll i=1;i<=level;i++)
{
store = (level+1-i)*arr[i];
store+=rec(i-1,cnt-1);
ans = min(ans,store);
}
return dp[level][cnt] = ans;
}
void calc()
{
cin>>n>>k;
memset(dp,-1,sizeof(dp));
for(ll i=1;i<=n;i++)
cin>>arr[i];
sort(arr+1,arr+n+1);
cout<<rec(n,k)<<"\n";
}
int main()
{
ll t; cin>>t;
while(t--)
calc();
return 0;
}Ciel and Eggs CodeChef Solution in C
#include <stdio.h>
#define gc getchar//_unlocked
inline int getn(){
int n = 0, c = gc();
while(c < '0' || c > '9') c = gc();
while(c >= '0' && c <= '9')
n = (n<<3) + (n<<1) + c - '0', c = gc();
return n;
}
#define MAX 2000000009
void swap(int* a, int* b){
int t = *a;
*a = *b;
*b = t;
}
void quickSort(int* a, int l, int r){
int c,p,i,j;
if(l + 10 <= r){
c = (l + r) / 2;
if(a[c] < a[l])
swap(a+l, a+c);
if(a[r] < a[l])
swap(a+r, a+l);
if(a[r] < a[c])
swap(a+r, a+c);
swap(a+c, a+r-1);
p = a[r-1], i = l, j = r - 1;
while(1){
while(a[++i] < p);
while(p < a[--j]);
if(i < j)
swap(a+i, a+j);
else
break;
}
swap(a+i, a+r-1);
quickSort(a, l, i-1);
quickSort(a, i+1, r);
}else{
for(i = l + 1; i <= r; i++){
p = a[i];
for(j = i; j > l && p < a[j-1]; j--)
a[j] = a[j-1];
a[j] = p;
}
}
}
int min(int a, int b){
return a < b ? a : b;
}
int main(){
int T = getn(),N,K, i,j, a[501],b[501], r,s,t;
while(T--){
N = getn(), K = getn(), r = MAX, s = a[0] = b[0] = 0;
for(i = 1; i < N+1; ++i)
a[i] = getn();
quickSort(a, 1, N);
for(i = 0; i < K+1; ++i){
t = a[i];
for(j = i; j < N+1; ++j){
a[j] -= t;
if(j)
b[j] = b[j-1] + a[j];
s += t;
}
t = MAX;
for(j = N; j >= K; --j)
t = min(t, (N - j) * a[j] + b[j] - b[j - (K - i)]);
r = min(r, s + t);
}
printf("%d\n",r);
}
return 0;
}
Ciel and Eggs CodeChef Solution in JAVA
import java.util.*;
import java.math.*;
public class Main{
public static void main(String[] args){
new Main();
}
final long inf = 1L << 40;
class pt{
long x, y;
public pt(long a, long b){
x = a;
y = b;
}
pt minus(pt q){
return new pt(x - q.x, y - q.y);
}
long cross(pt q){
return x * q.y - y * q.x;
}
}
long[] A;
long[][] G = new long[505][505];
pt[] T = new pt[505];
int n, sz;
void add(long x, long y){
pt p = new pt(x, y);
while(sz >= 2 && p.minus(T[sz - 1]).cross(p.minus(T[sz - 2])) <= 0)
sz--;
T[sz++] = p;
if(sz >= 2 && T[sz - 1].x == T[sz - 2].x) sz--;
}
long eval(int i, long x){
return T[i].x * x + T[i].y;
}
public Main(){
Scanner in = new Scanner(System.in);
int t = in.nextInt();
while(t-- > 0){
int K;
n = in.nextInt(); K = in.nextInt();
A = new long[n];
for(int i = 0; i < n; i++) A[i] = in.nextLong();
Arrays.sort(A);
for(int k = 0; k <= K; k++){
sz = 0;
for(int pos = n; pos >= 0; pos--)
if(pos == n) G[pos][k] = k == 0 ? 0L : inf;
else{
if(k > 0 && G[pos + 1][k - 1] != inf)
add(pos + 1, G[pos + 1][k - 1]);
long res = inf;
int le = 0, ri = sz - 1;
while(ri - le >= 4){
int a = le + (ri - le) / 3;
int b = le + (ri - le) * 2 / 3;
if(eval(a, A[pos]) < eval(b, A[pos])) ri = b;
else le = a;
}
for(int it = le; it <= ri; it++)
res = Math.min(res, eval(it, A[pos]) - A[pos] * pos);
G[pos][k] = res;
}
}
long ret = inf;
for(int i = 0; i < n; i++)
ret = Math.min(ret, G[i][K]);
System.out.println(ret);
}
}
}Ciel and Eggs CodeChef Solution in PYTH
import sys
import psyco
psyco.full()
def k_partition(arr, k):
n = len(arr)
A = []
for q in range(k):
A.append([0] * n)
A[0][0] = arr[0]
for q in range(1, k):
A[q][0] = 0
for i in range(n):
A[0][i] = arr[i] * (i + 1)
for q in range(1, k):
for i in range(q, n):
min_partition = sys.maxint
for j in range(q - 1, i):
this_partition = A[q - 1][j] + arr[i] * (i - j)
if this_partition < min_partition:
min_partition = this_partition
A[q][i] = min_partition
min_value = sys.maxint
for i in range(n):
if A[k - 1][i] < min_value and A[k - 1][i] > 0:
min_value = A[k - 1][i]
## if k == n:
## for q in A:
## outstr = ''
## for j in q:
## outstr = outstr + str(j) + '\t'
## print outstr
return min_value
num_tests = int(sys.stdin.readline())
for i in range(num_tests):
param_data = sys.stdin.readline().split()
k = int(param_data[1])
arr = []
str_arr = sys.stdin.readline().split()
for j in range(int(param_data[0])):
arr.append(int(str_arr[j]))
arr.sort(reverse=True)
print k_partition(arr, k)Ciel and Eggs CodeChef Solution Review:
In our experience, we suggest you solve this Ciel and Eggs CodeChef Solution and gain some new skills from Professionals completely free and we assure you will be worth it.
If you are stuck anywhere between any coding problem, just visit Queslers to get the Ciel and Eggs CodeChef Solution.
Conclusion:
I hope this Ciel and Eggs CodeChef Solution would be useful for you to learn something new from this problem. If it helped you then don’t forget to bookmark our site for more Coding Solutions.
This Problem is intended for audiences of all experiences who are interested in learning about Programming Language in a business context; there are no prerequisites.
Keep Learning!
