## Problem setter’s handbook - Example of the problem

In this section we present more complicated example with full details to give you better overall look at abilities of our services. It is still an elementary example but it will tell you much more about the specific of online judging.

#### Important

In the following example we created test cases according to the advice in the good test cases design appendix.

The problem is to count the sum of numbers from `1`

to given `n`

i.e.
`1 + 2 + 3 + ... + n`

, we call it the `Initial sum`

problem. We are going to
prepare it to handle with multiple input instances in a single test case by
proper input / output specification design.

Look at the following problem description:

**Example - The Initial Sum**

For a positive integer

ncalculate the value of the sum of all positive integers that are not greater thanni.e.1 + 2 + 3 + ... + n. For example whenn = 5then the correct answer is15.## Input

In the first line there will be the number

1≤ t ≤ 10000000which is the number of instances for your problem. In each of the nexttlines there will be one numbern** for which you should calculate the described initial sum.## Output

For each

nprint the calculated initial sum. Separate answers with new line character.## Examples

`Input 4 1 2 3 4 Output 1 3 6 10`

#### Note

Input specification allows us to construct rich test cases which are able to distinguish between faster and slower solutions.

Referring to the solution to the `Initial sum`

problem take into account that
the possible input data can be too big for the standard `int`

type thus we will
use the `long long`

type. Before we set test cases let us present two distinct
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;
}
```

#### Complexity note

The first solution refers directly to the definition of the problem i.e. the
function `initsum`

iterates from `1`

to `n`

to calculate desired value. The
calculation requires `n`

operations of addition to obtain the result.

It is basic school knowledge that there exists the compact formula for that problem and we use it in the second implementation:

```
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 problem but if we want to distinguish the algorithms we can design test cases that only the second solution can pass.

#### Note

It highly depends on the computational power of the machine that runs test cases. We present test cases that are valid for the computer of this text's author.

Our suggestion is to design one test case which is easy to pass for both algorithms to give information that the solution is correct and the second test case that is possible to pass only for the second algorithm. It can give an information to the user, that his solution is correct but too slow.

#### Tip

It is a good practice to design first test case to be the same as input / output example from the problem description. In this way, the user can verify his input and output management.

The user submitting solution similar to the first one will get information about test cases and will be able to see that his program passes first test case and exceed time limit in the second test case.

We cannot put all input and output data here because of its size thus we write it in shortened manner:

**Example**

Input Output Test case 1 1000

1

2

...

1000

10000001

3

...

500500

500000500000Test case 2 999000

1001

1002

...

1000000501501

502503

...

500000500000

Computational power of current machines is enough to finish first test case
instantly. Both presented algorithms finished computations with time below
`0.01s`

. However it is a good test case for a correctness verification only.

First `1000`

positive integers give us the assurance that solution is
mathematically correct. We have also added single test with big number i.e.
`n = 1000000`

to make sure that user's solution bases on `long long`

type. On
the other hand the second test case is rich enough to make the first algorithm
to exceed even `5s`

time limit.

The second algorithm works fast enough to pass that test case in time below
`0.1s`

. There is a huge gap between `0.1s`

and `5s`

thus we can easily choose
safe value as our time limit, for example `1s`

.

#### Note

For extended information about distinguishing the efficiency of algorithms see testing time complexity appendix.

We still haven't chosen judges for test cases and master judge for the problem.
We don't have floating point numbers in our output file specification thus we
rather decide to choose `Ignoring extra whitespaces`

judge for both test cases.
It leaves users with possibility of small formating errors without risk of
unwanted rejections of theirs solutions. For example it is possible to replace
new line 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 better score. The `Score is % of correctly solved sets`

master judge is perfect for that purpose. Submitting the first solution
achieves the result of `50%`

while the second solution passes both test cases
and its result is `100%`

.

#### Note

Presented scoring method assumed both tests as equally worth `50%`

each.
To achieve different distribution of scores you need to modify the master judge
and pick the scoring of test cases arbitrary. We present
the example in the
section writing master judges.

To sum up we present full problem specification:

## The Initial Sum

## Description

## The task

For a positive integer

ncalculate the value of the sum of all positive integers that are not greater thanni.e.1 + 2 + 3 + ... + n. For example whenn = 5then the correct answer is15.## Input specification

In the first line there will be the number

1 ≤ t ≤ 10000000which is the number of instances for your problem. In each of the nexttlines there will be one numbernfor which you should calculate the described initial sum.## Output specification

For each

nprint the calculated initial sum. Separate answers with new line character.## Examples

`Input 4 1 2 3 4 Output 1 3 6 10`

## Test cases

Input file Ouput file Judge Time limit Test case 1 1000

1

2

...

1000

10000001

3

...

500500

500000500000Ignoring extra whitespaces 1s Test case 2 999000

1001

1002

...

1000000501501

502503

...

500000500000Ignoring extra whitespaces 1s ## Master judge

Score is % of correctly solved sets