In this HackerEarth Old Keypad in a foreign land problem solution Some people remain old fashioned and John is one of them. He doesn't like the new smart phones with full keypads and still uses the old keypads which require you to tap a key multiple times to type a single letter. For example, if the keyboard has two keys, one with the letters "adef" and the other one with the letters "zyx", then typing 'a' requires one keystroke, typing 'f' requires four keystrokes, typing 'y' requires two keystrokes, and so on.

He recently moved to a new country where the language is such that his keypad is not the most efficient. In every language some characters occur more often than others. He wants to create a specific keyboard for this language that uses N different letters. He has a large body of text in this language, and has already analyzed it to find the frequencies of all N letters of its alphabet.

You are given an array 'frequencies' with N elements. Each element of frequencies is the number of times one of the letters in the new language appears in the text John has. Each element of frequencies will be strictly positive. (I.e., each of the N letters occurs at least once.)

You are also given an array keySize. The number of elements of keySize is the number of keys on the keyboard. Each element of keySize gives the maximal number of letters that maybe put on one of the keys.

Find an assignment of letters to keys that minimizes the number of keystrokes needed to type the entire text. Output that minimum number of keystrokes. If there is not enough room on the keys and some letters of the alphabet won't fit, Output -1 instead.


HackerEarth Old keypad in a foreign land problem solution


HackerEarth Old keypad in a foreign land problem solution.

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<fstream>
#include<cstdlib>
#include<cassert>
#include<vector>
#include<algorithm>
#include<stack>
#include<set>
#include<map>
#include<list>
#include<math.h>
#include<ctime>
#define LL long long
#define ULL unsigned long long
#define F first
#define S second
#define pb push_back
#define FOR(i,lb,ub) for(i=lb;i<=ub;i++)
#define RFOR(i,ub,lb) for(i=ub;i>=lb;i--)
#define FORS(it,v) for(it=v.begin();it!=v.end();it++)
#define st_clk double st=clock();
#define end_clk double en=clock();
#define show_time cout<<"\tTIME="<<(en-st)/CLOCKS_PER_SEC<<endl;
#define sc(n) scanf("%d",&n)
#define scst(n) scanf("%s",n)
#define f_in(st) freopen(st,"r",stdin);
#define f_out(st) freopen(st,"w",stdout);
LL gcd(LL a, LL b) { return b?gcd(b,a%b):a; }
using namespace std;
#ifndef ONLINE_JUDGE
inline int getchar_unlocked() { return getchar(); }
#endif
template <class T>
inline void r_f(T &p)
{
char c;
int neg=0;
while ((c=getchar_unlocked()) < 48 || c > 57)
if (c==45)
neg=1;
p=c-48;
while ((c=getchar_unlocked()) >= 48 && c <= 57) p=p*10+c-48;
if (neg) p*=-1;
}
int main()
{
#ifndef ONLINE_JUDGE
f_in("in.txt");
//f_out("out.txt");
#endif
int n,ar[55],ks,key_ar[1005],key_sum=0,i;
cin>>n;
assert(n<=50);
FOR(i,0,n-1)
{
cin>>ar[i];
assert(ar[i]<=1000);
}
sort(ar,ar+n);
cin>>ks;
assert(ks<=50);
FOR(i,0,ks-1)
{
cin>>key_ar[i];
assert(key_ar[i]<=50);
key_sum += key_ar[i];
}
sort(key_ar,key_ar+ks);
if (key_sum<n)
{
cout<<-1;
return 0;
}
int ans=0,indx=1,j;
for (i=n-1;i>=0;)
{
for (j=0;j<ks && i>=0;j++)
{
if (key_ar[j]>0)
{
key_ar[j]--;
ans += indx*ar[i];
i--;
}
}
indx++;
}
cout<<ans;

return 0;
}