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[1005];
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[0]=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[0][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;
}