| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 11805 | EECS_I2P17_FINAL_A |
|
| 11806 | EECS_I2P17_FINAL_B |
|
| 11807 | EECS_I2P17_FINAL_C |
|
| 11808 | EECS_I2P17_FINAL_D |
|
| 11813 | EECS_I2P17_FINAL_E |
|
| 11814 | EECS_I2P17_FINAL_BONUS |
|
Description
Given a sequence of positive integers, divide them into partitions (sequentially and greedily from left to right) so that the sum of the integers in each partition is as large as possible but no larger than 10.
All integers in the sequence are greater than 0 and no greater than 10.
[Example]
For example, if the input is
2 8 3 6 5 1 2 1 9 8 7 4 5
then the partitions are
[2, 8], [3, 6], [5, 1, 2, 1], [9], [8], [7], [4, 5]
The output is the number of partitions, which is 7 for this example.
Input
The first line of the input is an integer N indicating the length of the sequence. (0 < N < 1000)
The second line contains the sequence of N integers. All integers are larger than 0 and no greater than 10.
Output
The output is the number of partitions. There is NO newline character at the end of line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
The input contains N strings (0 < N < 100). Each string consists of at most 9 lowercase letters.
1. Find the longest nondecreasing substring(s) of each string. (There might be more than one longest nondecreasing substring.)
2. Count the number of occurrences (frequency) of each distinct substring.
3. Sort the substrings according to their frequencies (high to low). If two substrings have the same frequency, sort them in lexicographical order (alphabetical order).
4. Use the ranking of each substring as its score. E.g., the first one gets 1 point, the second gets 2 points, and so on.
5. Use the scores of substrings to re-evaluate the original input string and print the total score of each input string.
[Example]
For example, the input may be
7
xxaccb
xabcud
yyxacc
efgacc
tsefgab
aca
rqabcud
The longest nondecreasing substrings are
acc
abcu
acc
efg acc
efg
ac
abcu
The frequencies are
abcu 2
ac 1
acc 3
efg 2
The sorted order should be
acc 3
abcu 2
efg 2
ac 1
Their scores are
acc 1
abcu 2
efg 3
ac 4
The re-evaluation results are
xxaccb 1 (because acc gets 1 point)
xabcud 2 (because abcu gets 2 points)
yyxacc 1 (because acc gets 1 point)
efgacc 4 (because efg gets 3 points and acc gets 1 point)
tsefgab 3 (because efg gets 3 points)
aca 4 (because ac gets 4 points)
rqabcud 2 (because abcu gets 2 points)
Another example: If the input is
2
fgcdab
fgdbca
The longest nondecreasing substrings are
fg cd ab
fg bc
The frequencies are
fg 2
cd 1
ab 1
bc 1
The sorted order should be
fg 2
ab 1
bc 1
cd 1
Their scores are
fg 1
ab 2
bc 3
cd 4
The re-evaluation results are
fgcdab 7 (fg gets 1 point, cd gets 4 points, and ab gets 2 points)
fgdbca 4 (fg gets 1 point and bc gets 3 points)
Input
The first line of input is an integer N indicating the number of input strings. (0 < N < 100)
The next N lines are the input strings. Each string consists of at most 9 lowercase letters.
Output
The output contains N lines of strings and their scores. The strings are listed as their original input order.
Each line contains a string and its score.
Each line has a newline character at the end. (Note that the last line also needs to be ended with a newline character.)
Sample Input Download
Sample Output Download
Tags
Discuss
Description
From I2P(I)2017_Chen_Final_Practice
Given an undirected graph G, you have to check whether it is a bipartite graph (二分圖) or not.
Input
The first line contains an integer T, representing the number of test cases.
For each test case:
The first line contains two integers n, m, representing the number of vertices and the number of edges.
The next m lines contain two integers u, v, representing that there is an undirected edge between vertex u and vertex v.
It is guaranteed that:
- 1 ≤ T ≤ 10
- 2 ≤ n ≤ 1000
- n-1 ≤ m ≤ n2
- 1 ≤ u, v ≤ 1000
- NO multiple edge
- NO self cycle
- the graph is connected
Output
For each graph G, if G is a bipartite graph, please output "Yes", otherwise please output "No".
Sample Input Download
Sample Output Download
Tags
Discuss
Description
From I2P CS 2017 Fall Chen Final Exam
At the end of the semester, Roy Feng is bombarded (轟炸) by all kinds of final exams, reports, and projects. He regrets that he didn’t make the course withdrawal at the middle of the semester.
According to the rule, without any underload application, freshmen should take at least 16 credits (學分) each semester after course withdrawal. Given all the courses Roy took at the begin of the semester, your task is to help Roy to figure out how many ways he can withdraw his courses to satisfy the above rule. Each way should withdraw at least one of them.
Input
The input consists of a single test case in the following format.
n
s1 c1
s2 c2
...
...
sn cn
The first line contains one integer n satisfying 1 ≤ n ≤ 20. n denotes the total number of courses Roy took at the begin of the semester. The next n lines show the information of courses. The i-th line of them contains a string si whose length is between 1 and 100, inclusive, and an integer ci satisfying 0 ≤ ci ≤ 4, meaning that the i-th course is taken by Roy with the name si and the credit ci.
Output
Print the number of ways that Roy can withdraw his courses to meet the above condition.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
From I2P CS 2017 Fall Chen Final Exam
Now HT gives a list of students and their score, your task is to sort their score in decreasing order.
If there are many students with the same score, you need to maintain their relative order in the original list.
That is, if whenever there are two students A and B with the same score and with A appearing before B in the original list, A will appear before B in the sorted list.
Input
The input consists of a single test case in the following format.
n
s1 c1
s2 c2
...
...
sn cn
The first line contains one integer n satisfying 1 ≤ n ≤ 1000. n denotes the total number students on the given list. The next n lines show the information of students. The i-th line of them contains a string si whose length is between 1 and 50, inclusive, and an integer ci satisfying 0 ≤ ci ≤ 100, which means that the i-th student has the name si and his/her score is ci.
Output
Print the list of students' names after sorting, each name with a line.
Sample Input Download
Sample Output Download
Tags
Discuss
Description
Given an M-by-N integer matrix, compute the maximum column sum.
[Example]
For example, if the input is a 3-by-4 matrix containing
3 2 4 5
2 8 3 7
3 1 5 6
The maximum column sum is 18 (=5+7+6).
Input
The first line of the input contains two integers M and N indicating the size of the integer matrix (M for row and N for column, 0 < M, N< 10).
Next M lines list the elements of the matrix row by row. All elements are integers.
Output
The output contains an integer indicating the maximum column sum. There is NO newline character at the end of line.