The 8th "Turing Cup" NEUQ-ACM program design competition individual competition - warm up competition

7-1 Iris pot

Iris got her wish and became a life committee member. Today, she will divide her classmates into teams to complete the classroom tasks. To improve efficiency, each team must have exactly one team leader and at least one team member. In order to avoid students feeling unfair, each team must have the same number of people. Although iris' high scores are very good, she has the world in mind and has no time to solve these small problems. So Dirt asked you to help her figure out the number of feasible teams.

Input format

Enter a total of one line. Give a positive integer \ (n(2\leqslant n \leqslant 10^5) \).

Output format

Output a total of one line. A positive integer is given to represent the number of feasible team members and types.

sample input

Here is a set of inputs. For example:

10

sample output

The corresponding output is given here. For example:

3

Author: Pei buye
Setting: Qinhuangdao branch of Northeast University
Code length limit: 16 KB
Time limit: 1000 ms
Memory limit: 64 MB

PZ's solution

1. since each team must have exactly one team leader and at least one team member, each team must have at least \ (2\) individuals;

2. according to the conditions of the question, the question actually requires that how many \ (x \in [2,n) \) should meet \ (x|n\) (\ (x\) divide by \ (n\));

3. consider a small optimization. Since it is impossible to divide \ (n\) even if it is greater than \ (\frac{n}{2}\), the range of the loop can be reduced to \ ([2 \frac{n}{2}]\);

  • TAG: sign in question

PZ.cpp

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,ans=1;
int main(){
	scanf("%d",&n);
	for(int i=2;i<=n/2;++i) if(n%i==0) ++ans;
	printf("%d",ans);
	return 0;
}

7-2 long way to school

Xiao Ning is a student of hafnium silk high school in Jingzhou. He rides a bike to and from home and school every day. In order to stay in bed as much as possible, he hopes to accurately predict the time he will need to go to school. He needs to go through several sections of roads to go to school, and at most one traffic light is set between two adjacent sections of roads.

The traffic lights in Jingzhou work like this: each traffic light has three red, yellow and green lights and a display board that can show the countdown. Suppose traffic lights are set to red light \ (r\) seconds, yellow light \ (y\) seconds and green light \ (g\) seconds.

Then the red light will be on within \ ([0,r) \) seconds from \ (0\), and the vehicle is not allowed to pass;

\The green light is on within ([r,r+g) \) seconds, and the vehicle is allowed to pass;

\The yellow light is on within ([r+g,r+g+y) \) seconds, the vehicle is not allowed to pass, and then cycle in sequence.

The number displayed on the countdown display board \ (s (s>0) \) refers to the number of seconds from the next signal lamp change.

On the way to school, Xiao Ning recorded the time of each section of the road, the color of each traffic light and the countdown seconds when Xiao Ming arrived at the intersection. I hope you can help me calculate the time Xiao Ning spent in school this time.

Input format

The first line of input contains three positive integers \ (r,y,g\) separated by spaces, indicating the setting of traffic lights. None of the three numbers exceeds \ (10^6\).

The second line of input contains a positive integer \ (n(n\leqslant 100) \), which represents the sum of the number of road segments Xiao Ming has passed and the number of traffic lights he has seen.

The next \ (n\) lines contain two integers \ (k,t\) separated by spaces\ (k=0\) indicates that you have passed a section of road, which takes \ (t\) seconds. Here \ (t\) does not exceed \ (10^6\)\ (k=1,2,3\), it means that a red light, a yellow light and a green light are seen respectively, and the number displayed on the countdown display board is \ (t\), where \ (t\) will not exceed \ (r,y,g\) respectively.

Output format

Output the corresponding answer.

sample input

Here is a set of inputs. For example:

30 3 30
8
0 10
1 5
0 11
2 2
0 6
0 3
3 10
0 3

sample output

The corresponding output is given here. For example:

70

Tips

Xiaoming passes the first section of road for \ (10\) seconds, then waits for a red light of \ (5\) seconds, then passes the second section of road for \ (11\) seconds, then waits for a yellow light of \ (2\) seconds and a red light of \ (30\) seconds, then passes the third and fourth sections of road for \ (6 and 3\) seconds respectively, then passes the green light, and then passes the last section of road for \ (3\) seconds. Total \ (10 + 5 + 11 + 2 + 30 + 6 + 3 + 3=70\) seconds.

Author: Pei buye
Setting: Qinhuangdao branch of Northeast University
Code length limit: 16 KB
Time limit: 1000 ms
Memory limit: 64 MB

PZ's Solution

  • This problem can be simulated directly. See code Notes for details;

  • TAG: simulation

PZ.cpp

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int r,y,g,n,ans,k,t;
int main(){
	scanf("%d %d %d",&r,&y,&g);
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d %d",&k,&t);
		if(k==0) ans+=t;
		//For a section of road, pass it directly and accumulate the time
		else if(k==1)
			ans+=t;
		//In case of red light, wait for the red light before passing
		else if(k==2){
			ans+=t;
			ans+=r;
		//In the case of yellow light, the yellow light is followed by a red light, and you have to wait for the red light to pass
		} else if(k==3)
			continue;
		//In case of green light, you can pass it directly
	}
	printf("%d",ans);
	return 0;
}

7-3 long way to school

You have to go to school before you can leave school! (make a long way to school first)

The Guangming District, where the high school affiliated to Handong University of political science and law is located, recently implemented a smart city project called "smart Guangming". Specifically, in the transportation field, you can see the current status of all traffic lights in the bright area through the "smart bright" terminal. Xiaoming's school has also installed a "smart bright" terminal. Xiaoming wants to use the information given by this terminal to estimate the time he will return home from school.

