Individual game 12

Good night, , Theorem of arithmetic series

Title Description
Good evening , Question Maker

If a and d A positive integer for reciprocal , Then the arithmetic sequence a,a+d,a+2d,⋯ Contains an infinite number of primes

This is called Dirichlet's theorem of arithmetic series

for example , from 2 Start and add 3 Arithmetic sequence of , namely

2, 5, 8, 11, 14, 17, 20, 23, 26, 29, 32, 35, 38, 41, 44, 47, 50, 53, 56, 59, 62, 65, 68, 71, 74, 77, 80, 83, 86, 89, 92, 95, 98, … ,

Contains infinite primes

2, 5, 11, 17, 23, 29, 41, 47, 53, 59, 71, 83, 89, … .

Your task is to write a program , For a given positive integer a、d and n Find number... In this arithmetic sequence n Prime number .

Input format
The input contains multiple sets of data

Enter three positive integers for each group a d n, The meaning is as above
a≤9307,d≤346,n≤210

Output format
For each set of data , Output a number , Represents the... In the sequence n Prime number

Ensure that the number of outputs is always less than 1e6

Their thinking ：

This question can be obtained by sifting out the table first 2~1e6 All the prime Numbers between , Then for each arithmetic sequence , For each of us $a_i$ Two points to find whether it is a prime number. If so, add one to the number , If The number reaches n, Output , And stop the cycle .

Code ：

#include <stdio.h>
#include <cmath>
#include <cstring>
const int N = 2E6 + 10;

int n ,d,a,cnt;
int prime[N];
bool p[N];

// The meter 
void init(){
    
	memset(p,1,sizeof p);
	p[0] = p[1] = 0;
	 cnt = 0;
	for(int i = 2;i<N;++i){
    
		if(p[i]){
    
			prime[cnt++] = i;
			for(int j = 2*i ;j<N;j+=i)
				p[j] = 0;
		}
	}
}

int main(){
    
	init();
	while(~scanf("%d%d%d",&a,&d,&n)){
    
		if(!a&&!n&&!d)break;
		int cou = 0,i=0 ,num;
		while(1){
    
			num = a + i*d;
			int l = 0,r = cnt;
			bool flag = 0;
			//  Two points search 
			while(l<r){
    
				int mid = l+ r>>1;
				if(prime[mid] == num){
    
					flag = 1;
					break;
				}else if(prime[mid]>num) r = mid;
				else 
					l = mid+1;
			}
			if(flag) cou ++;
			if(cou == n){
    
				printf("%d\n",num);
				break;
			}
			i++;
		}
	}
	
	
	return  0;
}

Railway Freight

Title Description
RJ Freight company is a Japanese railway company engaged in freight business , Recently, a switching line was built in haze, Yokohama . The line layout is shown in the figure 1 Shown .
chart 1

The freight train is from 2 to 72 The truck consists of . Yes 26 There are two types of trucks , from 26 A lowercase letter indicates , from “a” To “z”. Cars of the same type cannot be distinguished from each other , And the direction of each car is not important . therefore , The length is 2 To 72 The lowercase character string of is enough to completely represent the configuration of the train .

After arriving at the switching line , The train is divided into two sub trains at any position （ Before entering the storage line ）. The direction of each sub train can be reversed （ Use reverse lines ）. Last , The two sub trains are connected in any order , To form the final configuration . Please note that , The reverse operation of each sub train is optional .

for example , If the arrival configuration is “abcd”, Then the train will be divided into two sub trains , Respectively 3:1、2:2 or 1:3 Coach compartment . For each split , Possible final configurations are as follows （“+” Indicates the final connection location ）：

[3:1]
abc+d  cba+d  d+abc  d+cba
[2:2]
ab+cd  ab+dc  ba+cd  ba+dc  cd+ab  cd+ba  dc+ab  dc+ba
[1:3]
a+bcd  a+dcb  bcd+a  dcb+a

Remove duplicates , There may be 12 Different configurations .

Given arrival configuration , Answer the number of different configurations that can be constructed using the above switching lines .

Input format
The input contains multiple sets of data
First, enter a positive integer m It means that there are several groups of data
Next m Line one string per line ( Contains only lowercase letters ), Indicates the sequence when the train enters the station

Output format
For each set of data , Output an integer , Indicates the total number of outbound modes after reversal

Their thinking ：

There may be a mathematical solution , But not , cry . But we can simulate this process , Generate all the results because the longest is 72 All stable . Simulation can be used substr() String with two parts , For this string, there are 4 In this case , One is （ double , Not turn over ）,（ Not turn over , Not turn over ）,（ Not turn over , double ）,（ double , double ）. There are two cases when connecting, so there are probably 8 Medium condition . Whether the generated string is repeated or not, we can use map To record .

Code ：

#include <stdio.h>
#include <string>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
using namespace std;
int n;
string s, left, right, nowl, nowr, temp;
int sum ;
map<string, int>vis;

