Kazicko forumo 2013 užduočių sprendimai

U1.cpp

// Justinas Stankevicius
// Alytaus Jotvingiu giminazija
// "Pirminiai skaiciai"

#include <iostream>
#include <fstream>
#include <cmath>

using namespace std;

// nors a,b <= 5000, apsukus, tarkime, skaiciu 4999, gausime 9994
// kas galetu virsyti ribas
const int MAX = 10000;

int apsukti(int sk) {
    int rez = 0;
    while (sk != 0) {
        rez *= 10;
        rez += sk % 10;
        sk /= 10;
    }
    return rez;
}

bool yra_pirminis(int n) {
    if (n == 1) { return false; }
    int upto = (int) ceil(sqrt((double)n));
    for (int i = 2; i < upto; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

void nulinti(int n, bool table[]) {
    // apnulina masyva (nustato false reiksmes visiems elementams)
    for (int i = 0; i < n; i++) {
        table[i] = false;
    }
}

void pirminiai(int iki, bool lentele[]) {
    // suskaiciuoja pirminius skaicius, ne didesnius nei iki
    // pazymi juos masyve, kur table[n] == true reiskia, kad n
    // yra pirminis skaicius
    for (int i = 2; i < iki; i++) {
        if(yra_pirminis(i)) {
            lentele[i] = true;
        }
    }
}

void fibonaciai(int iki, bool lentele[]) {
    // suskaiciuoja fibonacci skaicius, ne didesnius nei iki
    // pazymi juos masyev, kur table[n] == true reiskia, kad n
    // yra fibonacci sekos narys
    int a = 0;
    int b = 1;
    int tmp;
    while (a < iki) {
        lentele[a] = true;
        tmp = b;
        b = a+b;
        a = tmp;
    }
}

int main() {
    bool primes[MAX];
    bool fibo[MAX];

    ifstream in("U1.txt");
    ofstream out("U1rez.txt");

    int a, b; // reziai
    int rev;

    nulinti(MAX, primes);
    nulinti(MAX, fibo);
    // is anksto apsiskaiciuojame fibonacci ir pirminius skaicius musu reziuose,
    // kad butu galima ypac greitai tikrinti, ar skaicius yra pirminis/fibo
    pirminiai(MAX, primes);
    fibonaciai(MAX, fibo);

    in >> a >> b;
    for (int i = a; i <= b; i++) {
        rev = apsukti(i);
        if (primes[i] && fibo[i] && primes[rev]) {
            out << i << " " << rev << endl;
        }
    }
    in.close();
    out.close();
    return 0;
}

U2.cpp

// Justinas Stankevicius
// Alytaus Jotvingiu gimnazija
// "Vardai"

#include <iostream>
#include <fstream>
#include <iomanip>
#include <map>
#include <vector>
#include <string>

using namespace std;

typedef struct gatve_t {
    string pavadinimas;
    int seimu;
    int paveldimu;
} gatve_t;

typedef struct seima_t {
    int nariu;
    string tetis;
    string mama;
} seima_t;

bool berniukas(string str) {
    // paskutine raide - s
    return str.substr(str.length()-1, 1) == "s";
}

bool jau_yra(string vardas, vector<string> sarasas) {
    for (int i = 0; i < sarasas.size(); i++) {
        if (sarasas[i] == vardas) {
            return true;
        }
    }

    return false;
}

int main() {
    // lenteleje zymesime, kurioje gatveje buvo kokie vardai
    map<string, string> lentele;

    vector<string> m_vardai;
    vector<string> b_vardai;

    gatve_t gatves[20];
    seima_t seima;

    int p_berniukai = 0;
    int p_mergaites = 0;

    ifstream in("U2.txt");

    int n; // gatviu skaicius
    in >> n;

    for (int i = 0; i < n; i++) {
        in >> gatves[i].pavadinimas;
        in >> gatves[i].seimu;
        gatves[i].paveldimu = 0;

        for (int j = 0; j < gatves[i].seimu; j++) {
            bool paveldima;
            string vardas;
            paveldima = false;
            in >> seima.nariu;
            in >> seima.tetis;
            in >> seima.mama;
            for (int l = 0; l < (seima.nariu-2); l++) {
                in >> vardas;
                lentele[gatves[i].pavadinimas] += vardas;
                // zymime visus esamus mergaiciu/berniuku vardus
                if (berniukas(vardas) && !jau_yra(vardas, b_vardai)) {
                    b_vardai.push_back(vardas);
                }
                else if(!berniukas(vardas) && !jau_yra(vardas,m_vardai)) {
                    m_vardai.push_back(vardas);
                }
                // zymime pirmagimi
                if (l == 0) {
                    if (berniukas(vardas)) {
                        p_berniukai++;
                    }
                    else {
                        p_mergaites++;
                    }
                }
                if (vardas == seima.tetis || vardas == seima.mama) {
                    paveldima = true;
                }
            }
            if (paveldima) {
                gatves[i].paveldimu++;
            }


        }
    }

    for (int i = 0; i < n; i++) {
        cout << gatves[i].pavadinimas << " " << gatves[i].paveldimu << endl;
    }
    cout << "Berniukai " << p_berniukai << endl;
    cout << "Mergaites " << p_mergaites << endl;

    int atspausdinta = 0;

    for (int i = 0; i < m_vardai.size(); i++) {
        bool visose = true;
        atspausdinta = 0;
        for (int j = 0; j < n; j++) {
            // jei bent vienoje gatveje neradome vardo, jis nebus visose gatvese
            if (lentele[gatves[j].pavadinimas].find(m_vardai[i]) == -1) {
                visose = false;
                break;
            }
        }
        if (visose) {
            cout << m_vardai[i] << endl;
            atspausdinta++;
        }
    }
    if (atspausdinta == 0) { cout << "NËRA" << endl; }

        for (int i = 0; i < b_vardai.size(); i++) {
        bool visose = true;
        for (int j = 0; j < n; j++) {
            // jei bent vienoje gatveje neradome vardo, jis nebus pasikartojantis
            // visose gatvese
            if (lentele[gatves[j].pavadinimas].find(b_vardai[i]) == -1) {
                visose = false;
                break;
            }
        }
        if (visose) {
            cout << b_vardai[i] << endl;
            atspausdinta++;
        }
    }
    if (atspausdinta == 0) { cout << "NËRA" << endl; }

    return 0;
}

U3.cpp

// Justinas Stankevièius
// Alytaus Jotvingiø gimnazija
// "Zaidimas"

#include <iostream>
#include <fstream>
#include <cstdio>

// eiluteje 5 simboliai, kadangi fscanf prideda ir NUL baità
typedef char lentele_t[4][5];
typedef struct keitimas_t {
    // keitimo duomenys C formatu (koordinates prasideda nuo 0, ne 1)
    int e1;
    int s1;
    int e2;
    int s2;
} keitimas_t;

using namespace std;

bool lenteles_lygios(lentele_t start, lentele_t end) {
    // patikrina, ar lenteles lygios
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (start[i][j] != end[i][j]) {
                return false;
            }
        }
    }
    return true;
}

