50062. Merge Book Information

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

Task Description

Given an array of BookAuthor and an array of BookSelling, write a function merge to merge the two arrays and put the result into a BookInfoList structure.

The BookAuthor and BookSelling structures contain the author and the selling status of books respectively. They are defined as follows:

typedef struct {
    char book_title[MAXL], author[MAXL];
}BookAuthor;
 
typedef struct {
    char book_title[MAXL];
    int selling, date;
}BookSelling;

Your goal is to merge BookAuthor and BookSelling of the same $book$_$title$ into a BookInfo structure. The BookInfo structure contains both the author and selling status of the book, which is defined as follows:

typedef struct {
    char book_title[MAXL], author[MAXL];
    int selling, date;
}BookInfo;

All the $book$_$title$s in BookAuthor array will be unique. However, a $book$_$title$ may appear in BookSelling array multiple times and you need to create a BookInfo structure for each different $date$. A book will not have multiple selling information for the same date.

Finally, return an BookInfoList structure containing the BookInfo structures of all the books. The structure BookInfoList is defined as follows:

typedef struct {
    int num; // the number of BookInfo
    BookInfo books[MAXN];
}BookInfoList;

Integer $num$ indicates the number of BookInfo, and those books' information are the first $num$ elements of array $books$. The $books$ array should be alphabetically sorted by $book$_$title$. If a $book$_$title$ has multiple selling dates, sort them by the $date$ value increasingly.

The prototype of the function you need to implement is as follows:

BookInfoList merge(int N, int M, BookAuthor authorArr[], BookSelling sellingArr[]);

$N$ and $M$ are the length of $authorArr$ and $sellingArr$ respectively. If a $book$_$title$ appears only in BookAuthor array but not in BookSelling array (or vise versa), you don't need to create a BookInfo for this book.

Header and Main Program

book.h

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#ifndef _BOOK_H
#define _BOOK_H
 
#define MAXN 100
#define MAXL 25
 
typedef struct {
    char book_title[MAXL], author[MAXL];
}BookAuthor;
 
typedef struct {
    char book_title[MAXL];
    int selling, date;
}BookSelling;
 
typedef struct {
    char book_title[MAXL], author[MAXL];
    int selling, date;
}BookInfo;
 
typedef struct {
    int num; // the number of BookInfo
    BookInfo books[MAXN];
}BookInfoList;
 
BookInfoList merge(int N, int M, BookAuthor authorArr[], BookSelling sellingArr[]);
 
#endif

main.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>
#include <assert.h>
#include "book.h"
 
int main(){
    int N, M;
    BookAuthor authorArr[MAXN];
    BookSelling sellingArr[MAXN];
 
    assert(scanf("%d %d", &N, &M) == 2);
    for(int i = 0; i < N; i++)
        assert(scanf("%s %s", authorArr[i].book_title,
                              authorArr[i].author) == 2);
 
    for(int i = 0; i < M; i++)
        assert(scanf("%s %d %d", sellingArr[i].book_title,
                                 &sellingArr[i].selling,
                                 &sellingArr[i].date) == 3);
 
    BookInfoList result = merge(N, M, authorArr, sellingArr);
 
    for(int i = 0; i < result.num; i++)
        printf("%s %s %d %d\n", result.books[i].book_title,
                                result.books[i].author,
                                result.books[i].date, result.books[i].selling);
 
    return 0;
}

compile

gcc -std=c99 -O2 -c main.c -lm
gcc -std=c99 -O2 -c book.c -lm
gcc -std=c99 -O2 book.o main.o -lm

Input Format

Input contains one test case. The first line contains two integers $N$ and $M$, indicating the number of BookAuthor and BookSelling respectively. For the next $N$ lines, each line contains two strings, indicating the book title and book author. For the last $M$ lines, each line contains a string and two integers, indicating the book title, the selling and the date.

  • All strings contain only English letters.
  • $1 \leq \text{the length of title and author} \leq 20$
  • $1 \leq date \leq 2^{31} - 1$
  • $1 \leq selling \leq 100000$
  • $1 \leq N, M \leq 100$

Output Format

Output the BookInfoList returned.

Sample Input 1

3 3
SnowWhite Grimm
HarryPotter JKRowling
SteveJobs WalterIsaacson
SnowWhite 1012 19910631
HarryPotter 875 20060828
SteveJobs 189 20150709

Sample Output 1

HarryPotter JKRowling 20060828 875
SnowWhite Grimm 19910631 1012
SteveJobs WalterIsaacson 20150709 189

Sample Input 2

3 3
SnowWhite Grimm
HarryPotter JKRowling
SteveJobs WalterIsaacson
SnowWhite 1012 19910631
SnowWhite 875 18870128
SteveJobs 189 20150709

Sample Output 2

SnowWhite Grimm 18870128 875
SnowWhite Grimm 19910631 1012
SteveJobs WalterIsaacson 20150709 189

Discussion