Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.83/6: Рейтинг темы: голосов - 6, средняя оценка - 4.83
0 / 0 / 0
Регистрация: 12.05.2022
Сообщений: 64
1

Получается неправильный ответ,немног­о запутался в коде

15.08.2022, 17:33. Показов 1208. Ответов 10

Author24 — интернет-сервис помощи студентам
Всем привет,решал задачу с курса и кажись немного запутался в своем же коде,помогите пожалуйста.
Условие:
Сумма подряд идущих
Дан массив целых чисел a[1],a[2],...,a[n] и натуральные числа k и m. Укажите минимальное значение i, для которого a[i]+a[i+1]+...+a[i+k]=m (то есть сумма k+1 подряд идущих элементов массива равна m). Если такого значения нет, то выведите 0.

Входные данные

На вход программе сначала подаются значения n, k и m (m⩽109, 0<k<n⩽105, n — количество элементов в массиве). В следующей строке входных данных расположены сами элементы массива — целые числа, по модулю не превосходящие 100.

Выходные данные

Выведите ответ на задачу.
Мой код:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, k, m,o;
    cin >> n >> k >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    vector<int> p(n + 1);
    p[0] = 0;
    for (int i = 1; i <= n; ++i)
    {
        p[i] = p[i - 1] + a[i - 1];
    }
     vector<int> p1(n - k);
    p1[0] = p[k+1]-p[0];
    for (int i = 1; i <= n; ++i)
    {
        p1[i]=p[k+i+1]-p[i];
      
    }
    for (int i = n-k; i <=0; i++)
    {
          if (p1[i]==m)
        {
          o=i;  
        }else
        {
            o=0;
        }
        
    }
    cout<<o;
}
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
15.08.2022, 17:33
Ответы с готовыми решениями:

Блокировка интерфейса pyside (Qt) при реализации многопоточны­­­­х приложений
Здравствуйте. Реализовал приложение для опроса (пинговки) серверов, при помощи TCP запросов....

