inactive

Informatikos olimpiadų atsakymai

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

Dalintis šį pranešimą


Nuoroda iki šio pranešimo
Dalintis per kitą puslapį

„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

Dalintis šį pranešimą


Nuoroda iki šio pranešimo
Dalintis per kitą puslapį

„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

Dalintis šį pranešimą


Nuoroda iki šio pranešimo
Dalintis per kitą puslapį

„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

Dalintis šį pranešimą


Nuoroda iki šio pranešimo
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;
}

 

Dalintis šį pranešimą


Nuoroda iki šio pranešimo
Dalintis per kitą puslapį

„Ž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

Dalintis šį pranešimą


Nuoroda iki šio pranešimo
Dalintis per kitą puslapį

„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;
}

 

Dalintis šį pranešimą


Nuoroda iki šio pranešimo
Dalintis per kitą puslapį

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ų

×   You cannot paste images directly. Upload or insert images from URL.


  • Å iame puslapyje narÅ¡o:   0 nariai

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

  • eneba
  • eneba
  • eneba



  • SuperGames programele
  • SuperGames programele