50176. Bidding

I'm a slow walker, but I never walk backwards.

Task Description

Write a program to simulate bidding. You are given a sequence of bids in the order of time. Each bid has a bidder ID, an item ID, and a bid price. We are also given the a minimum price for each item that the seller is willing to sell the item. For each item, the bidder offering the highest bid, if it is no less than the minimum price offered by the seller, will get the item with his bid (called the closing price). If there are more than one bidder offering the same closing price, the first bidder (in time) offering that price gets the item.

For each item, if it is sold successfully, you need to print the bidder ID who wins the bid and the closing price. The output is sorted in increasing bidder ID order. If a bidder bids successfully for multiple items, you have to print the items in increasing item ID order.

Please write a function to print the results of the bidding. All data are stored in structures, and they are defined in bidding.h:

typedef struct bid {
  int bidderID;
  int itemID;
  int bidPrice;
} Bid;
 
typedef struct itemMinPrice{
  int itemID;
  int minPrice;
} ItemMinPrice;
 
void bidding(Bid bidSeq[], int m, ItemMinPrice minPriceSeq[], int n);

Here is the main function:

#include <stdio.h>
#include "bidding.h"
 
int main(int argc, char const *argv[]) {
  int m, n;
  scanf("%d%d", &m, &n);
  Bid bidSeq[m];
  ItemMinPrice minPriceSeq[n];
  for(int i = 0; i < m; i++) {
    scanf("%d%d%d", &bidSeq[i].bidderID, &bidSeq[i].itemID, &bidSeq[i].bidPrice);
  }
  for(int i = 0; i < n; i++) {
    scanf("%d%d", &minPriceSeq[i].itemID, &minPriceSeq[i].minPrice);
  }
  bidding(bidSeq, m, minPriceSeq, n);
  return 0;
}

Input Format (for main.c)

The first line has $m$ and $n$. $m$ is the length of $bidSeq$, and $n$ is the length of $minPriceSeq$. The following $m$ lines have $bidderID$, $itemID$, and $bidPrice$ for all bids. The following $n$ lines have $itemID$ and $minPrice$ for all items. All prices and IDs are not negative integers.

  • $0\leq m\leq 10000$
  • $1\leq n\leq 1000$

Output Format

Print “Bidder XXX gets item YYY with ZZZ dollars” in each line.

  • XXX is the $bidderID$ of the winner.
  • YYY is the $itemID$.
  • ZZZ is the closing price.

Sample Input 1

4 3
11111 0 123
11111 1 333
12333 2 99
12344 1 777
0 100
1 100
2 100

Sample Output 1

Bidder 11111 gets item 0 with 123 dollars
Bidder 12344 gets item 1 with 777 dollars

Sample Input 2

6 5
11111 1 123
11111 0 333
22222 3 1234
12333 2 99
12344 1 123
10000 3 4321
0 100
1 100
2 100
3 100
4 100

Sample Output 2

Bidder 10000 gets item 3 with 4321 dollars
Bidder 11111 gets item 0 with 333 dollars
Bidder 11111 gets item 1 with 123 dollars

Discussion