Description

Wild cats take care of each other in the wild. However, when winter comes, the preys are not enough to feed all the cats. Therefore, the cats dine according to the order of their occupations. The order is as follows:
1. elder
2. nursy
3. kitty
4. warrior
5. apprentice
6. medicent
7. deputy
8. leader

In the tradition of the cat society, three different cats serve as the medicent, the deputy, and the leader respectively.
As for the other cats, except that the apprentices have the dining priority of the young over the old, for the other occupations, the old have higher priority. If the occupations and the ages of two or more cats are the same, they will dine in lexicographic order according to their names.

Input

There are multiple test cases.

The first line of each test case contains two integers N and M, indicating the number of cats and the portions of food respectively, where 0<N,M<=10000.

The next N lines are the information of each cat, including name, occupation, and age.
The length of the names will not exceed 30 letters and will contain no spaces.

Output

Please output the cats that could eat the food in order, each name a line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

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

Partial Judge Header

Tags

Discuss

Description

Ranking system is common in everyday life.
Such as shopping site, mobile game, project contest, etc.

You have a struct of Node and a Table store Node*:
There’re 3 kinds of operation:

• INSERT score, name: Add Node* with (score, name) into Table.
• DELETE name: Delete the Node* with name in the Table.
• TOP x: Return int array contains the indices of top x Nodes in Table.
  The rank of Node* is defined below:
  • The higher score, the higher rank
  • For those with same score, ranking by their names in lexicological order.

Your task is to complete these 3 operations in ranking system.
Please trace the main.c, function.h for the detail interface and implementation.

main.c

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

#define MAX_SIZE 1000
#define MAX_LEN 100
int N = 0;
Node* Table[MAX_SIZE];


int main(){
    for(int i=0; i<MAX_SIZE; i++)
        Table[i] = NULL;

    int K;
    scanf("%d", &K);

    char op[10];

    while( K-- ){
        // printf("K: %d\n", K);
        scanf("%s", op);
        if( strcmp(op, "INSERT" ) == 0 ){
            int score;
            char name[MAX_LEN+1];
            scanf("%d %s", &score, name );

            Insert(Table, N, score, name );
            N++;
        }
        else if( strcmp(op, "DELETE" ) == 0 ){
            char name[MAX_LEN+1];
            scanf("%s", name);

            Delete(Table, N, name );
            N--;
        }
        else if( strcmp(op, "TOP" ) == 0 ){
            int x;
            scanf("%d", &x);

            int* idxs = Top(Table, N, x);
            printf("Top %d:\n", x);
            for(int i=0; i<x; i++){
                printf("%d %s\n", Table[idxs[i]]->score, Table[idxs[i]]->name );
            }
            free( idxs );
        }
    }
    for(int i=0; i<MAX_SIZE; i++){
        if( Table[i] != NULL ){
            free(Table[i]->name);
            free(Table[i]);
            Table[i] = NULL;
        }
    }

    return 0;
}

functin.h

// function.h
#ifndef __FUNCTION_H__
#define __FUNCTION_H__

typedef struct{
    int score;
    char* name;
} Node;

// Node* Table[MAX_SIZE];
// N = number of nodes in Table
 
void Insert( Node** Table, int N, int score, char* name );
void Delete( Node** Table, int N, char* name );
int* Top( Node** Table, int N, int x);
#endif

Input

There’s an integer K on the first line.
There’s 1 operation on the each of following K lines.

It’s guaranteed that:

• The # of elements in Table will not exceed 1000 during the process
• 1 ≤ The length of all names ≤ 100
• All names are distinct.

Output

Print the top x students in the Table for each TOP x operation.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

Last Pokemon Contest (神奇寶貝華麗大賽) between Satoshi (小智) and Haruka (小遙) ! After Satoshi won the victory in Battle Pyramid, Satoshi and Haruka signed up for an unofficial Pokemon Contest in Terracotta Town.

Pokemon Contest is a contest in which trainers and Pokemons coordinate strength and beauty. It is divided into two stages. In the first stage, the Performance Stage, trainers and their Pokemons will perform moves to showcase their styles and skills. In the second stage, the Battle Stage, trainers battles against each other as well as demonstrating charm of their Pokemons.

Satoshi and Haruka met in the Battle stage, where Satoshi's Sceptile (蜥蜴王) fought against Haruka's Blaziken (火焰雞). In the final ten seconds of the battle, Haruka's Blaziken activates Blaze (猛火) and fires Overheat (過熱). To battle in a dazzling style, the pattern of Overheat is cleverly designed with golden ratio:

The pattern of Overheat can be expressed with a string. First, Haruka and Blaziken design two short patterns F0 and F1. Then they generate longer patterns using the following recurrence formula: Fn-2 + Fn-1 = Fn (+ means string concatenation). Finally, Haruka tells Blaziken a number n, and Blaziken fires the Overheat with pattern Fn.

Given F0, F1, n, and k, please find out the k-th character in Fn.

For full episode, please google "AG191 Satoshi vs. Haruka! Last Battle!!" or refer to this page.

Explanation on Sample IO

All test data provide same F0 = "abc", F1 = "def". We can generate the following patterns:

• F2 = "abcdef"

