Mojito Algobadge

Buongiorno a tutti,
sto cercando di risolvere mojito, ma ottengo solo dei punteggi parziali.

Il problema è semplice, e mi sembra di essere riuscito a implementarlo correttamente ma evidentemente mi sto saltando qualcosa.

Un tip?

import java.util.Scanner;

public class mostra {

    private static int T;
    private static long[] turisti;

    private static int G;
    private static long[] guide;

    private static long solve(int tIdx, int gIdx) {
        if (tIdx == T) {
            return 0;
        }
        if (gIdx == G) {
            return T - tIdx;
        }

        if (guide[gIdx] > turisti[tIdx]) {
            return 2 + solve(tIdx + 1, gIdx + 1);
        }
        return solve(tIdx, gIdx + 1);
    }

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

        int cases = in.nextInt();

        for (int t = 1; t <= cases; t++) {
            System.out.print("Case #" + t + ": ");

            T = in.nextInt();
            turisti = new long[T];

            G = in.nextInt();
            guide = new long[G];

            for (int i = 0; i < T; i++) {
                turisti[i] = in.nextLong();
            }

            for (int i = 0; i < G; i++) {
                guide[i] = in.nextLong();
            }

            System.out.println(solve(0, 0));
        }
    }
}

1 Mi Piace

Immagino tu ti riferisca a “mostra” delle terry.
Il programma termina in tempi ragionevoli? La tua ricorsione ha complessità esponenziale e non dovrebbe riuscire a risolvere (in meno di svariati miliardi di anni) casi di input delle dimensioni di questo problema.

Si mi riferisco a mostra delle terry.

Il programma termina in tempi ragionevoli, e potendolo eseguire sulla mia macchina e dovendo sottoporre poi solo l’output finito, non ho problemi di tempo.

Il mio ragionamento è:
Se sono finiti i turisti, le guide restanti non pagano niente quindi restituisco 0.

Se sono finite le guide, i restanti turisti (dati da dimensione dell’array - indice attuale al quale sono arrivato) pagano uno.

Se la guida corrente ha più esperienza del turista corrente, avanzo tutti e due gli indici e faccio pagare 2.

Altrimenti, avanzo solo l’indice della guida, non facendo pagare niente.

Come pensavo avevo mal interpretato il problema LOL

Leggendo la speigazione dell’ultimo test:

Nota che non è possibile cambiare l’ordine delle persone, e in particolare non possiamo far entrare la prima guida col secondo turista e il primo turista con la seconda guida

Avevo pensato non potessi scegliere se saltare un turista ad una guida, ma dopo averlo riletto con più attenzione ho capito cosa volesse dire.

Ok pensavo che stessi implementando la ricorsione giusta (che ci metterebbe molto più della tua intera vita a eseguire). In realtà la ricorsione che hai implementato non funziona perché fai scelte greedy che non sono sempre ottimali.

1 Mi Piace