In this post, we will solve HackerRank Accessory Collection Problem Solution.
Victoria is splurging on expensive accessories at her favorite stores. Each store stocks A types of accessories, where the ith accessory costs i dollars (1 ≤ i ≤ A). Assume that an item’s type identifier is the same as its cost, and the store has an unlimited supply of each accessory.
Victoria wants to purchase a total of L accessories according to the following rule:
Any N-element subset of the purchased items must contain at least D different types of accessories.
For example, if L = 6, N = 3, and D = 2, then she must choose 6 accessories such that any subset of 3 of the 6 accessories will contain at least 2 distinct types of items.
Given L. A. N. and D values for T shopping trips, find and print the maximum amount of
money that Victoria can spend during each trip: if it’s not possible for Victoria to make a
purchase during a certain trip, print SAD instead. You must print your answer for each trip
on a new line.
Input Format
The first line contains an integer. T. denoting the number of shopping trips. Each of the T subsequent lines describes a single shopping trip as four space-separated integers corresponding to L. A. N. and D. respectively.
Output Format
For each shopping trip, print a single line containing either the maximum amount of money Victoria can spend; if there is no collection of items satisfying her shopping rule for the trip’s L, A, N, and D values, print SAD instead.
Sample Input
2
6 5 3 2
2 1 2 2
Sample Output
24
SAD
Explanation
Shopping Trip 1:
We know that:
Victoria wants to buy L = 6 accessories.
The store stocks the following A = 5 types of accessories: {1, 2, 3, 4, 5}.
For any grouping of N = 3 of her L accessories, there must be at least D = 2 distinct types of accessories.
Victoria can satisfy her shopping rule and spend the maximum amount of money by purchasing the following set of accessories: {3, 4, 5, 5, 4, 3}. The total cost is
3+4+5 +5 +4+3 = 24, so we print 24 on a new line.
Shopping Trip 2:
We know that:
Victoria wants to buy L = 2 accessories.
The store stocks A = 1 type of accessory: {1}.
For any grouping of N = 2 of her L accessories, there must be at least D = 2 distinct types of accessories.
Because the store only carries 1 type of accessory, Victoria cannot make a purchase satisfying the constraint that there be at least D = 2 distinct types of accessories. Because Victoria will not purchase anything, we print that she is SAD on a new line.
Accessory Collection C Solution
#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
#include <limits.h>
#include <stdbool.h>
int main(){
int T;
scanf("%d",&T);
for(int a0 = 0; a0 < T; a0++){
int L;
int A;
int N;
int D;
scanf("%d %d %d %d",&L,&A,&N,&D);
if (D == 1) {
printf("%lld\n", (long long)A*L);
continue;
}
int max, min, i, q, r;
long long count, result = 0;
max = (N-1)/(D-1);
if ((L-(N-1)+max-1)/max+D-1 > A) {
printf("SAD\n");
continue;
}
min = (L-(N-1)+A-(D-1)-1)/(A-(D-1));
for (i=max; i>=min; i--) {
q = (L-(N-1))/i;
r = (L-(N-1))%i;
count = (long long)(A-(D-1+q))*r + (long long)(A-(D-1+q)+1+A-1)*(D-2+q)/2*i + (long long)A*(N-1-i*(D-2));
if (count <= result) {
break;
}
result = count;
}
printf("%lld\n", result);
}
return 0;
}Accessory Collection C++ Solution
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
long long sumrange(long long a, long long b) {
long long res1 = (b * (b + 1)) / 2;
long long res2 = (a * (a - 1)) / 2;
return res1 - res2;
}
long long process(long long l, long long a, long long n, long long d) {
if (a < d)
return -1; /// Less then d different items to pick from
/// The first d-1 most expensive items will sum up to n-1
/// Let x be the frequency of (d-1) item
/// All items on left of (d-1) have higher or same frequency
/// And on right have equal frequency, except for the last one
/// What are the possible values of x?
if (d == 1)
return l * a; /// To avoid divison by zero on next line
long long upperlimit = (n - 1) / (d - 1);
long long res = 0;
for (int x = 1; x <= upperlimit; x++) {
/// If (d-1) index has value x, then all the values on left will be x
/// Except for the first one
/// Sum of first (d-1) items should be equal to n, and each item should have
/// at least equal to x value
long long extra =
((n - 1) - (d - 1) * x); /// The extra frequency of first item
/// If we remove the extra, all items can have at most x frequency
if (extra + a * x < l)
continue;
long long temp = extra * a;
/// Number of items bought with frequency x
long long num = (l - extra) / x;
long long subtotal = sumrange(a - num + 1, a);
temp += subtotal * x;
/// Possible that there is a last cell with less than x frequncy
if ((l - extra) % x != 0) {
long long last = (l - extra) % x;
temp += last * (a - num);
}
if (temp > res)
res = temp;
}
if (res == 0)
res = -1;
return res;
}
int main() {
// freopen("input.txt", "r", stdin );
int kase;
scanf("%d", &kase);
while (kase--) {
long long l, a, n, d;
scanf("%lld %lld %lld %lld", &l, &a, &n, &d);
long long res = process(l, a, n, d);
if (res == -1)
printf("SAD\n");
else
printf("%lld\n", res);
}
return 0;
}Accessory Collection C Sharp Solution
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Text;
class Solution {
static void Main(String[] args) {
var sb = new StringBuilder();
int tc = int.Parse(Console.ReadLine());
while (tc-- > 0) {
var tmp = Console.ReadLine().Split(' ');
int L = int.Parse(tmp[0]); // number of accessories
int A = int.Parse(tmp[1]); // types of accessories
int N = int.Parse(tmp[2]); // size of choosen subset
int D = int.Parse(tmp[3]); // at least different items
long ans = -1;
if (D > A) {
ans = -1;
} else if (D == 1) {
ans = Math.BigMul(L, A);
} else {
for (int i = L; i >= 1; i--) {
long ter = sol(L, A, N, D, i);
if (ter > ans) {
ans = ter;
} else if (ans != -1) break;
}
}
sb.Append(ans == -1 ? "SAD" : ans.ToString()).Append("\n");
}
Console.WriteLine(sb.ToString());
}
static long sol(long L, long A, long N, long D, long mid) {
long p = A - D + 1;
long top = mid + (N - 1 - mid * (D - 1));
if (top < mid) return -1;
long sum = mid;
long gold = mid * p;
for (long i = A; i > p; i--) { sum += top; gold += i * top; }
long r = p + 1;
while (sum > N && r < A) {
sum += mid - top;
gold += mid * r - top * r;
r++;
}
if (L < sum) return -1;
if (L == sum) return gold;
L -= sum;
r = p - 1;
if (r * mid < L) return -1;
var fix = L / mid;
var rem = L - fix * mid;
gold += mid * (q(r) - q(r - fix));
gold += rem * (r - fix);
return gold;
}
static long q(long n) {
return n * (n + 1) / 2;
}
}Accessory Collection Java Solution
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;
public class Solution {
static String acessoryCollection(long L, long A, long N, long D) {
long max=0;
if(D>N || N>L){
return "SAD";
}else if(D==1){
return String.valueOf(A*L);
}else{
long cmid=(N-1)/(D-1);
for(long mid=cmid;mid>=1;mid--){
long clarge=N+(mid-1)-((D-1)*mid);
long n=(L-clarge)/mid;
long csmall=(L-clarge)%mid;
if(n>A-1 || (csmall>0 && n==A-1)){
break;
}
long sum=clarge*A+csmall*(A-n-1)+(((A-1+A-n)*(n) *mid)/2);
if(sum<max)break;
max=sum;
}
}
if(max==0){
return "SAD";
}else{
return String.valueOf(max);
}
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int T = Integer.parseInt(scanner.nextLine().trim());
for (int TItr = 0; TItr < T; TItr++) {
String[] LAND = scanner.nextLine().split(" ");
long L = Long.parseLong(LAND[0].trim());
long A = Long.parseLong(LAND[1].trim());
long N = Long.parseLong(LAND[2].trim());
long D = Long.parseLong(LAND[3].trim());
String result = acessoryCollection(L, A, N, D);
bufferedWriter.write(result);
bufferedWriter.newLine();
}
bufferedWriter.close();
}
}Accessory Collection Python Solution
#!/bin/python3
import os
import sys
#
# Complete the acessoryCollection function below.
#
def acessoryCollection(L, A, N, D):
#
# Write your code here.
#
if D > A or N < D or N > L:
return "SAD"
elif D == 1:
return str (L * A)
else:
max = 0
a2Max = (N - 1) // (D - 1)
for a2 in range (a2Max, 0, -1):
a1 = N + (a2 - 1) - a2 * (D - 1)
n = (L - a1) // a2
a3 = (L - a1) % a2
if n > A - 1 or n == A - 1 and a3 > 0: break
sum = A * a1 + (A - 1 + A - n) * n // 2 * a2 + a3 * (A - n - 1)
if sum <= max: break
max = sum
if max: return str (max)
else: return "SAD"
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
T = int(input())
for T_itr in range(T):
LAND = input().split()
L = int(LAND[0])
A = int(LAND[1])
N = int(LAND[2])
D = int(LAND[3])
result = acessoryCollection(L, A, N, D)
fptr.write(result + '\n')
fptr.close()
