13099 - Wish List   

Status  |  Limits Submit

Description

During the New Year sale, Panda wants to purchase items from his wish list.

The wish list has N items.
Each item has name, original price, discount, quality (Si, Pi, Di, Qi).
The selling price for an item is its original price subtract discount (Pi − Di)

Panda’s budget is only X dollars which is too less to pruchase all items in wish list.
He designs 3 kinds of purchase strategies for items:

Strategy 1: less selling price first, the item with less selling price will be selected first.
Strategy 2: more discount first, the item with more discount will be selected first.
Strategy 3: higher quality first, the item with higher quality will be selected first.

Panda will sort the wish list by applying these strategies in a special order O.
Then purchase the items from top to down until his budget can’t buy anything.

This problem is a partial judge problem.
You have to complete functions under given interface.
Please refer to function.h, main.c for implementation details.

function.h

#ifndef __FUNCTION_H__
#define __FUNCTION_H__


typedef struct _Item {
    char* name;
    int price;
    int discount;
    int quality;
} Item;

Item* CreateList(int N);
void AddItem( Item* L, int idx, char* name, int price, int discount, int quality );
void DeleteList(Item* L, int N);

int price_cmp( const void* lhs, const void* rhs );
int discount_cmp( const void* lhs, const void* rhs );
int quality_cmp( const void* lhs, const void* rhs );

#endif

main.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "function.h"

#define MAX_NAME 100

typedef int (*func_ptr)(const void*, const void*);

int N, X;
int O[3];
func_ptr cmp[3] = { price_cmp, discount_cmp, quality_cmp };

int qsort_cmp( const void* lhs, const void* rhs){
    for(int i=0; i<3; i++){
        int res = cmp[ O[i]-1 ](lhs, rhs);
        if( res != 0 ) // If not same
            return res;
    }
    // This case will not appear in Test cases;
    int str_res = strcmp( ((Item*)lhs)->name, ((Item*)rhs)->name);
    if( str_res < 0 ) return -1;
    if( str_res > 0 ) return 1;
    return 0;
}


int main(){
    int T;
    scanf("%d", &T);
    for(int cnt=1; cnt<=T; cnt++){
        scanf("%d %d %1d%1d%1d", &N, &X, &O[0], &O[1], &O[2]);

        Item* L = CreateList(N);
        char name[MAX_NAME+1];
        int P, D, Q;
        for(int i=0; i<N; i++){
            scanf("%s %d %d %d", name, &P, &D, &Q);

            AddItem(L, i, name, P, D, Q);
        }
        
        qsort( L, N, sizeof( Item ), qsort_cmp);

        printf("case %d:\n", cnt);
        for(int i=0; i<N; i++){
            int sp = L[i].price - L[i].discount;
            if( sp < X ){
                printf("%s\n", L[i].name);
                X -= sp;
            }
        }
        DeleteList(L, N);
    }
    return 0;
}

Input

This problem contains multiple inputs.
There’s an integer T on the first line, denoting the number of input.

For each input, there’re N, X, O on the first line.
There’re Si, Pi, Di, Qi on the following N lines.

It’s guaranteed that:

  • 1 ≤ T ≤500
  • 1 ≤ N ≤ 1000
  • 1 ≤ X ≤106
  • |Si| ≤ 100
  • (Pi, Di, Qi) ≠ (Pj, Dj, Qj) for all i ≠ j.
  •  O ∈{123, 132, 213, 231, 312, 321 }

Output

Output the item names Panda decides to purchase ( in sorted wish list order ).

Explaintation for Sample I/O:

The budget is 200, and the wish list:

A 120 50 1 // selling price = 70
B 100 40 2 // selling price = 60
C 100 30 2 // selling price = 70
D 100 40 3 // selling price = 60
E 100 30 4 // selling price = 70
  • O = 123:
    • First, sort by selling price (increasing order)
    • Second, sort by discount (decreasing order) for those have the same selling price.
    • Third, sort by quality (decreasing order) for those have the same selling price and discount.
    • The sorted list: 
      D 100 40 3
B 100 40 2
A 120 50 1
E 100 30 4
C 100 30 2
    • Pandas will using 190 dollars to purchase “D”, “B”, “A”
  • O = 312:
    • First, sort by quality
    • Second, sort by selling price for those have the same quality.
    • Third, sort by discount for those have the same selling quality and selling price.
    • The sorted list: 
      E 100 30 4
D 100 40 3
B 100 40 2
C 100 30 2
A 120 50 1
    • Pandas will using 190 dollars to purchase “E”, “D”, “B”

Sample Input  Download

Sample Output  Download

Partial Judge Code

13099.c

Partial Judge Header

13099.h

Tags

#MadeToMakeYouCry



Discuss