Description

Given several operations, push x, pop, print, reverse, create a linked list dynamicly.

• push x: Add one Node (with data = x) at the front of linked list.
• pop: Delete the Node at the front of linked list.
• reverse: reverse the current linked list
• print: output the linked list in given format.

You have to implement 3 functions:

1. void Push(Node** ptr_head,int x)
2. void Pop(Node** ptr_head)
3. void Reverse_List(Node** ptr_head)

Note: Modify the Node* head by Node** ptr_head

Input

There’re operations on several lines.
All operations are one of push x, pop, print, reverse.
It’s guaranteed that:

• Number of operations is less than 5,000,000
• Integer x is in [−1000,1000]
• The maximum length of linked list is less than 10,000.

Output

Output the linked list for every print.

 

Sample Input  Download

Sample Output  Download

Partial Judge Code

12568.c

Partial Judge Header

12568.h

Tags

Discuss

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 ≤10⁶
• |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

Discuss