# Spring 2022 "Analysis and Design of Algorithms" Exercise 12

### 1378: Prime number for XP

Topic description

XP has been obsessed with prime numbers lately, especially those special ones, of which there is a class of primes called twin primes. It is defined as follows: If a number k is prime and k+2 is also prime, then k and k+2 become a pair of twin primes. Please count the number of twin prime pairs in a given interval m and n (0<m<n).

enter

single set of input data

m n

(0<m<n<1000)

output

Please output a line of results: the number of twin prime pairs in the interval [m,n]

Sample input Copy

```1 999
```

Sample output Copy

`35`
```#include<iostream>
using namespace std;

bool Prime(int n){
int i;
if(n==1)
return false;
for(i=2;i<n;i++){
if(n%i == 0)
return false;
}
return true;
}
int main(){
int m,n;
while(cin>>m){
cin>>n;

int ans=0;
for(int i=m;i<=n-2;i++){
bool a=Prime(i);
bool b=Prime(i+2);
if(a&&b)
ans++;
}
cout<<ans<<endl;
}
}```

### 1385: Bits of XP

Topic description

XP accidentally caught a cold, so he went to the school hospital for an intravenous drip. It's really boring to have a drip. He saw the salt water dripping drop by drop, and suddenly thought of a problem: if the salt water drips regularly, first drop one drop, stop for a while; then drop two drops, stop for a while; drip three drops, stop for a while. .., assuming this bottle of salt water has a total of n ml, each drop is y ml, and the time required for each drop is one second (if the last drop is less than y ml, the time it takes is also one second), and the time to stop is also one second. How long does it take for XP to finish this bottle of salt water?

enter

A single set of input data

n y (0<n,y<=1000)

output

output a line of results

Sample input Copy

```10 1
```

Sample output Copy

`13`
```import java.util.Scanner;

//Problem B: Bits of XP
//        Topic description
//        XP accidentally caught a cold, so he went to the school hospital for an intravenous drip. Drips are so boring.
//        He saw the salt water dripping drop by drop, and suddenly thought of a question: If the salt water drips regularly,
//        First drop one drop, stop for a while; then drop two drops, stop for a while; then drop three drops, stop for a while... Suppose this bottle of saline has a total of n milliliters,
//        Each drop is y milliliters, and the time required for each drop is one second (assuming the last drop is less than y milliliters, the time it takes is also one second),
//        The pause time is also one second. How long does it take for XP to finish this bottle of salt water?
public class Main{
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
double n=scan.nextInt();
double y=scan.nextInt();
int s=(int)Math.ceil((double)n/y);
double x=0;
double delta=8*s+1;
x=Math.ceil((-1+Math.sqrt(delta))/2);
x --;
System.out.println((int)x+s);
}
}```

### 1717: Placement of street lamps

Topic description

Xiao Q is designing a street lamp placement plan for a road of length n.

In order to make the problem simpler, Xiao Q regards the road as n squares, the places that need to be illuminated are represented by '.', and the obstacle grids that do not need to be illuminated are represented by 'X'.

Xiao Q now wants to set some street lights on the road. For the street lights placed at the pos position, this street light can illuminate the three positions of pos - 1, pos, and pos + 1.

Xiao Q hopes to place as few street lights as possible to illuminate all the '.' areas. I hope you can help him calculate the minimum number of street lights needed.

enter

```The first line of input contains a positive integer t (1 <= t <= 1000), representing the number of test cases
Next, every two lines of test data, the first line is a positive integer n (1 <= n <= 1000), which represents the length of the road.
In the second line a string s represents the construction of the road, containing only '.' and 'X'.```

output

`For each test case, output a positive integer indicating the minimum number of street lamps required.`

Sample input Copy

```2
3
.X.
11
...XX....XX```

Sample output Copy

```1
3```
```import java.util.Scanner;

public class Main{
public static void main(String[] args) {
int t;
int n;
String s;
Scanner scan = new Scanner(System.in);
t = scan.nextInt();
for (int i = 0; i < t; ++i) {
n = scan.nextInt();
s = scan.next();
char ss[] = s.toCharArray();
int count = 0;
for (int j = 0; j <ss.length; ++j) {
if (ss[j] == 'X') {
continue;
}
if (ss[j] == '.') {
j += 2;
count++;
}

}
System.out.println(count);
}
}
}```

### 1380: Small video of XP

Topic description

XP's cousin recommended him some small videos for learning computer programming, and these videos didn't play exactly the same length of time. Now given a period of time, can you tell XP how many videos he can watch at most? The playback time of each video and the given total time are in minutes.

