Soluție HackerRank pentru Accessory Collection. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Accessory Collection

Cerinta completa

Victoria is splurging on expensive accessories at her favorite stores. Each store stocks [Expresie matematică indisponibilă în copia arhivată] types of accessories, where the [Expresie matematică indisponibilă în copia arhivată] accessory costs [Expresie matematică indisponibilă în copia arhivată] dollars ([Expresie matematică indisponibilă în copia arhivată]). 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 [Expresie matematică indisponibilă în copia arhivată] accessories according to the following rule:

Any [Expresie matematică indisponibilă în copia arhivată]-element subset of the purchased items must contain at least [Expresie matematică indisponibilă în copia arhivată] different types of accessories.

For example, if [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], and [Expresie matematică indisponibilă în copia arhivată], then she must choose [Expresie matematică indisponibilă în copia arhivată] accessories such that any subset of [Expresie matematică indisponibilă în copia arhivată] of the [Expresie matematică indisponibilă în copia arhivată] accessories will contain at least [Expresie matematică indisponibilă în copia arhivată] distinct types of items.

Given [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], and [Expresie matematică indisponibilă în copia arhivată] values for [Expresie matematică indisponibilă în copia arhivată] 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, [Expresie matematică indisponibilă în copia arhivată], denoting the number of shopping trips.
Each of the [Expresie matematică indisponibilă în copia arhivată] subsequent lines describes a single shopping trip as four space-separated integers corresponding to [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], and [Expresie matematică indisponibilă în copia arhivată], respectively.

Constraints

  • [Expresie matematică indisponibilă în copia arhivată]
  • [Expresie matematică indisponibilă în copia arhivată]
  • [Expresie matematică indisponibilă în copia arhivată]
  • The sum of the [Expresie matematică indisponibilă în copia arhivată]‘s for all [Expresie matematică indisponibilă în copia arhivată] shopping trips [Expresie matematică indisponibilă în copia arhivată].

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 [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], and [Expresie matematică indisponibilă în copia arhivată] 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 [Expresie matematică indisponibilă în copia arhivată] accessories.
  • The store stocks the following [Expresie matematică indisponibilă în copia arhivată] types of accessories: [Expresie matematică indisponibilă în copia arhivată].
  • For any grouping of [Expresie matematică indisponibilă în copia arhivată] of her [Expresie matematică indisponibilă în copia arhivată] accessories, there must be at least [Expresie matematică indisponibilă în copia arhivată] distinct types of accessories.

Victoria can satisfy her shopping rule and spend the maximum amount of money by purchasing the following set of accessories: [Expresie matematică indisponibilă în copia arhivată]. The total cost is [Expresie matematică indisponibilă în copia arhivată], so we print [Expresie matematică indisponibilă în copia arhivată] on a new line.

Shopping Trip 2:
We know that:

  • Victoria wants to buy [Expresie matematică indisponibilă în copia arhivată] accessories.
  • The store stocks [Expresie matematică indisponibilă în copia arhivată] type of accessory: [Expresie matematică indisponibilă în copia arhivată].
  • For any grouping of [Expresie matematică indisponibilă în copia arhivată] of her [Expresie matematică indisponibilă în copia arhivată] accessories, there must be at least [Expresie matematică indisponibilă în copia arhivată] distinct types of accessories.

Because the store only carries [Expresie matematică indisponibilă în copia arhivată] type of accessory, Victoria cannot make a purchase satisfying the constraint that there be at least [Expresie matematică indisponibilă în copia arhivată] distinct types of accessories. Because Victoria will not purchase anything, we print that she is SAD on a new line.

Limbajul de programare folosit: cpp14

Cod:

#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;
}

Scor obtinut: 1.0

Submission ID: 464650200

Link challenge: https://www.hackerrank.com/challenges/accessory-collection/problem

Accessory Collection