Rezultati

Up. imeNalogaJezikRezultatČas oddaje
jam-2017 Pasavci Java 0/100Prekoračen čas (TLE) 11. maj '17 @ 18:15

Test Točke Porabljen spomin Porabljen čas Status
#1 5/5 37,020 MiB 0,000 s OK
#2 5/5 38,445 MiB 0,000 s OK
#3 5/5 40,098 MiB 0,000 s OK
#4 5/5 36,820 MiB 0,000 s OK
#5 5/5 42,367 MiB 0,000 s OK
#6 5/5 44,684 MiB 0,134 s OK
#7 5/5 49,695 MiB 0,090 s OK
#8 5/5 53,250 MiB 0,141 s OK
#9 6/6 52,234 MiB 0,088 s OK
#10 0/6 76,988 MiB 1,719 s Prekoračen čas
#11 6/6 34,496 MiB 0,000 s OK
#12 6/6 34,875 MiB 0,000 s OK
#13 6/6 39,797 MiB 0,000 s OK
#14 6/6 36,688 MiB 0,000 s OK
#15 6/6 35,113 MiB 0,000 s OK
#16 6/6 37,918 MiB 0,000 s OK
#17 6/6 36,672 MiB 0,000 s OK
#18 0/6 82,137 MiB 1,678 s Prekoračen čas

Ocenjevani program (Pasavci.java):
import java.util.*;

public class Pasavci {
    private static Gen[] geni = new Gen[1005];
    private static String niz;

    private static long MOD = 1000000007;

    public static void main(String[] str) {
        Scanner sc = new Scanner(System.in);

        niz = sc.next();
        geni[1] = readGen(sc.next());
        geni[2] = readGen(sc.next());

        int st_vrstic = sc.nextInt();
        for (int i = 0; i < st_vrstic; i++)
            geni[i + 3] = new Gen(sc.nextInt(), sc.nextInt());

        System.out.println(geni[st_vrstic + 2].x);
    }

    private static class Gen {
        String prvi;
        String zadnji;
        long x;

        Gen(String prvi, String zadnji, int x) {
            this.prvi = prvi;
            this.zadnji = zadnji;
            this.x = x;
        }

        Gen(int prvii, int drugii) {
            Gen prvi = geni[prvii];
            Gen drugi = geni[drugii];
            String skupni = prvi.zadnji + drugi.prvi;
            int sredina = prvi.zadnji.length();

            // dobivanje vmesnega x
            x = 0;
            for (int i = 1; i < niz.length(); i++) {
                int zac = sredina - i;
                int konec = zac + niz.length();
                if (zac < 0) break;
                if (konec > skupni.length()) continue;

                if (skupni.substring(zac, konec).equals(niz))
                    x++;
            }

            x = (prvi.x + x) % MOD;
            x = (drugi.x + x) % MOD;

            if (prvi.prvi.length() >= niz.length())
                this.prvi = prvi.prvi;
            else
                this.prvi = skupni;

            if (drugi.zadnji.length() >= niz.length())
                this.zadnji = drugi.zadnji;
            else
                this.zadnji = skupni;
        }
    }

    private static Gen readGen(String novi) {
        int x = 0;
        for (int i = 0; i < novi.length(); i++) {
            if (i + niz.length() > novi.length()) break;

            if (novi.substring(i, i + niz.length()).equals(niz))
                x++;
        }

        return new Gen(novi, novi, x);
    }
}

/*
UVU
U
V
4
1 2
2 1
3 1
5 4

ccc
abc
ccc
3
1 2
3 2
4 1
 */