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

In this problem, you are asked to design two functions
    1.

unsigned*** new_3d_array(unsigned n,unsigned m,unsigned k);

malloc an n*m*k 3D unsigned array, and then return its address. The main function will check the correctness of your array.

    2.

void delete_3d_array(unsigned ***arr);

Free the memory space of your array that was previously allocated by using malloc. Be careful about the memory uage of your program allocated dynamically so as to avoid MLE.

The two functions have been declared in function.h, and you are asked to complete the function definitions in function.c.

Your program should construct the 3D array by using only three malloc function calls. Notice that malloc is a time-consuming operation.

Note: for OJ submission:

       Step 1. Submit only your function.c into the submission block. (Please choose C compiler) 

       Step 2. Check the results and debug your program if necessary.

Input

Please refer to the main function.

The input only has one line, consisting of five positive integers t,n,m,k,r separated by space characters, where t is the number of tests, (n,m,k) represents the array size, and r is a parameter for testing. 

Note that n*m*k<=10000000 and t*n*m*k<=60000000

Output

In order to test your array's correctness, we will use your array to do some computations and output the results.

Sample Input  Download

Sample Output  Download

Partial Judge Code

Partial Judge Header

Tags

Discuss

Description

A mail carrier needs to deliver letters to multiple places and goes back to the post office to take a rest.

Traveling outside makes him feel tired, so he would like to come up with a shortest path.

Given all distances between every pair of places (including the post office and all destinations), please help the mail carrier figure out the best shortest path, which starts from the post office and ends at the post office.

An additional requirement is that the mail carrier can just go to each place only one time (excluding the starting point, he can go to the start point at the beginning and in the end).

Input

The first line contains an integer N, indicates there are N places (including the post office).

Then there is one N*N martix occupies N lines, with each line contains N integers (>= 0).

ith row jth column = Matrix(i,j) = distance between place i and place j.

The place with index = 0 is the post office.

For all i, j >= 0, Matrix(i,j) = Matrix(j,i), Matrix(i,i) = 0.

N is at most 10 among all test cases.

Output

Print out the minimum distance the mail carrier has to travel to complete his task.

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

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

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

Partial Judge Header

Tags

Discuss

Description

Flip game is played on a rectangular N x M field with two-sided pieces placed on each of its N x M squares. One side of each piece is white and the other one is black and each piece is lying either it's black or white side up. Each round you flip some pieces, thus changing the colors of their upper sides from black to white and vice versa. The pieces to be flipped on the N x M field are chosen every round according to the following rules:

1. Choose any one of the N x M pieces.
2. Flip the chosen piece and also all adjacent pieces to the left, to the right, to the top, and to the bottom of the chosen piece (if there are any). That is, depending on the position of the chosen piece, there can be totally 3 to 5 pieces flipped.

Consider the following position as an example:

bwbw
wwww
bbwb
bwwb

Here "b" denotes pieces lying their black side up and "w" denotes pieces lying their white side up. If we choose to flip the 1st piece from the 3rd row (this choice is shown at the picture), then the field will become:

bwbw
bwww
wwwb
wwwb

The goal of the game is to flip either all pieces white side up or all pieces black side up. You are to write a program that will search for the minimum number of rounds needed to achieve this goal.

If it's impossible, print "oops".

Input

The first line contains a single integer T (1 ≤ T ≤ 100). Then T test cases follow.

For each test case:

• The first line gives two integers N and M (1 ≤ N*M ≤ 16).
• Each of the next N lines consists of M ‘w’ or ‘b’ characters separated by spaces.

Limit:

Testcase 1: N = 1, M ≤  4

Testcase 2: N = 1, M ≤  16

Testcase 3: N ≤ 2, M ≤  2

Testcase 4: N ≤ 4, M ≤  4

Testcase 5: N ≤ 4, M ≤  4

Output

For each test, output the minimum number of rounds to reach a winning configuration, in case such a configuration exists, or the word "oops".

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