LMIO X-XII kl. užduočių sprendimai

filmukai.cpp

#include <iostream>
#include <cstdio>
#include <cstdlib>

using namespace std;

typedef struct {
    int pradzia;
    int pabaiga;
} veikla;

int lyginti_trukme(const void *a, const void *b) {
    // funkcija lyginanti filmuku trukme, rikiuoja didejimo tvarka
    // skirta qsort()

    return *((int*)a) -*((int*)b);
}

int daugiausiai_nevirsijant(int laisvas, int *film, size_t n) {
    // apskaiciuoja kiek daugiausiai filmuku bus galima
    // paziureti nevirsijant laisvo laiko
    int laikas = 0;
    int res = 0;
    int i;
    for (i = 0; i<n; i++) {
        laikas += film[i];
        res++;
        if (laikas > laisvas) {
            // cikle leidziame virsyti laisva laika ir stabdome ji tik po to
            // kai jis jau buna pridetas, todel rezultatas turi buti vienu
            // vienetu mazesnis
            return res-1;
        }
    }

    // jei laikas nevirsijamas, graziname neatimdami
    return res;

}

int laisvas_laikas(veikla *veiklos, size_t m) {
    unsigned int i;
    int suma = 0;
    for (i = 0; i < m-1; i++) {
        suma += veiklos[i+1].pradzia - veiklos[i].pabaiga;
    }

    return suma;
}

int main() {
    freopen("filmukai-vyr.in", "r", stdin);
    freopen("filmukai-vyr.out", "w", stdout);

    int n; // filmuku kiekis
    int m; // uzsiemimu kiekis

    int film[100]; // filmuku trukmes
    veikla veiklos[50]; // uzsiemimai

    int laisvas;
    int spes_paziureti;

    int i;

    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d",&film[i]);
    }

    scanf("%d", &m);

    for (i = 0; i < m; i++) {
        scanf("%d %d", &(veiklos[i].pradzia), &(veiklos[i].pabaiga));
    }

    laisvas = laisvas_laikas(veiklos, m);

    // surusiuojame masyva didejimo tvarka
    qsort(film, n, sizeof(int), lyginti_trukme);

    spes_paziureti = daugiausiai_nevirsijant(laisvas, film, n);
    printf("%d\n", spes_paziureti);

    return 0;
}

kryziukai.cpp

#include <iostream>
#include <cstdio>
#include <cmath>

using namespace std;

int kiek_hor(char lentele[5][6], char simbolis, int pozicijos[5]) {
    // patikrina, kiek horizontaliu liniju turi zaidejas (nurodytas "simbolis" X arba O)
    // taip pat iraso horizontaliu liniju pozicijas i masyva pozicijos
    // jei simbolis turi linija toje pozicijoje - irasoma 1, kitaip - 0
    // pvz. jeigu simbolis turi virsutine eilute, masyvas bus: 1 0 0 0 0

    int i;
    int liniju = 0;

    for (i = 0; i < 5; i++) {
        if (lentele[i][0] == simbolis && lentele[i][1] == simbolis &&
            lentele[i][2] == simbolis && lentele[i][3] == simbolis &&
            lentele[i][4] == simbolis) {
            liniju ++;
            if (pozicijos != NULL) {
                pozicijos[i] = 1;
            }
        }
        else {
            if (pozicijos != NULL) {
                pozicijos[i] = 0;
            }
        }
    }

    return liniju;
}

int kiek_vert(char lentele[5][6], char simbolis, int pozicijos[5]) {
    // patikrina, kiek vertikaliu liniju turi zaidejas
    // iraso pozicijas atitinkamai kaip kiek_hor, bet vertikalioms linijoms
    // pvz. jei simbolis turi antra linija nuo kaires, masyvas bus: 0 1 0 0 0
    // jei nereikia poziciju, vietoj treciojo argumento reikia paduoti NULL
    int i;
    int liniju = 0;
    for (i = 0; i < 5; i++) {
        if (lentele[0][i] == simbolis && lentele[1][i] == simbolis &&
            lentele[2][i] == simbolis && lentele[3][i] == simbolis &&
            lentele[4][i] == simbolis) {

            liniju++;
            if(pozicijos != NULL) {
                pozicijos[i] = 1;
            }
        }
        else {
            if (pozicijos != NULL) {
                pozicijos[i] = 0;
            }
        }
    }

    return liniju;
}

int kiek_poziciju(char lentele[5][6], char simbolis) {
    // suskaiciuoja, kiek poziciju (langeliu) lenteleje turi simbolis
    int i, j;
    int res = 0;
    for (i = 0; i < 5; i++) {
        for (j = 0; j < 5; j++) {
            if (lentele[i][j] == simbolis) {
                res++;
            }
        }
    }

    return res;
}

int turi_1_ist(char lentele[5][6], char simbolis) {
    // pirmoji istrizaine - nuo virsaus kaires ([0][0]) baigiant apacios desine ([4][4])
    if (lentele[0][0] == simbolis && lentele[1][1] == simbolis &&
        lentele[2][2] == simbolis && lentele[3][3] == simbolis &&
        lentele[4][4] == simbolis) {
            return 1;
    }

    return 0;
}

int turi_2_ist(char lentele[5][6], char simbolis) {
    // antroji istrizaine - nuo virsaus desines ([0][4]) baigiant apacios kaire ([4][0])
    if (lentele[0][4] == simbolis && lentele [1][3] == simbolis &&
        lentele[2][2] == simbolis && lentele [3][1] == simbolis &&
        lentele[4][0] == simbolis) {
        return 1;
    }

    return 0;
}

