Last semester, PSUT’s e-learning system crashed. Unfortunately, Dr. Khamis lost many of his files, including the grades of the Operating Systems course. After searching between his papers, he was lucky to find a hard copy of the grades. Unfortunately again, the hard copy was printed using the department’s old printer, which puts random ink drops on the printed papers. This made many of the student IDs hard to read.
Help Dr. Khamis by writing a program to check automatically if a certain ID is readable or not.
The input contains a student ID.
Each ID is made of exactly 8 digits (20110000 ≤ ID ≤ 20159999). If any of the digits is not readable due to an ink drop, the digit is replaced with a question mark ‘?’.
Print ‘Yes’ if the student ID is readable and print ‘No’ otherwise.
201105?0
No
?011????
No
20120300
Yes
Since some IDs were not readable, Dr. Khamis posted the hardcopy of the grades for the students and asked each student with a non-readable ID to tell him which ID and grade are his.
One of the students did not do well in the exam and thought of tricking Dr. Khamis in order to get a higher grade. However, Dr. Khamis is not easy to trick!
Given the ID of the student and a sequence of IDs and grades, where each ID contains at most one question mark. Your task is to find the maximum grade that the student can claim without Dr. Khamis noticing that he is not honest.
The first line of the input contains an integer N (1 ≤ N ≤ 15), which represents the number of student IDs and grades that will follow, followed by the ID of the student.
Each of the following N lines contains an ID (20110000 ≤ ID ≤ 20159999) and a grade G (0 ≤ G ≤ 100) separated by a space. Each ID contains at most one question mark.
Without the question marks, no two students in the class have the same ID, and all their IDs are in the given range.
Print the maximum grade the student can claim without Dr. Khamis noticing that he is dishonest.
4 20121234
201212?4 64
20121235 93
2012123? 87
2012?234 75
87
While registering for this contest, you were asked to choose one of the following options:
• I don’t mind participating individually or in a team (up to three members).
• I want to participate individually.
Mr. Ahmad Awwad and his team prepared X PCs for individual teams, Y PCs for teams with two members and Z PCs for teams with three members. These PCs differ only in the space around the PCs, so individual participants can be assigned into any of the X, Y and Z PCs, and teams of two can be assigned into any of the Y and Z PCs. Teams of three can be assigned to the Z PCs only.
By the end of the registration, N students chose to participate either individually or as a team (2 or 3 members) and M students chose to participate individually. Mr. Ahmad wants to know if it is possible to form the teams such that everyone can participate satisfying the option he has chosen.
The input contains 5 space-separated integers: N M X Y Z, as described in the problem statement.
All integers are between 0 and 100 (inclusive).
Print “Yes” if it is possible to form the teams in a way that will satisfy everyone, otherwise print “No”.
7 1 3 4 0
Yes
9 6 2 3 2
No
Mr. Ahmad found that in some cases, it is impossible to satisfy everyone. Therefore, some individuals might be assigned to teams.
There are K PCs available at the IT labs, which may be prepared for 1, 2 or 3 students. Find the minimum possible number of unsatisfied students.
The input contains 3 space-separated integers: N M K, where:
N is the number of students who don’t mind to participate individually or in a team of 2 or 3 members.
M is the number of students who chose to participate individually.
K is the number of available PCs in the IT Labs.
All integers are between 0 and 1,000,000,000 (inclusive).
If K PCs are not enough to allow everyone to participate, print -1, otherwise print the minimum number of unsatisfied students.
4 8 8
2
8 5 3
-1
6 3 6
0
A Proficiency test was held at PSUT to measure your skills and knowledge before graduation. The test consisted of 48 multiple-choice questions with 4 choices (A, B, C or D).
Since the results of this test do not affect the students directly, it was expected that some students would answer randomly without reading the questions. These students affect the results of the university negatively.
To detect and remove these students before the evaluation process, Dr. Arafat suggested to make one of each 8 consecutive questions a very simple question (there will be 6 simple questions out of the 48 questions). Simple questions are so simple that even a 10-years-old child can answer them. If a student answers at least 3 of the 6 questions incorrectly, his results will be removed from the evaluation process.
Your task is to write a program that reads the correct 48 answers and the answers of one student and then decides whether the results of the student should be removed or not.
The first line of the input contains a string of 48 letters. The first letter is the answer for the first question, the second one is the answer for the second question, and so on.
A lowercase letter indicates that the question is one of the 6 simple questions. It is guaranteed that exactly one of each 8 consecutive letters is a lowercase letter.
The second line contains a string of 48 uppercase letters, representing the answers of the student.
Print “Remove” if the results of this student must be removed according to the problem statement, otherwise print “Kafo”.
BABAADbBbBAAADDBBDBCBABdcBACCDAAdABDDCDBBABBcDBB
ADAACBCBAACAAACBAACDBADAACAACDCDDBCBBDBABBABCADD
Remove
CBCBaBCCDACDDDDbCDAbBCCACAACAaABDCBDdDDAdDABABDD
DBACDCDDCABBCADBDBBACCAABCCCBACBABADDADCDCCCBCDB
Kafo
A group of students took the profeciency test and were filtered as described in the previous question. Mr. Rabah was printing a document on Dr. Arafat’s machine and accidently deleted the questions from the database! No one now can tell which questions are the 6 simple questions.
The correct answers, the answers of the students and the decision for each student are all still available. However, we need to know the 6 simple questions in order to make decisions about the remaining groups of students.
Given the correct 48 answers, the answers of some students, and the decision of the program from the previous task for each student, can you save Rabah and identify for sure (uniquely) the 6 simple questions?
The first line of the input contains the correct answers as a string of 48 letters. The second line contains an integer N (1 ≤ N ≤ 100) representing the number of students for whom the decisions were available before losing the questions.
Each of the next N lines contains a string of 48 letters, representing the answers of one of the students, followed by “-“ if this student’s records were removed or + if the records were not removed.
It is guaranteed that the given data is valid.
Print “No” if it is impossible to identify the 6 questions uniquely, otherwise print “Yes”.
AACAADADCAADDDBCDABCDBBCACABCCCDADABCCCDCADADAAA
2
AACBDDADCAADDDBCDABCDDDCACABBCCDADABACCDCDDACABA +
AACDCDACCAADCABCBABCDDBCADABCBCDAAABCDCDCADABBAA -
No
AACAADADCAADDDBCDABCDBBCACABCCCDADABCCCDCADADAAA
2
DACAADADCAADCDBCDACCDBBCACABCCCDADABCCCDCADADAAA -
AACAADADCAADDDBCDABCDBBCACABCDCDADABCACDCADABAAA -
Yes
In order to improve teamworking skills of PSUT students, Dr. Saqer decided that each student must have a partner in his graduation project.
According to Dr. Saqer, the quality of any team can be predicted by summing the grades of the team members in his Systems Analysis course. Therefore, the maximum quality of a team is 200, if the two students each scored 100 in the Systems Analysis course.
As the head of the CS department, Dr. Saqer wants to form teams in a way that guarantees a good overall quality in the department. He wants to avoid having very strong teams and very weak teams at the same time. The overall quality can be determined by looking at the difference between the quality of each team and the average quality of all of the teams.
Dr. Saqer defines the quality imbalance as the “sum of the absolute difference between the quality of each project and the average quality of all of the projects”. A low imbalance is preferred over a high imbalance.
Given N teams and the grades of the 2N team members in the Systems Analysis course, calculate the imbalance of this teams formation.
The first line of input contains an integer N (1 ≤ N ≤ 50) representing the number of teams.
The second line contains 2N space-separated integers; each representing the grade of one student.
Each two consecutive students form a team.
Print the imbalance.
2
23 36 28 8
23.000000000
3
26 48 16 24 9 8
60.666666667
The imbalance value of last year was too large. Therefore, Dr. Saqr asked you to implement a program that produces a teams formation with the minimum possible imbalance value.
The first line of input contains an integer N (1 ≤ N ≤ 50) representing the number of teams.
The second line contains 2N space-separated integers; each representing the grade of one student.
Print the 2N integers, such that if every two consecutive students formed a team, the imbalance value would be the minimum possible.
If there is more than one possible solution, print any of them.
2
23 36 28 8
8 36 23 28
3
26 48 16 24 9 8
8 48 9 26 16 24
The ACM Student Chapter created a new Facebook group to answer the questions of the students currently taking the Structured Programming course.
Dr. Ibrahim asked the group administrators to answer any question within at most 3 hours. So, if a question is posted at time 08:04:02, one of the admins must post a reply strictly before 11:04:02.
Although Dr. Ibrahim is not a member in the group, he has a spy that sends him everyday a summary of when the questions were asked and when they were answered.
Write a program that allows Dr. Ibrahim to know automatically if all questions were answered within 3 hours or not.
The first line of input contains an integer N (1 ≤ N ≤ 50) representing the number of questions.
Each of the following N lines contains the time at which one of the questions was posted, followed by a space, then the time at which the reply was posted.
The format of the time is: HH:MM:SS (00 ≤ HH ≤ 23), (00 ≤ MM, SS ≤ 59).
It’s guaranteed that the given data is valid (no reply precedes its post) and within one day.
Print “Yes” if all the questions were answered within 3 hours, otherwise print “No”.
3
00:00:00 01:30:25
00:58:33 02:24:45
18:16:42 21:16:41
Yes
3
00:00:00 01:30:25
00:58:33 02:24:45
18:16:42 21:16:42
No
One day, Dr. Ibrahim noticed that some questions were answered after 3 hours and decided to increase the number ACM admins that answer questions on the group.
ACM admins are really good at Structured Programming. It takes any admin exactly 15 minutes to answer any question, but they can’t answer more than one question at the same time. For example, if an admin starts working on a question at time 03:00:00, he will answer at time 03:14:59 and will be free to start working on another question at 03:15:00 or later.
Given the summary of the posts of one day, find the minimum number of admins required to answer all the questions, such that each question is answered within 3 hours.
The first line of input contains an integer N (1 ≤ N ≤ 100,000) representing the number of questions.
Each of the following N lines contains the time at which one of the questions was posted.
The format of the time is: HH:MM:SS (00 ≤ HH ≤ 23), (00 ≤ MM, SS ≤ 59). Note that all of the given data is within one day, but not necessarily sorted. All questions must be answered within 3 hours even if it was posted at 23:59:59 (in this case, the answer will be in the next day).
Print the minimum number of admins Dr. Ibrahim has to assign so that all the questions are answered within 3 hours.
3
03:22:15
00:42:08
18:49:22
1
Dr. Rawan’s son loves to play computer games. His favorite game includes a snake that moves around a room tryig to reach an exit door. Dr. Rawan thought that this can make a good assignment for her AI class. As a warmup, she asked her students to write a program that checks if a certain sequence of moves will make the snake reach the exit door or not.
You are given the state of the snake on a 16×32 grid and a sequence of moves represented using the following symbols:
< : move left > : move right v : move down ^ : move up
The body of the snake is also represented on the grid using the same symbols, where each symbol represents the direction taken by the snake at that cell. Your task is to check if the snake can reach the exit cell using the given sequence or not.
The following example shows how the snake moves on the grid for the sequence: >^>
E represents the exit cell, and the colon ‘:’ represents the head of the snake. Note that all the body of the snake moves simultaneously.
Each line of the first 16 lines of input contains 32 characters, which represent the state of the snake on the grid.
The following line contains a non-empty string with no more than 256 characters representing the sequence of moves that should be taken by the snake.
It is guaranteed that the given sequence will not cause the snake to go out of the borders of the gird, nor make the snake intersect itself.
The given sequence will also not cause the snake to reach the exit cell and continue moving over it.
Print "Yes" if the snake reaches the exit cell using the given sequence and print "No" otherwise.
................................
................................
................................
................................
................................
................................
..........>v.:<<<...............
........E..v....^...............
...........v....^...............
...........>>>>>^...............
................................
................................
................................
................................
................................
................................
<<v<<<
Yes
Dr. Rawan’s students found the warmup exercise to be very easy and asked for a more challenging task. Therefore, Dr. Rawan asked them to write a program that will help the snake reach the exit door.
Given the state of a snake on the 16x32 grid as described before, your task is to find any sequence of moves (using the symbols >, <, ^ and v) that will allow the snake to reach the exit cell. The sequence of moves should not make the snake intersect itself.
Each line of the first 16 lines of input contains 32 characters, which represent the state of the snake on the grid.
The number of dots that are not reachable from the borders doesn't exceed 32, and all characters on the border are dots.
The length of the snake doesn't exceed 75 cells.
Print a sequence of moves that will make the snake reach the exit cell without intersecting itself. The sequence should contain at most 1024 characters.
If no sequence exists, print '—' (3 dashes) without the single quotes.
................................
................................
................................
................................
................................
................................
..........>v.:<<<...............
........E..v....^...............
...........v....^...............
...........>>>>>^...............
................................
................................
................................
................................
................................
................................
^<<<<vv<