codeforces-scrape

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

261.md (2780B)


      1 Source: https://codeforces.com/blog/entry/6398
      2 
      3 [262A - Roma and Lucky Numbers](/contest/262/problem/A "Codeforces Round 160 (Div. 2)")
      4 
      5 This problem just need to simulate everithing that was given in statment.
      6 
      7 [262B - Roma and Changing Signs](/contest/262/problem/B "Codeforces Round 160 (Div. 2)")
      8 
      9 We will "reverse" numbers from the begining to the end while numebrers are negative and we did't spend all k operations.  
     10 In the end there can leave some operetions, and we will "reverse" only one numeber, with minimal value k(that remains) times.
     11 
     12 [261A - Maxim and Discounts](/contest/261/problem/A "Codeforces Round 160 (Div. 1)")
     13 
     14 Ofcourse the most optimal way is to use discount with minimal q_i. We will sort our numbers and will go from the end to begin of the array. We will by use our discount as soon as it will be possible. It's not hard to see that we will buy all the items with numbers I (zero-numeration from the end of the sorted array) such, that I%(q+2)<q.
     15 
     16 [261B - Maxim and Restaurant](/contest/261/problem/B "Codeforces Round 160 (Div. 1)")  
     17 If all people can come, we will return answer as n.  
     18 If it is impossible, there will be finded some person that will be the last to come. We will brtueforce this value. Then we will detrminate dp[i,j,s] in how many ways j persons from the first i with total length s can be in the resturant. It is easy to calculate.  
     19 Then we will add to the answer values dp[n][i][s]*i!*(n-1-i)! for all i,s such that s+p[h]>P. Where P — total length of the table, p[h] — length of the fixed person.
     20 
     21 [261C - Maxim and Matrix](/contest/261/problem/C "Codeforces Round 160 (Div. 1)")  
     22 For fixed m, the sum in the last row will be 2^(bit_count(m+1)-1). So now if T is not power of 2, answer is 0. Else we can find number of bits that we need. And know we have stndart problem. How many numbers form 2 to n+1 have exactly P bits in binary presentation of the number. It is well known problem can be done using binomial cooficients. We will count number of numebers smaller then out number with fixed prefix.
     23 
     24 [261D - Maxim and Increasing Subsequence](/contest/261/problem/D "Codeforces Round 160 (Div. 1)")
     25 
     26 This problem can be done using dp[i,j] where we can end our increasing sequence with length i and last number j. Its not hard to understand that number of states will be n*b. To make a tranfer we need to know array first[j] — first position of the number j in the sequence b, next[i][j] — first position of the number j in the sequence b after position i.
     27 
     28 Now its easy to calculate all values.
     29 
     30 [261E - Maxim and Calculator](/contest/261/problem/E "Codeforces Round 160 (Div. 1)")
     31 
     32 I will add tutorial later. But I will give you a hint: number of numbers with maximal prime divisor<=100 is near 3000000 numbers.