• F3 = "defabcdef"

• F4 = "abcdefdefabcdef"

The first test data asks 0-th character of F0, therefore output 'a'. Similarly, the outputs for the second to fifth test data are 'd', 'f', 'f', 'e', respectively.

Input

The input contains multiple test data. The first line of input contains an integer T, being number of test data. After that are T test data.

The first line of test data contains two non-empty strings F0 and F1.

The second line of test data contains two integers n and k.

• 1 <= T <= 100

• F0 and F1 contain only lower case alphabets (a-z) and have length no greater than 2000.

• 0 <= n < 60 and 0 <= k < |Fn|, where |Fn| is length of Fn

Output

For each test data, output the answer in a single line.  Remember to add new line in the end.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

There are N students in the class, the teacher wants to play a game with them, the student who makes the longest sentence will win.
But there are rules for making sentences, in this game each operation is randomly drawn, the teacher will randomly select students who can make sentences, and randomly decide what they can do.

There are 5 types of operations:

1. add x s: Add the string s to the end of the sentence of student x
2. delete x k: Delete the last k characters word of student x's sentence(do nothing if the sentence is empty)
3. swap x y: Swap sentences of student x and student y
4. longest: Output the length of the longest sentence and the sentence, if many students have same length, output the sentence of the student with smallest number.
5. all: Print all sentences from student 1 to N

Input

The first line contains two integers N, M: the number of students and the number of operations.
The following M lines, each line contains one type of operation.

testcases:

(3/6) 0 < x, y <= N <= 100, 0 < M <= 100, 0 < |s| <= 100 

(3/6) 0 < x, y <= N <= 100, 0 < M <= 10000, 0 < |s| <= 100

Note that: s is the string to be added during the add operation, the length of student's sentence may exceed 100.

Note: Please use malloc() and free() properly.

Output

See the description

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a string \(s\) that consists of only lowercase Latin characters, there are \(Q\) operations to apply on this string.

There are 3 types of operations, with the following 3 forms:

• \(1\) \(A\) \(B\)
• \(2\) \(id\) \(C\)
• \(3\) \(id_a\) \(id_b\)

For operation of type \(1\), you have to turn every \(A\) in the given string to \(B\).

For operation of type \(2\), you have to set the \(id\)th character to \(C\).

For operation of type \(3\), you have to swap the \(id_a\)th character and the \(id_b\)th character.

After the \(Q\) operations, you should print the resulting string in one line(remember to print a new line character).

Input

The first line contains a string s, which consists of only lowercase Latin characters.

The second line contains an integer \(Q\).

The next \(Q\) lines, each contains an operation

Constraints

• \(1 \le |s| \le 10^6\)
• \(1 \le Q \le 10^5\)
• \(0 \le id, id_a, id_b \le |s|-1\)
• \(A, B, C \in \{a \dots z\}\)

Output

Print your answer in one line and end with a newline character.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Dorami established a logistics company, TSP (TransportS Perfectly) Logistics! To reduce the cost of transporting goods to the stores, we have to design a delivery route for the truck to minimize the travel length.

In this problem, please notice the following description:

• All the goods are deposited at the cargo center (place 0). 
• The capacity of the truck is 30 units, and each store has specific units of goods that are demanded to deliver.
• We have to load the goods at the cargo center by not exceeding the maximum capacity of 30 units, deliver them and satisfy the demand for each store. 
• You can't divide the goods that are going to deliver to the same store, that is, you have to deliver all the goods that a store are demanded at one time.
• You might need to return to the cargo center several times since the capacity of the truck is limited. 
• The truck starts from the cargo center, and after the delivery process, the truck should return to the cargo center. 
• There are some roads between two places, You can travel from one place to another if there is a road between them.
• Find the minimum length of the delivery route.

This is a partial judge problem. You can refer to 12498 - Partial Judge Example to know how a partial judge problem works.

In this problem, several structures are defined:

​You need to implement the function below to find the answer:

For the sample input, one of the best strategies is: 

0 (Load 30) -> 1 -> 3 (Deliver 30) -> 1 -> 0 (Load 30) -> 1 (Deliver 14) -> 2 (Deliver 16) -> 0. The length of the delivery route is 24.

******Hint. 

• [hint.pdf]    This is one of the concepts for solving this problem.​ You can refer to this and try to implement, or try to find your approach! 
• ​In 13800.h, there is a function called"distance", which uses the technique of the Floyd–Warshall algorithm to find the shortest path between every two places. Uncomment and trace the code to understand the algorithm!
• Dorami Thanks for your help!

Input

• The first line contains two integers N and M - the numbers of stores and roads.
• The second line contains N integers u₁~u_N - units of goods that are demanded to deliver for stores 1, 2, ..., N
• The next M lines describe the roads, each of them containing 3 integers a, b, w - the indexes of the two places at the ends of the road and the length of the road.

It guarantees that you can travel from the cargo center to all the stores.

Test case constraints

• 1 <= N <= 12
• 1 <= M <= N(N+1)/2
• 1 <= u_i <= 30
• 0 <= a, b <= N
• 1 <= w <= 10⁹
• The capacity of the truck = 30

Output

Output one line contains the minimum length of the delivery route.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss