2016 Ma Nong Valley National College Student Programming Invitational (First Round of Qualifying Competition)

2016 Ma Nong Valley National College Student Programming Invitational (First Round of Qualifying Competition)

ACM template

Uh, it was a bit embarrassing this time. Although the question was not difficult, I was a little flustered after sleeping for 45 minutes. Then, I was careless when I did the question. I missed the conditions. The most embarrassing thing is that I can only submit it once...

Question 1 Rank the programmers' programming level

description

The old coders have to sort the programming levels of N coders. The numbers of these coders are 1, 2, 3,..., N, but the old coders cannot obtain their specific level data, only the relative level, for example , "PQ" means that the level of P is higher than that of Q. Please write a program to help the old code farmers to sort.
Note: The sorting that meets the conditions may not be unique. At this time, the code producer with the smallest number is required to be the first when outputting; the input data is guaranteed to be correct, that is, the input data must be guaranteed to have a ranking that meets the requirements.

[Input description]
There are 2 numbers N and M in the first line, where N (2<=N<=50) represents the number of code farmers, and M represents the next M lines of input data.
In the next M rows of data, each row also has two numbers P and Q, indicating that the level of P is higher than that of Q.
Separate the numbers in the same line with a space.

[Output description]
Give a ranking order that meets the requirements, separated by a space between coders, and there is no space after the last coder.

Example
Input:
4 3
1 2
2 3
4 3
Output:
1 2 4 3

answer

The idea is very clear, you need to use the linked list, before inserting the linked list, you need to sort some conditions first. (I have just switched to C++ for a month, and I have not used linked lists yet. I am too unfamiliar with the linked list methods, and the methods used are all Baidu)

Code

# include <iostream> # include <list> using namespace std; typedef list< int > LISTINT; int p[ 100 ]; int q[ 100 ]; int a[ 100 ]; int main ( int argc, const char * argv[]) { LISTINT listPeople; LISTINT::iterator it; int N, M; int P, Q; cin >> N >> M; int key = 0 ; while (M--) { cin >> P >> Q; p[key] = P; q[key++] = Q; } for ( int i = 0 ; i <key- 1 ; i++) { for ( int j = i + 1 ; j <key; j++) { if (p[i]> p[j]) { swap (p[i], p[j]); swap (q[i], q[j]); } else if (p[i] == p[j] && q[i] <q[j]) { swap (p[i], p[j]); swap (q[i], q[j]); } } } listPeople. push_back (p[ 0 ]); listPeople. push_back (q[ 0 ]); int flag = key- 1 ; while (flag) { l: for ( int i = 1 ; i <key; i++) { if (p[i] != 0 ) { for (it = listPeople. begin (); it != listPeople. end (); it++) { if (*it == q[i]) { listPeople. insert (it, p[i]); p[i] = 0 ; flag--; goto l; } else if (*it == p[i]) { listPeople. insert (++it, q[i]); it--; p[i] = 0 ; flag--; goto l; } } } } } int k = 0 ; for (it = listPeople. begin (); it != listPeople. end (); it++) { a[k++] = *it; } for ( int i = 0 ; i <k- 1 ; i++) { cout << a[i] << '' ; } cout << a[k- 1 ] << '\n' ; free (&it); free (&listPeople); return 0 ; } Copy code

Test Question Two Strange Number: 6174

description

For any four-digit positive integer A, the numbers on each digit are not all the same. If you rearrange the numbers on each digit, extract the largest number (M) and smallest number (N) from all permutations, and then subtract these two numbers (MN). Repeat this process, after up to seven steps, you will definitely get 6174.
Note: If there is 0 in a certain digit, it is allowed to put 0 on the leftmost to form 4 digits. For example: if the number obtained in a certain step is 1000, then 1000-0001=999, and the maximum number of recombination at this time is 9990 , The minimum number is 0999.
Please write a program to output the number of steps passed for a 4-digit positive integer input.
Requirements: Do not use library functions for sorting, otherwise, the program will be judged invalid during manual review.

[Input description]
A 4-digit positive integer A.

[Output description]
A positive integer (number of steps).

Sample
Input:
5652
Output:
4

answer

Just use string processing, water question.

Code

