竞争编码算法

-3

这是一个持续竞争的问题。
https://www.codechef.com/AUG17/problems/CHEFFA 竞争编码算法

鉴于阵列A = (A1, A2, ..., AN)，最初具有N个整数在它。现在对于i ≥ 1, if Ai > 0, Ai+1 > 0和Ai+2存在，则他可以将Ai和Ai+1都减1，并将Ai+2增加1。如果Ai+2不存在，但Ai > 0和Ai+1 > 0，那么他可以将Ai和Ai+1（它将成为数组的当前最后两个元素）减1，并在末尾添加一个新元素，其值为1

使用此操作多次计算A可能生成的不同数组的数量。

假设数组是{2,3,1}：然后：所有可能的排列是：

(2, 3, 1) → (2, 2, 0, 1) 

(2, 2, 0, 1) → (1, 1, 1, 1) 

(1, 1, 1, 1) → (1, 1, 0, 0, 1) 

(1, 1, 0, 0, 1) → (0, 0, 1, 0, 1) 

(1, 1, 1, 1) → (1, 0, 0, 2) 

(1, 1, 1, 1) → (0, 0, 2, 1) 

(2, 3, 1) → (1, 2, 2) 

(1, 2, 2) → (0, 1, 3)

因此，答案是9

注：

我知道，这可使用动态编程完成，但不知道如何，我尝试使用递归，但获得TLE。我不期望完整的解决方案，但一点点的方向是我需要的。

来源

2017-08-08 Ayush Patel

这是目前的[CodeChef挑战]（https://www.codechef.com/AUG17/problems/CHEFFA）。在这里发帖寻求帮助违反了比赛[行为准则]（https://discuss.codechef.com/questions/18662/does-codechef-have-any-code-of-conduct） – Prune

[“有人能帮助我吗？”是不是一个有效的SO问题]（https://meta.stackoverflow.com/questions/284236/why-is-can-someone-help-me-not-an-actual-question）。这通常表明，你需要的是半个小时的时间与当地的导师，或通过一个教程，而不是堆栈溢出。 – Prune

@keyvanvafaee：关于你在这里的编辑，再次有更多报价设备的材料，这不是一个报价。请不要仅将这些添加为装饰。 – halfer

考虑以下伪：

result = 1 
queue = {array} 
while queue is not empty 
    array = queue.pop() 
    n = array.length() 
    for i from 0 to n-2 
     if array[i] * array[i+1] >0 
      temp = array 
      temp[i] -= 1 
      temp[i+1] -= 1 
      temp[i+2] += 1 
      if temp not already present in queue 
       queue.push(temp) 
       result += 1 
    if array[n-1] * array[n-2] >0 
     array[n-1] -= 1 
     array[n-2] -= 1 
     array.push(1) 
     if array not already present in queue 
       queue.push(array) 
       result += 1 
print result

值结果将是可能的阵列的数目。对于大尺寸的数组或大数组值，算法可能效率不高。

来源

2017-08-12 11:43:18

我试过使用listoflists但得到TLE，我很确定它可以使用动态编程来完成 –

竞争编码算法

回答

相关问题