STEAM VR , Liv, синхронизаци­­­­­­­я видео в реальности и Vr( tilt brush )
Здравствуйте, у меня задача настроить качественную запись видео художника рисующего в vr ( в...

Видеорегиста­­­тор NVR8016
Здравствуйте Помогите сбросить пароль на видеорегистаторе NVR8016

Неисправност­­­ь планок SDRAM?
Из того, что нашлось в закромах, получилась ретросборка на мат. плате с 370-м сокетом, докупил к...

10
687 / 444 / 209
Регистрация: 18.10.2020
Сообщений: 1,606
15.08.2022, 22:33 2
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include <iostream>
#include <fstream>
#include <ctime>
using namespace std;
 
void create(int n, const char* FileName = "input.txt")
{
    ofstream fout; fout.open(FileName);
    fout << n << " " << 2000 << " " << (rand() * 3) % 2000 << "\n";//здесь тоже нужно будет поменять на что-то в ваших диапазонах чисел (10^5 и 10^9)
    for (int i = 0; i < n; i++)
        fout << rand() % 2 + 1 << "\n";//здесь меняем на rand() % 201 - 100
    fout.close();
}
 
int main()
{
    srand(time(NULL));
    //create(rand() * 3);//это что-то не превосходящее 100000
    ifstream fin; fin.open("input.txt");
    int n, m, k;
    fin >> n >> m >> k;
 
    int* arr = new int[n];
 
    for (int i = 0; i < n; i++)
        fin >> arr[i];
    fin.close();
 
    int sum = 0, i = 0;
    for (i = 0; i <= k; i++)
        sum += arr[i];
 
    for (; i < n; i++)
    {
        sum += arr[i];
        if (sum == m)
            break;
        else
            sum -= arr[i - k - 1];
    }
 
    if (sum == m)
    {
        cout << "i0 = " << i - k - 1 << "  and  " << "ik = " << i << "\n";
        //sum = 0;
        //for (int j = i - k - 1; j <= i; j++)
        //  cout << arr[j] << "\n"; sum += arr[j];
        //
        //cout << sum << "  " << m;
    }
    else
        cout << "0\n";
    delete[] arr;
    cin.get();
    return 0;
}
пример input, при котором находит участок
Вложения
Тип файла: zip input.zip (11.9 Кб, 0 просмотров)
1
Just Do It!
3841 / 2288 / 636
Регистрация: 23.09.2014
Сообщений: 7,073
Записей в блоге: 2
15.08.2022, 22:48 3
вар:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <vector>
 
int sumk(std::vector<int>& a, int k)
{   int s = 0; for(int i = 0; i < k; ++i) s += a[i]; return s;
}
 
int main()
{
    int n; std::cin >> n;
    int k; std::cin >> k;
    int m; std::cin >> m;
 
    std::vector<int> a(n); for (auto& e : a) std::cin >> e;
 
    int res = sumk(a, k);
 
    for(int i = 0, j = k; j < n; ++i, ++j)
    {
        if(res == m) { std::cout << i; return 0; }
           res -= a[i];
           res += a[j];
    }
 
    std::cout << 0;
}
2
Just Do It!
3841 / 2288 / 636
Регистрация: 23.09.2014
Сообщений: 7,073
Записей в блоге: 2
15.08.2022, 22:57 4
Цитата Сообщение от programmer_08 Посмотреть сообщение
#include <fstream>
можно без этой либы.

пишешь батник run.bat:
Код
main.exe < test.txt
pause
пишешь текст с тестом test.txt:
Код
12 3 6 
1 2 2 2 3 4 1 2 2 2 3 4
в одну папку складываешь:
Код
main.exe
test.txt
run.bat
жмакаешь run.bat

смотришь рез:
Получается неправильный ответ,немног­о запутался в коде

названия у мя отличаются ибо набирал рандомно.

Данный тест пройден успешно!

main.exe - код выше
1
0 / 0 / 0
Регистрация: 12.05.2022
Сообщений: 64
15.08.2022, 23:22  [ТС] 5
Цитата Сообщение от programmer_08 Посмотреть сообщение
void create(int n, const char* FileName = "input.txt")
{
    ofstream fout; fout.open(FileName);
    fout << n << " " << 2000 << " " << (rand() * 3) % 2000 << "\n";//здесь тоже нужно будет поменять на что-то в ваших диапазонах чисел (10^5 и 10^9)
    for (int i = 0; i < n; i++)
        fout << rand() % 2 + 1 << "\n";//здесь меняем на rand() % 201 - 100
    fout.close();
}
Здравствуйте,не понял зачем эта функция

Добавлено через 2 минуты
Цитата Сообщение от XLAT Посмотреть сообщение
if(res == m) { std::cout << i; return 0; }
           res -= a[i];
           res += a[j];
Объясните пожалуйста что тут происходит
0
Just Do It!
3841 / 2288 / 636
Регистрация: 23.09.2014
Сообщений: 7,073
Записей в блоге: 2
15.08.2022, 23:49 6
Цитата Сообщение от Rezu Посмотреть сообщение
Объясните пожалуйста что тут происходит
подряд идущие k элементов это как змейка длины k.
Голова у ней j, а хвост i

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

на каждом таком шаге проверяем её массу всех текущих k чисел её тела с числом m

если равно то выводим этот номер шага на консоль.

Добавлено через 6 минут
Цитата Сообщение от Rezu Посмотреть сообщение
a[i]+a[i+1]+...+a[i+k]=m
Цитата Сообщение от Rezu Посмотреть сообщение
сумма k+1
C++
16
    int res = sumk(a, ++k);
поправил.
0
0 / 0 / 0
Регистрация: 12.05.2022
Сообщений: 64
16.08.2022, 00:25  [ТС] 7
Ого,понял,спасибо большое,короткое и красивое решение,но он почему то все равно не проходит тесты
0
Just Do It!
3841 / 2288 / 636
Регистрация: 23.09.2014
Сообщений: 7,073
Записей в блоге: 2
16.08.2022, 00:53 8
Лучший ответ Сообщение было отмечено Rezu как решение

Решение

Цитата Сообщение от Rezu Посмотреть сообщение
но он почему то все равно не проходит тесты
покажи тесты

Добавлено через 5 минут
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <iostream>
#include <vector>
 
typedef signed long long T;
 
T sumk(std::vector<T>& a, T k)
{   T s = 0; for(T i = 0; i < k; ++i) s += a[i]; return s;
}
 
int main()
{
    T n; std::cin >> n;
    T k; std::cin >> k;
    T m; std::cin >> m;
 
    std::vector<T> a(n); for (auto& e : a) std::cin >> e;
 
    if(++k > n) { std::cout << 0; return 0; }
 
    T res = sumk(a, k);
 
    for(T i = 0, j = k; j < n; ++i, ++j)
    {
        if(res == m) { std::cout << i; return 0; }
           res -= a[i];
           res += a[j];
    }
 
    std::cout << 0;
}
0
687 / 444 / 209
Регистрация: 18.10.2020
Сообщений: 1,606
16.08.2022, 01:55 9
Цитата Сообщение от Rezu Посмотреть сообщение
Здравствуйте,не понял зачем эта функция
создание файла с входными данными (чтобы не руками) для теста.

Добавлено через 4 минуты
к слову программу нврн можно оптимизировать по кол-ву сохраняемых данных... держать в памяти не все n, а только k+1 член, ну мб чуть больше...

Добавлено через 1 минуту
и тесты могут не проходиться, если там результат выводится не так как нужно, нврн
0
Вездепух
Эксперт CЭксперт С++
11694 / 6373 / 1723
Регистрация: 18.10.2014
Сообщений: 16,057
16.08.2022, 01:59 10
Цитата Сообщение от Rezu Посмотреть сообщение
C++
1
2
3
    vector<int> a(n);
    vector<int> p(n + 1);
    int m[n - k];
Ничего не понял. Зачем в такой элементарной задаче аж три массива?

И почему два первых объявлены через std::vector, а третий внезапно - обычным массивом с неконстнатным размером (что в С++ не разрешается)?
0
0 / 0 / 0
Регистрация: 12.05.2022
Сообщений: 64
16.08.2022, 13:18  [ТС] 11
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
Ничего не понял. Зачем в такой элементарной задаче аж три массива?
В первый массив записываем числа,что даются в условии,во второй массив сумму n чисел от начала,а в третий массив используя суммы от начала получаем суммы k+1 чисел(но в этом коде много ошибок).
Цитата Сообщение от TheCalligrapher Посмотреть сообщение
а третий внезапно - обычным массивом с неконстнатным размером (что в С++ не разрешается)
Изначально я сделал так,но после компиляции меня выводило в новую вкладку,и код работал неправильно

Добавлено через 2 минуты
неизвестно какие тесты,но их 33

Добавлено через 3 минуты
Цитата Сообщение от XLAT Посмотреть сообщение
покажи тесты
Немного подкорректил код и он теперь проходит 17 тестов из 33(там просто происходил небольшой сдвиг и я добавил 1,чтобы он сместился вправо)

Добавлено через 35 минут
Все,я решил не добавлять новый массив,а просто проверил в цикле с помощью условия,и код прошел.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n, k, o = 0;
    cin >> n >> k;
    int m;
    cin >> m;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }
    vector<int> p(n + 1);
    p[0] = 0;
    for (int i = 1; i <= n; ++i)
    {
        p[i] = p[i - 1] + a[i - 1];
    }
    for (int i = 0; i < n; i++)
    {
        if (p[i + k] - p[i-1] == m)
        {
            o = i;
            cout << o;
            return 0;
        }
    }
 
    cout << o;
    return 0;
}
0
16.08.2022, 13:18
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
16.08.2022, 13:18
Помогаю со студенческими работами здесь

Аналог register_nex­t_step_handl­er в Google Apps Script
Добрый день. На Python в библиотеке pytelegrambotapi через register_next_step_handler() есть...

Как сделать аутентификац­ия по SMS без пароля с использовани­ем Xamarin
Здравствуйте подскажите пожалуйста, как можно сделать чтобы когда пользователь вводил номер...

Может ли EF Core актуализиров­ать информацию, посмотрев на ContextModel­Snapshot?
Доброго времени суток, дотнетчики! Возникла следующая проблема - зафакапил truncate'ом некоторые...

Выяснить сюръективнос­­­­­ть/инъективност­­­­­ь отображения по матрице
Линейное отображение из 3-мерного линейного пространства в 4-мерное задано матрицей А. Выяснить,...

MutationObse­rver не перехватывае­т программные события
Подскажите пожалуйста, вот ставлю MutationObserver на элемент к примеру ввода. Затем просто веду...

stm32f030r8t­­­6
Здравстуйте. Вопрос: какие библиотеки надо использовать, чтобы LCD1602A принимал текст от...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
11
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru