Codificación aritmética P37123


Statement
 

pdf   zip

thehtml

Considera un alfabeto Σ donde cada letra ci tiene asociado una probabilidad pi. Por ejemplo, Σ={c1=A, c2=B, c3=C} con

p(A) = p1 = 
1
2
,    p(B) = p2 = 
1
5
    p(C) = p3 = 
3
10
 

A cada palabra (secuencia de letras) s del alfabeto Σ le asignamos un intervalo I(s)=[a;b) según las reglas siguientes.

  • El intervalo de la palabra vacía s=λ es
    I(λ)=[0; 1). 
  • El intervalo de la palabra s=t· ci, donde t es una palabra con I(t)=[a; b) y ci es la última letra de s, es
    I(s)=[a + (p1 + ⋯ + pi−1)·(b−a); a + (p1 + ⋯ + pi)·(b−a)).

Por ejemplo, a las palabras λ, A, AA, AAC, AACB les corresponden los siguientes intervalos:

     
I(λ)= [0; 1)          
I(A)= [0 + 0· 1; 0 + 0.5 · 1) = [0; 0.5)          
I(AA)= [0 + 0 · 0.5; 0 + 0.5 · 0.5) = [0; 0.25)          
I(AAC)= [0 + 0.7 · 0.25; 0 + 1 · 0.25) =[0.175; 0.25)          
I(AACB)= [0.175 + 0.5 · 0.075; 0.175 + 0.7 · 0.075) = [0.2125; 0.2275)          

Cuantas más letras añadimos, más pequeño es el intervalo resultante.

Entrada

Una línea con el número n de letras del alfabeto. A continuación, n líneas con las letras ci del alfabeto y las probabilidades pi de cada letra. Todas las probabilidades cumplen pi≥ 0.1 y se te garantiza que p1 + ⋯ + pn = 1.

Por último, un número indeterminado de líneas con los casos de prueba. Cada caso de pruebas es un número natural k<6 y un número real r entre 0 y 1.

Salida

Para cada caso, escribe la única palabra s de k letras cuyo intervalo I(s) contiene el real r. Se te garantiza que las entradas serán tales que nunca tendrás problemas de precisión usando double.

Public test cases

  • Input

    2
A 0.5
B 0.5
1 0.25
1 0.75
0 0.5
2 0.99
5 0.7501
5 0.7499

    Output

    A
B

BB
BBAAA
BABBB

  • Input

    3
A 0.5
B 0.2
C 0.3
4 0.2124
4 0.2126
4 0.2274
4 0.2276
4 0.9999
4 0.9

    Output

    AACA
AACB
AACB
AACC
CCCC
CBCA
    • Information
    Author
    Omer Giménez
    Language
    Spanish
    Official solutions
    C++
    User solutions
    C++