Mojito Algobadge

Aiuto
1

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
2

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.

3

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.

4

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.

5

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