Mixed Implementation Problems

Every week so far handed you a tool, then problems that obviously needed it. A contest doesn't: a problem describes a situation and asks for an answer, and nobody writes "this is a sorting problem" at the top. Deciding which tools the situation needs — and joining them into one program — is what this week is about. The tools themselves you already have: input and output, conditions, loops, arrays, strings, functions, sorting, stacks, queues, sets and maps.

A long problem is rarely hard because one step is hard. It is hard because there are many steps, and one misread word sends all of them the wrong way. So work in a fixed order:

Read twice, then restate

The first reading is for the story; the second is for the details. On the second pass, find four things: what exactly is given, what exactly must be printed, what the limits are, and what the statement says about unusual cases — "if there is no such pair, print −1", "if several answers exist, print the smallest". Notice, too, whether the input holds several test cases: then every total and counter starts again from scratch for each one.

Then say the task in one sentence, without the story. "Bekzod runs a market stall and writes down every coin he earns…" becomes "print the sum of n numbers". If you can't say it in one sentence, you haven't understood it yet: read again, and work through the sample by hand until you can.

Check the limits

The limits under a statement are not decoration. Two of them decide your program before you write a line of it.

They choose the types. An int holds values up to 2 147 483 647, about 2.1 · 10⁹. Put the largest allowed values into your formula: 10⁵ numbers of up to 10⁹ each add up to 10¹⁴. If the result can pass 2 · 10⁹, use long long, which goes up to about 9.2 · 10¹⁸.

They choose the speed. A computer does roughly 10⁸ simple steps per second. Count the steps of your idea for the largest n: