Ois_biglietti 30/100

Salve a tutti, ho provato a risolvere il problema con questo algoritmo:

#include <bits/stdc++.h>
using namespace std;

int compra(int N, int M, int A, int B){
    int ans = 0;
        if(N <= M){
            if(N * A < B)
                ans = N * A;
            else
                ans  = B;    
        }
        else{
            int resto = N - M;
            
            if(N * A < B + A * resto)
            ans = N * A;
            else
                if(B + A * resto < B + resto * B)
                ans = B + A * resto;
                else
                ans = B + resto * B;
                
        }
    return ans;
    
}

int main(){
    
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    int N, M, A, B;
    fin >> N >> M >> A >> B;
    fout << compra(N, M, A, B);

    return 0;
}

Non riesco a prendere 100/100 per colpa di 4 subtask. Le subtask sono 013, 014, 018, 021
Qualcuno ha qualche idea? Grazie in anticipo.

Non ho compreso del tutto la logica del tuo programma, però mi sembra che questo if:

if(B + A * resto < B + resto * B)

non sia corretto, perché può portare ad un risultato sbagliato quando B < A.

Con questo input:

10 5 2 1

il risultato è 2, ma il tuo programma stampa 6.

Effettivamente riguardandolo non ha molto senso, ho provato a cambiare soluzione ma mi da comunque qualche errore:

#include <bits/stdc++.h>
using namespace std;

int compra(int N, int M, int A, int B){
    int ans = 0;
    
    if(N <= M){
            if(N * A < B)
                ans = N * A;
            else
                ans  = B;    
    }
    else{
        
        do{
            if(N >= M){
                ans += B;
                N -= M;     
            }
            else{
                if(B <= A){
                    ans += B;
                    N -= M;
                }
                else{
                    ans += A;
                    N--;
                }
                    
            }
                
        }while(N > 0);
       
        
    }
    return ans;
}

int main(){
    
    ifstream fin("input.txt");
    ofstream fout("output.txt");
    int N, M, A, B;
    
    fin >> N >> M >> A >> B;
    
    fout << compra(N, M, A, B);

    return 0;
}

Con il tuo input il risultato è corretto, purtroppo però non riesco ad arrivare a 100.

Prova con l’input 8 5 9 10. La risposta dovrebbe essere 20 ma il tuo codice ritorna 37.
Il problema è che nel do-while:

  1. Assumi che sia sempre vantaggioso comprare un carnet se mancano almeno M viaggi

  2. Non stai moltiplicando il costo del biglietto per il numero di biglietti da comprare quando mancano meno di M viaggi

1 Mi Piace

Grazie, finalmente sono riuscito a prendere 100/100!