Qual è l'approccio corretto per risolvere SPOJ DIEHARD?

Question

Stavo cercando di risolvere una domanda di pratica su SPOJ https://www.spoj.pl/problems/DIEHARD/. Tuttavia, entrambi i miei avidi approcci hanno portato a una risposta errata e la ricorsione era troppo lenta per il caso peggiore. Qualcuno può dire come affrontare questo problema? Sto cercando qualcuno che mi indichi la giusta direzione.

Il gioco è semplice. All'inizio hai una quantità di salute "H" e una quantità di armatura "A". In qualsiasi momento puoi vivere in uno qualsiasi dei tre luoghi: fuoco, acqua e aria. Dopo ogni unità di tempo, devi cambiare il tuo luogo di vita. Ad esempio, se attualmente stai vivendo un incendio, puoi passare all'acqua o all'aria.

• Se fate un passo in aria, la vostra salute aumenta di 3 e la vostra armatura aumenta di 2
• Se fate un passo in acqua, la vostra salute diminuisce di 5 e la vostra armatura diminuisce di 10
  Se fate un passo nel fuoco , la vostra salute diminuisce di 20 e la vostra armatura aumenta di 5

Se la vostra salute o armatura diviene < = 0, si muore all'istante

Trova il tempo massimo si può sopravvivere.

ingresso:

La prima linea si compone di un numero intero t, il numero di casi di test. Per ogni caso di test ci saranno due interi positivi che rappresentano la H iniziale e la salute iniziale armatura A.

uscita:

Per ogni caso di prova a trovare il tempo massimo che si può sopravvivere.

Answer 1

Hai provato DFS? Lo stato è una tupla di (aria | fuoco | acqua, H, A). Questo ha:

3 * 1000 * 1000 = 3,000,000 game states 

Fare un DFS su di esso e trovare le mosse più alte. (Cioè impostare tutto a stati -1 e l'iniziale a 0, poi DFS da 0 Stati di tutte le posizioni raggiungibili)

Answer 2

Ecco un altro modo per farlo analiticamente:

a = number of times visiting air state 
F = number of times visiting fire state 
W = number of times visiting water state 

M = a + F + W // total moves 

// positive 
a >= 0 
F >= 0 
W >= 0 

// because of the restriction of moving between states... 
a <= F + W + 1 
F <= W + a + 1 
W <= a + F + 1 

// the effect of armor and health... 
H < -3a + 5H + 20F 
A < -2a + 10W - 5F 

Massimizzare M. Si può fare questo tramite la ricerca binaria di M, oppure è possibile utilizzare la programmazione lineare.

La ricerca binaria ciclo:

int ok = 0; 
int impossible = 1000000000; 
while (impossible - ok > 1) 
{ 
    int candidate = ok + (impossible-ok)/2; 

    if (check(candidate)) 
     ok = candidate; 
    else 
     impossible = candidate; 
} 
return ok; 

In entrambi i casi l'uso di base di algebra liceo per semplificare l'disuguaglianze/equazione.

Answer 3

Ho fatto utilizzando la programmazione dinamica. Dp [salute] [armatura] [aria/fuoco/acqua] - è il tempo massimo che si può vivere se si inizia da questa condizione quindi le condizioni ricorrenti diventano semplicemente Dp [salute] [armatura] [aria/fuoco/acqua ] = 1 + max degli stati successivi puoi andare a Ovvio che il caso base è quando non può andare da nessuna parte così la risposta diventa zero.

Answer 4

Okay, prima prova a risolverlo con un approccio avido. È ovvio che l'aria è la scelta migliore possibile in quanto aumenta sia l'armatura che la salute ma si può andare in aria solo alternativamente. Quindi ogni mossa dispari (cioè 1,3,5 ...) sarà in onda. Ora dobbiamo decidere cosa fare con le mosse pari?

Quindi abbiamo due scelte Fuoco o acqua? Dobbiamo essere ragionevoli e scegliere una tale mossa che mantenga sia H che A sopra 0. Ora saltare nel fuoco costa salute -20 anche se aumenta l'armatura di 5, ma hey aspetta, a che serve l'armatura aumentata se non lo fai? ottenere la vostra salute> 0. Quindi se H> 5 e A> 10 scelgono l'acqua.

Ora, se siamo a corto di armature ma abbiamo abbastanza salute? In tal caso non abbiamo altra scelta che saltare al fuoco.

così ora abbiamo un approccio greedy:

Quindi, se abbiamo H e sufficiente, andremo ad acqua. Altrimenti, se H è sufficiente e A non è sufficiente, andare al fuoco. Altrimenti, è finita!

ecco il link Ideone di realizzazione: http://ideone.com/rkobNK

#include<stdio.h> 
int main(){ 
    long long int x,i,a,b,t,h,arm; 
    scanf("%lld",&x); 
    for(i=0;i<x;i++){ 
     scanf("%lld %lld",&a,&b); 
     if(a==0||b==0) 
     printf("0\n"); 
     else{ 
      t=1; 
      h=a+3; 
      arm=b+2; 
      while(1){ 
       if(h>5&&arm>10){ 
        h=h-2; 
        arm=arm-8; 
        t=t+2; 
       }else if(h>20&&arm<=10){ 
        h=h-17; 
        arm=arm+7; 
        t=t+2; 
       }else { 
        printf("%lld\n",t); 
        break; 
       } 
      } 
    } 
    } 
    return 0; 
}