Les portes del pànic P38542

A la prova Les portes del pànic cal travessar m muralles per arribar a la meta. Les muralles tenen p portes cadascuna, aparentment idèntiques, però unes són de paper i les altres estan tapiades amb fusta. A cada muralla, cal triar una de les portes i tirar-s’hi de cap. Si la porta era de paper, el concursant la travessa i es dirigeix a la muralla següent (o, si era l’última, ja ha arribat a la meta). Si la porta era de fusta, el concursant rebota i queda eliminat (i possiblement inconscient). Com que no tindria gràcia que es veiessin quines portes han quedat obertes, després de cada concursant es tapien amb fusta totes les portes que ha travessat (per augmentar les probabilitats de trompada del concursant següent). Al començament de la prova, cada muralla té el mateix nombre t de portes tapiades.

Us han encarregat preparar aquesta prova. Ja s’han muntat les m muralles amb p portes cadascuna. Coneixent el nombre de concursants c, el vostre problema és decidir t, el màxim nombre de portes que es poden tapiar a cada muralla inicialment, tot satisfent en Takeshi: Ell vol que hi hagi almenys n maneres diferents de que tots c concursants arribin a la meta.

[r]

A la dreta hi ha un exemple amb m = 4 muralles amb p = 5 portes cadascuna, de les quals t = 2 (marcades en negre) estan inicialment tapiades, i les altres p − t = 3 són inicialment de paper. A l’exemple es veu una de les 1296 maneres de que c = 2 concursants arribin a la meta.

Entrada

L’entrada consisteix en diversos casos, cadascun amb quatre enters: el nombre 1 ≤ m ≤ 5 de muralles, el nombre 1 ≤ p ≤ 6 de portes a cada muralla, el nombre 1 ≤ c ≤ 10 de concursants, i el nombre 1 ≤ n ≤ 10¹⁵ de maneres de que els concursants passin.

Sortida

Per a cada cas, escriviu en una línia t, el màxim nombre de portes per muralla que es pot tapiar inicialment, tot satisfent l’exigència d’en Takeshi. Si és impossible aconseguir-ho, escriviu “Impossible, Takeshi!”.