codeforces-scrape

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

622A.md (1312B)


      1 Source: https://codeforces.com/problemset/problem/622/A
      2 
      3 A. Infinite Sequence
      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 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Consider the infinite sequence of integers: 1, 1, 2, 1, 2, 3, 1, 2, 3, 4, 1, 2, 3, 4, 5.... The sequence is built in the following way: at first the number 1 is written out, then the numbers from 1 to 2, then the numbers from 1 to 3, then the numbers from 1 to 4 and so on. Note that the sequence contains numbers, not digits. For example number 10 first appears in the sequence in position 55 (the elements are numerated from one).
     22 
     23 Find the number on the *n*-th position of the sequence.
     24 
     25 Input
     26 
     27 The only line contains integer *n* (1 ≤ *n* ≤ 1014) — the position of the number to find.
     28 
     29 Note that the given number is too large, so you should use 64-bit integer type to store it. In C++ you can use the long long integer type and in Java you can use long integer type.
     30 
     31 Output
     32 
     33 Print the element in the *n*-th position of the sequence (the elements are numerated from one).
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 3
     41 ```
     42 
     43 Output
     44 
     45 ```
     46 2
     47 ```
     48 
     49 Input
     50 
     51 ```
     52 5
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 2
     59 ```
     60 
     61 Input
     62 
     63 ```
     64 10
     65 ```
     66 
     67 Output
     68 
     69 ```
     70 4
     71 ```
     72 
     73 Input
     74 
     75 ```
     76 55
     77 ```
     78 
     79 Output
     80 
     81 ```
     82 10
     83 ```
     84 
     85 Input
     86 
     87 ```
     88 56
     89 ```
     90 
     91 Output
     92 
     93 ```
     94 1
     95 ```