Once after school, Xiao Ming had planned his way home and could predict the time of each section. At the same time, Xiao Ming saw the indication status of all traffic lights on the road at the time of departure through the "smart light" terminal installed in the school. Please help calculate the time required for Xiaoming to go home this time.

Input format

The first line of input contains three positive integers \ (r,y,g\) separated by spaces, indicating the setting of traffic lights. None of the three numbers exceeds \ (10^6\).

The second line of input contains a positive integer \ (n\), which represents the sum of the number of road segments Xiao Ming has passed and the number of traffic lights he has seen.

The next \ (n(n\leqslant 10^5) \) lines contain two integers \ (k,t\) separated by spaces\ (k=0\) indicates that it will take \ (t\) seconds to pass through a section of road. Here \ (t\) does not exceed \ (10^6\)\ (k=1,2,3\) respectively indicates the departure time. The traffic light status here is red, yellow and green, and the number displayed on the countdown display board is \ (t\), where \ (t\) will not exceed \ (r,y,g\) respectively.

Output format

Output a number indicating the time taken for Xiaoming to return home from school this time.

sample input

Here is a set of inputs. For example:

30 3 30
8
0 10
1 5
0 11
2 2
0 6
0 3
3 10
0 3

sample output

The corresponding output is given here. For example:

46

Tips

Xiaoming goes through the first section of the road first. It takes \ (10\) seconds. When the first traffic light starts, it is a red light, and \ (5\) seconds remain; When Xiao Ming arrives at the intersection, the traffic light has changed to green. He doesn't have to wait to pass directly. Next, it takes \ (11\) seconds to pass through the second section. The second traffic light is yellow when starting, and there are two seconds left; When Xiao Ming arrives at the intersection, the traffic light has changed to a red light. There are \ (11\) seconds left. It takes \ (9\) seconds to pass through the third and fourth sections. The third traffic light is green when starting, and \ (10\) seconds remain; When Xiao Ming arrives at the intersection, the traffic light has turned red. There are two seconds left. It takes \ (3\) seconds to pass the last section. Total \ (10+11+11+9+2+3 = 46\) seconds.

PZ's Solution

1. this question is slightly different from 7-2, because all the information we know is the information at the beginning, and the signal light at the intersection is closely related to Xiaoming's walking time;

2. in fact, the process of finding the answer is the process of finding the time when Xiaoming passed the road. Set the variable \ (ans\) as the answer variable, which is also the record variable of the current elapsed time;

3. if a signal lamp is encountered, two situations need to be handled:

1) The countdown time of the signal light \ (t\) is longer than that of Xiaoming, which means that when Xiaoming reaches the intersection, the signal light has not changed;

2) The countdown time of the signal light \ (t\) is shorter than that of Xiaoming, which indicates that when Xiaoming reaches the intersection, the state of the signal light has been different from the starting time;

4. after distinguishing the status, you can simulate the change of the signal lamp currently encountered through the \ (ans\) variable, and judge the passing time of the current intersection through the change. See the code Notes for details;

  • TAG: simulation

PZ.cpp

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int r,y,g,n,k,t;
long long ans,tim;
//10^11 exceeds int, so the time variable needs to use the long long type
void change_k(int &x){
	if(x==1) x=3;
	else if(x==2) x=1;
	else if(x==3) x=2;
}
//A transition function is written here, which uses k to judge the current status of the signal lamp
// 1 - > red light
// 2 - > yellow light
// 3 - > Green
int main(){
	scanf("%d %d %d",&r,&y,&g);
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d %d",&k,&t);
		if(k==0) 
			ans+=t;
		//If it is only a section of road, go straight to it, and the time is t
		else{
			tim=ans;
			if(tim<t){
			//If the countdown t is longer than the current elapsed time tim, the signal lamp has not changed
				t-=tim;
				//Update the countdown t to the time at the current position
				if(k==1)
					ans+=t;
				//Red light, wait until it turns green
				else if(k==2){
					ans+=t;
					ans+=r;
				//Yellow light, it also needs to change to red light and then to green light
				}else if(k==3)
					continue;
				//Green light passes directly
			} else {
			//If the countdown t is shorter than the current elapsed time tim, it means that the signal light has changed before Xiao Ming arrives
				tim-=t;
				change_k(k);
				//The countdown is over, and the signal lamp changes
				tim%=(r+y+g);
				//Here is a pruning to shorten the time, because the signal changes of green, yellow and red are cycles. Just skip these cycles and find out the last critical change time
				while(1){
					if(k==1){
						if(tim<r) break;
						else tim-=r;
						change_k(k);
					}else if(k==2){
						if(tim<y) break;
						else tim-=y;
						change_k(k);
					}else if(k==3){
						if(tim<g) break;
						else tim-=g;
						change_k(k);
					}
				}
				//The above is the code of the change process of the signal lamp. Finally, k can be used to judge the current state of the signal lamp
				if(k==1)
					ans+=r-tim;
				//It is currently red and the remaining time to wait is r-tim
				else if(k==2)
					ans+=r+y-tim;
				//The current light is yellow. Wait until it turns red before turning green
				else if(k==3)
					continue;
				//The current light is green, and you can go directly through
			}
		}
	}
	/*
	In fact, I noticed here that the countdown interval of the signal light is left closed and right open, that is, when the countdown is 0,
	The signal light has changed. Of course, the code also accurately reflects this feature. I just thought of it and wanted to mention it: 3
	*/
	printf("%lld",ans);
	return 0;
}

Posted by psn on Fri, 03 Jun 2022 12:01:46 +0530