Jump to content

Projekto ATGIMIMAS - nepraleisk progos!

Mūsų projektas sėkmingai gyvuoja virš 8 metų, turime 7 išskirtinius serverius, pasižyminčius unikaliomis ir įdomiomis sistemomis, todėl žaidimas čia tampa smagus kiekvienam Counter-Strike 1.6 žaidėjui!

ATGIMIMAS: atnaujinimai, prižiūrėtojų atrankos, naujos paslaugų sistemos galimybės, antras šansas mėgstantiems peržengti taisyklių ribas!

Skaityti plačiau
Sign in to follow this  
Memories

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ų ar šiaip prireiks kokios nors pagalbos, galit kreiptis:
  • pagrindinis šios temos tikslas - pagelbėti žmonėms, kurie tuo domisi, arba galbūt kažką apskritai sudominti programavimu.

Jau išspręsti uždaviniai:

Redaguota nario Memories
  • Patinka 3
  • Confused 1

Share this post


Link to post
Share on other sites

„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 Memories
  • Confused 1

Share this post


Link to post
Share on other sites

„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ėtį 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 Memories
  • Confused 1

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

„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 AxBx, tai sumažinti/padidinti Ay (priklausomai ar Ax < Bx);
    • jeigu Ay = By, tai sumažinti/padidinti Ax (priklausomai ar Ay < By);
    • jeigu AyBy, 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;
}
Redaguota nario Memories

Share this post


Link to post
Share on other sites

„Ž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 ) {
        std::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;
}

Share this post


Link to post
Share on other sites

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

 

  • Patinka 1
  • Confused 1

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  


Mūsų projektas rekomenduoja

×