keitimas_t rasti_keitima(lentele_t start, lentele_t end, int e, int s) {
    bool virsus = true, apacia = true, desine = true, kaire = true;
    keitimas_t keit;
    keit.e1 = e;
    keit.s1 = s;

    // ieskome, su kuriomis pusemis galima daryti keitima - laikomes lentos ribu
    if (s == 0) {
        kaire = false;
    }
    if (s == 3) {
        desine = false;
    }
    if (e == 0) {
        virsus = false;
    }
    if (e == 3) {
        apacia = false;
    }

    // ieskome keitimo, kuris pataisytu nesutapima lentelese
    // jei desineje esantis akmenelis nesutampa su ta pacia pozicija
    // galutineje lenteleje, turbut butu naudinga keisti musu akmeneli
    // butent su juo
    if (desine && (start[e][s+1] != end[e][s+1])) {
        keit.e2 = e;
        keit.s2 = s+1;
    }
    if (kaire && start[e][s-1] != end[e][s-1]) {
        keit.e2 = e;
        keit.s2 = s-1;
    }
    if (virsus && start[e-1][s] != end[e-1][s]) {
        keit.e2 = e-1;
        keit.s2 = s;
    }
    if (apacia && start[e+1][s] != end[e+1][s]) {
        keit.e2 = e+1;
        keit.s2 = s;
    }

    return keit;
}

void keisti(lentele_t start, keitimas_t keit) {
    // funkcija, atliekanti pati akmeneliu sukeitima
    int tmp;

    tmp = start[keit.e1][keit.s1];
    start[keit.e1][keit.s1] = start[keit.e2][keit.s2];
    start[keit.e2][keit.s2] = tmp;
}

void spausdinti_lentele(lentele_t lent) {
    // funkcija, naudota tik klaidu taisymui programos rasymo metu
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            cout << lent[i][j];
        }
        cout << endl;
    }
}

void delioti(lentele_t start, lentele_t end, keitimas_t keitimai[], int &n) {
    // iesko nesutapimu lentelese ir juos tvarko
    keitimas_t keit;
    while(!lenteles_lygios(start,end)) {
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                if (start[i][j] != end[i][j]) {
                    keit = rasti_keitima(start, end, i, j);
                    keisti(start, keit);
                    keitimai[n] = keit;
                    n++;
                }
            }
        }
    }
}

void spausdinti_keitimus(keitimas_t keitimai[], int n) {
    // isvedame kiekviena keitima zmogisku formatu (prie reiksmiu pridedami po 1)
    for (int i = 0; i < n; i++) {
        cout << keitimai[i].e1+1 << " " << keitimai[i].s1+1 << " ";
        cout << keitimai[i].e2+1 << " " << keitimai[i].s2+1 << endl;
    }
}

int main() {
    FILE *in = fopen("U3.txt", "r");

    keitimas_t keitimai[10000];
    int n = 0; // padarytu keitimu skaicius

    lentele_t start, end;
    if (in != NULL) {
        // nuskaitome pradine ir galutine lenteles
        for (int i = 0; i < 4; i++) {
            fscanf(in, "%4s", start[i]);
        }
        for (int i = 0; i < 4; i++) {
            fscanf(in, "%4s", end[i]);
        }
    }

    delioti(start, end, keitimai, n);
    cout << n << endl;
    spausdinti_keitimus(keitimai, n);
}