函数题集锦

【2015-2016 期末】Quick Power

The function Power calculates the exponential function $N^k$. But since the exponential function grows rapidly, you are supposed to return $(N^k)\%10007$ instead.

Format of function：int Power(int N, int k);

Both $N$ and $k$ are integers, which are no more than 2147483647.

Sample program of judge:

#include <stdio.h>

int Power(int, int);

const int MOD = 10007;
int main(){
    int N, k;
    scanf("%d%d", &N, &k);
    printf("%d\n", Power(N, k));
    return 0;
}

/* Your function will be put here */

Sample Input 1：2 3

Sample Output 1：8

Sample Input 2：128 2

Sample Output 2：6377

【2016-2017 期末】Programming Contest

Bob will participate in a programming contest. There are altogether n problems in the contest. Unlike in PAT (Programming Ability Test), in a programming contest one can not obtain partial scores. For problem i, Bob will need time[i] to solve it and obtains the corresponding score[i], or he may choose not to solve it at all. Bob will be happy when he obtains a total score no less than happy_score. You are supposed to find the minimum time needed for Bob to be happy. The function need_time must return the minimum time, or -1 if it is impossible for Bob to obtain a score no less than happy_score.

Format of function：int need_time(const int time[], const int score[], int happy_score, int n);

Here n (1 $≤$ n $≤$ MAXN) is the number of problems; happy_score (1 $≤$ happy_score $≤$ MAXS) is the minimum score for Bob to be happy; time[] is the array to store time[i] (1 $≤$ time[i] $≤ 100$) which is the time to solve problem i; score[] is the array to store score[i] (1 $≤$ score[i] $≤ 100$) which is the score Bob gets for solving problem i.

Sample program of judge:

#include <stdio.h>

#define MAXN 10
#define MAXS 1000

int need_time(const int time[], const int score[], int happy_score, int n);

int main() {
int n, i, happy_score;
int time[MAXN], score[MAXN];
scanf("%d %d", &n, &happy_score);
for (i = 0; i < n; ++i)
    scanf("%d", &time[i]);
for (i = 0; i < n; ++i)
    scanf("%d", &score[i]);
printf("%d\n", need_time(time, score, happy_score, n));
return 0;
}

/* Your function will be put here */

Sample Input：

6 121

84 87 78 16 94 38
87 93 50 22 63 28

Sample Output：125

【2017-2018 期末】AVL Tree Insertion

You are supposed to implement the Insert function, which inserts an integer Key into an AVL tree T. The resulting tree must be returned.

Format of function：AVLTree Insert ( int Key, AVLTree T );

where AVLTree is defined as the following:

typedef struct AVLNode *PtrToAVLNode;
struct AVLNode{
    int Data;
    PtrToAVLNode Left;
    PtrToAVLNode Right;
    int Height;
};
typedef PtrToAVLNode AVLTree;

Sample program of judge：

#include <stdio.h>
#include <stdlib.h>

typedef struct AVLNode *PtrToAVLNode;
struct AVLNode{
    int Data;
    PtrToAVLNode Left;
    PtrToAVLNode Right;
    int Height;
};
typedef PtrToAVLNode AVLTree;

AVLTree Insert ( int Key, AVLTree T );
void PostOrderPrint( AVLTree T ); /* details omitted */
void InOrderPrint( AVLTree T );   /* details omitted */

int main()
{
    int N, Key, i;
    AVLTree T = NULL;

    scanf("%d", &N);
    for ( i=0; i<N; i++ ) {
        scanf("%d", &Key);
        T = Insert( Key, T );
    }
    PostOrderPrint( T );
    InOrderPrint( T );

    return 0;
}
/* Your function will be put here */

Sample Input：

7
31 27 6 67 88 53 15

Sample Output：

Post-order: 6 27 15 53 88 67 31
In-order: 6 15 27 31 53 67 88

【2018-2019 期末】Variable Manipulation

