preface

Just two months from the Blue Bridge Cup, the last horn has sounded and there is no retreat!

In the last time, it is difficult to thoroughly understand the algorithm required by the game, but the final result may not be very good, so we use the form of real problem + analysis to make the final sprint!

Don't say much, open our next day!

2015b nine array scores (DFS)

The nine numbers 1, 2, 3... 9 form a fraction, and its value is exactly 1 / 3. How to group it?
The following program realizes this function. Please fill in the missing code in the underlined part.

A blank filling question, DFS backtracking problem, let's look at the code he gives

#include <stdio.h>

void test(int x[]) {
    int a = x[0]*1000 + x[1]*100 + x[2]*10 + x[3];
    int b = x[4]*10000 + x[5]*1000 + x[6]*100 + x[7]*10 + x[8];

    if(a*3 == b) printf("%d / %d\n", a, b);
}

void f(int x[], int k) {
    int i,t;
    if(k>=9){
        test(x);
        return;
    }

    for(i=k; i<9; i++) {
        {t=x[k]; x[k]=x[i]; x[i]=t;}
        f(x,k+1);
        ___________________// Fill in the blanks
    }
}

int main() {
    int x[] = {1,2,3,4,5,6,7,8,9};
    f(x,0);
    return 0;
}

It's not difficult. The code is as follows. Take time to write special topics on dfs and bfs

{t=x[k]; x[k]=x[i]; x[i]=t;}

2015b addition and multiplication

We all know: 1 + 2 + 3 +... + 49 = 1225
Now ask you to turn two non adjacent plus signs into Multiplication signs to make the result 2015

For example:
1+2+3+...+1011+12+...+2728+29+...+49 = 2015
Is the answer that meets the requirements.

Please look for another possible answer and submit the number to the left of the multiplication sign in the front (for example, submit 10).
Note: what you need to submit is an integer. Don't fill in any superfluous content.

The first one of the code questions is relatively simple. It is worth noting that the second for should not be written from 1, but from the next bit of the first for

#include<iostream>
using namespace std;
int main() {
	for(int i = 1; i<=48; i++)
		for (int j = i + 1; j <= 48; j++) {
			if (i == j)	continue;
			//ans conversion twice
			int ans = 1225 - 2 * i - 2 * j - 2;
			ans = ans + i * (i + 1) + j * (j + 1);
			if (ans == 2015) {
				printf("%d\n", i);
			}
		}
	return 0;
}

If is in the case, and if is in the case, so it should be changed to 16

if (ans == 2015 && i != 10) 

2015b I was kidnapped

The title is a joke, yes Number of card types

Xiaoming was hijacked to X casino and forced to play cards with three other people.
A deck of playing cards (excluding the big and small trumps, a total of 52 cards) will be distributed evenly to 4 people, with 13 cards for each person.
At this time, Xiaoming suddenly had a problem in his mind:
If you don't consider the decor, only consider the points, and don't consider the order of the cards you get, how many kinds of initial card type combinations can you get in your hand?

Please fill in this integer and do not fill in any redundant content or explanatory text.

There is no time limit. We can violently enumerate the number of cards held by each card and finally judge whether there are 13 cards in our hand.

#include<iostream>
using namespace std;
int a[14], ans;
int main() {
	for (a[1] = 0; a[1] <= 4; ++a[1])
		for (a[2] = 0; a[2] <= 4; ++a[2])
		     for (a[3] = 0; a[3] <= 4; ++a[3])
			     for (a[4] = 0; a[4] <= 4; ++a[4])
				     for (a[5] = 0; a[5] <= 4; ++a[5])
					     for (a[6] = 0; a[6] <= 4; ++a[6])
						     for (a[7] = 0; a[7] <= 4; ++a[7])
							     for (a[8] = 0; a[8] <= 4; ++a[8])
								     for (a[9] = 0; a[9] <= 4; ++a[9])
										 for (a[10] = 0; a[10] <= 4; ++a[10])
										     for (a[11] = 0; a[11] <= 4; ++a[11])
											     for (a[12] = 0; a[12] <= 4; ++a[12])
												     for (a[13] = 0; a[13] <= 4; ++a[13]) {
												         int t = a[1] + a[2] + a[3] + a[4] + a[5] + a[6] + a[7] + a[8] + a[9] + a[10] + a[11] + a[12] + a[13];
															 if (t == 13) ans++;
		
	}
	printf("%d\n", ans);
	return 0;
}

DFS can also write

#include <bits/stdc++.h>
using namespace std; 
int cnt; 
void dfs(int i, int j) { // There are j cards in the i hand 
     if(i > 13) return; 
     if(j > 13) return; // Pruning when the number of cards in hand is greater than 13, it certainly does not meet the requirements. 
     if(j == 13) {
         cnt ++;
         return ;
     }
     dfs(i+1, j);
     dfs(i+1, j+1);
     dfs(i+1, j+2);
     dfs(i+1, j+3);
     dfs(i+1, j+4);
}  
int main() {
     dfs(0, 0);
     printf("%d\n", cnt);
     return 0;
}

last

Today we will brush these questions. They are not difficult, but they are all real questions. Stick to them and time will give the answer!