codeforces-scrape

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

1070K.md (2169B)


      1 Source: https://codeforces.com/problemset/problem/1070/K
      2 
      3 K. Video Posts
      4 
      5 time limit per test
      6 
      7 3 seconds
      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 Polycarp took $n$ videos, the duration of the $i$-th video is $a_i$ seconds. The videos are listed in the chronological order, i.e. the $1$-st video is the earliest, the $2$-nd video is the next, ..., the $n$-th video is the last.
     22 
     23 Now Polycarp wants to publish exactly $k$ ($1 \le k \le n$) posts in Instabram. Each video should be a part of a single post. The posts should preserve the chronological order, it means that the first post should contain one or more of the earliest videos, the second post should contain a block (one or more videos) going next and so on. In other words, if the number of videos in the $j$-th post is $s_j$ then:
     24 
     25 * $s_1+s_2+\dots+s_k=n$ ($s_i \gt 0$),
     26 * the first post contains the videos: $1, 2, \dots, s_1$;
     27 * the second post contains the videos: $s_1+1, s_1+2, \dots, s_1+s_2$;
     28 * the third post contains the videos: $s_1+s_2+1, s_1+s_2+2, \dots, s_1+s_2+s_3$;
     29 * ...
     30 * the $k$-th post contains videos: $n-s_k+1,n-s_k+2,\dots,n$.
     31 
     32 Polycarp is a perfectionist, he wants the total duration of videos in each post to be the same.
     33 
     34 Help Polycarp to find such positive integer values $s_1, s_2, \dots, s_k$ that satisfy all the conditions above.
     35 
     36 Input
     37 
     38 The first line contains two integers $n$ and $k$ ($1 \le k \le n \le 10^5$). The next line contains $n$ positive integer numbers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^4$), where $a_i$ is the duration of the $i$-th video.
     39 
     40 Output
     41 
     42 If solution exists, print "Yes" in the first line. Print $k$ positive integers $s_1, s_2, \dots, s_k$ ($s_1+s_2+\dots+s_k=n$) in the second line. The total duration of videos in each post should be the same. It can be easily proven that the answer is unique (if it exists).
     43 
     44 If there is no solution, print a single line "No".
     45 
     46 Examples
     47 
     48 Input
     49 
     50 ```
     51 6 3  
     52 3 3 1 4 1 6
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 Yes  
     59 2 3 1
     60 ```
     61 
     62 Input
     63 
     64 ```
     65 3 3  
     66 1 1 1
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 Yes  
     73 1 1 1
     74 ```
     75 
     76 Input
     77 
     78 ```
     79 3 3  
     80 1 1 2
     81 ```
     82 
     83 Output
     84 
     85 ```
     86 No
     87 ```
     88 
     89 Input
     90 
     91 ```
     92 3 1  
     93 1 10 100
     94 ```
     95 
     96 Output
     97 
     98 ```
     99 Yes  
    100 3
    101 ```