The ministers of the cabinet were quite upset by the message from the Chief of Security stating that they would all have to change the four-digit room numbers on their offices.
— It is a matter of security to change such things every now and then, to keep the enemy in the dark.
— But look, I have chosen my number 1033 for good reasons. I am the Prime minister, you know!
— I know, so therefore your new number 8179 is also a prime. You will just have to paste four new digits over the four old ones on your office door.
— No, it’s not that simple. Suppose that I change the first digit to an 8, then the number will read 8033 which is not a prime!
— I see, being the prime minister you cannot stand having a non-prime number on your door even for a few seconds.
— Correct! So I must invent a scheme for going from 1033 to 8179 by a path of prime numbers where only one digit is changed from one prime to the next prime.
Now, the minister of finance, who had been eavesdropping, intervened.
— No unnecessary expenditure, please! I happen to know that the price of a digit is one pound.
— Hmm, in that case I need a computer program to minimize the cost. You don't know some very cheap software gurus, do you?
— In fact, I do. You see, there is this programming contest going on... Help the prime minister to find the cheapest prime path between any two given four-digit primes! The first digit must be nonzero, of course. Here is a solution in the case above.
1033
1733
3733
3739
3779
8779
8179
The cost of this solution is 6 pounds. Note that the digit 1 which got pasted over in step 2 can not be reused in the last step – a new 1 must be purchased.
Input
One line with a positive number: the number of test cases (at most 100). Then for each test case, one line with two numbers separated by a blank. Both numbers are four-digit primes (without leading zeros).
Output
One line for each case, either with a number stating the minimal cost or containing the word Impossible.
Sample Input
3
1033 8179
1373 8017
1033 1033
Sample Output
6
7
0
题意：输入两个四位素数a、b，每次改变a的一位，改变后仍为素数，求a变为b的最少次数。
BFS广度搜索。从原素数开始搜索能从它变换一位数字得到的新素数，
每搜出一个新素数，继续搜索下一个能从原素数变形得到的新素数，等这一层的素数搜完了，发现没有产生最终目标素数，再从这一层逐一出发搜下一层，逐层搜索，求得最小步数.
需要一个素数判断函数，判断出下一个可变换成的素数。
#include <iostream>
#include <string.h>
#include <math.h>
using namespace std;
int isprime( int n)
{
int i,t;
t=sqrt(n+0.0);
for (i=2;i<=t;i++)
{
if (n%i==0)
return -2;
}
return -1;
}
const int S=10050;
int prime[S],f[S],w[4];
int main()
{
int i,T,x,y,tmp,a,b,c,d,t;
for (i=2;i<S;i++) prime[i]=isprime(i);
cin>>T;
while (T--)
{
cin>>x>>y;
memcpy(f,prime,S*sizeof(int));
f[x]=0;
queue<int> q;
q.push(x);
while (!q.empty()&&(f[y]==-1))
{
t=q.front();
tmp=t;
q.pop();
for (i=0;i<=3;i++)
{
w[i]=tmp%10;
tmp/=10;
}
for (i=0;i<=9;i++)
{
tmp=i+10*w[1]+100*w[2]+1000*w[3];
if (f[tmp]==-1)
{
f[tmp]=f[t]+1;
q.push(tmp);
}
}
for (i=0;i<=9;i++)
{
tmp=w[0]+10*i+100*w[2]+1000*w[3];
if (f[tmp]==-1)
{
f[tmp]=f[t]+1;
q.push(tmp);
}
}
for (i=0;i<=9;i++)
{
tmp=w[0]+10*w[1]+100*i+1000*w[3];
if (f[tmp]==-1)
{
f[tmp]=f[t]+1;
q.push(tmp);
}
}
for (i=1;i<=9;i++)
{
tmp=w[0]+10*w[1]+100*w[2]+1000*i;
if (f[tmp]==-1)
{
f[tmp]=f[t]+1;
q.push(tmp);
}
}
}
if (f[y]!=-1)
cout<<f[y]<<endl;
else
cout<<"Impossible\n";
}
return 0;
}
A common pastime for poker players at a poker table is to shuffle stacks of chips. Shuffling chips is performed by starting with two stacks of poker chips, S1 and S2, each stack containing C chips. Each stack may contain chips of several different colors.
The actual shuffle operation is performed by interleaving a chip from S1 with a chip from S2 as shown below for C = 5:
Input
The first line of input contains a single integer N, (1 ≤ N ≤ 1000) which is the number of datasets that follow.
Each dataset consists of four lines of input. The first line of a dataset specifies an integer C, (1 ≤ C ≤ 100) which is the number of chips in each initial stack (S1 and S2). The second line of each dataset specifies the colors of each of the C chips in stack S1, starting with the bottommost chip. The third line of each dataset specifies the colors of each of the C chips in stack S2 starting with the bottommost chip. Colors are expressed as a single uppercase letter (A through H). There are no blanks or separators between the chip colors. The fourth line of each dataset contains 2 * C uppercase letters (A through H), representing the colors of the desired result of the shuffling of S1 and S2 zero or more times. The bottommost chip’s color is specified first.
Output
Output for each dataset consists of a single line that displays the dataset number (1 though N), a space, and an integer value which is the minimum number of shuffle operations required to get the desired resultant stack. If the desired result can not be reached using the input for the dataset, display the value negative 1 (−1) for the number of shuffle operations.
Sample Input
2
4
AHAH
HAHA
HHAAAAHH
3
CDE
CDE
EEDDCC
Sample Output
1 2
2 -1
题意：给定两个长度为len的字符串s1和s2， 接着给出一个长度为len*2的字符串s12。
将字符串s1和s2通过一定的变换变成s12，找到变换次数
变换规则如下：
假设s1=12345,s2=67890,
变换后的序列 s=6172839405.
如果s和s12完全相等那么输出变换次数
如果不完全相等，s的前半部分作为s1，后半部分作为s2，重复上述过程
首先输出处理数据组的编号（编号从1开始）
再输出变换次数并换行。
注意两个数字之间有空格。
对于变换次数，如果无需变换直接得到s12，那么输出0，如果无论怎么变换都不会得到s12，那么输出 -1。
#include<cstdio>
#include<string>
#include<map>
#include<iostream>
#include<algorithm>
using namespace std;
map<string, int>m;
string s1, s2, ans;
string s;
int h;
int step;
int dfs()
{
s = "";
for (int i = 0; i < h; i++)
{
s += s2[i], s += s1[i];
}
step++;
m[s]++;
if (s == ans)
return step;
if (m[s] > 1)
return -1;
s1 = "", s2 = "";
for (int i = 0; i < h; i++)
s1 += s[i];
for (int i = h; i < 2 * h; i++)
s2 += s[i];
dfs();
}
int main()
{
int t;
int tt = 1;
cin >> t;
while (t--)
{
step = 0;
cin >> h;
cin >> s1 >> s2;
cin >> ans;
cout << tt++ << " " << dfs() << endl;
}
return 0;
}
Severe acute respiratory syndrome (SARS), an atypical pneumonia of unknown aetiology, was recognized as a global threat in mid-March 2003. To minimize transmission to others, the best strategy is to separate the suspects from others.
In the Not-Spreading-Your-Sickness University (NSYSU), there are many student groups. Students in the same group intercommunicate with each other frequently, and a student may join several groups. To prevent the possible transmissions of SARS, the NSYSU collects the member lists of all student groups, and makes the following rule in their standard operation procedure (SOP).
Once a member in a group is a suspect, all members in the group are suspects.
However, they find that it is not easy to identify all the suspects when a student is recognized as a suspect. Your job is to write a program which finds all the suspects.
Input
The input file contains several cases. Each test case begins with two integers n and m in a line, where n is the number of students, and m is the number of groups. You may assume that 0 < n <= 30000 and 0 <= m <= 500. Every student is numbered by a unique integer between 0 and n−1, and initially student 0 is recognized as a suspect in all the cases. This line is followed by m member lists of the groups, one line per group. Each line begins with an integer k by itself representing the number of members in the group. Following the number of members, there are k integers representing the students in this group. All the integers in a line are separated by at least one space.
A case with n = 0 and m = 0 indicates the end of the input, and need not be processed.
Output
For each case, output the number of suspects in one line.
Sample Input
100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0
Sample Output
4
1
1
题意：有很多组学生，在同一个组的学生经常会接触，也会有新的同学的加入。SARS很容易传染，只要在某组有一位同学感染SARS，那么该组的所有同学都被认为得了SARS。求有多少位学生感染SARS。
假定编号为0的同学得了SARS。
这是一道并查集算法题。
遍历所有的节点的时候注意是找到根节点为a[0]的元素。
#include<iostream>
#define maxn 30500
using namespace std;
int a[maxn],per[maxn], num[maxn], n, m;
void init()
{
for (int i = 0; i < n; ++i)
{
per[i] = i;
num[i] = 1;
}
return;
}
int find(int x)
{
if (x == per[x])
return x;
return per[x] = find(per[x]);
}
void join(int x, int y)
{
int fx = find(x);
int fy = find(y);
if (fx != fy)
{
per[fx] = fy;
num[fy] += num[fx];
}
return;
}
int main()
{
while (cin>>n>>m, n || m)
{
init();
while (m--)
{
int t;
cin>>t;
for (int i = 0; i < t; ++i)
{
cin>>a[i];
}
for (int i = 0; i < t - 1; ++i)
join(a[i], a[i + 1]);
}
int k = find(0);
cout<<num[k]<<endl;
}
return 0;
}
