codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

268B.md (1830B)


      1 Source: https://codeforces.com/problemset/problem/268/B
      2 
      3 B. Buttons
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 Manao is trying to open a rather challenging lock. The lock has *n* buttons on it and to open it, you should press the buttons in a certain order to open the lock. When you push some button, it either stays pressed into the lock (that means that you've guessed correctly and pushed the button that goes next in the sequence), or all pressed buttons return to the initial position. When all buttons are pressed into the lock at once, the lock opens.
     22 
     23 Consider an example with three buttons. Let's say that the opening sequence is: {2, 3, 1}. If you first press buttons 1 or 3, the buttons unpress immediately. If you first press button 2, it stays pressed. If you press 1 after 2, all buttons unpress. If you press 3 after 2, buttons 3 and 2 stay pressed. As soon as you've got two pressed buttons, you only need to press button 1 to open the lock.
     24 
     25 Manao doesn't know the opening sequence. But he is really smart and he is going to act in the optimal way. Calculate the number of times he's got to push a button in order to open the lock in the worst-case scenario.
     26 
     27 Input
     28 
     29 A single line contains integer *n* (1 ≤ *n* ≤ 2000) — the number of buttons the lock has.
     30 
     31 Output
     32 
     33 In a single line print the number of times Manao has to push a button in the worst-case scenario.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 2
     41 ```
     42 
     43 Output
     44 
     45 ```
     46 3
     47 ```
     48 
     49 Input
     50 
     51 ```
     52 3
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 7
     59 ```
     60 
     61 Note
     62 
     63 Consider the first test sample. Manao can fail his first push and push the wrong button. In this case he will already be able to guess the right one with his second push. And his third push will push the second right button. Thus, in the worst-case scenario he will only need 3 pushes.