-1

N кеглей выставили в один ряд, занумеровав их слева направо числами от 1 до N. Затем по этому ряду бросили K шаров, при этом i-й шар сбил все кегли с номерами от li до ri включительно. Определите, какие кегли остались стоять на месте.

Формат входных данных:

Программа получает на вход количество кеглей N и количество бросков K. Далее идет K пар чисел li, ri, при этом 1 ≤ li, ri ≤ N.

Формат выходных данных:

Программа должна вывести последовательность из N символов, где j-й символ есть “I”, если j-я кегля осталась стоять, или “.”, если j-я кегля была сбита.

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

10 3
8 10
2 5 
3 6

Ответ:

I.....I...

#include <iostream>
#include <vector>
using namespace std;

int main() {
    char d1 = 'I';
    char d2 = '.';

    int n, k;
    cin >> n;
    cin >> k;

    vector<int> kegli(n);
    vector<int> brosok1(k);
    vector<int> brosok2(k);
    vector<char> konec(n);

    for (int i = 0; i < k; i++) {
        cin >> brosok1[i];
        cin >> brosok2[i];
    }

    for (int i = 0; i < n; i++)
        kegli[i] = i + 1;

    for (int i = 0; i < k; i++) {
        kegli[brosok1[i] - 1] = 0;
        kegli[brosok2[i] - 1] = 0;
        kegli[brosok1[i]] = 0;
    }

    for (int j = 0; j < n; j++) {
        if(kegli[j] != 0)
            kegli[j] = 1;
    }

    for (int j = 0; j < n; j++) {
        if (kegli[j] == 1)
            konec[j] = d1;
        else if (kegli[j] == 0)
            konec[j] = d2;
    }

    for (auto temp : konec)
        cout << temp;

    return 0;
}

Верный ответ на первый тест я смог получить, но дальнейшие тесты проваливаются. Думаю, что дело в этом цикле:

for (int i = 0; i < k; i++) {
    kegli[brosok1[i] - 1] = 0;
    kegli[brosok2[i] - 1] = 0;
    kegli[brosok1[i]] = 0;
}

Но я не знаю, какой алгоритм здесь должен быть.

8
  • Не понял, откуда эти три присваивания. Там должен быть вложенный цикл, от brosok1[i] до brosok2[i] включительно. 11 янв 2020 в 17:16
  • @HolyBlackCat сейчас попробую реализовать
    – Nikita
    11 янв 2020 в 17:18
  • Плюс, в коде много лишнего. Достаточно взять один вектор - kegli (даже не из интов, а из bool), и в одном большом цикле читать информацию о бросках и менять вектор. А потом в еще одном цикле выводить ответ. 11 янв 2020 в 17:18
  • @HolyBlackCat у меня не выходит сделать это, можете помочь?
    – Nikita
    11 янв 2020 в 17:33
  • Покажите вашу попытку. Или нет, ниже уже ответили... 11 янв 2020 в 17:49

1 ответ 1

1

Вроде, вот, попробуйте. Вместо того, чтобы сохранять данные и т.п. и т.д., будем делать всё одновременно.

#include <iostream>
#include <vector>

int main() {
    size_t n, k;
    std::cin >> n >> k;

    std::vector<bool> skittles(n);

    for (size_t i = k; i > 0; i--) {
        size_t dropped_a, dropped_b;

        std::cin >> dropped_a >> dropped_b;

        // Чтобы соблюсти индексирование с нуля, уменьшим dropped_a
        // И в условии поставим оператор <
        for (size_t x = --dropped_a; x < dropped_b; x++)
            skittles[x] = true;
    }

    for (const bool& skittle : skittles)
        std::cout << (skittle ? '.' : 'I');

    std::cout << std::endl;
}

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.