2024 Fall PAT Certification Level A (Problem Solutions A-D)
write sth. upfront
This PAT Class A was supposed to be the easiest of the last few times, the 3 hour match was ak in almost 30 minutes (also took rk1 for the whole match), here's the problem solving report, each question was almost 20-30 lines of code, and the difficulty was around the Loyalist popularity group (cf 1000-1200 points)
A. A-1 Happy Patting
Title Description
The "Happy Patting" game is to arrange the children into n rows, with m people in each row. When the game starts, each child will receive a digital command on his/her mobile phone simultaneously: 1 for forward, 2 for backward, 3 for left, and 4 for right. The children must follow the command to pat the children in the specified direction. How many children are patted by more than one friend?
Note: In the plane diagram, the top of a grid is "front" and the bottom is "back". Children in the corners may pat the air, which is also allowed.
importation
Each input file contains one test case. The first line gives 2 positive integers n and m (2≤n,m≤100), which are the number of rows and the number of people in each row, respectively.
Then n lines follow, each contains m numbers, which represent the digital commands received by the children at the corresponding position.
All the numbers in a line are separated by a space.
importation
For each test case, print in a line the number of children who are patted by more than one friend.
example
in:
3 5
1 2 3 4 1
4 1 4 3 3
3 2 1 1 3
out:
4
brief outline of the topic
give a\(n * m\)of matrices, each with a number on it representing the side to which a child on this grid moves, and finally asking how many of all the grids have more than 1 child on them
reasoning
Direct simulation, using a two-dimensional array to store the number of children in each position, each time a number is entered, representing the current position of the child will move to the target position of the grid, so that the number of children in the target position +1 can be, and finally traverse the two-dimensional array, counting the number of numbers greater than 1 can be (if out of bounds will not be recorded)
AC code
#include<bits/stdc++.h>
using namespace std;
int main()
{
(0) -> sync_with_stdio(0);
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n + 1, vector<int>(m + 1));
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m ; j ++)
{
int t;
cin >> t;
int x = i, y = j;
if(t == 1) x --;
if(t == 2) x ++;
if(t == 3) y --;
if(t == 4) y ++;
if(x < 1 || x > n || y < 1 || y > m) continue;
graph[x][y]++;
}
int ans = 0;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m ; j ++)
ans += graph[i][j] > 1;
cout << ans;
}
B. A-2 Baggage Carousel
Title Description
When a flight arrives, the passengers will go to the Arrivals area to pick up their luggages from a baggage carousel（luggage carousel）.
Now assume that we have a special airport that has only one pickup window for each baggage carousel. The passengers are asked to line up to pick up their luggage one by one at the window. The carousel can hold at most m luggages, and each luggage has a unique tag number. When a passenger's tag number is matched by a luggage on the carousel, the luggage is then handed to the passenger and the next luggage will be sent onto the carousel.
But if one arrives at the window yet finds out that one's luggage is not on the carousel, one will have to move to the end of the queue and wait for the next turn. Suppose that each turn takes 1 minute, your job is to calculate the total time taken to clear the baggage carousel.
importation
Each input file contains one test case. The first line gives 2 positive integers \(n\) (≤500) and \(m\) (≤50), which are the number of passengers and the size of the baggage carousel, respectively.
Then n distinct tag number are given in the next line, each is an 8-digit number. The tag numbers are given in the order of being sent to the carousel. It is assumed that \(min(n,m)\) luggages are already on the carousel at the beginning.
The next line gives another sequence of n distinct tag numbers, which corresponds to the passengers in the queue.
All the numbers in a line are separated by a space.
exports
For each test case, print in a line the total time taken to clear the baggage carousel.
NOTE
If the tag number of a passenger cannot be found at all, that means the passenger's luggage is lost. In this case you must output in a line TagNumber is lost! where TagNumber is the tag number, and then remove this passenger from the queue right away. Since the number of luggages is the same as the number of passengers, if one passenger's luggage is lost, there must be one luggage left and the carousel can never be cleared. In this case, output in the last line the total time taken to clear the passengers' queue.
example
in1:
10 4
00000001 00000002 00000003 00000004 00000005 00000006 00000007 00000008 00000009 00000010
00000010 00000008 00000006 00000001 00000004 00000007 00000003 00000009 00000005 00000002
out1:
16
in2:
10 4
00000001 00000002 00000003 00000004 00000005 00000006 00000007 00000008 00000009 00000010
00000008 12345678 00000006 00000001 00000004 00000007 87654321 00000009 00000005 00000002
out2:
12345678 is lost!
87654321 is lost!
14
brief outline of the topic
there are\(n\)individuals and\(n\)baggage and a room for up to\(m\)Pieces of luggage on the luggage carousel, people and luggage have unique numbers, people are lined up in a given order, luggage goes on the luggage carousel in a given order, each time the person at the top of the queue walks up the luggage carousel, if there is his luggage on the luggage carousel then he will take his luggage and leave straight away, if he doesn't find his luggage, he will go back to the end of the queue and get back in line again but if his luggage isn't in this\(n\)Among the pieces of luggage, you should report that his luggage is missing, and then he will simply leave. The time it takes each person to walk up and check the baggage carousel operation is recorded as one unit, and you are asked how much time it will take when all the people have left.
reasoning
This question actually asks you to model a baggage carousel (which can be maintained with set), and two queues (a queue for baggage and a queue for people), and you can start by using the map container to record each baggage that has appeared, from the baggage queue\(min(m, n)\)pieces of luggage into the luggage carousel, each time you take out the head of the queue of the person queue, first query the map to see if there is this person's luggage, if there is no indication that the person's luggage is lost, directly jump to the next person, otherwise use the set of the count function to determine whether the current person's luggage is on the luggage carousel, if it is on the baggage carousel, then his luggage from the baggage carousel to delete (using the erase function to complete), and at the same time Remove the head of the queue from the baggage queue and fill it into the baggage carousel, then move on to the next person; if it is not on the baggage carousel, then re-enter the person into the queue and move on to the next person. Until the person's queue is empty, just record the time.
AC code
#include<bits/stdc++.h>
// #include<>
using namespace std.
int main()
{
(0) -> sync_with_stdio(0);
cin >> sync_with_stdio(0); int n, m;
cin >> n >> m;
queue<string> luggage; //queue for luggage
map<string, int> has;
for(int i = 0; i < n; i ++)
{
string s; cin > >
cin >> s;
(s); // queue each bag in order
has[s] = 1; // Record the current occurrence of the baggage.
}
queue<string> q; // Passenger's queue
for(int i = 0; i < n; i ++)
{
cin > > // Passenger's queue
cin > > s; }
(s);
}
set<string> now; // luggage carousel
int ans = 0; while(m-- && ()
while(m-- && ()) // first take m pieces of luggage and put them on the carousel
{
(()); // take m pieces of luggage and put them on the carousel first { (())
();
}
while(())
{
ans++; // +1 time per operation
string t = (); // take out the head of the passenger queue
(); if(!has[t])
if(!has[t]) // if this passenger's luggage hasn't appeared that means it's missing
{
cout << t << " is lost!\n".
continue; // go straight to the next step
}
if(! (t)) (t); // if baggage is not on the carousel, re-enter the queue
else // on the baggage carousel
{
(t); // remove this piece of luggage from the luggage carousel
if(()) // add a piece of luggage from the luggage queue to the carousel
{
(()); // delete this bag from the baggage carousel { (t)
();
}
}
}
// Output the answer
cout << ans.
}
C. A-3 Finding Independent Set
description of title
Given a simple undirected graph \(G=(V,E)\). An independent set of G is a set \(S⊆V\) such that no two members of \(S\) are connected by an edge in \(E\). Finding the maximum independent set of \(G\) is an NP-hard problem. Here you are supposed to implement a greedy hueristic to find a near-maximum independent set.
The algorithm works in the following way:
- Collect any one un-visited vertex v into \(S\).
- Delete all the vertices (and all the edges incident on them) that are adjacent to \(v\) from \(G\).
- Repeat steps 1 and 2 until there is no un-visited vertex left in \(G\).
In order to obtain the unique solution, when there are many options in step 1, you must always choose the vertex with the smallest index.
importation
Each input file contains one test case. For each case, the first line contains 2 positive integers: n (≤1000), the number of vertices; and m, the number of edges. Then m lines follow, each gives indices of the two ends of an edge. The vertices are indexed from 1 to n.
exports
Print in a line the indices of the vertices in the independent set obtained by the given greedy algorithm. The indices must be in increasing order, and must be separated by exactly 1 space. There must be no extra space at the beginning or the end of the line.
example
in:
8 7
1 5
5 4
4 2
2 3
3 6
6 1
6 2
out:
1 2 7 8
brief outline of the topic
Given a graph, find an independent set in order, selecting one point at a time and deleting all points adjacent to this point until there are no points to delete, outputting this independent set.
Independent set: a subgraph of a graph in which no edges are connected between any two points in the graph, or, in other words, a set is selected such that a point adjacent to a point in the set is not in the set.
Brief description of the topic2
Given a graph, find the independent set with the smallest dictionary sequence
reasoning
Selects a point in order, adds him to the answer sequence if the point is not marked, and marks all his neighboring points, or just skips them if they have been marked.
AC code
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
vector<int> edge[N];
int main()
{
int n,m;
cin >> n >> m;
while(m --)
{
int a,b;
cin >>a >>b;
edge[a].push_back(b);
edge[b].push_back(a);
}
vector<int> vis(n + 1), ans;
for(int i = 1; i <= n; i ++)
{
if(vis[i]) continue;
vis[i] = 1;
ans.push_back(i);
for(auto v : edge[i]) vis[v] = 1;
}
for(int i = 0; i < (); i ++)
cout << ans[i] <<" \n"[() - 1 == i];
}
D. A-4 The Smallest Open Interval
description of title
Given a set \(S\) of points on the \(x\)-axis. For any point \(p\), you are suppose to find the smallest open interval that contains \(p\), provided that the two ends of the interval must be in \(S\).
importation
Each input file contains one test case. Each case consists of several lines of commands, where each command is given in the format:
cmd num
where cmd is either I for "insert", or Q for "query", or E for "end"; and num is an integer coordinate of a point on the x-axis. It is guaranteed that num is in the range \([−10^9, 10^9]\).
The input is ended by E. It is guaranteed that there are no more than \(10^5\) distinct points in \(S\), and so is the number of queries. The total number of commands (E not included) is no more than \(3×10^5\).
exports
For each I case, insert num into \(S\). For each \(Q\) case, output the smallest open interval that contains num in the format \((s1, s2)\), where both \(s_1\) and \(s_2\) must be in \(S\). On the other hand, if num is no larger than the smallest point in \(S\), s1 shall be replaced by \(-inf\), representing negative infinity; or if num is no smaller than the largest point in \(S\), \(s_2\) shall be replaced by \(+inf\), representing positive infinity.
It is guaranteed that there must be at least 1 point in S before the first query.
example
in:
I 100
Q 100
I 0
I 33
I -200
Q 25
Q 33
Q -200
Q 200
E
out:
(-inf, +inf)
(0, 33)
(0, 100)
(-inf, 0)
(100, +inf)
brief outline of the topic
Given a set of points on an axis, insert a point at a time, or query for a point, and output the smallest open interval containing that point.
Brief description of the topic2
Maintains a balanced search tree that supports insertion and querying for predecessor and successor points (outputs +-inf if not present)
reasoning
Just use the C++ set container to maintain it.
AC code
#include<bits/stdc++.h>
using namespace std;
int main()
{
set<int> tr;
string op;
while(cin >> op, op != "E")
{
int p;
cin >>p;
if(op == "I") (p);
else
{
if(() == 0)
{
cout << "(-inf, +inf)\n";
continue;
}
auto next = tr.upper_bound(p);
auto pre = tr.lower_bound(p);
--pre;
if(*pre >= p)
cout << "(-inf,";
else
{
cout << "(" << *pre << ",";
}
if(next == ())
cout << " +inf)\n";
else cout << " " << *next <<")\n";
}
}
}