Shirikodama preservation P59994


pdf   zip


We live in uncertain times, and the threats of yore are combing back to join the ones that we are creating anew. In particular, recent years have seen an explosion in the number of kappas in Japanese rivers: barely any stream has not been taken over by these mischievous beings, which were already thought to be a thing of the past—or even just a myth to scare children. Through this come-back, kappas have kept their lust for the shirikodama, the ball inside people’s anus which contains their soul. A group of villagers crossing a river often results in hundreds of kappas swarming to the zone, all avid to take part in the oncoming—and disturbing—pygian banquet.

The river is modelled as a grid of w columns and d rows. Each column of the river contains a kappa. They constantly move either up towards row 0 or down towards row d − 1. It takes them one turn to move one position, and they only stay one turn in the two terminal rows 0 and d − 1. k villagers jump into the river at column 0, one villager per turn, and then move to the next column also once per turn. They are safe when they go beyond column w − 1, but if they end up in a column for which the kappa is in row 0, the creature will take their shirikodama and they will spend the rest of their lives in decadence as a soulless human.

Below you can see the first turns of the first sample input, where only the third villager can escape safe.

Looking at the patterns of movement of kappas in your local river, can you tell which villagers will save their asses (literally)?


Input consists of several cases. Each case starts with w, d, and k. Follow w pairs r c describing each kappa in increasing column order, where 0 ≤ r < d is the row, and c is either ‘u’ or ‘d’ for the direction (up or down). If r = 0 (most shallow) then c is ‘u’, and if r = d − 1 (deepest) then c is ‘d’. The situation is described just before the first villager jumps into the water at column 0. Assume 1 ≤ w ≤ 104, 2 ≤ d ≤ 104, and 1 ≤ k ≤ 104.


For each case, print k characters, one per villager, in the order that they jump into the water: print a ‘+’ if they will save their soul, or a ‘-’ otherwise.

Public test cases
  • Input

    7 4 8
    0 u 1 d 3 d 1 d 0 u 3 d 1 d
    4 3 7
    1 u 2 d 1 d 0 u
    3 2 5
    1 d 0 u 0 u


  • Information
    Edgar Gonzàlez
    Official solutions
    User solutions