Guest User

Untitled

a guest
Feb 27th, 2020
432
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # 6 - Le sprint final
  2.  
  3. Ca y est, vous êtes le dernier survivant !!
  4.  
  5. Pour définitivement survivre et remporter la Bataille, il faut vous mettre à l'abri, et la **zone sécurisée** rétrécit dangereusement.
  6.  
  7. La carte est représentée en 1 dimension, et se compose de zones sécurisées (`.`) et de zones dangereuses (`#`).
  8.  
  9. Chaque minute, une zone sécurisée de la carte devient dangereuse. Seule une zone sécurisée touchant une zone dangereuse peut devenir dangereuse.
  10.  
  11. Par exemple, la carte `.#..` peut devenir à la minute suivante `##..` ou `.##.`, mais pas `.#.#`.
  12.  
  13. Afin de survivre et enfin remporter la Bataille, écrivez une fonction qui à partir de la carte actuelle, retourne le nombre de façons qu'il y a de complètement remplir la carte de zones dangereuses.
  14.  
  15.  
  16. ## Entrée
  17.  
  18. La carte est représentée en 1 dimension, et est découpée en zones : `#` est une zone dangereuse, `.` est une zone sécurisée. Il y a moins de 1000 zones par carte.
  19.  
  20. L'entrée est constituée de 20 testcases (tout en bas de ce fichier), chaque testcase comporte un entier en première ligne qui représente la taille de la carte, et en deuxième ligne la carte.
  21.  
  22. ## Sortie
  23.  
  24. Vous devez retourner un entier par test case représentant le nombre de façons qu'il y a de complètement remplir la carte de zones dangereuses.
  25.  
  26. Cet entier doit être retourné **modulo 10^9 + 7**
  27.  
  28. Envoyez par email à contact@h25.io les résultats des tests cases qui sont affichés plus bas, un entier par ligne, ainsi que votre code en pièce jointe.
  29.  
  30. ## Tests d'exemple
  31.  
  32. ### **1**
  33. **Entrée**
  34. ```python
  35. .#..
  36. ```
  37. **Sortie**
  38. `3`
  39. Explication :
  40. ```
  41. .#.. - ##.. - ###. - ####
  42. \
  43. .##. - ###. - ####
  44. \
  45. .### - ####
  46. ```
  47.  
  48. ### **2**
  49. **Entrée**
  50. ```python
  51. #...
  52. ```
  53. **Sortie**
  54. `1`
  55.  
  56.  
  57. ### **3**
  58. **Entrée**
  59. ```python
  60. #...##...
  61. ```
  62. **Sortie**
  63. `80`
  64.  
  65.  
  66.  
  67.  
  68.  
  69. # 6 - The final sprint
  70.  
  71. That's it, you're the last survivor!!
  72.  
  73. To definitely survive and win the Battle, you have to take cover, and the **safe zone** is shrinking dangerously.
  74.  
  75. The map is represented in 1 dimension, and is composed of safe areas (`.`) and dangerous areas (`#`).
  76.  
  77. Every minute, a secure area of the map becomes dangerous. Only a safe area touching a danger zone can become dangerous.
  78.  
  79. For example, the `.#..` map may become `##..` or `.##.` one minute later, but not `.#.#`.
  80.  
  81. In order to survive and finally win the Battle, write a function that, starting with the current map, returns the number of ways to completely turn the map dangerous.
  82.  
  83.  
  84. ## Input
  85.  
  86. The map `grid` is represented in 1 dimension, and is divided into zones: `#` is a dangerous zone, `.` is a secure zone. There are less than 1000 zones per map.
  87.  
  88. The input is a made of 20 testcases (at the bottom of this file), each testcase has the size of the map as its first line and the map as its second line.
  89.  
  90. ## Output
  91.  
  92. You must print one integer per test case representing the number of ways there are to completely turn the map dangerous.
  93.  
  94. This integer must be returned **modulo 10^9 + 7**.
  95.  
  96. Send your answers and source code by email at contact@h25.io, one integer per line.
  97.  
  98. ## Sample tests
  99.  
  100. ### **1**
  101. **Input**
  102. ```python
  103. .#..
  104. ```
  105. **Output**
  106. `3`
  107. Explanation:
  108. ```
  109. .#.. - ##.. - ###. - ####
  110. \
  111. .##. - ###. - ####
  112. \
  113. .### - ####
  114. ```
  115.  
  116. ### **2**
  117. **Input**
  118. ```python
  119. #...
  120. ```
  121. **Output**
  122. `1`
  123.  
  124.  
  125. ### **3**
  126. **Input**
  127. ```python
  128. #...##...
  129. ```
  130. **Output**
  131. `80`
  132.  
  133.  
  134.  
  135.  
  136. =================================================================
  137.  
  138. # TESTCASES
  139.  
  140. 44
  141. #########################...................
  142. 12
  143. ....##......
  144. 38
  145. #.......##########....#########..###..
  146. 44
  147. #.....####.........................#........
  148. 24
  149. ################...##...
  150. 43
  151. ##........##########....#######......######
  152. 37
  153. #.#.##.#.#.##.##.....#.#.####.#.#....
  154. 10
  155. ####..#.#.
  156. 37
  157. ####......###...........#####......##
  158. 28
  159. ......########..##.....###..
  160. 847
  161. ##...#....#.#.##.#.....##.###....#.#.#.#.#..##.####.#..#.#......#####...##.#####..##.###....####.###....#.#...#.####..####.#.#.#.#.#..##.......#..####..#.#......#.####..###..#.#####.####.##....#######.##...#.###..##...#.#.#...#.#.#...#.##......###.#.###.#.#.#...#.....##......##.....####...###..###...##...###....#.###.####....#..##.#.##...#.#.##...##...#######.####.......###....#...#.#.#####...###.#.#..#####.##.###.###....##.#.##.##.#..#.##..#.#....###.#...#.##.....#.##..##.##.##......#.#.#..#.##.###.#####....###.#####..#.#.#.....#...#.#.###..##..##..######..#.###.#.#.#....#......#..###..##....#.##...##.##..##..##.#....##.##........#####.##.#.#.#####.##.....##.#...#...#.##.##..##..#.#..#.###.####..##.####..###.#.###..##....##.#..#.##.#.####.#.#.#.#..#.#..###.#..#..###....#...#.....#.#..#.#..###.#.#..#..##.....#..#..###.#..##..####.##..#
  162. 667
  163. ..#.########################.#....#############...........#...........####################....############..###.........##......#..#######.......###..#..............###......###....#...........###........##################.###......###########.###..###..##...###.....#####..#.............#.........#########..........####...##.########.....##..####.....###....####..#######.###......###...#....................###....................##.######..........##.##################....#..#..##########..###################.#.............##########..#######....#....#########..####........#..#.......#...#..###..........###.......###########....#####..........#.##......######
  164. 990
  165. #.#####..#.##.##..##.#######..##....#.#....#######..#.#.###...#...#...######.##..........#..##.....#..###.#..#....###.....#######..#..#..#......#............######.###.####.##.##.#######...###.###..#..######.######......##.###.##....#.##..#######..###......###.##.###..###..###...#########.############....####..###..####.....###......####..##...#..###......#########...#..#................#....####..####..##.###...##......##...#...............#....########......##.##.##.#..###...#...#...####.#.....####......#########.........###......##...###...#..##............###..#####.####..#.###..####.####.#.#..##...###.##....#....#........#..#.#.#......#.#.###...##.#...............#...#.............##......##...#...###.####....##.#.###..##......##...###..........######........######...###.....#...#...#..######..##.#.#.....#...###..#...##.######.###.###.####.#..###.#######.....##....####....#.####...#......#####.....#.##....#.#...####...#.....#......####.###...#.......####........#.#.####.
  166. 745
  167. ...#.#.###......#######....##.......####..###..###.....##...#....#....#........#####..##########.#.#######....#.........##############.####....##..........#....#####.....##...###.........#....#############.......########...######.###.....##########....#####....................##....####..####........######..............##...........####.#....###########............#............#####################...##.....#.....#........##..........###.#....###########.####....######.#####...#######...#...#######..############.....########......####.#.#.#...####...##.#.....#######.......####.......##..########.###....#####.......#####.......###..##.#######....#.#.......##.............##......###....###..........##..........########.#..#####.##.....##
  168. 827
  169. #############....######................######....###.....#..######....##..........##.....###########...##############....#..#.........##...........#########.........#####..............###############..................######.#..##...####..#.#.....#########...######..################.....###................###........#####........################################......###.######..######....###..........######..####..#####.##############........###.########..###...#.######...#####.######.##................#...##..#####.################...####.......##########................#####......#############.#######...................#########.........###....#############...########.#.#########..########....###.########...#.....#...........#...##..#######.....#........##.....#...##..#####.#########..###...###########...........##
  170. 761
  171. #######...###.......####.............##################.......................###############.######...............###...##############...###..........###############...#########.#######..###........#####.......####################.............#####....####...#######.....#######.....######.....##.........#####..###########.......#.####......##########............########........###################........######........................################...........#..###...........#...................#####...###..........#################.....######.########........##############################............###..######........#######............######.....###########......#..............................###################...#######..#............##......##
  172. 598
  173. #.#.#.#######.......#.###......########.....#......##################...#.....########...........##.....###########.............#####...###.##############.......##########..####.....####......###..#........###...####...#####....##########...........##..######..............##........############.....###.......#...#########.#########......##.########...#....##########.....####........########......#########............##........##########....##########...###.........##.........#............######..#####.......#....###..#########...##################...................###..........##.##........
  174. 823
  175. ###........########.#.........###############....#..##......#######..########...######...##########...#.##.###.#...######....#.....##....#...########.....################...##......####..############...###....####.#.......#########.#.................#####...#####...######.##.#.######..#####.#..#...................#...########.#####...##..#####.########...###...###...##...#........###..#.#######.###.....................#.####..#........#..#..#####..#.####...###..#...#.....#.........#######..#.......#######....##......##............######........................#.##..###.....####.....#########.....#########....................##..####.......########.###########.......#####..####......######...##.#..########.....####.............#########.#...####...###.........####.............########......##..####.....##########
  176. 700
  177. ...#####.......##########..###########....#..#####.............#########..#######....###############.................###...#####################.......######...#####.....#....############........#######...............###................#########....######################..##############......................................................###..............####..######......###########.####...######...........###########.###################........####...................##########################....########.........#################################.######.............###..#############################...#####...........######......#################.###############.........######.......#....#
  178. 567
  179. #.....##.#################........##.......#....##.#####.##..##................##############.###...#.###########.##.....##....#....#.######..###...........##.#######...#########.######...###.......##....######..............##.##########....#..#################.##..................#########.###.............####....#...##.....#....###.###...........###.#######.....#...#..##..............##..###.#....##..##...#...####..########...#......##.....#####.##########....#######.......#....#..#..........#####...............#.#..#.....#####.##.#######....##.........###...
RAW Paste Data