Peršokti į turinį
  • ŽAIDIMAI
  • , ŽAIDIMAI
  • ŽAIDIMAI

Informatikos olimpiadų atsakymai


inactive

Ši tema yra neaktyvi. Paskutinis pranešimas šioje temoje buvo prieš 1858 dienas (-ų). Patariame sukurti naują temą, o ne rašyti naują pranešimą.

Už neaktyvių temų prikėlimą galite sulaukti įspėjimo ir pranešimo pašalinimo!

Recommended Posts

Šioj temoj bandysiu pateikti kiekvienos olimpiados (nuo 1989 m.) sprendimus, kurių nėra jau įkeltų C++ kalba (vadinasi, čia nerasit naujausių uždavinių, kadangi šiame tinklalapyje jie yra pateikti su efektyviausiais sprendimais).

Keletas pastabų (jei kam tai aktualu):

  • sprendimai nebūtinai bus patys efektyviausi (kiek leis mano sugebėjimai - tiek bandysiu optimizuoti);
  • stengsiuosi pateikti bent vieną sprendimą į savaitę (priklausomai nuo laisvo laiko ir noro);
  • šalia sprendimų pateiksiu keletą pastabų bei savo mąstymo procesą (jei toks bus);
  • jei kils klausimų dėl uždavinių, galit kreiptis AŽ, Skype ar Discord (nurodyti šioje temoje).

Jau išspręsti uždaviniai:

Redaguota , nario hugegoofus
Nuoroda į komentarą
Dalintis per kitą puslapį

(redaguota)

„Penki skaičiai“ (1989 - 1990 m.) [8 - 12 kl.] [^]

Uždavinio sąlyga: http://www.lmio.mii.vu.lt/?act=getFile&id=197

Mąstymo procesas:

  • pradžioj pabandžiau atrast kažkokį tai pattern'ą tarp tų penkių numerių:
    • iš pavyzdinių skaičių (3, 1, 4, 6, 12) pasiėmiau antrąjį skaičių ir žiūrėjau: galbūt išeitų rasti kokią nors priklausomybę, kad jei 2-asis nuo pradžios skaičius yra mažesnis už 3 likusius skaičius, atsakymas yra, kad toks skaičius (kuris yra didesnis ir mažesnis už 2 skaičius) neegzistuoja;
    • bet ši teorija nepasiteisino, nes tai paneigti galima paprasčiausiai paėmus pirmąjį skaičių (3), vietoj antrojo (1).
  • tada nusprendžiau surikiuoti skaičius didėjančia tvarka: 1, 3, 4, 6, 12;
  • gavus šį variantą, pastebėjau, kad vidurinysis skaičius visada privalo būti didesnis už du pirmuosius ir mažesnis už du antruosius skaičius, kad uždavinio sąlyga būtų patenkinta.

Pastabos:

  • buvo galima naudoti vector'ių, tačiau taip daryti nelabai apsimoka, kadangi mes duomenų skaičių žinome (5), tad nereiks dinamiškai pridėti papildomų elementų;
  • egzistuoja mažiau efektyvesnis, tačiau aiškesnis uždavinio sprendimas (bruteforce metodas): eiti per kiekvieną elementą ir tikrinti, ar jis yra didesnis ir mažesnis už 2 skaičius. Šio algoritmo 'skaičiavimo sudėtingumas' (computational/time complexity) yra O(n²) blogiausiu bei dažniausiu atveju, O(n) - geriausiu, o žemiau pateikto: O(n)/O(1) - geriausiu; O(n²) - blogiausiu/dažniausiu;
  • nenaudojau pointer'ių, kadangi jie prasčiau skaitomi ir su jais kiek sudėtingiau žaistis (šioj situacijoj: norint gauti pradinį (std::begin) ir galutinį (std::end) taškus).

Sprendimas:

#include <fstream>
#include <algorithm>
#include <iterator>


auto ReadData( int ( &nums )[ 5 ] ) -> int ( & )[ 5 ] {
    std::ifstream input( "penki-skaiciai.in" );

    int k;

    for ( unsigned i = 0; 5 != i; ++i ) {
        input >> k;

        nums[ i ] = k;
    }

    input.close();

    return nums;
}


bool ExistsMedian( int ( &nums )[ 5 ] ) {
    std::sort( std::begin( nums ), std::end( nums ) );

    return ( nums[ 2 ] > nums [ 1 ] && nums[ 2 ] < nums[ 3 ] );
}