enter

single set of input data

The first row is m n

m is a given length of time (minutes) (0<n,m<=1000)

n represents the number of videos

Next are n integers representing the playback time of each video (the playback time of each video is a positive integer not exceeding 1000)

output

Output an integer representing the maximum number of videos XP can watch.

Sample input Copy

```84 6
65 46 18 76 79 3```

Sample output Copy

`3`
```#include<bits/stdc++.h>
using namespace std;
int x;

int main()
{//Use greedy thinking, watch the shortest video first, and you will see more at the end
int n;
int  all;
scanf("%d %d",&all,&n);

int last=0;
memset(x,0,sizeof(x));
for(int i=1;i<=n;i++){
cin>>x[i];
}
sort(x+1,x+n+1);
for(int j=1;j<=n;j++){
double temp=all-x[j];
if(temp>=0.0){
all=temp;
last++;
}
}
cout<<last<<endl;

return 0;
}```

### 1473: Minimum Spanning Tree (Prim)

Topic description

Using Prim's algorithm to find the minimum spanning tree (MST) of a graph

enter

Each set of data is divided into two parts, the first part is the number of points n of the graph, and the number of edges m,
The second part consists of m lines, each line contains three numbers, the first two are the numbers of the two vertices, and the third is the edge weight.

output

Minimum spanning tree, output according to the ascending order of the two endpoints of the edge. (Look at the left endpoint first, then look at the right endpoint, the endpoints do not change positions)

Sample input Copy

```3 3
0 1 10
0 2 15
1 2 50
```

Sample output Copy

```0 1 10
0 2 15```
```#include <bits/stdc++.h>
using namespace std;
const int cmax = 1e3+5;
typedef long long ll ;
const int INF = 0x3f3f3f3f;
int a[cmax][cmax];  //  The adjacency matrix stores the undirected graph
bool vis[cmax];   //  vis[i] records the node numbered i, whether it is in the v set
struct node {
int start;
int end;
int weight;
};    //  Store the start and end points and weights of each edge
node res[cmax];
//  Edge Sort Comparison Function
bool cmp(node m,node n){
if (m.start!=n.start)
return m.start<=n.start;
else
return m.end<=n.end;
}
int flag=0;
void prim(int n){
int lowcost[cmax],closeset[cmax];
//  lowcost[i] represents the least cost of the weight from the node number i to the v set
//  closeset[i] represents the node numbered i to the nearest neighbor in the v set
//  -----------------------initialization-------------------------- --
vis=true;  //  At the beginning, there is only one node in the v set, and I use the node numbered 0 here.
for (int i = 0; i < n; ++i) {
lowcost[i]=fabs(a[i]);  //  lowcost array, initialized as the distance from node 0 to node i
closeset[i]=0;  //  closeset array, initialized to the nearest node from node 0 to node i
}
//  ----------------------- Find the smallest cost to go to the v set --------------------
for (int i = 1; i < n; ++i) {
int j=0;
for (int k = 0; k < n; ++k) {
if (!vis[k]&&lowcost[k]<lowcost[j]){
j=k;
}
}
//        printf("%d %d %d\n",closeset[j],j,lowcost[j]);
if (a[closeset[j]][j]>0){
res[flag].start=closeset[j];
res[flag].end=j;
res[flag].weight=lowcost[j];
flag++;
}
else{
res[flag].start=j;
res[flag].end=closeset[j];
res[flag].weight=lowcost[j];
flag++;
}
vis[j]=true;
//---------------------------Update lowcost[cmax],closeset[cmax]---------
for (int i = 0; i < n; ++i) {
if (!vis[i]&&(a[j][i]<lowcost[i])){
lowcost[i]=fabs(a[j][i]);
closeset[i]=j;
}
}
}
}
int main(){
int n,m;
while (~scanf("%d%d",&n,&m)){
flag=0;
int start,end,weight;
memset(a,INF,sizeof(a));
memset(vis, false,sizeof(vis));
for (int i = 0; i < m; ++i) {
scanf("%d%d%d",&start,&end,&weight);
a[start][end]=weight;
a[end][start]=-1*weight;
}
prim(n);
sort(res,res+flag,cmp);
for (int i = 0; i < flag; ++i) {
printf("%d %d %d\n",res[i].start,res[i].end,res[i].weight);
}
}
return 0;
}```

Tags: C++ Algorithm

Posted by forumnz on Wed, 05 Oct 2022 03:58:02 +1030