Description

Denny just learned the sorting method in school.

Sorting once is too easy for him, so the teacher asked a question that needs to be sorted twice to test him.

In this question, you will get N strings of length 6, you need to sort the strings internally according to a ~ z, and then sort the N strings in dictionary order.

For example:

N = 2

S₁ = abcabc, S₂ = ababab

Internally sorted string: S₁ = aabbcc, S₂ = aaabbb

The sorted string after sorting: aaabbb aabbcc

Input

The first line contains a integer N, the number of strings you need to sort

The following line contains N strings S₁ ~ S_N

For all testcase:

1 <= N <= 100

Output

The Output contains only one line, the sorted string after sorting.

note: remember to add a '\n' in the end of output

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

<The part with green text is the only part that differs from problem 14151>

Hodilo is a well-known hot pot restaurant, and it's extremely challenging to have a table during peak dining hours in Hodilo. Even though, the restaurant does not accept reservations in advance, requiring every guest to visit the restaurant, take a number, and wait for their turn. Hodilo is opening a new branch in Hsinchu, and you have been invited to design a queuing system, which helps assign a table to each guest. 

This is a partial judge problem, please trace the code and check the following description.

main.c

In the main function, we start by reading the input, creating the table and guest struct, and simulating the flow of time: 11:00 (OPEN_TIME) ~ 15:00 (CLOSE_TIME).

At certain time points, we check if there are guests leaving at that moment and output the log of a guest leaving the restaurant. Then, we check the frontmost guest who has not yet entered the restaurant and output the log of a guest entering the restaurant if a table is available. Also, we output the status of all the tables every hour.

After the restaurant closes, list the guests who were not fortunate enough to enjoy hot pot today (if any).

(If the frontmost guest is not entering the restaurant, the following guests are blocked by that frontmost guest and have to wait in queue. Guests are allowed to enter the restaurant at closing time and complete their entire dining time)

The output part is already implemented, and you can trace the code and refer to the output format description for more details.

#include <stdio.h>
#include "function.h"
#define TABLE_COUNT 50
#define GUEST_COUNT 50
#define OPEN_TIME 660
#define CLOSE_TIME 900

Table *table[TABLE_COUNT];
Guest *guest[GUEST_COUNT];
int tableCount, guestCount;
int currentGuest = 0;

void tableStatus(int time) {
    printf("%02d:%02d (%d) -> table: |", time/60, time%60, time);
    for (int i=0; i<tableCount; i++) {
        if (table[i]->guest) printf("%s(%dmin)", table[i]->guest->guestName, table[i]->leaveTime-time);
        printf("|");
    }
    printf("\n");
}

int main() {
    scanf("%d", &tableCount);
    for (int i=0; i<tableCount; i++) table[i] = createTable();
    scanf("%d", &guestCount);
    for (int i=0; i<guestCount; i++) guest[i] = createGuest();
    // Problem 14163
    for (int i=0; i<guestCount-1; i++) guest[i]->nextGuest = guest[i+1];  
    for (int i=OPEN_TIME; i<=CLOSE_TIME; i++) {
        while (1) {
            Guest *leave = checkLeave(table, tableCount, i);
            if (!leave) break;
            printf("%02d:%02d (%d) -> %s: leave\n", i/60, i%60, i, leave->guestName);
        }
        while (currentGuest < guestCount && guest[currentGuest]->arriveTime <= i) {
            int success = assignTable(table, tableCount, i, guest[currentGuest]);
            if (!success) break;
            printf("%02d:%02d (%d) -> %s: enter\n", i/60, i%60, i, guest[currentGuest]->guestName);
            currentGuest++;
        }
        if (i % 60 == 0) tableStatus(i);
    }
    // Problem 14163
    if (currentGuest < guestCount) printStillWaiting(guest[currentGuest]);
}

function.h

• Table* createTable() 
  • A function that reads the input, allocates memory for the table struct, and returns it.
• Guest* createGuest() 
  • A function that reads the input, allocates memory for the guest struct, and returns it.
  • Remember to also allocate memory for the guest name string.
• Guest* checkLeave(Table **table, int tableCount, int currentTime) 
  • Given the table array and its size, along with the current time.
  • Find the first table in the array at which the occupied guest is about to leave, return the pointer to that guest, and update the table status (guest = NULL).
    • Check through the array and find the first table where leaveTime == currentTime.
• int assignTable(Table **table, int tableCount, Guest *guest)  
  • Given the table array and its size, along with the guest pointer.
  • Find the first table that is available and large enough for the guest.
    • Check through the array and assign the first available table where table->tableSize >= guest->groupSize.
  • If the table is successfully assigned to the guest, update the table's status (leaveTime, guest) and return 1; otherwise, return 0.
• void printStillWaiting(Guest *guest)         // Problem 14163  
  • In main.c, each guest has a member pointer that points to the next guest in the waiting queue (guest->nextGuest).
  • The first guest who is still waiting is passed to the function, and you should print the names of all the guests who are still waiting. Hint: Utilize nextGuest to iterate through all the guests who are still waiting, starting from the guest passed to the function.

#ifndef __FUNCTION_H__
#define __FUNCTION_H__

typedef struct Guest {
    char *guestName;
    int groupSize;
    int arriveTime;
    int diningTime;
    struct Guest *nextGuest;
} Guest;

typedef struct Table {
    int tableSize;
    int leaveTime;
    Guest *guest;
} Table;

Table* createTable();
Guest* createGuest();
Guest* checkLeave(Table **table, int tableCount, int currentTime);
int assignTable(Table **table, int tableCount, int currentTime, Guest *guest);
void printStillWaiting(Guest *guest);

#endif

Input

• The first line contains an integer N (1 ≤ N ≤ 50), representing the number of tables in the restaurant.
• The second line contains N integers x₁, x₂, ..., x_n (1 ≤ x_i ≤ 4) , each representing the size of a table in the restaurant.
• The third line contains an integer M (1 ≤ M ≤ 50), representing the number of incoming guests.
• Each of the following M lines represents the information of each guest, containing a string and three integers.
  These represent the guest name, the size of the guest group, the arrival time, and the dining time.
  • The guest name is a string consisting only of the English alphabet a-z/A-Z, and its size does not exceed 10 characters.
  • 1 ≤ size of the guest group ≤ 4
  • 660 ≤ arrival time ≤ 900
    • The time is represented in the format of the number of minutes after 00:00.
    • The arrival times are guaranteed to be in non-decreasing order.
  • 1 ≤ dining time ≤ 300 (mins)

Output

(This part is already implemented in main.c)
A program that outputs the log for each guest entering and leaving the restaurant.

For every moment a table is ready to be assigned to an arriving guest or when a guest is about to leave, output
hh:rr(minsAfter00:00) -> guestName: enter/leave

Additionally, every hour, output the status of the N tables,
including the names of the occupied guests and their remaining dining time:
hh:rr(minsAfter00:00) -> |guestName(remainingTime)|...|guestName(remainingTime)|

(This part has not been implemented yet.)

At the end, output the names of those guests who are still waiting and cannot get into the restaurant.
If there are such guests, output one line: Still waiting: <guestName1>,<guestName2>,<guestName3>
Remember to print \n at the end.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss