codeforces-scrape

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

1498C.md (3560B)


      1 Source: https://codeforces.com/problemset/problem/1498/C
      2 
      3 C. Planar Reflections
      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 Gaurang has grown up in a mystical universe. He is faced by $n$ consecutive 2D planes. He shoots a particle of decay age $k$ at the planes.
     22 
     23 A particle can pass through a plane directly, however, every plane produces an identical copy of the particle going in the opposite direction with a decay age $k-1$. If a particle has decay age equal to $1$, it will NOT produce a copy.
     24 
     25 For example, if there are two planes and a particle is shot with decay age $3$ (towards the right), the process is as follows: (here, $D(x)$ refers to a single particle with decay age $x$)
     26 
     27 1. the first plane produces a $D(2)$ to the left and lets $D(3)$ continue on to the right;
     28 2. the second plane produces a $D(2)$ to the left and lets $D(3)$ continue on to the right;
     29 3. the first plane lets $D(2)$ continue on to the left and produces a $D(1)$ to the right;
     30 4. the second plane lets $D(1)$ continue on to the right ($D(1)$ cannot produce any copies).
     31 
     32 In total, the final multiset $S$ of particles is $\{D(3), D(2), D(2), D(1)\}$. (See notes for visual explanation of this test case.)
     33 
     34 Gaurang is unable to cope up with the complexity of this situation when the number of planes is too large. Help Gaurang find the size of the multiset $S$, given $n$ and $k$.
     35 
     36 Since the size of the multiset can be very large, you have to output it modulo $10^9+7$.
     37 
     38 Note: Particles can go back and forth between the planes without colliding with each other.
     39 
     40 Input
     41 
     42 The first line of the input contains the number of test cases $t$ ($1 \le t \le 100$). Then, $t$ lines follow, each containing two integers $n$ and $k$ ($1 \le n, k \le 1000$).
     43 
     44 Additionally, the sum of $n$ over all test cases will not exceed $1000$, and the sum of $k$ over all test cases will not exceed $1000$. All test cases in one test are different.
     45 
     46 Output
     47 
     48 Output $t$ integers. The $i$-th of them should be equal to the answer to the $i$-th test case.
     49 
     50 Examples
     51 
     52 Input
     53 
     54 ```
     55 4
     56 2 3
     57 2 2
     58 3 1
     59 1 3
     60 ```
     61 
     62 Output
     63 
     64 ```
     65 4
     66 3
     67 1
     68 2
     69 ```
     70 
     71 Input
     72 
     73 ```
     74 3
     75 1 1
     76 1 500
     77 500 250
     78 ```
     79 
     80 Output
     81 
     82 ```
     83 1
     84 2
     85 257950823
     86 ```
     87 
     88 Note
     89 
     90 Let us explain the first example with four test cases.
     91 
     92 Test case 1: ($n = 2$, $k = 3$) is already explained in the problem statement.
     93 
     94 See the below figure of this simulation. Each straight line with a different color represents the path of a different particle. As you can see, there are four distinct particles in the multiset. Note that the vertical spacing between reflected particles is for visual clarity only (as mentioned before, no two distinct particles collide with each other)
     95 
     96  ![](https://espresso.codeforces.com/91b8b91bc97b8e5dbdaf5b5beafb5787dd887133.png) 
     97 
     98 Test case 2: ($n = 2$, $k = 2$) is explained as follows:
     99 
    100 1. the first plane produces a $D(1)$ to the left and lets $D(2)$ continue on to the right;
    101 2. the second plane produces a $D(1)$ to the left and lets $D(2)$ continue on to the right;
    102 3. the first plane lets $D(1)$ continue on to the left ($D(1)$ cannot produce any copies).
    103 
    104 Total size of multiset obtained $\{D(1), D(1), D(2)\}$ is equal to three.
    105 
    106 Test case 3: ($n = 3$, $k = 1$), there are three planes, but decay age is only one. So no new copies are produced while the one particle passes through the planes. Hence, the answer is one.
    107 
    108 Test case 4: ($n = 1$, $k = 3$) there is only one plane. The particle produces a new copy to the left. The multiset $\{D(2), D(3)\}$ is of size two.