Неверный ответ в SUBSEQ spoj

Question

Я решал подсчет побочной проблемы в спои, но получаю неправильный ответ. вот ссылка http://www.spoj.com/problems/SUBSEQ/

Вот мой код

#include<stdio.h> 
#include<cmath> 
#include<algorithm> 
int main(){ 
int t,n; 
scanf("%d",&t); 
while(t-->0){ 
    scanf("%d",&n); 
    long arr[n+1]; 
    for(int i=0;i<n;i++){ 
     scanf("%ld",&arr[i]); 
    } 
    long sum=arr[0]; 
    int start=0; 
    long ans=0; 
    for(int i=1;i<=n;i++){ 
     while(sum>47 && start<i-1){ 
      sum-=arr[start]; 
      start++; 
     } 
     if(sum==47) 
      ans+=1; 
     if(i<n) 
      sum+=arr[i]; 
    } 
    printf("%ld\n",ans); 
} 

}

Пожалуйста, помогите мне найти ошибку ..

Answer 1

Вы код не получится следующий тестовый случай (по крайней мере):

1 
4 
47 -47 48 -1 

Ваши программы дают ответ , где в качестве ответа должен быть , где 3 последовательности следующим образом:

47 -47 48 -1 [The entire sequence]

47 [1st element only]

48 -1 [3rd plus 4th elements]

Таким образом, ясно, что у вас есть ошибки.

PS: Кстати, почему вы объявляя массив п + 1 пунктов: long arr[n+1];, когда вы никогда не будут ссылаться на arr[n]? (На самом деле этот пункт даже не существует)

[Edit] #: Добавление пояснений для вышеприведенного использования случай

Как об этом - Его проще, чем вы думаете :-)

1. Сканирование номеров серийно. Для каждого встреченного числа добавьте его к сумме, найденной до сих пор.

2. Сохраните карту количества раз, когда сумма (до сих пор) была найдена.

3. Теперь, чтобы сделать в общей сложности 47, нужно только найти число, которое при вычитании из суммы должно дать число 47. Это необходимо, потому что если мы вычтем такое количество из найденной суммы , это даст 47, полученный из суммирования некоторой последовательности (s) смежных чисел.

Возьмем пример выше, 47 -47 48 -1

1. Инициализировать карту с номером 0, имеющий счетчик = 0 (Это означает, что мы нашли не сумма до сих пор ровно один раз - так как мы в начале)

2. Сканирование списка с самого начала, взять номер 47, сумма до сих пор, скажем, с = 47. Мы делаем 2 вещи:

   • map (47) = 1 (поскольку мы нашли сумму до сих пор = 47 в первый раз).
   • Теперь нам нужно найти количество раз, мы можем найти s-47 = 0 (что равно 1).Итак, ответьте до сих пор = map (0) = 1

3. Сделайте следующий номер, -47. Сумма до сих пор, с = 0

   • карта (0) = 1 до сих пор, так что никакой карты (0) становится = 2
   • Нам нужно найти количество вхождений S-47 = -47. Что = 0. Таким образом, ответ до сих пор = ответа до сих пор + 0 (остается = 1)

4. Возьмите следующий номер, 48, сумма до сих пор, s = 48

   • карта (48) = 1
   • Нам нужно найти количество вхождений s-48 = -1. Что = 0. Таким образом, ответ до сих пор = ответа до сих пор + 0 (остается = 1)

5. Возьмите последний номер, -1, сумма до сих пор, s = 47

   • карты (47) = 1 (на шаге 2.1), так что теперь отображение (47) становится = 2
   • Нам нужно найти число вхождений s-47 = 0. Который = 2 (на шаге 3.1). Поэтому ответ до сих пор = ответ до сих пор + 2 = 3

Так окончательный ответ =

Это должно быть довольно тривиально закодировать это.