CYLL has an integer-typed variable $X$ whose initial value is 1. The variable can be updated in each step by applying either of the two operations:

Multiply the variable by a fixed integer $K$: $X = X \times K$
Add an integer $T$ ($1 \le T \le 10$) to the number: $X = X + T$

Given two integers $N$ and $K$ as inputs, can you help CYLL to decide the minimum number of steps required before she obtains the number $N$ as the variable value?

Format of functions：int FindMinSteps(int N, int K);

Here $N$ ($ 1\le N \le 10^6 $) is the target number and \(K$ (\) 1 \le K \le N $) is the multiplication factor, which are integers as described in the problem specification.

The function is expected to return the minimum number of steps before the variable $X$ reaches value $N$. (See the sample input/output for a concrete example.)

Sample program of judge：

#include

int FindMinSteps(int N, int K);

int main() {
int N, K;

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

printf("%d", FindMinSteps(N, K));

return 0;
}

/* Implement the 'FindMinSteps' function here */

Sample input：101 2

Sample output：6

Sample explanation :

step 1: $X = 1 + 10 = 11$

step 2: $X = 11 * 2 = 22$

step 3: $X = 22 * 2 = 44$

step 4: $X = 44 + 6 = 50$

step 5: $X = 50 * 2 = 100$

step 6: $X = 100 + 1 = 101$

Note that this is not the only way to reach 101 in 6 steps, however, we care about the minumum number of steps, which is unique, rather than how you reach there.

【2019-2020 期末】Decode

