2035 - Empowermage

Enunt

Este cunoscut faptul că unul din cele mai vechi concursuri existene (poate cel mai vechi) este un concurs numit EMPOWERMAGE, unde vrăjitori din toată lumea vin să concureze pentru a câștiga titlul de vrăjitorul anului. În fiecare an, pionierul acestui concurs, vrăjitorul Arpsod, a ținut cont câți participanți au concurat. Din cauza trecerii timpului, de pe pergamentele cu statistica referitoare la numărul de participanți, au mai rămas vizibili doar N ani. Știind ce ani mai sunt încă vizibili și câți participanți au fost în fiecare dintre acești ani, vi se cere să răspundeți la mai multe afirmații de forma: “Anul Y a avut cei mai mulți participanți de la anul X incoace”. Răspunsul poate fi de 3 feluri: ADEVARAT, FALS, POATE

Răspunsul este considerat adevărat dacă: - Numărul de participanți pentru anii X și Y cât și pentru toți anii dintre ei este cunoscut. - Numărul de participanți din anul Y a fost cel mult egal cu numărul de participanți din anul X. - Pentru toți anii intermediari Z (X < Z < Y), număru de participanți a fost strict mai mic decât în anul Y

Răspunsul este POATE dacă sunt îndeplinite condițiile de mai sus (mai puțin prima) dar nu avem informații despre anumiți ani care ne interesează. Răspunsul este FALS dacă nu este nici ADEVARAT nici POATE.

Cerința

Cunoscând numărul de ani vizibili și numărul de participanți din fiecare din acești ani, să se răspundă la mai multe afirmații de tipul enunțat mai sus.

Date de intrare

Pe prima linie a fișierului empowermage.in se va afla numărul natural N, reprezentând numărul de ani vizibili. Urmează apoi N linii a câte 2 valori separate prin spațiu: ai pi cu semnificația că în anul ai au participat pi participanți. Pe linia N+2 se află numărul natural M, reprezentând numărul de afirmații la care trebuie să răspundeți. Urmează apoi M linii a câte două valori: X Y ce codifică afirmația “Anul Y a avut cei mai mulți participanți de la anul X incoace”.

Date de ieșire

Fișierul empowermage.out va conține M linii, pe linia i fiind răspunsul la afirmația i. Răspunsul poate fi ADEVARAT, FALS sau POATE (CU MAJUSCULE)

Restricții și precizări

• 1 ≤ N ≤ 50.000
• 1 ≤ M ≤ 10.000
• -109 ≤ an ≤ 109
• 1 ≤ participanti dintr-un an ≤ 109
• -109 ≤ X < Y ≤ 109
• Cei N ani sunt dați în ordine cronologică

Exemplul 1

intrare

4

2002 4920

2003 590

2004 2832

2005 3890

2

2002 2005

2003 2005

3

1985 5782

1995 3048

2005 4890

2

1985 2005

2005 2015

iesire

Datele introduse corespund restrictiilor impuse.

FALS

ADEVARAT

POATE

POATE

Exemplul 2

intrare

-2

2004 9920

2006 595

2008 28345

2010 3893

1

2009 2010

2013 2008

-4

1984 5781

iesire

Datele de intrare nu corespund restrictiilor impuse.

Rezolvare

#2035 - Empowermage 

def verifica_afirmatii(participanti):
    rezultate = []

    for i in range(len(participanti)):
        for j in range(i + 1, len(participanti)):
            X = participanti[i][1]
            Y = participanti[j][1]
            anul_X = participanti[i][0]
            anul_Y = participanti[j][0]

            conditie_adevarat = all(
                participanti[k][1] <= Y for k in range(i + 1, j)
            )

            if conditie_adevarat:
                rezultate.append("ADEVARAT" if X >= Y else "POATE")
            else:
                rezultate.append("FALS")

    return rezultate

for i in range(len(rezultate_afirmatii)):
    print(f"Afirmatia {i+1}: {rezultate_afirmatii[i]}")