Problem setter's handbook
Example of a programming problem


In this chapter, we present a more advanced example with full details to give you a better overall impression of Sphere Engine Problems service capabilities. It is still an elementary example but illustrates much more about the specifics of Online Judge systems.

Note

In the following example, we create test cases according to the advice given in the good test cases design section of the Appendix.

The problem is to count the sum of numbers from 1 to given n i.e., 1 + 2 + 3 + ... + n, which we call the Initial sum problem. We are going to prepare it to deal with multiple pairs of input/output data in a single test case by proper input/output specification design.

Consider the following problem description:

The Initial Sum - description

For a positive integer n calculate the value of the sum of all positive integers that are not greater than n i.e. 1 + 2 + 3 + ... + n. For instance, when n = 5 the correct answer is 15.

Input specification

In the first line is the number 1 ≤ T ≤ 10000000 which is the number of instances for your problem. In each of the next T lines, there will be one number n for which you should calculate the defined initial sum.

Output specification

For each n print the calculated initial sum. Separate answers with the newline character.

Examples
Input
4
1
2
3
4

Output
1
3
6
10
Tip

Input specification allows us to construct rich test cases which are able to distinguish between faster and slower solutions. This topic is discussed in the time complexity section of the Appendix.

Before we design test cases let us present two different solutions to the problem:

long long initsum(long long n)
{
    int i;
    long long sum = 0;
    for (i=1; i <= n; i++)
    {
        sum += i;
    }
    return sum;
}

int main()
{
    int t;
    long long n;
    scanf("%d", &t);
    while (t > 0)
    {
        scanf("%lld", &n);
        printf("%lld\n", initsum(n));
        t--;
    }
    return 0;
}

The first solution is implemented to calculate the sum according to the definition of the problem, i.e. the function initsum iterates from 1 to n to calculate the desired value. The calculation requires n operations of addition to obtain the result.

We can apply a different approach to obtain the same results. There is a compact formula that allows for fast calculations:

long long initsum(long long n)
{
    return n*(n+1)/2;
}

int main()
{
    int t;
    long long n;
    scanf("%d", &t);
    while (t > 0)
    {
        scanf("%lld", &n);
        printf("%lld\n", initsum(n));
        t--;
    }
    return 0;
}

Both programs are correct answers to the Initial Sum problem but the second one requires considerably fewer operations to calculate the result. We can design test cases to distinguish between these solutions, i.e. we can create a test case that only the second solution is able to pass.

Important

The computation speed depends on the machine that runs the user's program. Test cases dedicated to testing efficiency should be designed to be compatible with machines that execute programs.

Our suggestion is to design one test case for both algorithms that is easy to pass, to provide information that the solution is correct. We also suggest designing a second test case that only the second algorithm can pass.

It is also good practice to design a single test case to be the same as an example from the problem description. In this way, the user can verify that they handle input and output data correctly.

We cannot put all input and output data here because of its large size. We therefore share a shorter version:

The Initial Sum - test cases
Test case Input file Output file
1
(example data)
4
1
2
3
4
1
3
6
10
2 1000
1
2
...
1000
1
3
...
500500
3 999000
1001
1002
...
1000000
501501
502503
...
500000500000

The user submitting a solution similar to the first example receives information that it successfully passes two first test cases (the low difficulty and example test cases). However, it doesn't pass the third test case because of the exceeded time limit.

The computational power of modern era computers is enough to finish the first test case instantly. Both presented algorithms finish computations with a time below 0.01s. However, it is a good test case to verify correctness concerning returned values.

Verification that covers the first 1,000 positive integers provides assurance that the solution is mathematically correct. On the other hand, the third test case is rich enough to make the first example solution exceed even 5s time limit.

The second algorithm works fast enough to pass the third test case in a time below 0.1s. There is a huge gap between 0.1s and 5s so we can easily choose a safe value for the time limit, for example, 1s.

Note

For extended information about distinguishing the efficiency of algorithms please refer to the time complexity section of the Appendix.

We still haven't chosen judges for test cases and a master judge for the problem. The Ignore extra white spaces test case judge is a good choice for defined test cases. It leaves users with the possibility of small formatting errors and without the risk of unwanted rejections of their solutions. For instance, it is possible to replace newline characters with spaces in output formatting and still pass the test case.

We assume that we want to accept every correct solution but distinguish the better ones and give them a superior score. The master judge called Score is the % of correctly solved sets is a suitable choice for this purpose. Submitting the first example solution returns a result of 66% (i.e. the first and the second test cases are solved correctly but the third isn't solved in time) while the second presented solution passes all three test cases to obtain a final score equal to 100%.

Note

The presented scoring method assumes all three tests as equally worth 33% each. To achieve a different distribution of scores you need to modify the master judge and pick the scoring of test cases arbitrarily. We present such an example in the custom master judges section of the Custom Judges chapter.

To sum up we present the full problem specification:

The Initial Sum - complete example

Description

The task

For a positive integer n calculate the value of the sum of all positive integers that are not greater than n i.e. 1 + 2 + 3 + ... + n. For instance, when n = 5, the correct answer is 15.

Input specification

In the first line is the number 1 ≤ T ≤ 10000000, which is the number of instances for our problem. In each of the next T lines, there will be one number n for which we should calculate the defined initial sum.

Output specification

For each n print the calculated initial sum. Separate answers with the newline character.

Examples
Input
4
1
2
3
4

Output
1
3
6
10

Test cases

Test case Input file Output file Judge Time limit
1
(example data)
4
1
2
3
4
1
3
6
10
Ignoring extra whitespaces 1s
2 1000
1
2
...
1000
1
3
...
500500
Ignoring extra whitespaces 1s
3 999000
1001
1002
...
1000000
501501
502503
...
500000500000
Ignoring extra whitespaces 1s

Master judge

Score is % of correctly solved sets

Previous chapter
Next chapter