codeforces-scrape

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

848A.md (2105B)


      1 Source: https://codeforces.com/problemset/problem/848/A
      2 
      3 A. From Y to Y
      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 From beginning till end, this message has been waiting to be conveyed.
     22 
     23 For a given unordered multiset of *n* lowercase English letters ("multi" means that a letter may appear more than once), we treat all letters as strings of length 1, and repeat the following operation *n* - 1 times:
     24 
     25 * Remove any two elements *s* and *t* from the set, and add their concatenation *s* + *t* to the set.
     26 
     27 The cost of such operation is defined to be ![](https://espresso.codeforces.com/d6245ecc5766ad90cc96811959cd01bbfd6e18df.png), where *f*(*s*, *c*) denotes the number of times character *c* appears in string *s*.
     28 
     29 Given a non-negative integer *k*, construct any valid non-empty set of no more than 100 000 letters, such that the minimum accumulative cost of the whole process is exactly *k*. It can be shown that a solution always exists.
     30 
     31 Input
     32 
     33 The first and only line of input contains a non-negative integer *k* (0 ≤ *k* ≤ 100 000) — the required minimum cost.
     34 
     35 Output
     36 
     37 Output a non-empty string of no more than 100 000 lowercase English letters — any multiset satisfying the requirements, concatenated to be a string.
     38 
     39 Note that the printed string doesn't need to be the final concatenated string. It only needs to represent an unordered multiset of letters.
     40 
     41 Examples
     42 
     43 Input
     44 
     45 ```
     46 12
     47 ```
     48 
     49 Output
     50 
     51 ```
     52 abababab
     53 ```
     54 
     55 Input
     56 
     57 ```
     58 3
     59 ```
     60 
     61 Output
     62 
     63 ```
     64 codeforces
     65 ```
     66 
     67 Note
     68 
     69 For the multiset {'a', 'b', 'a', 'b', 'a', 'b', 'a', 'b'}, one of the ways to complete the process is as follows:
     70 
     71 * {"ab", "a", "b", "a", "b", "a", "b"}, with a cost of 0;
     72 * {"aba", "b", "a", "b", "a", "b"}, with a cost of 1;
     73 * {"abab", "a", "b", "a", "b"}, with a cost of 1;
     74 * {"abab", "ab", "a", "b"}, with a cost of 0;
     75 * {"abab", "aba", "b"}, with a cost of 1;
     76 * {"abab", "abab"}, with a cost of 1;
     77 * {"abababab"}, with a cost of 8.
     78 
     79 The total cost is 12, and it can be proved to be the minimum cost of the process.