int main() {
    
	while (~scanf("%d", &n)) {
    
		while (n--) {
    
			cin >> s;
			vis.clear();
			sum = 0;
			for (int i = 1; i < s.size(); ++i) {
    
				left = s.substr(0, i), right = s.substr( i );
				temp = left + right ;
				if ( vis[temp] == 0) {
    
					sum ++;
					vis[temp] = 1;
				}
				temp = right + left ;
				if ( vis[temp] == 0) {
    
					sum ++;
					vis[temp] = 1;
				}
				nowl = left, nowr = right;
				reverse(nowl.begin(), nowl.end()) ;
				temp = nowl + right ;
				if ( vis[temp] == 0) {
    
					sum ++;
					vis[temp] = 1;
				}
				temp = right + nowl;
				if ( vis[temp] == 0) {
    
					sum ++;
					vis[temp] = 1;
				}
				nowl = left, nowr = right;
				reverse(nowr.begin(), nowr.end()) ;
				temp = left + nowr ;
				if ( vis[temp] == 0) {
    
					sum ++;
					vis[temp] = 1;
				}
				temp = nowr + left;
				if ( vis[temp] == 0) {
    
					sum ++;
					vis[temp] = 1;
				}
				nowl = left, nowr = right;
				reverse(nowl.begin(), nowl.end()) ;
				reverse(nowr.begin(), nowr.end()) ;
				temp = nowl + nowr ;
				if ( vis[temp] == 0) {
    
					sum ++;
					vis[temp] = 1;
				}
				temp = nowr + nowl;
				if ( vis[temp] == 0) {
    
					sum ++;
					vis[temp] = 1;
				}
			}
			printf("%d\n", sum);
		}
	}
	return  0;
}

Curling game 2.0

Title Description
stay MM-21 On the planet , After the Olympic Games this year , Curling games are becoming more and more popular . But the rules are somewhat different from ours . The game is played on the ice game board , There is a square grid on the board . They only use one stone . The purpose of the game is to guide the stone from the beginning to the end with the least number of moves .

chart 1 Shows an example of the game board . Some squares may be occupied by obstacles . There are two special squares , That is, the starting point and the ending point , No obstacles .（ The start point does not coincide with the end point ） Once the stone starts to move , It will continue to move , Until you hit an obstacle or fall out of the game board . To bring the stone to the goal , You may need to hit a stone against an obstacle , Then throw it again

The movement of stones follows the following rules ：

At the beginning of the , The stone stops at the starting point .

The movement of stones is limited to horizontal and vertical directions . Do not move diagonally .

When the stone is still , You can make it move by throwing stones . You can throw it in any direction that is not blocked （ chart 2（a））.

After throwing , The stone will continue to move in the same direction , Until one of the following happens ：

A stone hits a stone （ chart 2（b）、（c））.

The stone stopped on the square next to the obstacle it hit .
Then the obstacle disappears .
The stone fell out of the board .

The game failed .
The stone reached the target square .

The stone stopped there , Game success .
In a game , You can't throw stones more than 10 Time . If the stone is 10 The goal is not achieved in the step , The game will end in failure .

According to the above rules , We want to know whether the stone at the beginning can achieve the goal , If possible , We want to know the minimum number of moves needed .

If the initial situation is as shown in the figure 1 Described , Then we move 4 You can reach the target square once , chart 3 Of a,b It represents the changes of the chessboard after the route and movement respectively

Input format
Input no more than 100 Group data , Separated by two spaces 0 End of input

For each group of data, first enter two positive integers separated by spaces w and h It represents the left and right width and upper and lower height of the chessboard respectively

2≤w≤20,1≤h≤20

Next h Every line m Number , Contains only 0 1 2 3 One of them
among
0 Indicates that the square is empty
1 Indicates that there is an obstacle on the square
2 Indicates the starting position
3 Indicates the target location

For example, figure 1 The chessboard in is described as follows

6 6
1 0 0 2 1 0
1 1 0 0 0 0
0 0 0 0 0 3
0 0 0 0 0 0
1 0 0 0 0 1
0 1 1 1 1 1

Output format
For each set of data , Output the minimum number of moves , If the target location cannot be reached , Output -1

Their thinking ：

2 Point is the starting point , stay dfs Pay attention to the process 2 The particularity of point , It is not 1（ wall ）, Don't just encounter non 1 Always stop at .
Because the curler will stop when it hits the wall , Then the wall disappears . So the graph changes at any time , use dfs The backtracking of can be well solved , Although this question is a bit like bfs, But the picture changes at any time , use bfs Also back up the diagram , The complexity of time and space is greatly improved .

Code ：

#include <stdio.h>
#include <cstring>
#include <algorithm>

using namespace std;
const int INF = 0x3f;
const int N = 100;

int dx[4] = {
    0, 0, 1, -1}, dy[4] = {
    1, -1, 0, 0};
int n, m, sx, sy, res;
int mp[N][N];


void dfs(int x, int y, int step) {
    
	if (step > 10)
		return ;
	for (int i = 0; i < 4; ++i) {
    
		int xx = x + dx[i], yy = y + dy[i];
		if (mp[xx][yy] == 1) //  If the first one is all obstacles, change the direction 
			continue;
		//  Slide in this direction without obstacles 
		while (mp[xx][yy] == 0 || mp[xx][yy] == 2 )
			xx +=  dx[i], yy +=  dy[i];
		//  The grid that cannot slide is -1  It means crossing the border 
		if (mp[xx][yy] == -1)
			continue;
		//  Stop when encountering obstacles 
		if (mp[xx][yy] == 1) {
    
			//  Remove this obstacle 
			mp[xx][yy] = 0;
			//  Because it's to the grid next to the obstacle , So go back one space 
			dfs(xx - dx[i], yy - dy[i], step + 1) ;
			mp[xx][yy] = 1; //  to flash back 
		}
		if (mp[xx][yy] == 3) {
    
			res = min(res, step);
			continue;
		}
	}
}

int main() {
    
	while (~scanf("%d%d", &m, &n)) {
    
		if (!n && !m)
			break;
		memset(mp, -1, sizeof mp);
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= m; ++j) {
    
				scanf("%d", &mp[i][j]);
				if (mp[i][j] == 2)
					sx = i, sy = j;
			}
		res = INF;
		dfs(sx, sy, 1);
		if (res < INF)
			printf("%d\n", res);
		else
			puts("-1");
	}
	return 0;
}