Description

Problem A - Homework

Roy Feng (馮謙) is a freshman at the Department of Computer Science, NTHU. This semester he takes the course "introduction to Programming." The professor (naughty HT) may give multiple assignments after a class, and each assignment may have a different deadline.

To become a top-level programmer, every day Roy completes at most one assignment as follows. Let S be the set of all unfinished assignments whose deadline has not yet passed. If S is empty, Roy will go out to find his “missing” girlfriend. Otherwise, his will arbitrarily pick an assignment A among S and complete it. With such a strategy, Roy might not be able to complete all assignments.

Given the schedule of assignments, your task is to compute the minimum and the maximum numbers of assignments Roy will be able to complete. 

Input

The input consists of a single test case in the following format.

n

s₁ t₁

s₂ t₂

...

...

s_n t_n

The first line contains an integer n satisfying 1 ≤ n ≤ 100. n denotes the total number of assignments of the course. The next n lines show the schedule of assignments. The i-th line of them contains two integers s_i and t_i satisfying 1 ≤ s_i ≤ t_i ≤ 100, which mean that the i-th assignment is given on the s_i -th day of the semester, and its deadline is the end of the t_i -th day.

Output

Print the minimum number and the maximum number of assignments Roy will be able to complete.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Problem B - Christmas

Last Christmas, Roy Feng found out that he didn’t need to complete any assignment. He wanted to give some special one his heart, but nobody wanted to invite him to join a Christmas party. Without any choice, he decided to go to the movies by himself.

When he was buying the ticket, he noticed that there was a row of seats remained unsold. In order to take revenge on those lovey-dovey couples, he decided to buy some of the seats of that empty row which satisfying the following strategy. First, he didn’t want anybody to sit beside him. Second, he didn’t want to leave any two adjacent seats so that those couples could sit together.

Given the number of seats in that row, your task is to help Roy to compute the minimum number of seats he needs to buy.

By the way, if you are also alone last Christmas, maybe you can invite Roy to go to the movies next time!

Input

The input consists of multiple test cases. The first line of the input contains one integer T, which is the number of the test cases (1 ≤ T ≤ 100). Each of the following n lines contains a test case formatted as follows.

n

n (1≤ n ≤ 100) is the number of empty seats in the row.

Output

For each test case, print the minimum number of the seats Roy needs to buy to satisfy the above conditions.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Problem C - Withdrawal

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

s₁ c₁

s₂ c₂

...

...

s_n c_n

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 s_i whose length is between 1 and 100, inclusive, and an integer c_i satisfying 0 ≤ c_i ≤ 4, meaning that the i-th course is taken by Roy with the name s_i and the credit c_i.

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

Problem D - Grade

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

s₁ c₁

s₂ c₂

...

...

s_n c_n

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 s_i whose length is between 1 and 50, inclusive, and an integer c_i satisfying 0 ≤ c_i ≤ 100, which means that the i-th student has the name s_i and his/her score is c_i.

Output

Print the list of students' names after sorting, each name with a line.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Problem E - Rotation

Given two strings s and t, your task is to figure out whether there exists s’ equals to t, where we denote s’ as a left rotation or a right rotation of s.

For example, if s = “abcd”, then s’ can either equals to “abcd”, “bcda”, ”cdab” or ”dabc”.

Input

The input consists of multiple test cases. The first line of the input contains one integer T, which is the number of the test cases (1 ≤ T ≤ 100). Each of the following n lines contains a test case formatted as follows.

s t

s and t are the two string mentioned above. The length of s and t are the same, and both of them are between 1 and 100, inclusive.

Output

For each test case, print "Yes" if there exists s' equals to t, otherwise print "No".

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Problem F - 2018

As you all know, Frank Lin likes to go mountain climbing. Unlike lonely Roy who celebrates New Year’s Eve at the dorm himself, Frank decides to watch the smoky sunrise in the mountains at the beginning of 2018. Before the journey, Frank plans n different routes to climb up the mountain. Given the n different routes, your task is to find out how many different locations these routes will end up with.

You can consider the whole journey and the location as lines and points on the coordinate plane system. Frank will start his journey at point (0, 0). The route representation contains only four characters ‘N’, ‘S’, ‘E’, and ‘W’ which stands for that Frank moves up, down, right, or left one unit parallel to the y-axis (‘N’ and ‘S’) or the x-axis (‘E’ and ‘W’) respectively.

source : http://www.ysnp.gov.tw

Input

The input consists of a single test case in the following format.

n

s₁

s₂

...

...

s_n

The first line contains an integer n satisfying 1 ≤ n ≤ 2000. n denotes the total number of different routes to climb up the mountains. The next n lines show the directions of routes. The i-th line of them contains a string s_i with only four characters ‘N’, ‘S’, ‘E’, and ‘W' whose length is between 1 and 100, inclusive, which is the information of the i-th route.

Output

Print the number of locations these routes will end up with. 

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

To any distressed people:

        My name is Arc. I am a “Time Traveler”. I know that many people are having trouble in solving HT Chen’s final exam. Thus, I traveled back to yesterday and overheard some hints in TAs’ chat. Moreover, I secretly hack NTHU OJ System and submit these hints to you. Since all TAs aren’t as smart as me, they can't delete this letter.

PA - Homework

Difficulty: ★★★★★

        I think it is the most difficult question in this exam, so I can’t remember how to solve it. However, I heard that TAs said the two of four cases of (n, min) are (5, 2) (sample) and (100, 73). If you can calculate MAX appropriately, then you can pass these two cases with some techniques.

PB - Christmas

Difficulty: ★☆☆☆☆

        I'm only informed that this question can be easily solved by specific mathematical rules.

PC - Withdrawal

Difficulty: ★★★★☆

        TAs solved it with for-loops and many lines within. However, I think I can solve it by recursion with several lines. If you can solve it by recursion, you must be better than all TAs.

PD - Grade

Difficulty: ☆☆☆☆☆

       In TAs’ chat, they didn’t say anything about this question.

PE - Rotation

Difficulty: ★★★☆☆

        I think it requires no special skill to solve it. You need to shift length of string times to judge if it satisfy the condition. Just do it!

PF - 2018 (Bonus)

Difficulty: ? ? ? ? ?

        What?! I didn’t hear anything about the bonus question yesterday. Maybe it appeared in this morning…

        I heard another important hint from TAs. It is that except for bonus question, the first case of each question is sample input! Anyway, hope that this letter can help you pass the exam!

Sincerely,

Arc

Input

Output

Sample Input  Download

Sample Output  Download

Tags

Discuss