# Contest : Carnival Finale Coding Competition | CodeChef

codermine29 | CodeChef User Profile for Nishtha Kapoor | CodeChef
Tester: Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9
Editorialist: Codechef Adgitm Chapter : https://www.codechef.com/users/test_account_9

Medium

# PROBLEM:

Chef and Priyank are close friends. The chef is looking for ingredients to make his best cuisine, priyank is helping Chef in search for the ingredients. Priyank is preparing the list having the prices of the ingredients(Note: There can be two prices for the same ingredient). But priyank lost the track record. So, now he want you to find the two possible lists having the maximum difference in cost. There must be only n ingredients And the total sum of prices is given. Find the two lists if possible else you can print NO.

Note : The whole list can be imagined as integer so list can’t have zero as first price of list

# EXPLANATION:

Use Even Odd concept.

# SOLUTION:

C++:
#include <bits/stdc++.h>
using namespace std;

vector finddiff(vector mx, vector mn) {
int cr = 0, st = mx.size() - 1;
// for(int i = 0; i <= st; i++) {
// cout << mx[i];
// }
// cout << endl;
// for(int i = 0; i <= st; i++) {
// cout << mn[i];
// }
// cout << endl;
vector ans;
while (st >= 0) {
if (mx[st] - cr >= mn[st]) {
ans.push_back(mx[st] - cr - mn[st]);
cr = 0;
}
else {
ans.push_back(10 + mx[st] - cr - mn[st]);
cr = 1;
}
st–;
}
reverse(ans.begin(), ans.end());
return ans;
}

void solve() {
int n , s;
cin >> n >> s;
vector f(n,0),se(n,0);
f[0] = 1;
se[0] = 1;
if(s < n || s > n*9) {
cout << “NO” << endl;
return;
}
s -= 1;
int num = s;
for(int i = 0; i < n; i++) {
if(f[i]) {
if(num >= 8) {
f[i] += 8;
num -= 8;
} else {
f[i] += num;
num -= num;
break;
}
}
else {
if(num >= 9) {
f[i] = 9;
num -= 9;
} else {
f[i] = num;
num -= num;
break;
}
}
}

``````for(int i = n-1; i >= 0; i--) {
if(se[i]) {
if(s >= 8) {
se[i] += 8;
s -= 8;
} else {
se[i] += s;
s -= s;
break;
}
}
else {
if(s >= 9) {
se[i] = 9;
s -= 9;
} else {
se[i] = s;
s -= s;
break;
}
}
}

vector<int> ans = finddiff(f,se);
int i = 0;
while(i < n && ans[i] == 0) {
i++;
}
for(; i < n; i++) {
cout << ans[i] ;
}
cout << endl;