# include <iostream> using namespace std; char num[ 5 ]; char numA[ 5 ]; char numB[ 5 ]; int main ( int argc, const char * argv[]) { cin >> num; int res = 0 ; while ((num[ 0 ]- '0' ) * 1000 + (num[ 1 ]- '0' ) * 100 + (num[ 2 ]- '0' ) * 10 + (num[ 3 ]- '0' ) != 6174 ) { res++; for ( int i = 0 ; i < 3 ; i++) { for ( int j = i + 1 ; j < 4 ; j++) { if (num[i]> num[j]) { swap (num[i], num[j]); } } } int MAX = (num[ 3 ]- '0' ) * 1000 + (num[ 2 ]- '0' ) * 100 + (num[ 1 ]- '0' ) * 10 + (num[ 0 ]- '0 ' ); int MIN = (num[ 0 ]- '0' ) * 1000 + (num[ 1 ]- '0' ) * 100 + (num[ 2 ]- '0' ) * 10 + (num[ 3 ] - '0' ); int dif = MAX-MIN; num[ 3 ] = dif% 10 + '0' ; dif/= 10 ; num[ 2 ] = dif% 10 + '0' ; dif/= 10 ; num[ 1 ] = dif% 10 + '0' ; dif/= 10 ; num[ 0 ] = dif + '0' ; } cout << res << '\n' ; return 0 ; } Copy code

Question 3 Sort an English sentence in reverse order by word

description

Please write a program to sort an English sentence in reverse order in units of words, and the letters in each word are also in reverse order, and then output. For example, "I am ma nong gu", the reverse order is "ug gnon am ma I".
Requirements: Do not use library functions for sorting, otherwise, the program will be judged invalid during manual review.

[Input description] The
first line is an integer N (2< N <20), which represents the number of words in the English sentence.
The second line is an English sentence. The length of each word does not exceed 15 characters, and the words are separated by a space. In addition to English letters, the sentence does not contain other characters.

[Output description] The
output is one line, and all words are separated by a space.

Sample
Input:
5
I am ma nong gu
Output:
ug gnon am ma I

answer

It feels like an insult to IQ...

Code

# include <iostream> # include <cstring> using namespace std; char word[ 22 ][ 16 ]; int main ( int argc, const char * argv[]) { int N; cin >> N; for ( int i = 0 ; i <N; i++) { cin >> word[i]; } for ( int i = N- 1 ; i> 0 ; i--) { int len = ( int ) strlen (word[i]); for ( int j = len- 1 ; j >= 0 ; j--) { cout << word[i][j]; } cout << '' ; } int len = ( int ) strlen (word[ 0 ]); for ( int j = len- 1 ; j >= 0 ; j--) { cout << word[ 0 ][j]; } cout << '\n' ; return 0 ; } Copy code

Question 4 Number of schemes for small code farmers to select resources

description

The small code farmer celebrated his birthday today, and the old code farmer took him to the code farm to buy learning resources as a birthday gift. The old code farmer told him that he can buy 3 learning resources in the code farm today, but these three resources must meet the conditions. : The sum of the prices of 3 resources is equal to half of the sum of the prices of all resources. For example, if there are 5 resources whose prices are 14, 13, 8, 9, and 10, there is only one plan for small farmers to select resources: (8, 9, 10).
Please write a program to help small code farmers calculate the number of solutions for selecting resources. If there are eligible solutions, output the number of solutions; if there are no eligible solutions, output 0.

[Input description] The
first line is an integer N (N<100), which indicates the total number of resources to be selected.
There are N integers in the second line, and each integer is separated by a space to indicate the price of each resource (price<50).

[Output description]
1 integer, representing the number of schemes for selecting gifts, or 0.

[Input example]
5
14 13 8 9 10

Sample output
1

answer

If there is no requirement to choose only three books, the gold content will increase a little, because the most intuitive way is to use recursion. But when it comes to mentioning that you can only choose three books, so you can use a three-layer for loop.

Code

# include <iostream> using namespace std; int N; int sum = 0 ; int res = 0 ; int price[ 101 ]; int flag[ 101 ] = { 0 }; void solve ( int n, int s, int q) { if (n <N && s == sum/ 2 && q == 1 ) { res++; return ; } if (n == N || s> sum/2 || q == 1 ) { return ; } solve (n + 1 , s + price[n], q--); solve (n + 1 , s, q); return ; } int main ( int argc, const char * argv[]) { cin >> N; for ( int i = 0 ; i <N; i++) { cin >> price[i]; sum += price[i]; } solve ( 0 , 0 , 3 ); cout << res << '\n' ; return 0 ; } Copy code