# 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:

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:

Test case Input file Output file 1

(example data)4

1

2

3

41

3

6

1021000

1

2

...

10001

3

...

5005003999000

1001

1002

...

1000000501501

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:

## 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

41

3

6

10Ignoring extra whitespaces 1s 21000

1

2

...

10001

3

...

500500Ignoring extra whitespaces 1s 3999000

1001

1002

...

1000000501501

502503

...

500000500000Ignoring extra whitespaces 1s ## Master judge

Score is % of correctly solved sets