| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11267 | Equivalent relation |
|
| 12474 | The Travelling Bard |
|
| 12497 | Oil Deposits |
|
| 12501 | Ape Society |
|
| 12524 | I,THIEF-test |
|
| 12526 | Split String |
|
| 12527 | Power Set |
|
Description
There are N integer pointers, indexed from 0 to N-1 (N<100). Each pointer initially points to an integer of value 0.
There are two kinds of instructions. The instruction “S n k” is used to set the integer, which pointer n points to, to be k. For example, S 1 10 means that the integer that pointer 1 points to is set to 10. And the instruction “P n m” means that pointer n points to the integer that pointer m points. For example, P 2 1 means that pointer 2 points to the integer that pointer 1 points to. After P 2 1, pointer 2 and pointer 1 point to the same integer, which is pointed by pointer 1.
Note that you don't have to change all the pointers if one pointer changes its target. The following table is an example. The instructions are P 1 2 and then P 2 3. You do not have to change the target of pointer 1.
|
instruction |
Description |
|
P 1 2 |
Pointer 1 points to the integer that pointer 2 points to.
|
|
P 2 3 |
Pointer 2 points to the integer that pointer 3 points to. And you don’t have to change the target of pointer 1. |
Finally, output all the values that pointers 0 to N-1 point to in order.
Note that
1. This problem involves three files.
- function.h: Function definition of execInstruct.
- function.c: Function describe of execInstruct.
- main.c: A driver program to test your implementation.
You will be provided with main.c and function.h, and asked to implement function.c.
2. 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.
Hints:
main.c
#include <stdio.h>
#include "function.h"
#define SIZE 100
int main() {
int *ptrArr[SIZE];
int dataArr[SIZE] = {0};
char inst;
int dataNum, instNum;
int param1, param2;
int i;
/* input */
scanf("%d %d", &dataNum, &instNum);
/* initialize the ptrArr */
for (i = 0; i < dataNum; i++)
ptrArr[i] = &dataArr[i];
for (i = 0; i < instNum; i++) {
scanf(" %c %d %d", &inst, ¶m1, ¶m2);
execInst(ptrArr, inst, param1, param2);
}
/* output */
for (i = 0; i < dataNum - 1; i++) {
printf("%d ", *ptrArr[i]);
}
printf("%d", *ptrArr[i]);
return 0;
}
function.h
#ifndef FUNCTION_H
#define FUNCTION_H
void execInst(int *ptrArr[], char inst, int param1, int param2);
#endif
Input
The first line contains two positive X and Y. X indicates the size of data. Y indicates that there are Y instructions needed to be done.
The next Y lines contain the instructions.
Output
All the values that pointers 0 to pointer N-1 point to in order. Each value is seperated by a blank ' '.
# Note that there is no '\n' at the end of the output.
Sample Input Download
Sample Output Download
Partial Judge Code
11267.cPartial Judge Header
11267.hTags
Discuss
Description
Peter, a travelling bard, is commisioned by his king to visit N kingdoms.
Initially, Peter is at the S'th kingdom, and is about to travel to the N - 1 other kingdoms.
He knows how much time he needs to move to the y'th kingdom from the x'th kingdom, denoted as D[x][y].
Help him find out the minimum time he needs to visit all the other N - 1 kingdoms exactly once, and return to the S'th kingdom from the last foreign kingdom.
Input
The first line has two integers separated by a space, N and S.
Then N lines follow, the i'th line of which consists of N integers separted by a space.
The y'th number in the x'th line (among the last N lines) represents D[x][y].
1 < N <= 10
1 <= S <= N
0 <= D[x][y] < 100000
Output
The minimum total cost, followed by a newline character.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
(modified by uva572)
The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits. GeoSurvComp works with one large rectangular region of land at a time, and creates a grid that divides the land into numerous square plots. It then analyzes each plot separately, using sensing equipment to determine whether or not the plot contains oil. A plot containing oil is called a pocket. If two pockets are adjacent, then they are part of the same oil deposit. Oil deposits can be quite large and may contain numerous pockets. Your job is to determine how many different oil deposits are contained in a grid.
Input
The input file contains one or more grids. Each grid begins with a line containing m and n, the number of rows and columns in the grid, separated by a single space. If m = 0 it signals the end of the input; otherwise 1 ≤ m ≤ 100 and 1 ≤ n ≤ 100. Following this are m lines of n characters each (not counting the end-of-line characters). Each character corresponds to one plot, and is either ‘#’, representing the absence of oil, or ‘$’, representing an oil pocket.
( An oil deposit will not contain more than 100 pockets. )
Output
For each grid, output the number of distinct oil deposits and the maximum oil deposits with special form "(n,m)"
n: the number of distinct oil deposits, m: the maximum oil deposits
Note that Two different pockets are part of the same oil deposit if they are adjacent horizontally, vertically, or diagonally. (each line followed by a newline character at the end of output string)
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Morris is a smart ape. His work is to teach N small apes the rules in the ape society.
Morris wanted to know how much small apes learned, therefore, he held a midterm exam last week. The result of exam made Morris so mad that he decided to flunk M-last apes.
Morris has the names, grades, and ages of these apes.
Can you help Morris to find the M-last apes by following rules?
Between two apes, the ape with the greater grade is better than the other one.
If they have the same grades, the younger ape is better than the older ape.
If they have the same grades and ages, compare their names in lexicographical order. The ape with small name is better than the other one.
Input
Two integer N, M on the first line.
The following N lines contain information of apes.
Each line is consisted of S, G, A representing the name, grade, age of an ape respectively.
- 1 ≤ N ≤ 1,000
- 0 ≤ M ≤ N
- 0 ≤ G, A ≤ 100
- 1 ≤ |S| ≤ 10
- it’s guaranteed that the names are different.
Output
Print M lines of apes’ name which will be flunked by Morris.
The output order is ascending order, which means the worst ape will be printed first, and then the second last, the third last, and so on.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
You are a thief who try hard to steal money as much as possible along the street. However, it's too dangerous to steal two adjacent houses. You should avoid this situation.
Output the houses you stole in ascending order where the above two requirements are met.
HINT: If you get TLE, you can try to store the answer of subproblem. Then next time you want the answer of some subproblem you've calculated before, you don't need to recalculate it.
Input
N
S_i
N is the number of house. 0<N<=100
S_i is representing the amount of money of each house, money amount is no more than 10000
Output
S
S are the houses you stole.
Print the house you stole in ascending order.
You should print an additional space at the end of the line, and don't print the newline character at the end of the line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Split String by given a specific pattern is the common operation for string manipulation. In python code, you can write below code to use it conveniently.
str = 'helloabcworldabc!!'
str.split('abc') # str == ['hello', 'world', '!!']
However, in this problem, you are asked to implement split function by yourself
In this problem, you are asked to design two functions
1.
char **split_str_by_pattern(char* str, char* pattern, int* split_num);
implement split string function by given input string and pattern, then malloc a 2d char array to store the split result and return it. (also set correct split_num)
2.
void free_result(char **result, int split_num);
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.
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.
hint: you can use strlen function to get the lenght of input string (already include header file in main.c)
char s[15] = "Hello World";
printf("%d\n",strlen(s)); // 11
Input
S_input
S_p
S_input: The input string should be splited , 20 <= S_input < 500
S_p: The pattern string , 1 <= S_p < 10
Output
output the strings splited by given pattern. (followed by a newline character at the end of each output string)
Sample Input Download
Sample Output Download
Partial Judge Code
12526.cPartial Judge Header
12526.hTags
Discuss
Description
In mathematics, the power set (or powerset) of any set S is the set of all subsets of S, including the empty set and S itself
Take the set S1 = {'1','2'} for example:
the power set of S1 is {{},{'1'},{'2'},{'1','2'}}
00 -> empty set, 01 -> {'1'}, 10 -> {'2'} , 11 -> {'1','2'} (00,01,10,11 is the binary representation of power set's index)
Take the set S2 = {'1','2','3'} for example:
the power set of S2 is {{},{'1'},{'2'},{'1','2'},{'3'},{'1','3'},{'2','3'},{'1','2','3'}}
In this problem, you are asked to generate power set by given a aspecific set.
Input
S
S: the input string can be viewed as a set ( 4 <= S <= 21)
Output
Output the element of power set (followed by a newline character at the end of each output element)