Description

Assume that we need to send a stream of data items as a series of packets. The size limit of a packet is M, and each item i has a size s_i satisfying s_i < M, for i = 1, 2, ....N
For each item i, we can append it to the current packet as long as the total size of the items in the packet does not exceed the limit; otherwise, we put the item into a new packet. 
Our task is to simulate the process and decide how many packets are needed.

Case1: 0<M<=1*10^2, 0<=N<=20
Case2: 0<M<=2*10^4, 0<=N<=100
Case3: 0<M<=1*10^5, 0<=N<=10000
Case4: 0<M<=2*10^9, 0<=N<=10000

Input

The input consists of several test cases.
Each test case starts with an integer M indicating the size limit of a packet.
The subsequent positive integers enumerate the sizes of the items, and a number 0 denotes the end of the current stream.

Output

The output contains several lines.
Each line prints the number of packets needed to send the stream for the corresponding test case.
Each line is ended with a newline character.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given a simple, undirected weighted graph G = (V, E, W), output the weight of its minimum spanning tree.

Input

The input includes multiple test cases. The first of the input is an integer T (T <= 1000) specifying the number of test cases. For each case, the first line contains two integers: the number of the node N and the number of the edges M. In the following M lines, each line contains three integers (s_i, e_i, c_i), 1 <= s_i, e_i <= N, 1 <= c_i <= 100, representing the indices of end vertices of an edge and the weight of the edge.

Case 1: 2 <= N <= 10², 1 <= M <= 10³
Case 2: 2 <= N <= 10³, 1 <= M <= 10³
Case 3: 2 <= N <= 10³, 1 <= M <= 10⁴
Case 4: 2 <= N <= 10³, 1 <= M <= 10⁵

Output

For each case, output a single line that indicates the weight of the minimum spanning tree of the graph.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given the grades of N people. Please output the sorted result. (Increasing order)

Input

The input includes multiple test cases.

In each test case, the first line contains one integer N. The following N lines specify the name Si and the grade Gi.

1 <= |Si| <= 10
0 <= Gi <= 100 (Gi is an integer.)

Test Case 1 : 1 <= N <= 10²
Test Case 2 : 1 <= N <= 10⁴
Test Case 3 : 1 <= N <= 10⁵
Test Case 4 : 1 <= N <= 10⁶

Output

For every test case, output the result in N lines. Every line contains the name and the grade. If more people’s grades are same, output by input order. (That means it uses stable sort.)

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Consider an input string of  numeric characters, e.g.,
      1234567895793

Your task is to add thousands separators so that the output would look like
      1,234,567,895,793

If the input string contains non-numeric characters, e.g.,
     123q5
then you just need to print
     NaN

Input

The first line is an integer N(<=1000) indicating the number of test cases.
Each of the next N lines is a string that needs to be printed with thousands separators.

case 1 : 0 < len(string) <= 10, all characters are number
case 2 : 0 < len(string) <= 100, all characters are number
case 3 : 0 < len(string) <= 100000
case 4 : 0 < len(string) <= 100000

Output

The output contains N lines showing  the results of the N test cases.
Each line is ended with a newline character.
If the test case is a valid numeric string, then print that number with thousands separators; otherwise,  print NaN.

Sample Input  Download

Sample Output  Download

Tags

Discuss

Description

Given several fractions, compute their sum and express the answer in the simplest fraction form.

Input

There are many test cases in one subtask.

The first line of each test case contains an integer t, which indicates the number of fractions in the input. Each of the following t lines contains two integers a and b, which represent the numerator and the denominator of a fraction.

subtask 1 : t=2. 1<=a,b<=10.
subtask 2 : t<=5. 1<=a,b<=10.
subtask 3 : t<=5. 1<=a,b<=50.
subtask 4 : t<=10. 1<=a,b<=100.

Output

Each test case outputs one line.

The output is the sum reduced to the simplest fraction form. You need to print a '/' between the numerator and the denominator.

Sample Input  Download

Sample Output  Download

Tags

Discuss