एसपीओजे डायहार्ड को हल करने का सही तरीका क्या है?

Question

मैं एसपीओजे https://www.spoj.pl/problems/DIEHARD/ पर एक अभ्यास प्रश्न हल करने की कोशिश कर रहा था। हालांकि मेरे लालची दृष्टिकोण दोनों के परिणामस्वरूप गलत जवाब और बुरी स्थिति के लिए रिकर्सन बहुत धीमी थी। क्या कोई इस समस्या से कैसे संपर्क कर सकता है? मैं किसी को सही दिशा में इंगित करने के लिए ढूंढ रहा हूं।

खेल सरल है। शुरुआत में आपके पास 'एच' स्वास्थ्य की मात्रा और 'ए' कवच की मात्रा है। किसी भी पल में आप तीनों स्थानों में से किसी एक में रह सकते हैं - आग, पानी और हवा। प्रत्येक इकाई के समय के बाद, आपको अपनी जिंदगी की जगह बदलनी होगी। उदाहरण के लिए यदि आप वर्तमान में आग में रह रहे हैं, तो आप या तो पानी या हवा में कदम उठा सकते हैं।

• आप हवा में कदम है, तो 3 से आपके स्वास्थ्य बढ़ जाती है और 2
• करके अपने कवच बढ़ जाती है कि आप पानी में कदम है, तो 5 से आपके स्वास्थ्य कम हो जाती है और 10
  करके अपने कवच कम हो जाती है आप आग में कदम तो 20 से आपके स्वास्थ्य कम हो जाती है और 5

करके अपने कवच बढ़ जाती है आपके स्वास्थ्य या कवच < = 0 हो जाता है, तो आप मर जाएगा तुरन्त

अधिक से अधिक समय आप जीवित रह सकते हैं का पता लगाएं।

इनपुट:

पहली पंक्ति एक पूर्णांक टी के होते हैं, परीक्षण के मामलों की संख्या।

प्रत्येक परीक्षा मामले के लिए अधिक से अधिक समय आप जीवित रह सकते हैं लगता है: प्रत्येक परीक्षा मामले के लिए वहाँ दो सकारात्मक प्रारंभिक स्वास्थ्य एच और प्रारंभिक कवच ए

आउटपुट का प्रतिनिधित्व पूर्णांकों हो जाएगा।

Answer 1

आप डीएफएस की कोशिश की है? राज्य एक ट्यूपल (वायु | आग | पानी, एच, ए) है। इसमें है:

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

उस पर एक डीएफएस करें और उच्चतम चाल खोजें। (यानी सब पहुंच योग्य पदों के लिए 0 राज्यों से 0 -1 और प्रारंभिक राज्यों को सब कुछ निर्धारित करते हैं, तो डीएफएस)

Answer 2

यहाँ एक और तरीका यह विश्लेषणात्मक करना है:

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 

अधिकतम एम आप क्या कर सकते हैं यह एम के लिए बाइनरी खोज द्वारा, या आप रैखिक प्रोग्रामिंग का उपयोग कर सकते हैं।

द्विआधारी खोज पाश:

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; 

या तो मामले में बुनियादी उच्च विद्यालय बीजगणित का उपयोग असमानताओं/समीकरण सरल करने के लिए।

Answer 3

मैंने डायनामिक प्रोगोगिंग का उपयोग करके किया था। डी पी [स्वास्थ्य] [कवच] [हवा/आग/पानी] - अधिक से अधिक समय आप रह सकते हैं यदि आप इस हालत से शुरू तो बार-बार होने की स्थिति बस डी पी [स्वास्थ्य] [कवच] [हवा/आग/पानी बन है ] = 1 + अगले राज्यों में से अधिकतम आप पर जा सकते हैं स्पष्ट रूप से बेस केस तब होता है जब वह कहीं भी नहीं जा सकता है, इसलिए इसका उत्तर शून्य हो जाता है।

Answer 4

ठीक है, सबसे पहले लालची दृष्टिकोण से इसे हल करने का प्रयास करें। यह स्पष्ट है कि वायु सबसे अच्छा विकल्प संभव है क्योंकि यह कवच और स्वास्थ्य दोनों को बढ़ाता है लेकिन आप केवल हवा में ही जा सकते हैं। तो हर विषम (यानी 1,3,5 ...) चाल हवा के लिए होगा। अब हमें तय करना है कि चाल के साथ क्या करना है?

तो हमारे पास दो विकल्प हैं आग या पानी? हमें उचित होना चाहिए और ऐसे कदम को चुनना है जो एच और ए दोनों को 0 से ऊपर रखता है। अब अग्नि में कूदने से स्वास्थ्य -20 खर्च होता है, भले ही यह 5 तक कवच बढ़ाता है, लेकिन हे इंतजार है, बढ़ते कवच का उपयोग क्या है यदि आप ' आपका स्वास्थ्य प्राप्त नहीं करें> 0। तो अगर एच> 5 और ए> 10 पानी का चयन करें।

अब क्या होगा यदि हम कवच से कम हैं लेकिन पर्याप्त स्वास्थ्य है? उस स्थिति में हमारे पास आग पर कूदने के अलावा कोई विकल्प नहीं है।

तो, अगर हमारे पास पर्याप्त एच और एक है, हम पानी के लिए जाना होगा:

तो अब हम एक लालची दृष्टिकोण है। अन्यथा, यदि एच पर्याप्त पर्याप्त है और ए पर्याप्त नहीं है, तो आग पर जाएं। अन्यथा, यह खत्म हो गया है! 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; 
}