Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: 105 Base3  (Citit de 2963 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« : Septembrie 04, 2005, 16:12:46 »

Aici puteţi discuta despre problema Base3.
Memorat
blue_phoenix
Client obisnuit
**

Karma: 0
Deconectat Deconectat

Mesaje: 57



Vezi Profilul
« Răspunde #1 : Aprilie 30, 2012, 15:26:18 »

buna! m-am tot gandit la problema asta, si as avea cateva idei:
1)daca fixez un sir si un 1 din el, sa spunem ca am x1y (x=nr de cifre din stanga lui 1 pe care l-am fixat, y= acelasi nr din dreapta)
  daca cele trei siruri date au lungimile a,b,c, atunci noi vrem
        x+t1*a+u1*b+v1*c=y+t2*a+u2*b+v2*c=min
   se cere acel min nr natural care se poate scrie sub cele doua forme de mai sus, cu t1,u1,...v2 naturale
  problema e ca nu stiu cum sa-l aflu si mai trebuie sa sa fixex un sir si un 1 din el
2)prima oara m-am gandit ca sol bruta ar fi cu o parcurgere in latime, dar mi-am dat seama ca nu merge, pt ca lungimile sirurilor nu sunt egale; as putea sa folosesc dijkstra, dar nu mi-e clar care e graful (sursa e sirul vid, dar de unde stiu cate destinatii am, trebuie sa pot sa tin vectorul de distante si nu stiu cum sa numerotez nodurile; la parcurgerea in latime as fi putut sa expandez nodurile pe pparcurs, fara sa stiu graful de la inceput);

mi-ar putea da cineva un hint de cum sa folosesc dijkstra aici? macar sa stiu cam la ce complexitate ar trebui sa ajung, ca sa stiu daca pot sa folosesc ideea cu fixatul unui 1
Memorat
darkseeker
De-al casei
***

Karma: 29
Deconectat Deconectat

Mesaje: 106



Vezi Profilul
« Răspunde #2 : Aprilie 30, 2012, 15:45:39 »

Solutia oficiala are complexitate (L1 + L2 + L3) * log (L1 + L2 + L3) . Daca vrei mai multe detalii poti descarca solutiile de la ONI 2004, acestea aflandu-se in sectiunea downloads .
Memorat
pauldb
Nu mai tace
*****

Karma: 821
Deconectat Deconectat

Mesaje: 1.901



Vezi Profilul
« Răspunde #3 : Aprilie 30, 2012, 19:37:29 »

Ideea e sa incerci sa calculezi len[ i ] = lungimea minima a unui sir care are un 1 in centru si diferenta dintre lungimea partii sirului la dreapta de 1 si lungimea partii sirului la stanga de 1 egala cu i (i poate fi si negativ, dar nu e o problema mare). Adaugarea de siruri noi la stanga si la dreapta te duce in stari noi. Daca vezi starile len ca noduri ale unui graf, atunci prin adaugarea unui sir la stanga/dreapta se formeaza muchii cu cost. Si de aici ideea de Dijkstra.
Memorat

Am zis Mr. Green
blue_phoenix
Client obisnuit
**

Karma: 0
Deconectat Deconectat

Mesaje: 57



Vezi Profilul
« Răspunde #4 : Mai 01, 2012, 06:13:59 »

Multumesc mult amandurora! Very Happy
Memorat
Impaler_009
Client obisnuit
**

Karma: 23
Deconectat Deconectat

Mesaje: 59



Vezi Profilul
« Răspunde #5 : August 13, 2013, 13:19:06 »

Daca problema n-ar fi cerut numarul minim de cifre, ci doar un numar posibil (eventual cu afisarea in sine a solutiei in baza 3), s-ar fi putut face dragut cu Algoritmul Extins al lui Euclid, daca nu ma insel.  Very Happy
Memorat
SebiSebi
Nu mai tace
*****

Karma: 76
Deconectat Deconectat

Mesaje: 306



Vezi Profilul
« Răspunde #6 : Martie 31, 2014, 13:21:50 »

