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;
}
Но я не знаю, какой алгоритм здесь должен быть.
brosok1[i]
доbrosok2[i]
включительно.kegli
(даже не из интов, а изbool
), и в одном большом цикле читать информацию о бросках и менять вектор. А потом в еще одном цикле выводить ответ.