Suppose that a string of English letters is encoded into a string of numbers. To be more specific, A - Z are encoded into 0 - 25. Since it is not a prefix code, the decoded result may not be unique. For example, 1213407 can be decoded as BCBDEAH, MBDEAH, BCNEAH, BVDEAH or MNEAH. Note that 07 is not 7, hence cannot be decoded as `H.

Your job is to tell in how many different ways we can decode a numeric string.

Format of function：int Decode( char NumStr[] );

where NumStr is a string consisting of only the numbers 0 - 9.

The function Decode is supposed to return the number of different ways we can decode NumStr.

Since the answer might be super large, you only need to output the answer modulo 1000000007.

Sample program of judge：

#include <stdio.h>
#include <string.h>

#define MAXN 100
#define BASE 1000000007

int Decode( char NumStr[] );

int main() {
    char NumStr[MAXN];

    scanf("%s", NumStr);
    printf("%d", Decode(NumStr));

    return 0;
}

/* Your function will be put here */

Sample Input：1213407

Sample Output：5

【2020-2021 期末】Hand-made Cream

Suppose you are a baker planning to bake some hand-made cream breads.

To bake a cream bread, we need to use one slice of bread and one kind of cream. Each hand-made cream bread has a taste score to describe how delicious it is, which is obtained by multiplying the taste score for bread and the taste score for cream. (The taste scores could be negative, howerver, two negative tast scores can still produce delicious cream bread.)

The bread and cream are stored separately.

The constraint is that you need to examine the breads in a given order, and for each piece of bread, you have to decide immediately (without looking at the remaining breads) whether you would like to take it.

After you are finished with breads, you will take the same amount of cream in the same manner. The breads and creams you take will be paired in the same order as you take them.

Given $N$ taste scores for bread and $M$ taste scores for cream, you are supposed to calculate the maximum total taste scores for all hand-made cream bread.

Input Specification：

Each input file contains one test case. For each case, the first line contains two integers $N$ and $M$ ($1≤N$, $M≤10^3$), which are the numbers of bread and cream, respectively.

The second line gives $N$ taste scores for bread.

The third line gives $M$ taste scores for cream.

The taste scores are integers in $[−10^3, 10^3]$.

All the numbers in a line are separated by a space.

Output Specification：

Print in a line the maximum total taste score.

Sample Input：

3 4
-1 10 8
10 8 11 9

Sample Output：

Hint： The maximum total taste score for the sample case is $10×10+8×11=188$.

【2021-2022 期末】Building an AVL Tree

An AVL tree is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property. Figures 1-4 illustrate the rotation rules.

Now given a sequence of insertions, you are supposed to build the AVL tree. Then given a sequence of statements about the structure of the resulting tree, you are supposed to tell if they are correct or not. A statement is one of the following:

(1) A is the root

(2) A is the right child of B

(3) A is the left child of B

(4) A and B are siblings

(5) A is the parent of B

Format of functions：

Tree Build_AVL ( int insertion[ ], int n );
int Test ( Tree T, int type, int A, int B );

The function Build_AVL is supposed to build an AVL tree according to the input sequence.

Here Tree is defined as the following:

typedef struct TNode *Tree;
struct TNode {
    int key;     //key of the node
    int height;  //height of the subtree with this node as the root
    Tree left, right;  //pointing to the left and right children of this node
};

The array insertion contains n (a positive integer) distinct keys to be inserted in order into an initially empty AVL tree. The root pointer of the resulting tree is supposed to be returned by Build_AVL.

The function Test is supposed to test if a given statement for an AVL tree T is correct or not, and return 1 if the result is true, or 0 otherwise. The parameter type is an integer in [1,5], which gives the index of a statement, as listed in the problem description; and A and B are the corresponding key values. For type 1, the value of B can be ignored. It is guaranteed that both A and B in the statements are in the tree.

Sample program of judge：

#include <stdio.h>
#include <stdlib.h>

typedef struct TNode *Tree;
struct TNode {
    int key;     //key of the node
    int height;  //height of the subtree with this node as the root
    Tree left, right;  //pointing to the left and right children of this node
};

Tree Build_AVL ( int insertion[ ], int n );
int Test ( Tree T, int type, int A, int B );

int main()
{
    int n, *insertion;
    int m, type, A, B, i;
    Tree T;

    scanf("%d", &n);
    insertion = (int *)malloc(sizeof(int) * n);
    for (i=0; i<n; i++) scanf("%d", &insertion[i]);
    T = Build_AVL(insertion, n);
    scanf("%d", &m);
    for (i=0; i<m; i++) {
        scanf("%d %d", &type, &A);
        if (type != 1) scanf("%d", &B);
        if (Test(T, type, A, B)) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

/* Your function will be put here */

Sample Input 1 (Figure 1)：

Sample Output 1：

Yes
No
Yes
No
Yes
No
No
Yes

Sample Input 2 (Figure 2)：

5
88 70 61 96 120
7
1 70
2 120 96
2 88 70
3 88 70
3 88 96
4 96 88
5 96 120

Sample Output 2：

Yes
Yes
No
No
Yes
No
Yes

Sample Input 3 (Figure 3)：

6
88 70 61 96 120 90
8
1 70
1 88
2 90 88
2 96 88
3 90 96
4 90 61
5 70 61
5 96 70

Sample Output 3：

No
Yes
No
Yes
Yes
No
Yes
No

Sample Input 4 (Figure 4)：

7
88 70 61 96 120 90 65
7
1 88
2 70 65
3 65 88
3 70 88
4 96 70
4 61 70
5 61 65

Sample Output 4：

Yes
Yes
Yes
No
No
Yes
No

【2022-2023 期末】Maximum Subsequence Product

Given a sequence of $K$ values ${a_1, a_2, …, a_K}$(not necessarily integers). A continuous subsequence is defined to be ${a_i, a_{i+1}, …, a_j}$ where $1≤i≤j≤K$. The maximum subsequence is the subsequence that has the largest product of its elements. For example, given sequence ${2,3,0.5,−2,4}$, its maximum subsequence is ${2,3}$. The largest product is therefore $6$.

Now you are supposed to find the largest product of the continuous subsequence. Hint: consider the optimal substructure of both the maximum and minimum product using your knowledge of dynamic programming.

Function Interface:

double MaxSequence(double nums[], int n);

where nums is an array of integers with n elements.

Judge Program:

#include <stdio.h>
#include <math.h>
#define MAXN 60000
#define max(x,y) ((x) > (y) ? (x) : (y))
#define min(x,y) ((x) < (y) ? (x) : (y))

double MaxSequence(double nums[], int n);

int main()
{
    double nums[MAXN];
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; ++i) scanf("%lf", &nums[i]);
    printf("%.2f", MaxSequence(nums, n));
    return 0;
}
/* Your function will be put here */

Sample Input:

5
2 3 0.5 -2 4

Sample Output:

6.00

【2023-2024 期末】Manager of Tasks

There are $N$ tasks arranged in a sequence on a machine waiting to be executed, and their order cannot be changed. You need to divide these $N$ tasks into several groups, each containing several consecutive tasks. Starting from time 0, the tasks are processed in groups, and the time required to execute the $i$-th task is $T_i$. Additionally, the machine requires a startup time $S$ before each group of tasks begins, so the time required for a group of tasks is the startup time $S$ plus the sum of the time required for each task in this group.

After a task is executed, it will wait briefly in the machine until all tasks in that group are completely executed. That is to say, the tasks in the same group will be completed at the same time. The cost of each task is its completion time multiplied by a cost coefficient $C_i$.

Please plan a grouping scheme for the machine to minimize the total cost.

For all testing data, $1≤N≤1000, 0≤S≤50, 1≤T_i, C_i≤100$

Function Interface:

long long min_cost(int N, int S, int T[], int C[]);

where T, C are arrays of integers with N elements, and S is the startup time $S$ mentioned above.

Judge Program:

#include <stdio.h>
#define MAXN 1000
long long min_cost(int N, int S, int T[], int C[]);
int main() {
    int N, S;
    int T[MAXN], C[MAXN];
    scanf("%d%d", &N, &S);
    for (int i = 0;i < N; ++ i) {
        scanf("%d%d", &T[i], &C[i]);
    }
    printf("%lld\n", min_cost(N, S, T, C));
    return 0;
}
/* Your function will be put here */

Sample Input:

Sample Output：

Sample Explanation

We have grouped the tasks into 3 groups, which are {1, 2}, {3}, {4, 5}. The completion time corresponding to each task, in the order of the task numbers, is {5, 5, 10, 14, 14}. Similarly, the cost corresponding to each task, again in the order of the task numbers, is {15, 10, 30, 42, 56}. The total cost of these tasks is 153.

【2024-2025 期末】Knapsack

Given $n$ items, where the i-th one has weight $w_i$ and value $v_i$. We only have a knapsack with capacity $W$ which might not be large enough to hold all the items. Fortunately, we can use magic — for item $i$, each time the magic can reduce its weight by $1$ for the cost of $c_i$. On the other hand, the weight of any item must always be positive — meaning that we cannot use magic to reduce the weight to 0 or less. We can use the magic any number of times. The profit of packing item $i$ into the knapsack is $v_i − k_i × c_i$ where $k_i$ is the number of times we apply the magic on item $i$.

The question is: what is the maximum profit we can get?

It is guaranteed that $1≤n≤200,1≤W≤200,1≤w_i≤200,1≤v_i≤10^6,1≤c_i≤10^6$.

Function Interface：

int knapsack(int n, int W, int w[], int v[], int c[]);

where n represents the number of items. W represents the capacity of the knapsack. The arrays w[0…n-1],v[0…n-1],c[0…n-1] are the weights, values, and costs of the items.

Judge Program：

#include <stdio.h>

int knapsack(int n, int W, int w[], int v[], int c[]);
const int maxn = 200;

int main()
{
    int n, W;
    int v[maxn], w[maxn], c[maxn];
    scanf(“%d %d”, &n, &W);
    for(int i = 0; i < n; i++) 
        scanf(“%d%d%d”, &w[i], &v[i], &c[i]);
    printf(“%d\n”, knapsack(n, W, w, v, c));

    return 0;

}
/* Fill your program here*/

Sample Input：

Sample Output：