Member 14710774 Ответов: 2

Учитывая несортированный массив a размером N неотрицательных целых чисел, найдите непрерывный подмассив, который добавляет к заданному числу S.


ВХОД:
Первая строка входных данных содержит целое число T, обозначающее количество тестовых случаев . затем следует T тестовых случаев.каждый случай состоит из двух строк .первая строка каждого тестового случая-N и S. где N-размер aaray, а S-сумма .вторая строка тестового случая содержит N разделенных пробелами интергеров, обозначающих элементы массива.

выход:
для каждого тестового случая в новой строке выведите начальную и конечную позиции(1 индексация) первого такого встречающегося подмассива слева , если сумма равна подмассиву , иначе выведите -1.
ограничения :
1<=T<=100
1<=N<=10^7
1<=A<=10^10
Пример:
вход:
2
5 12
1 2 3 7 5
10 15
1 2 3 4 5 6 7 8 9 10
выход :
2 4
1 5

Что я уже пробовал:

#include <stdio.h>

int main()
{
    int kases;
    scanf("%d", &kases);
    int kase;
    for(kase = 1; kase <= kases; kase++) {
        int  N;
        scanf("%d", &N);
        int result[1000];
        result[0] = 1;
        int length = 1, i, j, temp, carry = 0;
        for(i = 2; i <= N; i++) {
            for(j = 0; j < length; j++) {
                temp = carry + result[j] * i;
                carry = temp / 10;
                result[j] = temp % 10;
            }
            while(carry) {
                result[j] = carry % 10;
                carry /= 10;
                j++;
            }
            length = j;
        }
        for(int i = length - 1; i >= 0; i--){
            printf("%d", result[i]);
        }
        printf("\n");
    }
    return 0;
}

phil.o

В чем заключается ваш вопрос?

Patrice T

А у вас есть проблема или вопрос ?

OriginalGriff

И что же?
Что он делает такого, чего вы не ожидали, или не делает того, что вы сделали?
Что вам надоело выяснять, почему?
Что показал отладчик?
Где ты застрял?
Какая помощь вам нужна?

Используйте виджет "улучшить вопрос", чтобы добавить информацию к вашему вопросу.

Rick York

Вы можете считывать входные данные из файла вместо того, чтобы вводить их каждый раз. Это сделало бы вашу отладку намного быстрее и проще.

2 Ответов

Рейтинг:
2

CPallini

Алгоритм прост, достаточно использовать три переменные:

  • beg - индекс первого элемента искомого подмассива
  • end - индекс последнего элемента подмассива
  • sum - сумма элементов подмассива

1. let beg = 0
2. let sum = array[beg]; end=beg;
3. if sum > S then 
     let beg = beg + 1; goto 2;
   else if sum == S then 
     print( beg + 1, end + 1); exit;
   else // here sum < S
     end = end + 1; sum = sum + array[end]; goto 3;


Угловой случай 'подмассива не найден остается как упражнение.


Patrice T

Слишком добрый
+5

Рейтинг:
0

Patrice T

Я вижу, ваш код даже отдаленно не связан с требованием, у вас нет ни комментариев, ни вопросов. Вы просто хотите, чтобы мы дали вам полное решение для взрыва, чтобы вы могли утверждать, что оно ваше. Это вряд ли произойдет.

Мы не делаем вашу домашнюю работу.
Домашнее задание не предназначено для проверки ваших навыков просить других людей выполнять вашу работу, оно предназначено для того, чтобы заставить вас думать и помочь вашему учителю проверить ваше понимание курсов, которые вы прошли, а также проблем, которые вы испытываете при их применении.
Любая ваша неудача поможет учителю выявить ваши слабости и наметить меры по исправлению положения.
Любая ваша неудача поможет вам узнать, что работает, а что нет, это называется "методом проб и ошибок".
Так что попробуйте, перечитайте свои уроки и приступайте к работе. Если вы застряли на конкретной проблеме, покажите свой код и объясните эту точную проблему, мы можем помочь.

Как программист, ваша задача-создавать алгоритмы это решает конкретные проблемы, и вы не можете полагаться на кого-то другого, чтобы вечно делать это за вас, поэтому есть время, когда вам придется научиться этому. И чем скорее, тем лучше.
Когда вы просто спрашиваете о решении, это похоже на попытку научиться водить машину, обучая кого-то другого.
Создание алгоритма - это в основном поиск математики и необходимая адаптация к вашей реальной проблеме.


CPallini

"Я вижу, ваш код даже отдаленно не связан с требованием"
Это "его последний трюк". :-)

Patrice T

:)