int sugadinta_istrizainemis(char lentele[5][6], char simbolis) {
    // funkcija, kuri tikrina, ar galima tureti simbolio turima istrizaine
    // ir vertikalia linija kartu
    // grazina 1, jei sugadinta, 0 - jei ne.

    // jei turi 1-aja istrizaine, tada vienintele galima tureti vertikali linija yra kaire
    // o horizontali - apatine (4)
    int vert[5];
    int hor[5];

    if (turi_1_ist(lentele, simbolis)) {
        if (kiek_vert(lentele, simbolis, vert) == 1) {
            if (vert[0] != 0) {
                return 1;
            }
        }

        if (kiek_hor(lentele, simbolis, hor) == 1) {
            if (hor[4]  != 1) {
                return 1;
            }
        }
        // jei daugiau nei viena vertikali linija - sugadinta
    }

    // jei turi 2-aja istrizaine, analogiskai galima tureti tik desiniausia (paskutine)
    // vertikalia linija, o horizontalia - virsutine (0)

    if (turi_2_ist(lentele, simbolis)) {
        if(kiek_vert(lentele, simbolis, vert) == 1) {
            if (vert[0] != 4) {
                return 1;
            }
        }

        if (kiek_vert(lentele, simbolis, vert) == 1) {
            if (vert[0] != 1) {
                return 1;
            }
        }

    }

    return 0;
}

int laimejo(char lentele[5][6], char simbolis) {
    // patikrina, ar simbolis laimejo zaidima
    // netikrina, ar lentele sugadinta

    if (kiek_hor(lentele, simbolis, NULL) > 0 || kiek_vert(lentele, simbolis, NULL) > 0 ||
        turi_1_ist(lentele, simbolis) || turi_2_ist(lentele, simbolis)) {
            return 1;
    }

    return 0;
}

int sugadinta(char lentele[5][6]) {
    // tikrina, ar lentele sugadinta
    // grazina 1, jei sugadinta, 0 - jei ne.

    // jei X/O skaicius skiriasi daugiau negu vienu
    int skirtumas = kiek_poziciju(lentele, 'X') - kiek_poziciju(lentele, 'O');

    int x_hor[5], x_vert[5]; // x turimu liniju horizontalioms/vertikalioms pozicijoms saugoti
    int o_hor[5], o_vert[5]; // atitinkamai O

    // kryziuku gali buti TIK vienu daugiau nei nuliuku (jei paskutinis buvo X ejimas),
    // arba lygiai su nuliukais (jei paskutinis buvo nuliuku ejimas)
    if (skirtumas != 0 && skirtumas != 1) {
        return 1;
    }

    if (laimejo(lentele,'X') && skirtumas != 1) {
        // jei laimejo X, paskutinis ejimas turejo buti X, todel X turi buti
        // vienu daugiau
        return 1;
    }

    if (laimejo(lentele,'O') && skirtumas != 0) {
        // jei laimejo O, paskutinis jeimas turejo buti O, todel X ir O
        // turi buti po lygiai
        return 1;
    }

    // jei kuris nors zaidejas turi daugiau nei viena horizontalia linija
    if (kiek_hor(lentele, 'X', x_hor) > 1 || kiek_hor(lentele, 'O', o_hor) > 1) {
        return 1;
    }

    // jei kuris nors zaidejas turi daugiau nei viena vertikalia linija
    if (kiek_vert(lentele, 'X', x_vert) > 1 || kiek_vert(lentele, 'O', o_vert) > 1) {
        return 1;
    }

    // jei abu turi po horizontalia linija
    if (kiek_hor(lentele, 'X', x_hor) != 0 && kiek_hor(lentele, 'O', o_hor) != 0) {
        return 1;
    }

    // jei abu turi po vertikalia linija
    if (kiek_vert(lentele, 'X', x_vert) != 0 && kiek_vert(lentele, 'O', o_vert) != 0) {
        return 1;
    }

    // jei visa kita praejo, belieka patikrinti, ar lentele yra kurio nors
    // zaidejo sugadinta istrizainemis
    return (sugadinta_istrizainemis(lentele, 'X') || sugadinta_istrizainemis(lentele, 'O'));
}

int baigta(char lentele[5][6]) {
    // patikrina, ar lentele baigta
    // grazina 1, jei baigta, 0 - jei ne

    int i, j;
    for (i = 0; i < 5; i++) {
        for (j = 0; j < 5; j++) {
            if (lentele[i][j] == '.') {
                return 0;
            }
        }
    }

    return 1;
}

int main() {
    freopen("kryziukai-vyr.in", "r", stdin);
    freopen("kryziukai-vyr.out", "w", stdout);

    char lentele[5][6]; // 5x5 lentele, kiekvienoje eiluteje palikta vieta NUL baitui,
                  // nes scanf iraso i eilute ir ji.

    int i;

    for (i = 0; i < 5; i++) {
        scanf("%5s", lentele[i]);

    }

    //printf("%d %d", kiek_vert(lentele, 'X'), kiek_hor(lentele, 'O'));
    //printf("%d\n", sugadinta(lentele));
    if(sugadinta(lentele)) {
        printf("SUGADINTA\n");
        return 0;
    }

    if (laimejo(lentele, 'X')) {
        printf("X\n");
    }

    else if (laimejo(lentele, 'O')) {
        printf("O\n");
    }

    else {
        // nelaimejo nei vienas. Jeigu lentele baigta - LYGIOSIOS, jei ne - NEBAIGTA
        if (baigta(lentele)) {
            printf("LYGIOSIOS\n");
        }
        else {
            printf("NEBAIGTA\n");
        }
    }

    return 0;
}