Problema


  1. #1
    0-day Member horatiu11 reprezinta o cantitate neglijabila
    Data de inscriere
    02-04-2012
    Sex
    M
    Mesaje
    1
    Putere Reputatie
    0
    Reputatie
    10
    Puncte CF
    0.0

    Problema

    Problema 1 - palindrom 100 puncte
    Cu mult timp în urmă, într-un tărâm foarte, foarte îndepărtat, a existat o ţară numită Tnamap. Locuitorii acestei ţări puteau să aplice instantaneu transformări asupra
    cifrelor unui număr, utilizând un tablou de corespondenţe T.
    O cifră c a unui număr poate fi înlocuită cu cifra corespunzătoare ei, Tc.
    Dalv şi Sogard, doi indivizi speciali ai acestei societăţi ciudate se aflau în drum spre INO când au conştientizat că pot transforma instantaneu, folosind număr minim de transformări de cifre, orice număr N într-un palindrom divizibil cu un număr natural K. Dacă sunt mai multe astfel de numere, îl determină pe cel mai mare.
    Voi puteţi?

    Cerinţă

    Cunoscând valorile T0, T1, …, T9, numărul ce urmează a fi transformat N şi numărul K (divizorul palindromului), determinaţi:
    1. Numărul maxim care se poate obţine aplicând transformări succesive numărului N dat.
    2. Cel mai mare dintre palindromurile divizibile cu K, ce se pot obţine din numărul N, efectuând un număr minim de transformări asupra cifrelor numărului dat, respectiv asupra cifrelor numerelor obţinute pe parcurs.

    Date de intrare

    Pe prima linie a fişierului palindrom.in sunt memorate 10 cifre distincte, separate prin câte un spaţiu, reprezentând valorile T0, T1, …, T9.
    Pe a doua linie sunt memorate cifrele numărului N, iar pe cea de a treia linie un numărul natural K.

    Date de ieşire

    Fişierul palindrom.out va conţine pe prima linie numărul maxim care se poate obţine aplicând transformări succesive numărului N, iar pe a doua linie palindromul divizibil cu K,de valoare maximă, ce se poate obţine din numărul N, efectuând un număr minim de transformări asupra cifrelor.

    Restricţii şi precizări

    • 1≤N<101.000.000;
    • N are un număr par de cifre;
    • 2 ≤ K ≤ 20;
    • se garantează faptul că toate testele au soluţie;
    • pentru rezolvarea primei cerinţe se va acorda 20% din punctaj, iar pentru rezolvarea celei de-a doua cerinţe se va acorda 80% din punctaj.

    Exemplu
    palindrom.in palindrom.out Explicaţii
    0 4 6 5 1 2 7 8 9 3
    1234 4994
    4224 1234→4234→4634→4734→4834→4934→4954→4 924→4964→4974→4984→4994
    Numărul N trece prin următoarele stări înainte de a deveni palindrom cu valoarea maximă, divizibil cu 3:
    1234→4234→4254→4224.
    Timp maxim de executare: 0.4 secunde/test.
    Total memorie disponibilă 256MB, din care 64 MB pentru stivă
    Dimensiunea maximă a sursei: 10 KB..

    Ma puteti ajuta cu o idee? Incerc sa o fac si nu imi reuseste.

  2. #2
    0-day Member gigi400 reprezinta o cantitate neglijabila
    Data de inscriere
    02-04-2012
    Varsta
    36
    Sex
    M
    Mesaje
    1
    Putere Reputatie
    0
    Reputatie
    10
    Puncte CF
    0.0
    Da iti putem raspunde

    ---------- Post added 02-04-2012 at 10:15 ----------

    vrei sa te ajut?

    ---------- Post added 02-04-2012 at 10:20 ----------

    vrei sa iti dau o idee sau dirct programul sursa?
    Vrei mai putine reclame? Inregistreaza-te sau logheaza-te

  3. #3
    Member alex707's Avatar alex707 reprezinta o cantitate neglijabila
    Data de inscriere
    28-09-2006
    Varsta
    43
    Sex
    M
    Mesaje
    183
    Mesaje bazar
    63
    Putere Reputatie
    0
    Reputatie
    8
    Puncte CF
    30.0
    Defineste ce intelegi prin "idee" + Ce a intrebat gigi400.
    Ce ai incercat pana acum (pune cod), unde te-ai blocat sau ce nu intelegi. Fii concret.
    Ce era mai important nu ne-ai spus, in ce limbaj? Presupun ca C, dar cunoscand scolile romanesti parca aud un turbo pascal, dar ar fi fost frumos sa ne spui tu si sa nu ma lasi pe mine sa ghicesc. Sau poate C++?

    Offtopic: Ce-i cu timpul ala maxim de executie? 0.4 secunde pe test?
    Mi se pare foarte random cifra aia. Banuiesc ca 0.4s pe procesoarele de la voi de la scoala, pentru ca daca stam sa calculam:
    - pe un 386 @ 33Mhz avem 11.4 MIPS care in 0.4s ar fi 4.56 mil/test
    - pe un i7 2600k @ 3.4GHz 128,300 MIPS care in 0.4s ar fi 51,320 mil/test
    Deci intre 5 si 51320 milioane, cum fac? Imi aleg eu cate operatii pot face?

    Ontopic:
    Ca sa poata citi de tot poporul datele din exemplu le mai scriu eu odata mai citet:
    Cod:
    Exemplu
    T0 T1 T2 T3 T4 T5 T6 T7 T8 T9
     0  4  6  5  1  2  7  8  9  3
    
    N=1234
    
    N max = 4994
    
    N max divizibil cu 3 = 4224	
    
    Transformari pentru 4994: 1234→4234→4634→4734→4834→4934→4954→4924→4964→4974→4984→4994
    
    Transformari pentru 4224: 1234→4234→4254→4224
    P.S.: Si primul si al doilea post sunt primele posturi ale unor useri noi, ar fi funny sa aflu ca primul post este al unui elev in timpul laboratorului si al doilea post al profesorului care l-a prins , desi profesor la 24 de ani mai rar, then again nu cred ca si-ar fi pus varsta reala. Sooo... who knows ... oricum, ma indoiesc ca mai raspunde cineva la topicul asa cum de multe ori se intampla la posturi de genul asta si mie mi s-a facut dor de python.

    Asa ca ...

    palindrom.in
    Cod:
    0 4 6 5 1 2 7 8 9 3
    1234
    3
    main.py
    Cod:
    class main:
        transform = None
        data = {}
        path = []
        
        def readFileAndExtractNeededValues(self):
            file = open('palindrom.in')
            content = file.read()
            content = content.split('\n')
            N = content[1]
            div = content[2]
            transform = content[0].split(' ')
            for i, value in enumerate(transform):
                transform[i] = int(value)
            self.transform = transform
            self.data = { 'N': N, 'divizor': div, 'transform': transform }
    
        def buildPathsInWhichNCanChange(self):
            transform = self.transform
            path = []
            list = []
            i = 0
            while True:
                if (len(list) > 0):
                    path.append(list)
                list = []
                while True:
                    if list.count(i) == 0:
                        list.append(i)
                        next = transform[i]
                        if list.count(next) > 0:
                            for value in list:
                                transform[value] = -1
                            for key, value in enumerate(transform):
                                if value != -1:
                                    i = key
                                    break
                            break
                        else:
                            i = next
                if transform.count(-1) == 10:
                    path.append(list)
                    self.path = path
                    break
    
    a = main()
    a.readFileAndExtractNeededValues()
    a.buildPathsInWhichNCanChange()
    Cineva gandise exercitiul asta pentru liste simplu inlantuite, dar in afara de exercitii de liceu eu nu le-am vazut niciodata rostul si nici nu am gasit pe net vreo aplicatie practica reala a lor. Therefore ... listeeeeeeeee ... simple si neinlantuite.
    Cam asa as vedea eu logica sa faci modul in care se pot schimba cifrele din N, dupa ce rulezi obtii
    Cod:
    [[0], [1, 4], [2, 6, 7, 8, 9, 3, 5]]
    Care le folosesti foarte usor identificand cifra de la care pornesti si determini prin ce pasi treci (mergand in sus prin liste) ca sa ajungi la cifra maxima.
    Maximul o sa fie un pic mai usor de determinat, in exemplul dat 4994 ajungi la el destul de rpd, numai ca treci prin mai multi pasi.
    Palindromul divizibil cu 3 in cei mai putini pasi e un pic mai tricky pentru ca si 4884, 4554 sunt divizibile cu 3 in ex dat dar ajungi la el in mai multi pasi decat la 4224 asa ca probabil varianta mai safe este sa le determini pe toate divizibile cu k si sa contorizezi numarul de pasi prin care ajungi la ei si sa iei minimul de pasi dintre toti.
    Last edited by alex707; 03-04-2012 at 00:54.
    Success is not final, failure is not fatal: it is the courage to continue that counts. --Sir Winston Churchill

  4. #4
    Member alex707's Avatar alex707 reprezinta o cantitate neglijabila
    Data de inscriere
    28-09-2006
    Varsta
    43
    Sex
    M
    Mesaje
    183
    Mesaje bazar
    63
    Putere Reputatie
    0
    Reputatie
    8
    Puncte CF
    30.0
    Continuand ideea trebuie sa facem un mic plan. Ce ne mai trebuie?
    1 - o functie care sa determine maximul cifrei prin transformari pentru o pereche de cifre n1, n2. Adica daca iei prima si ultima cifra a numarului, mai intai sa verifici carui grup apartine si maximul la care poti ajunge (pentru exemplu dat sa ia 4 si 1 apartine grupului 2, maximul este 4, si pentru urmatorul grup 3 si 4 apartine grupului 3 si maximul este 9 rezultand 4994 ca maximul la care poti ajunge pornind de la 1234;

    ar fi:
    Cod:
        def maxN(self):
            assert self.hasMaxN(self.data['N'])
            N = self.data['N']
            for a in range(len(N)/2):
                self.result['maxN'] = self.result['maxN'] + str(max(self.path[self.locate(N[a])]))
            for i in self.result['maxN'][::-1]:
                self.result['maxN'] = self.result['maxN'] + i
            print 'Maximum palindrome reachable:', self.result['maxN']
                
        def locate(self, value):
            for i, lst in enumerate(self.path):
                if lst.count(int(value)) > 0:
                    return int(i)
    
       def hasMaxN(self, n):
            nString = str(n)
            for lst in self.path:
                if (int(nString[0])) in lst: 
                    if int(nString[-1]) not in lst:
                        return False
                    elif len(nString) > 2:
                        return self.hasMaxN(nString[1:-1])
                    else:
                        return True
                else:
                    continue
    Nota: pentru ca sa garantezi o solutie asa cum e dat in exemplu tabelul de succesiuni nu se aplica. Pentru ca de exemplu daca prima si ultima cifra (sau orice alta pereche care o verifici sa fie palindrom) nu apartin aceluiasi grup nu ai cum sa ajungi la o solutie. De ex. 4366 nu are solutie pentru ca nu poti (pentru prima si ultima cifra) sa transformi pe 4 in 6. Asa ca lista de transformari ar trebui sa fie circulara ca sa poti garanta o solutie (deci lista de transformari sa aiba un singur element format dintr-o lista cu toate cele 10 numere). Dar asta o sa ma ocup mai la sfarsit (i.e. o functie care sa verifice daca lista de transformari este circulara) sau sa fac o functie care sa verifice ca perechile de numere (primul si ultimul, al doilea si penultimul etc) pot ajunge la aceeasi cifra, iar daca nu sa afisez ca numarul dat nu are solutie.

    2 - o functie care sa verifica daca un numar e palindrom, ma gandesc la o functie recursiva cu cazul de baza fiind pentru length 2 returneaza string[1] == string[-1] unde string este numarul transformat in string si pentru restul cazurilor sa returneze recursiv functia apelata cu nr-ul care se obtine daca scoti prima si ultima cifra.

    Nu cred ca o sa am nevoie de asta ca am facut cu asserturi, dar ca sa fie:
    Cod:
        def isPalindrome(self, n):
            nString = str(n)
            if 2 == len(nString):
                return nString[0] == nString[-1]
            else:
                return self.isPalindrome(nString[1:-1])
    3 - pentru punctul 2 ar trebui sa determin toate palindroamele care se pot obtine, deci ne trebuie o functie care sa returneze o lista de palindroame posibile pentru nr dat (in ex nostru 1234 ar rezulta intr-o lista de palindroame posibile in care prima si ultima cifra sunt 1 sau 4 iar a doua si a 3-a pot fi 2, 6, 7, 8, 9, 3, 5 deci ... 14 palindroame posibile)

    4 - o functie care sa filtreze lista obtinuta anterior la cele care sunt divizibile cu k si sa returneze cel mai mare nr din cele divizible cu k sau as putea sa o combin cu pasul anterior si sa fac un singur pas ... mai vedem;

    3 si 4 le-am facut pe amandoua intr-o singura functie
    Cod:
        def determineMaxPalindromeDivisibleByK(self):
            buildingBlocks = []
            howLong = range(len(self.data['N'])/2)
            for i in howLong:
                for lst in self.path:
                    if int(self.data['N'][i]) in lst:
                        buildingBlocks.append(lst)
                        break
            totalNumberOfPalindromes = 1
            for lst in buildingBlocks:
                totalNumberOfPalindromes = totalNumberOfPalindromes * len(lst)
            maxCounter = []
            counter = []
            for i in range(len(buildingBlocks)):
                maxCounter.append(len(buildingBlocks[i])-1)
                counter.append(0)
            palindrome = []
            for i in range(totalNumberOfPalindromes):
                palindrome.append('')
                for j in range(len(maxCounter)):
                    palindrome[i] = palindrome[i] + str(buildingBlocks[j][counter[j]])
                counter[j] = counter[j] + 1
                for k in range(len(counter)-1, -1, -1):
                    if counter[k] > maxCounter[k]:
                        counter[k] = 0
                        counter[k-1] = counter[k-1]+1
            finalPalindrome = {}
            for i, p in enumerate(palindrome):
                palindrome[i] = p + p[::-1]
                if int(palindrome[i]) % int(self.data['divizor']) == 0:
                    finalPalindrome[int(palindrome[i])] = self.stepsToReachNumber(palindrome[i])
            print self.minimumSteps(finalPalindrome)
    5 - o functie care sa determine numarul de pasi necesari pentru a ajunge la numarul divizibil cu k si sa returneze numarul optim (divizibil cu k la care se ajunge prin cel mai mic numar de pasi). Daca doua sau mai multe numere au acelasi numar de pasi se returneaza cel mai mare

    6 - si bineinteles o functie care sa afiseze pasii cu transformarile dupa ce m-am convins la numerele la care trebuie sa ajung;

    Cam asta ar fi planul ... acum sa-l punem in practica.

    P.S. pentru ca sa fie cat mai clean am sa incerc sa fac cat mai multe din functii recursive desi in momentul asta nu-mi dau seama daca se poate aplica recursivitatea pentru toate (in afara de cea care verifica ca e palindorm care e cam evident ca se poate face recursiva). Asta probabil pentru ca ma tratez cu niste whiskey ... yum

    Editez ce am facut pana acum si le pun inline ... Mai ramane 5 si 6 de facut si niste asserturi ca sa ne asiguram ca exista numere divizible cu k, dar altadata.

    Nu am pus commenturi prin cod in primul rand de lene si in al doilea rand ma indoiesc ca e cineva interesat o solutie la ex asta. It's just done for funsies.
    Last edited by alex707; 19-05-2012 at 23:33.
    Success is not final, failure is not fatal: it is the courage to continue that counts. --Sir Winston Churchill

  5. #5
    Member alex707's Avatar alex707 reprezinta o cantitate neglijabila
    Data de inscriere
    28-09-2006
    Varsta
    43
    Sex
    M
    Mesaje
    183
    Mesaje bazar
    63
    Putere Reputatie
    0
    Reputatie
    8
    Puncte CF
    30.0
    Pentru pct. 5:

    Cod:
    def minimumSteps(self, palindromes):
            assert len(palindromes) > 0
            minSteps = min(palindromes.values())
            maxPalindromes = []
            for palindrome, step in palindromes.iteritems():
                if step == minSteps:
                    maxPalindromes.append(int(palindrome))
            
            print 'Max palindrome divisible by', self.data['divizor'], 'in minimum number of steps('+str(minSteps)+'):', max(maxPalindromes)
            self.stepsToReachNumber(str(max(maxPalindromes)), True)
    Si pentru pct. 6 o combinatie intre determinarea pasilor si printarea lor:

    Cod:
    def stepsToReachNumber(self, number, printPath = False):
            fromNumber = str(self.data['N'])
            count = 0
            if printPath:
                print fromNumber
            while fromNumber != number:
                for i, n in enumerate(fromNumber):
                    if n != str(number)[i]:
                        index = self.path[self.locate(int(n))]
                        while n != str(number)[i]:
                            where = index.index(int(n))
                            if where+1 == len(index):
                                fromNumber = fromNumber[0:i] + str(index[0]) + fromNumber[i+1:]
                                n = str(index[0])
                                count += 1
                            else:
                                fromNumber = fromNumber[0:i] + str(index[where+1]) + fromNumber[i+1:]
                                n = str(index[where+1])
                                count += 1
                            if printPath:
                                print fromNumber
                        break
            return count
    Punand totul cap la cap si apeland:

    Cod:
    a = main()
    a.readFileAndExtractNeededValues()
    a.buildPathsInWhichNCanChange()
    a.maxN();
    a.determineMaxPalindromeDivisibleByK()
    obtinem ca output pentru exemplu:

    Cod:
    transform path = [[0], [1, 4], [2, 6, 7, 8, 9, 3, 5]]
    Maximum palindrome reachable: 4994
    1234
    4234
    4634
    4734
    4834
    4934
    4954
    4924
    4964
    4974
    4984
    4994
    Max palindrome divisible by 3 in minimum number of steps(3): 4224
    1234
    4234
    4254
    4224
    Stiu ca in execitiu trebuia pus in palindrome.out but ... I can't be bothered to. Se poate modifica sa construiasca palindrome.out in loc de print.

    assert self.hasMaxN verfica daca are solutie (am scris mai sus cand nu ar avea solutie), si "assert len(palindromes)" > 0 verifica daca exista nr divizibil cu K (pentru ca e posibil sa nu aiba).

    Cam atat.
    Success is not final, failure is not fatal: it is the courage to continue that counts. --Sir Winston Churchill
    Vrei mai putine reclame? Inregistreaza-te sau logheaza-te

Tags for this Thread

Google+

Cautati logo-ul CraiovaForum?

Iata cateva variante: