Deal or No Deal#3176
Deal or No Deal dünyanın bir çox ölkəsində yayımlanan televiziya oyun şousudur. Gəlin oyunun qaydalarını nəzərdən keçirək.
Oyunun əvvəlində hərəsində fərqli məbləğdə pul olan çamadan var. Yalnız pulu yerləşdirən şəxs hansı məbləğin hansı çamadanda olduğunu bilir. Oyunçu bir çamadanı özü üçün seçir, lakin onu açmır. Sonra oyunçu istədiyi ardıcıllıqla qalan çamadanları açmağa başlayır.
Hər çamadan açılmadan öncə bankir oyuna daxil olur. Bankir oyunçuya müəyyən bir məbləğ təklif edir. Oyunçu təklifi qəbul edərsə, təklif edilən məbləği alır və oyun bitir. Əks halda, açılmamış çamadanları açmağa davam edir. Oyunda yalnız iki çamadan qaldıqda, oyunçu təklifi rədd etsə, iki qalan çamadanlardan birini seçib içindəki məbləği götürə bilər. Hər bir halda, oyunçu oyundan müəyyən bir məbləğlə ayrılır. Oyunçunun məqsədi mümkün qədər çox qazanmaqdır. Bankirin məqsədi isə oyunçunun mümkün qədər azla getməsini təmin etməkdir.
Tutaq ki, bankirin təklifi oyunçunun aşağıdakı davranış modelinə əsaslanır. Əgər bankir oyunçuya məbləğində təklif versə, oyunçunun təklifi qəbul etmə ehtimalı aşağıdakı kimi hesablanır:
Burada və oyunda qalan ən kiçik və ən böyük məbləğlərdir. Bankirə optimal təklifləri verəcəyi halda oyunçunun oyundan aparacağı pulun gözlənilən dəyərini hesablayın.
Girişin birinci sətrində (2 \leq n \leq 16) — ümumi çamadan sayı verilir. Növbəti sətrdə hər çamadanda olan məbləğlər: a_1, a_2, \ldots, a_n verilib. Sonra bankirin maraqlandığı vəziyyətlərin sayı (1 \leq q \leq 100) verilir. Ardınca hər vəziyyət aşağıdakı kimi təsvir olunur: (2 \leq k \leq n) — oyunda qalan məbləğlərin sayı; b_1, b_2, \ldots, b_k (1 \leq a_i, b_i \leq 10^6) — qalan məbləğlər.
Hər bir vəziyyət üçün oyunçunun qazanacağı məbləğin gözlənilən dəyərini və bankirin verməli olduğu optimal təklifi çap edin. Hər iki ədədi iki onluq dəqiqliyi ilə göstərin.
Nümunə 1