API tools faq
paste
Advertisement
Guest User

ZCO afternoon2

a guest
Nov 23rd, 2012
55
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 4.23 KB | None | 0 0
raw download clone embed print report
  1. Zonal Computing Olympiad 2013, 10 Nov 2012
  2.  
  3.  
  4. Problem 2: Save Spaceman Spiff
  5.  
  6.  
  7. Spaceman Spiff has crash landed on Planet Quorg. He has to reach his ship quickly. But the evil Yukbarfs have stolen many Death Ray Blasters and have placed them along the way. You'll have to help him out!
  8.  
  9. Spaceman Spiff is initially at the top left corner (1,1) of a rectangular N × M grid . He needs to reach the bottom right corner (N,M). He can only move down or right. He moves at the speed of 1 cell per second. He has to move every second-that is, he cannot stop and wait at any cell.
  10.  
  11. There are K special cells that contain the Death Ray Blasters planted by the Yukbarfs. Each Blaster has a starting timet and a frequency f. It first fires at timet seconds, followed by another round at time t+fseconds, then at time t+2f seconds …. When a Blaster fires, it simultaneously emits four pulses, one in each of the four directions: up, down, left and right. The pulses travel at 1 cell per second.
  12.  
  13. Suppose a blaster is located at (x,y) with starting time t and frequency f. At time tseconds, it shoots its first set of pulses. The pulse travelling upwards will be at the cell (x,y-s) at time t+sseconds. At this time, the pulse travelling left will be at cell(x-s,y), the pulse travelling right will be at cell(x+s,y) and the pulse travelling down will be at cell(x,y+s). It will fire next at time t+f seconds. If a pulse crosses an edge of the grid, it disappears. Pulses do not affect each other if they meet. They continue along their original path. At any time, if Spaceman Spiff and a pulse are in the same cell, he dies. That is the only way pulses interact with Spaceman Spiff. Given these, you should find the least time (in seconds) in which Spaceman Spiff can reach his ship safely.
  14.  
  15. As an example consider a 4×4 grid that has only one Blaster, at (3,2), with starting time 1 and frequency 3. In the grids below, S denotes Spaceman Spiff, B denotes the blaster and P denotes a pulse. The sequence of grids describes a successful attempt to reach his ship that takes 6 seconds.
  16.  
  17. t=0 t=1 t=2 t=3
  18. S . . . . S . . . . S . . P . S
  19. . . . . . . . . . P . . . . . .
  20. . B . . . P . . P B P . . B . P
  21. . . . . . . . . . P . . . . . .
  22.  
  23.  
  24.  
  25.  
  26. t=4 t=5 t=6
  27. . . . . . . . . . P . .
  28. . . . S . P . . . . . .
  29. . P . . P B P S . B . P
  30. . . . . . P . . . . . S
  31.  
  32.  
  33.  
  34.  
  35. Input format
  36. Line 1: Three space separated integers N, Mand K, describing the number of rows and columns in the grid and the number of Blasters, respectively.
  37.  
  38. Lines 2 to K+1: These lines describe the Kblasters. Each line has four space separated integers. The first two integers on the line denote the row and column where the Blaster is located, the third integer is its starting time, and the fourth integer is its frequency.
  39.  
  40.  
  41.  
  42.  
  43. Output format
  44. The first line of output must either consist of the wordYES, if Spaceman Spiff can reach his ship safely, or the word NO, if he cannot do so. If the output on the first line is YES then the second line should contain a single integer giving the least time, in seconds, that it takes him to reach his ship safely.
  45.  
  46.  
  47.  
  48.  
  49. Sample Input 1
  50. 4 4 1
  51. 3 2 1 3
  52.  
  53.  
  54.  
  55.  
  56. Sample Output 1
  57. YES
  58. 6
  59.  
  60.  
  61.  
  62.  
  63. Sample Input 2
  64. 5 5 2
  65. 5 1 1 2
  66. 4 4 1 2
  67.  
  68.  
  69.  
  70.  
  71. Sample Output 2
  72. YES
  73. 8
  74.  
  75.  
  76.  
  77.  
  78. Test data
  79. In all subtasks, you may assume that:
  80.  
  81. 2 ≤ N,M ≤ 2500.
  82.  
  83. All the frequencies are guaranteed to be integers between 1 and 3000, inclusive.
  84.  
  85. All the starting times are guaranteed to be integers between 0 and 3000, inclusive.
  86.  
  87. All the coordinates of the Blasters are guaranteed to be valid cells in the N×M grid. No two Blasters will be on the same cell.
  88.  
  89. Subtask 1 (30 marks) : K = 1.
  90.  
  91. Subtask 2 (70 marks) : 1 ≤ K ≤ 2500.
  92.  
  93.  
  94.  
  95.  
  96. Live evaluation data
  97. Subtask 1: Testcases 0,1.
  98.  
  99. Subtask 2: Testcases 2,3,4,5.
  100.  
  101.  
  102.  
  103.  
  104. Limits
  105. Time limit : 3s
  106.  
  107. Memory limit: 128 MB
  108.  
  109. CPU Timelimit: 3 seconds
  110. Memory limit: 128M
  111. Grading style: ioi
  112. UsernamePasswordRegister Now
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!