In cazul soluției descrise de Paul în postul de mai sus, complexitatea nu este destul de mare având în vedere faptul ca numărul de stări creste considerabil: din fiecare stare generam încă alte 6 stări, în total se duce undeva le 3^N. Cum putem reduce numărul stărilor?
Memorat
Impaler_009
Client obisnuit
**

Karma: 23
Deconectat Deconectat

Mesaje: 59



Vezi Profilul
« Răspunde #7 : Martie 31, 2014, 17:07:22 »

Numarul maxim de stari aici este SumLen = suma lungimilor celor 3 cuvinte. O stare este data de diferenta dintre lungimea din stanga mijlocului si lungimea din dreapta mijlocului. Nu este necesat sa consideri stari mai mari ca SumLen. Daca exista drum minim intre 2 stari <= SumLen, se va putea ajunge de la una la cealalta mergand prin noduri <= SumLen. Se ajunge dintr-o stare in alta concatenand la stanga si la dreapta. Ordinea in care faci concatenarile nu conteaza. Le vei putea face intotdeauna intr-o ordine astfel incat diferenta dintre partea dreapta si cea stanga sa nu depaseasca SumLen in nicio stare intermediara (poti concatena de fiecare data in jumatatea mai mica daca mai sunt concatenari de facut acolo de exemplu). Dar asta nu te intereseaza in implementare. Pui doar conditia de a ignora muchiile care duc catre stari mai mari ca SumLen.
Memorat
tudorgalatan
Strain
*

Karma: -1
Deconectat Deconectat

Mesaje: 27



Vezi Profilul
« Răspunde #8 : Septembrie 05, 2016, 09:13:26 »

Ce este greșit în această abordare?

Cod:
#include <fstream>
#include <climits>

using namespace std;

bool okay (string s);

string s[4];

string N;
long long int i, j, k;

long long int sol;

int main ()
{
    ifstream fin ("base3.in");
    fin >> s[1] >> s[2] >> s[3];
    fin.close();
    if (okay(s[1]) == 1)
    {
        N = s[1];
        sol = N.length();
    }
    else if (okay(s[2]) == 1)
    {
        N = s[2];
        sol = N.length();
    }
    else if (okay(s[3]) == 1)
    {
        N = s[3];
        sol = N.length();
    }
    else
    {
        i = j = 1;
        N = s[1];
        do
        {
            N += s[j];
            j++;
            if (j == 3)
                j = 1;

        } while (okay(N) == 1);
        sol = N.length();
        i = j = 1;
        N = s[2];
        do
        {
            N += s[j];
            j++;
            if (j == 3)
                j = 1;
        } while (okay(N) == 1);
        if (N.length() < sol)
            sol = N.length();
        i = j = 1;
        N = s[2];
        do
        {
            N += s[j];
            j++;
            if (j == 3)
                j = 1;
        } while (okay(N) == 1);
        if (N.length() < sol)
            sol = N.length();
    }
    ofstream fout ("base3.out");
    fout << sol;
    fout.close();
    return 0;
}

bool okay (string s)
{
    if (s.length()%2 == 0)
        return 0;
    if (s.at(((int)s.length())/2+1) != '1')
        return 0;
    return 1;
}
Memorat
klamathix
Echipa infoarena
Nu mai tace
*****

Karma: 733
Deconectat Deconectat

Mesaje: 1.216



Vezi Profilul
« Răspunde #9 : Septembrie 05, 2016, 13:16:21 »

Salut!

În general nu e prea productiv să postezi cod și să aștepți ca cineva să-ți găsească greșelile. Mai util ar fi să-ți descrii ideea în limbaj natural. Iar cel mai util (dar și mai dificil, ce-i drept) ar fi să te înveți să-ți descoperi singur greșelile. Încearcă să-ți demonstrezi că ideea este corectă, e posibil ca în timp ce faci asta să-ți dai seama care parte din raționament e incorectă. Dacă asta nu funcționează, poți să-ți faci un generator de teste și să-l folosești ca să-ți găsești un contraexemplu.

Spor!  Smile
Memorat
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines