2023年福建省第三届大学生程序设计竞赛题目.doc

Problem A Solve equation
Accept: 111    Submit: 229
Time Limit: 1000 mSec    Memory Limit : 32768 KB
Problem Description
You are given two positive integers A and B in Base C. For the equation:
A=k*B+d
We know there always existing many non-negative pairs (k, d) that satisfy the equation above. Now in this problem, we want to maximize k.
For example, A="123" and B="100", C=10. So both A and B are in Base 10. Then we have:
(1) A=0*B+123
(2) A=1*B+23
As we want to maximize k, we finally get one solution: (1, 23)
The range of C is between 2 and 16, and we use 'a', 'b', 'c', 'd', 'e', 'f' to represent 10, 11, 12, 13, 14, 15, respectively.
Input
The first line of the input contains an integer T (T≤10), indicating the number of test cases.
Then T cases, for any case, only 3 positive integers A, B and C (2≤C≤16) in a single line. You can assume that in Base 10, both A and B is less than 2^31.
Output
For each test case, output the solution “(k,d)” to the equation in Base 10.
Sample Input
3
2bc 33f 16
123 100 10
1 1 2

Sample Output
(0,700)
(1,23)
(1,0)

Problem B Bin & Jing in wonderland
Accept: 4    Submit: 28
Time Limit: 1000 mSec    Memory Limit : 32768 KB
Problem Description
Bin has a dream that he and Jing are both in a wonderland full of beautiful gifts. Bin wants to choose some gifts for Jing to get in her good graces.
There are N different gifts in the wonderland, with ID from 1 to N, and all kinds of these gifts have infinite duplicates. Each time, Bin shouts loudly, “I love Jing”, and then the wonderland random drop a gift in front of Bin. The dropping probability for gift i (1≤i≤N) is P(i). Of cause, P(1)+P(2)+…+P(N)=1. Bin finds that the gifts with the higher ID are better. Bin shouts k times and selects r best gifts finally.
That is, firstly Bin gets k gifts, then sorts all these gifts according to their ID, and picks up the largest r gifts at last. Now, if given the final list of the r largest gifts, can you help Bin find out the probability of the list?
Input
The first line of the input contains an integer T (T≤2,000), indicating number of test cases.
For each test cast, the first line contains 3 integers N, k and r (1≤N≤20, 1≤k≤52, 1≤r≤min(k,25)) as the description above. In the second line, there are N positive float numbers indicates the probability of each gift. There are at most 3 digits after the decimal point. The third line has r integers ranging from 1 to N indicates the finally list of the r best gifts’ ID.
Output
For each case, output a float number with 6 digits after the decimal points, which indicates the probability of the final list.
Sample Input
4
2 3 3
0.3 0.7
1 1 1
2 3 3
0.3 0.7
1 1 2
2 3 3
0.3 0.7
1 2 2
2 3 3
0.3 0.7
2 2 2

Sample Output
0.027000
0.189000
0.441000
0.343000

Problem C Floor problem
Accept: 133    Submit: 150
Time Limit: 1000 mSec    Memory Limit : 32768 KB
Problem Description
In this problem, we have f(n,x)=Floor[n/x]. Here Floor[x] is the biggest integer such that no larger than x. For example, Floor[1.1]=Floor[1.9]=1, Floor[2.0]=2.
You are given 3 positive integers n, L and R. Print the result of f(n,L)+f(n,L+1)+...+f(n,R), please.
Input
The first line of the input contains an integer T (T≤100), indicating the number of test cases.
Then T cases, for any case, only 3 integers n, L and R (1≤n, L, R≤10,000, L≤R).
Output
For each test case, print the result of f(n,L)+f(n,L+1)+...+f(n,R) in a single line.
Sample Input
3
1 2 3
100 2 100
100 3 100

Sample Output
0
382
332

Problem D Digits Count
Accept: 11    Submit: 64
Time Limit: 10000 mSec    Memory Limit : 262144 KB
Problem Description
Given N integers A={A[0],A[1],...,A[N-1]}. Here we have some operations:
Operation 1: AND opn L R
Here opn, L and R are integers.
For L≤i≤R, we do A[i]=A[i] AND opn (here "AND" is bitwise operation).
Operation 2: OR opn L R
Here opn, L and R are integers.
For L≤i≤R, we do A[i]=A[i] OR opn (here "OR" is bitwise operation).
Operation 3: XOR opn L R
Here opn, L and R are integers.
For L≤i≤R, we do A[i]=A[i] XOR opn (here "XOR" is bitwise operation).
Operation 4: SUM L R
We want to know the result of A[L]+A[L+1]+...+A[R].
Now can you solve this easy problem?
Input
The first line of the input contains an integer T, indicating the number of test cases. (T≤100)
Then T cases, for any case, the first line has two integers n and m (1≤n≤1,000,000, 1≤m≤100,000), indicating the number of elements in A and the number of operations.
Then one line follows n integers A[0], A[1], ..., A[n-1] (0≤A[i]<16,0≤i<n).
Then m lines, each line must be one of the 4 operations above. (0≤opn≤15)
Output
For each test case and for each "SUM" operation, please output the result with a single line.
Sample Input
1
4 4
1 2 4 7
SUM 0 2
XOR 5 0 0
OR 6 0 3
SUM 0 2

Sample Output
7
18

Hint
A = [1 2 4 7]
SUM 0 2, result=1+2+4=7;
XOR 5 0 0, A=[4 2 4 7];
OR 6 0 3, A=[6 6 6 7];
SUM 0 2, result=6+6+6=18.

Problem E How many tuples
Accept: 0    Submit: 0
Time Limit: 10000 mSec    Memory Limit : 65536 KB
Problem Description
Given m positive integer a[1],a[2]…a[m]. We run the following program (in C++):
const int MAXN = 20;
int a[MAXN], m;
int gcd(int a, int b) {return b ? gcd(b, a % b) : a;}
long long cnt = 0;
void gao(int cur, int g) {
if (cur > m) {
if (g == 1)++cnt;
return;
}
for (int i = 1; i <= a[cur]; ++i)
gao(cur + 1, g < 0 ? i : gcd(g, i));
}
int main() {
scanf("%d", &m);
for (int i = 1; i <= m; ++i)
scanf("%d", a + i);
gao(1, -1);
cout << cnt << endl;
return 0;
}

Here gcd is the Greatest Common Divisor, Obviously, the program above is to find the number of tuples (b[1], b[2], …, b[m]) such that:
(1) gcd(b[1], b[2], …, b[m])=1. (Here we define gcd(num)=num, that is: gcd(9)=9, gcd(2)=2)
(2) 1≤b[i]≤a[i]. (1≤i≤m, b[i] is an integer)
Now in this problem, the m and a[i] may be very large! So could you write one efficient program to find the answer? The answer may be too large. So you can just output the answer Mod 1,000,000,007.
Input
The first line of the input contains an integer T (T≤10,000), indicating the number of test cases.
Then T cases, for any case, only two lines.
The first line is one integer m(1≤m≤20).
The second line has m integers indicate a[1], a[2], …, a[m] (1≤a[i]≤100,000,000, 1≤i≤m).
The answer may be too large. So you can just output the answer Mod 1,000,000,007.
Output
For each test case, print a line containing the answer Mod 1,000,000,007.
Sample Input
3
2
5 5
2
10000 9873
2
1234 5678

Sample Output
19
60026156
4261566

Problem F Hua Rong Dao
Accept: 22    Submit: 66
Time Limit: 1000 mSec    Memory Limit : 32768 KB
Problem Description
Cao Cao was hunted down by thousands of enemy soldiers when he escaped from Hua Rong Dao. Assuming Hua Rong Dao is a narrow aisle (one N*4 rectangle), while Cao Cao can be regarded as one 2*2 grid. Cross general can be regarded as one 1*2 grid.Vertical general can be regarded as one 2*1 grid. Soldiers can be regarded as one 1*1 grid. Now Hua Rong Dao is full of people, no grid is empty.
There is only one Cao Cao. The number of Cross general, vertical general, and soldier is not fixed. How many ways can all the people stand?
Input
There is a single integer T (T≤4) in the first line of the test data indicating that there are T test cases.
Then for each case, only one integer N (1≤N≤4) in a single line indicates the length of Hua Rong Dao.
Output
For each test case, print the number of ways all the people can stand in a single line.
Sample Input
2
1
2

Sample Output
0
18
Hint
Here are 2 possible ways for the Hua Rong Dao 2*4.

Problem H Mountain Number
Accept: 2    Submit: 7
Time Limit: 1000 mSec    Memory Limit : 32768 KB
Problem Description
One integer number x is called "Mountain Number" if:
(1) x>0 and x is an integer;
(2) Assume x=a[0]a[1]...a[len-2]a[len-1](0≤a[i]≤9, a[0] is positive). Any a[2i+1] is larger or equal to a[2i] and a[2i+2](if exists).
For example, 111, 132, 893, 7 are "Mountain Number" while 123, 10, 76889 are not "Mountain Number".
Now you are given L and R, how many "Mountain Number" can be found between L and R (inclusive) ?
Input
The first line of the input contains an integer T (T≤100), indicating the number of test cases.
Then T cases, for any case, only two integers L and R (1≤L≤R≤1,000,000,000).
Output
For each test case, output the number of "Mountain Number" between L and R in a single line.
Sample Input
3
1 10
1 100
1 1000

Sample Output
9
54
384

Problem I Star
Accept: 78    Submit: 320
Time Limit: 1000 mSec    Memory Limit : 32768 KB
Problem Description
Overpower often go to the playground with classmates. They play and chat on the playground. One day, there are a lot of stars in the sky. Suddenly, one of Overpower’s classmates ask him: “How many acute triangles whose inner angles are less than 90 degrees (regarding stars as points) can be found? Assuming all the stars are in the same plane”. Please help him to solve this problem.
Input
The first line of the input contains an integer T (T≤10), indicating the number of test cases.
For each test case:
The first line contains one integer n (1≤n≤100), the number of stars.
The next n lines each contains two integers x and y (0≤|x|, |y|≤1,000,000) indicate the points, all the points are distinct.
Output
For each test case, output an integer indicating the total number of different acute triangles.
Sample Input
1
3
0 0
10 0
5 1000

Sample Output
1

Problem J Min Number
Accept: 85    Submit: 261
Time Limit: 1000 mSec    Memory Limit : 32768 KB
Problem Description
Now you are given one non-negative integer n in 10-base notation, it will only contain digits ('0'-'9'). You are allowed to choose 2 integers i and j, such that: i!=j, 1≤i<j≤|n|, here |n| means the length of n’s 10-base notation. Then we can swap n[i] and n[j].
For example, n=9012, we choose i=1, j=3, then we swap n[1] and n[3], then we get 1092, which is smaller than the original n.
Now you are allowed to operate at most M times, so what is the smallest number you can get after the operation(s)?
Please note that in this problem, leading zero is not allowed!
Input
The first line of the input contains an integer T (T≤100), indicating the number of test cases.
Then T cases, for any case, only 2 integers n and M (0≤n<10^1000, 0≤M≤100) in a single line.
Output
For each test case, output the minimum number we can get after no more than M operations.
Sample Input
3
9012 0
9012 1
9012 2

Sample Output
9012
1092
1029

Problem K Tickets
Accept: 14    Submit: 50
Time Limit: 3000 mSec    Memory Limit : 32768 KB
Problem Description
You have won a collection of tickets on luxury cruisers. Each ticket can be used only once, but can be used in either direction between the 2 different cities printed on the ticket. Your prize gives you free airfare to any city to start your cruising, and free airfare back home from wherever you finish your cruising.
You love to sail and don't want to waste any of your free tickets. How many additional tickets would you have to buy so that your cruise can use all of your tickets?
Now giving the free tickets you have won. Please compute the smallest number of additional tickets that can be purchased to allow you to use all of your free tickets.
Input
There is one integer T (T≤100) in the first line of the input.
Then T cases, for any case, the first line contains 2 integers n, m (1≤n, m≤100,000). n indicates the identifier of the cities are between 1 and n, inclusive. m indicates the tickets you have won.
Then following m lines, each line contains two integers u and v (1≤u, v≤n), indicates the 2 cities printed on your tickets, respectively.
Output
For each test case, output an integer in a single line, indicates the smallest number of additional tickets you need to buy.
Sample Input
3
5 3
1 3
1 2
4 5
6 5
1 3
1 2
1 6
1 5
1 4
3 2
1 2
1 2

Sample Output
1
2
0