void WriteData( const bool result ) {
    std::ofstream output( "penki-skaiciai.out" );

    output << ( result ? "YRA" : "NERASTA" );

    output.close();
}


int main() {
    int nums[ 5 ];

    WriteData( ExistsMedian( ReadData( nums ) ) );
}

 

Redaguota , nario hugegoofus
Nuoroda į komentarą
Dalintis per kitą puslapį

(redaguota)

„Sukeičiami skaitmenys“ (1989 - 1990 m.) [8 - 12 kl.] [^]

Uždavinio sąlyga: http://www.lmio.mii.vu.lt/?act=getFile&amp;id=198

Mąstymo procesas:

  • pasiėmęs pavyzdinį skaičių, pabandžiau paimti du didžiausius skaičius ir juos sukeisti vietomis, taip galvodamas, kad radau didžiausią (na, visada pasitaiko durnų minčių, toks gyvenimas);
  • tada ganėtinai greitai užmačiau, kad norint rasti didžiausią skaičių, reikia perkelti didžiausią skaitmenį į priekį;
  • taip susiformulavo pagrindinis uždavinys: sukeisti didžiausią skaitmenį su pirmuoju skaitmeniu;
  • tačiau, kad ir kaip buvo džiugu, mano algoritme atsirado spragų (pasitaikydavo specifinių atvejų (pvz. du vienodi skaitmenys iš eilės, paskutinis skaitmuo yra pats didžiausias ir kiti niuancai), kai jis sugeneruodavo neteisingą atsakymą);
  • nusprendžiau eiti tiesiu keliu:
    • paimti galutinį skaitmenį ir lyginti su kairėje esančiu;
    • jeigu jis (esantis kairėje) didesnis - neapkeičiu;
    • jeigu mažesnis - apkeičiu;
    • vėl tikrinu, ar tas apkeistas skaičius yra didesnis už jo kairėje esantį;
    • jei taip, sugrąžinu visus skaičius į pradinę padėti ir apkeičiu viršuje minėtus skaičius;
    • kartoju, kol praeinu visus skaitmenis;
    • (aišku, įeina ir keletas kitokių patikrinimų).

Pastabos:

  • šio algoritmo skaičiavimo sudėtingumas daugmaž O(n);
  • daugiau kaip ir neliko ką pasakyti:
    • nenaudojau jokių reference, kadangi unsigned int nėra per daug brangus, kad negalėtume turėti jo kopijų;
    • vector'ių naudojau, nes nežinojau, kiek skaitmenų sudarys duotąjį skaičių.

Sprendimas (1-asis variantas (naudoja tris ciklus, tačiau tik du if branch'us ir mažiau kintamųjų)):

#include <fstream>
#include <vector>


unsigned ReadData() {
    std::ifstream input( "sukeiciami-skaitmenys.in" );

    unsigned n;
    input >> n;

    input.close();

    return n;
}


unsigned ComputeMaxNum( unsigned n ) {
    std::vector< unsigned > digits;

    do {
        digits.push_back( n % 10 );
    } while ( ( n /= 10 ) % 10 || n > 0 );

    unsigned maxDigit       = 0;
    unsigned maxIndex       = 0;
    unsigned switchIndex    = 0;
    unsigned index          = 0;

    for ( auto it = digits.begin(), end = digits.end(); it != end; ++it ) {
        index = it - digits.begin();

        if ( *it > maxDigit && index != digits.size() - 1 && *( it + 1 ) <= *it ) {
            maxDigit    = *it;
            maxIndex    = index;
            switchIndex = index + 1;
        } else if ( *it < maxDigit ) {
            switchIndex = index;
        }
    }

    digits[ maxIndex ]      = digits[ switchIndex ];
    digits[ switchIndex ]   = maxDigit;

    unsigned num = 0;

    for ( auto it = digits.end(), end = digits.begin(); it != end; --it ) {
        ( num *= 10 ) += *( it - 1 );
    }

    return num;
}


void WriteData( const unsigned maxNum ) {
    std::ofstream output( "sukeiciami-skaitmenys.out" );

    output << maxNum;

    output.close();
}


int main() {
    WriteData( ComputeMaxNum( ReadData() ) );
}

Sprendimas (2-asis variantas (naudoja du ciklus, tačiau yra 4 if branch'ai ir daugiau kintamųjų)):

#include <fstream>
#include <vector>


unsigned ReadData() {
    std::ifstream input( "sukeiciami-skaitmenys.in" );

    unsigned n;
    input >> n;

    input.close();

    return n;
}


unsigned ComputeMaxNum( unsigned n ) {
    std::vector< unsigned > digits;

    unsigned digit      = n % 10;
    unsigned maxDigit   = digit;
    unsigned oldDigit   = digit;
    unsigned maxIndex   = 0;
    unsigned swapIndex  = 0;
    unsigned oldIndex   = 0;

    do {
        digits.push_back( digit );

        if ( oldDigit > digit || ( !maxIndex && digit >= maxDigit ) ) {
            if ( digit != maxDigit ) {
                swapIndex = digits.size() - 1;
            }

            if ( !maxIndex && digit >= maxDigit ) {
                maxIndex    = ( digit == maxDigit ) ? 0 : digits.size() - 1;
                maxDigit    = digit;
                oldDigit    = digit;
                oldIndex    = maxIndex;
            } else if ( oldDigit > digit && digits[ maxIndex ] != digit ) {
                maxDigit = oldDigit;
                maxIndex = oldIndex;
            }
        } else if ( oldDigit < digit ) {
            oldDigit = digit;
            oldIndex = digits.size() - 1;
        }
    } while ( ( digit = ( n /= 10 ) % 10 ) || n > 0 );

    digits[ maxIndex ]  = digits[ swapIndex ];
    digits[ swapIndex ] = maxDigit;

    unsigned num = 0;

    for ( auto it = digits.end(), end = digits.begin(); it != end; --it ) {
        ( num *= 10 ) += *( it - 1 );
    }

    return num;
}


void WriteData( const unsigned maxNum ) {
    std::ofstream output( "sukeiciami-skaitmenys.out" );

    output << maxNum;

    output.close();
}


int main() {
    WriteData( ComputeMaxNum( ReadData() ) );
}

 

Redaguota , nario hugegoofus
Nuoroda į komentarą
Dalintis per kitą puslapį

  • Parašė po 1 mėnesio...
(redaguota)

„Faktorialo skaidymas“ (1989 - 1990 m.) [8 - 12 kl.] [^]

Uždavinio sąlyga: http://www.lmio.mii.vu.lt/?act=getFile&amp;id=194

Mąstymo procesas:

  • iš pradžių bandžiau tiesiog susidaryt pirminių skaičių masyvą: {1, 3, 5, 7, 11, 13, ...}, tačiau tai nepasiteisino - ranka neišėjo tiek surašyti;
  • tada pasieškojau pirminių skaičių radimo algoritmų ir atradau Sieve of Eratosthenes, tačiau irgi kažkodėl nepasiteisino ir tai man pasirodė ganėtinai keista;
  • nusprendžiau peržvelgt sprendimo kodą Pascal kalba ir atradau įdomų dalyką: jie ima net ir ne pirminius skaičius, o greičiau nelyginius (na, išskyrus 2, su kuriuo yra žaidžiama pradžioj), tad ir aš nusprendžiau pakoreguot savo sprendimą atitinkamai.

Sprendimas:

#include <fstream>

unsigned ReadData() {
    std::ifstream input( "faktorialo-skaidymas.in" );

    unsigned n;
    input >> n;

    input.close();

    return n;
}

unsigned ExpandFactorial( unsigned n ) {
    unsigned k = 1;
    
    for ( ; n; --n ) {
        k *= n;
    }

    unsigned primes = 0;

    while ( !( k % 2 ) ) {
        ++primes;
        k /= 2;
    }

    for ( unsigned i = 3; i <= k; ) {
        if ( !( k % i ) ) {
            k /= i;
            ++primes;
        } else {
            i += 2;
        }
    }

    return primes;
}

void WriteData( const unsigned primes ) {
    std::ofstream output( "faktorialo-skaidymas.out" );

    output << primes;

    output.close();
}

int main() {
    WriteData( ExpandFactorial( ReadData() ) );

    return 0;
}

 

Redaguota , nario hugegoofus
Nuoroda į komentarą
Dalintis per kitą puslapį

„Paprastas kelias“ (1991 - 1992 m.) [8 - 12 kl.] [^]

Uždavinio sąlyga: http://www.lmio.mii.vu.lt/?act=getFile&amp;id=211

Mąstymo procesas:

  • pradžioj galvojau, jog privalu naudoti ciklą ir kiekvienos iteracijos metu vis didinti narių, esančių sekoje, skaičių;
  • remiantis praeita filosofija pradėjau dėlioti įvairius tikrinimus:
    • jeigu Ax Bx, tai sumažinti/padidinti Ay (priklausomai ar Ax < Bx);
    • jeigu Ay = By, tai sumažinti/padidinti Ax (priklausomai ar Ay < By);
    • jeigu Ay  By, tai įvedžiau ciklą, kuris tęsėsi tol, kol Ax < Bx ir Ay < By.
  • bėgant laikui įvedžiau vis daugiau tikrinimų, ir tai tiesiog atrodė per daug ilgas sprendimo būdas;
  • plius, atsirado variantų, kai tas sprendimas nefunkcionuoja, kaip jam priklausytų;
  • po kurio laiko, kažkokiu tai būdo atėjo galvon, kad galima dirbti su koordinačių skirtumų moduliais, tai ir pabandžiau su jais pažaisti:
    • A(2; 9)
    • B(65; 72)
    • difX = |Ax - Bx| = |2 - 65| = 63
    • difY = |Ay - By| = |9 - 72| = 63
    • tada patikrinu, ar skirtumai lygūs arba difX > difY:
      • jeigu taip, narių skaičius lygus difX + 1 (1 yra pradinis blokas (Ax; Ay));
      • jeigu ne, narių skaičius lygus difY + 1.

Pastabos:

  • šio algoritmo skaičiavimo sudėtingumas daugmaž O(n);
  • buvo galima naudoti paprastą, dvinarį masyvą vietoj struktūros (struct), bet man taip buvo patogiau.

Sprendimas:

#include <fstream>
#include <cmath>

struct Coord {
    int x = 0;
    int y = 0;
};

void ReadData( Coord &A, Coord &B ) {
    std::ifstream input( "paprastas-kelias.in" );

    input >> A.x >> A.y;
    input >> B.x >> B.y;

    input.close();
}

unsigned ComputeMembers( const Coord A, const Coord B ) {
    const int difX = std::abs( A.x - B.x );
    const int difY = std::abs( A.y - B.y );

    return 1 + ( ( difX == difY || difX > difY ) ? difX : difY );
}

void WriteData( const unsigned n ) {
    std::ofstream output( "paprastas-kelias.out" );

    output << n;

    output.close();
}

int main() {
    Coord A;
    Coord B;

    ReadData( A, B );
    WriteData( ComputeMembers( A, B ) );

    return 0;
}

 

Nuoroda į komentarą
Dalintis per kitą puslapį

(redaguota)

„Žalioji ateivių planeta“ (2011 m. kovo 27-30 d.) [10 - 12 kl.] [^]

Uždavinio sąlyga: http://www.lmio.mii.vu.lt/?act=getFile&amp;id=223

Mąstymo procesas:

  • iš dalies čia ganėtinai paprasta užduotis, tačiau labai ilga, nes reikalauja daug kintamųjų, eigos apmąstymo ir t.t.;
  • ciklai praktiškai buvo neišvengiama šio uždavinio dalis, kadangi reikėjo tikrinti kiekvieną kvadratą ir dėlioti skaitmenis;
  • pagrinde visą mąstymo proceso dalį užėmė ciklų dėliojimas ir koregavimas pagal logiką, plius teko nusibraižyt lentelę, nes vien vizualinio brėžinio galvoje nepakako.

Pastabos:

  • šio algoritmo skaičiavimo sudėtingumas ... padorus;
  • galimai kurią nors dieną pasistengsiu šį algoritmą supaprastinti/optimizuoti.

Sprendimas:

#include <fstream>
#include <vector>
#include <algorithm>

using std::vector;

using std::sort;

struct Target {
    unsigned x      = 0;
    unsigned y      = 0;
    unsigned length = 0;
    unsigned amount = 0;
};

struct Map {
    unsigned r;
    unsigned c;
    unsigned v;
    
    vector<vector<unsigned>> ores;
};

void ReadData( Map &m ) {
    std::ifstream input( "ateiviai-vyr.in" );

    input >> m.r >> m.c >> m.v;

    for ( unsigned i = 0; i != m.r; ++i ) {
        vector<unsigned> ores;

        unsigned amount;

        for ( unsigned j = 0; j != m.c; ++j ) {
            ores.push_back( ( input >> amount, amount ) );
        }

        m.ores.push_back( ores );
    }

    input.close();
}

Target AnalyseMap( Map &map ) {
    unsigned size       = 2;
    unsigned reached    = 0;
    vector< Target > targets;

    while ( reached < map.v ) {
        for ( unsigned i = 0, end = map.r - size + 1; end != i; ++i ) {
            for ( unsigned j = 0, end = map.c - size + 1; end != j; ++j ) {
                unsigned k = reached = 0;
                Target target;

                while ( k != size ) {
                    reached += map.ores[ i + k ][ j ] + map.ores[ i + k ][ j + 1 ];
                    ++k;
                }

                if ( reached >= map.v ) {
                    target.x        = j;
                    target.y        = i;
                    target.length   = size;
                    target.amount   = reached;

                    targets.push_back( target );
                }
            }
        }

        ++size;
    }

    sort( targets.begin(), targets.end(), []( const Target &lhs, const Target &rhs ) { return lhs.amount > rhs.amount; } );
    sort( targets.begin(), targets.end(), []( const Target &lhs, const Target &rhs ) { return lhs.amount >= rhs.amount && lhs.y < rhs.y; } );
    sort( targets.begin(), targets.end(), []( const Target &lhs, const Target &rhs ) { return lhs.amount >= rhs.amount && lhs.y < rhs.y && lhs.x < rhs.x; } );

    return targets[ 0 ];
}

void WriteData( const Target &target ) {
    std::ofstream output( "ateiviai-vyr.out" );

    output << target.x << " " << target.y << " " << target.length << " " << target.amount;

    output.close();
}

int main() {
    Map map;

    ReadData( map );
    WriteData( AnalyseMap( map ) );

    return 0;
}

 

Redaguota , nario hugegoofus
Nuoroda į komentarą
Dalintis per kitą puslapį

  • Parašė po 3 mėnesių...

„Lygybė“ (1991 - 1992 m.) [8 - 12 kl.] [^]

Uždavinio sąlyga: http://www.lmio.mii.vu.lt/?act=getFile&amp;id=213

Mąstymo procesas:

  • nelabai toks ir buvo, tiesiog nusprendžiau sudaryti keturis ciklus (po vieną kiekvienai raidei) ir tikrinti, ar tų skaitmenų reprezentacijų suma ketvirtuoju yra lygi skaičiui, gautam iš tų skaitmenų.

Sprendimas:

#include <fstream>
#include <cmath>

void WriteData( unsigned k ) {
    std::ofstream output( "lygybe.out" );
    output << k << std::flush;
    output.close();
}

unsigned FindK() {
    unsigned k = 0;

    for ( unsigned a = 1; 10 != a; ++a ) {
        for ( unsigned b = 0; 10 != b; ++b ) {
            for ( unsigned c = 0; 10 != c; ++c ) {
                for ( unsigned d = 0; 10 != d; ++d ) {
                    k = 1000 * a + 100 * b + 10 * c + d;

                    if ( k == std::pow( a + b + c + d, 4 ) ) {
                        return k;
                    }
                }
            }
        }
    }

    return 0;
}

int main() {
    WriteData( FindK() );

    return 0;
}

 

Nuoroda į komentarą
Dalintis per kitą puslapį

Ši tema yra neaktyvi. Paskutinis pranešimas šioje temoje buvo prieš 1858 dienas (-ų). Patariame sukurti naują temą, o ne rašyti naują pranešimą.

Už neaktyvių temų prikėlimą galite sulaukti įspėjimo ir pranešimo pašalinimo!

Prisijungti prie diskusijos

Palikti atsakymą galite iš karto, o užsiregistruoti vėliau. Jeigu jau turite paskyrą mūsų forume, Prisijunkite.

Svečias
Atsakyti šioje temoje...

×   Įklijuotas tekstas turi teksto formatavimą.   Pašalinti teksto formatavimą

  Galimi tik 75 veidukai.

×   Nuoroda buvo automatiškai įterpta.   Įterpti nuorodą paprastai

×   Jūsų ankstesnis pranešimas buvo atkurtas.   Išvalyti redaktorių

×   Jūs negalite įkelti nuotraukas tiesiogiai.Įkelkite arba įdėkite nuotraukas iš URL.

  • Šiame puslapyje naršo:   0 nariai

    • Nėra registruotų narių peržiūrinčių šį forumą.

Skelbimai


×
×
  • Sukurti naują...