codeforces-scrape

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

294.md (4043B)


      1 Source: https://codeforces.com/blog/entry/7287
      2 
      3 #### [294A - Shaass and Oskols](/contest/294/problem/A "Codeforces Round 178 (Div. 2)")
      4 
      5 Although Oskol is not really name of a specie of birds, In Iran it's known as a kind of bird which is very forgetful and can't even remember his way back to home when he flies away! It's commonly used instead of the word "stupid" among the kids! :D
      6 
      7 In this problem you just have to now how many birds are there on each wire after each shot. A good trick for the first and the last wire would be to define wires 0 and *n* + 1. In this way the birds that fly away sit on these wires and you don't need to worry about accessing some element outside the range of your array.
      8 
      9 Here is a neat implementation in C++ from contestant [rpslive](/profile/rpslive "Newbie rpslive"): [3484601](/contest/294/submission/3484601 "Submission 3484601 by rpslive")
     10 
     11 #### [294B - Shaass and Bookshelf](/contest/294/problem/B "Codeforces Round 178 (Div. 2)")
     12 
     13 As said in the statement, the thickness of each book is either 1 or 2. Think about when we want to arrange *v*1 books of thickness 1 and *v*2 books of thickness 2 vertically and arrange all other *n* - *v*1 - *v*2 books horizontally above them to achieve a configuration with total thickness of vertical books equal to *v*1 + 2*v*2. Is it possible to find such arrangement? Because the total thickness of vertical books is fixed it's good to calculate the minimum possible total width of horizontal books. As the width of a book doesn't matter in vertical arrangement it's good to use the books with shorter width horizontally and the ones with longer width vertically. So pick out *v*1 books with longest width among books of thickness 1 and do the same with books of thickness 2. The sum of width of *n* - *v*1 - *v*2 remaining books should be at most *v*1 + 2*v*2.
     14 
     15 The solution would be to try the things we explained above for all possible values of *v*1 and *v*2. And print the best answer. :)
     16 
     17 There exists other ways to solve this problem mostly using dynamic programming but this was the intended solution of the problem.
     18 
     19 Here is a nice implementation in C++ from contestant [bayram](/profile/bayram "Expert bayram"): [3485189](/contest/294/submission/3485189 "Submission 3485189 by bayram") (You should also know that 'bir' means 'one' in Turkish and 'iki' means two!)
     20 
     21 #### [294C - Shaass and Lights](/contest/294/problem/C "Codeforces Round 178 (Div. 2)")
     22 
     23 I just want to solve the third sample of this problem for you and you can figure out the rest by yourself. :)
     24 
     25 The third sample is `...#...#...` where `#` is a switched on lamp and `.` is a switched off lamp. As you can see we have three different types of lights. The first three lights (Type A), the 5th to 8th lights (Type B) and the last three lights (Type C). We have to switch on the lights three times for each type of lights. Aside from the order of moves for each type there are ![](https://espresso.codeforces.com/1b5bdb0b628363ed403438d4ca15bbcc92393ad7.png) possible permutations of the string AAABBBCCC which tells us how to combine the steps of different types. Switching on the lights is done uniquely for types 1 and 3. But for type 2 each time we have to possible options until we're left with one off light. So there are 23 - 1 ways to do this. So the answer would be `1680*1*4*1 = 6720`.
     26 
     27 The general solution would be to find all groups off consecutive switched off lamps and calculate the number of ways to combine all these groups. Then for each group you should calculate in how many ways it can be solved.
     28 
     29 The implementation needs some standard combinatorial computations which you can see here: [3485187](/contest/294/submission/3485187 "Submission 3485187 by alex20030190")
     30 
     31 #### [294D - Shaass and Painter Robot](/contest/294/problem/D "Codeforces Round 178 (Div. 2)")
     32 
     33 TODO
     34 
     35 #### [294E - Shaass the Great](/contest/294/problem/E "Codeforces Round 178 (Div. 2)")
     36 
     37 TODO
     38 
     39 I promise the editorial will be completed come soon soon soon! :)