Форум программистов, компьютерный форум CyberForum.ru

Нужно сконструировать алгоритм задачи - C++

Восстановить пароль Регистрация
 
Nexia
0 / 0 / 0
Регистрация: 06.06.2013
Сообщений: 8
06.06.2013, 11:18     Нужно сконструировать алгоритм задачи #1
Добрый день.
Задача: Отрезок числовой оси от 0 до 109 покрашен в белый цвет. Затем некоторые части этого отрезка были покрашены в чёрный, затем некоторые снова в белый и так далее. В общей сложности было сделано N перекрашиваний (1 ≤ N ≤ 5000). Ваша задача — найти самый длинный белый интервал после заданной последовательности перекрашиваний.
Исходные данные
В первой строке записано единственное число N. Следующие N строк содержат информацию о перекрашиваниях. Каждая из этих строк имеет вид:
ai bi ci
где ai и bi — целые числа, а ci — символ 'b' или 'w', ai, bi, ci разделены пробелами.
Эта тройка параметров определяет перекрашивание отрезка от ai до bi в цвет ci ('w' — белый, 'b' — чёрный). Вы можете считать, что 0 < ai < bi < 109.
Результат
Выведите через пробел два числа x и y (x < y), определяющие начало и конец самого длинного белого интервала. Если существует множество интервалов такой длины, выведите самый левый из них (с наименьшим x).



Расскажите как решать и чем пользоваться для более рационального решения
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.06.2013, 11:18     Нужно сконструировать алгоритм задачи
Посмотрите здесь:

C++ сконструировать класс
C++ Подскажите алгоритм решения задачи
C++ Алгоритм решения задачи
Алгоритм решения олимпиадной задачи C++
Нужно составить алгоритм задачи! C++
Итерационный алгоритм. Прикладные задачи математики! C++
Не могу понять алгоритм задачи C++
C++ Неправильный алгоритм задачи с массивом

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nexia
0 / 0 / 0
Регистрация: 06.06.2013
Сообщений: 8
07.06.2013, 12:01  [ТС]     Нужно сконструировать алгоритм задачи #2
не могу уместиться в массив:
C++
1
int mass[1000000000]
Что делать?
Гром
 Аватар для Гром
199 / 118 / 10
Регистрация: 20.03.2009
Сообщений: 1,075
Записей в блоге: 15
07.06.2013, 12:36     Нужно сконструировать алгоритм задачи #3
Зачем вам вообще такой массив?
Алгоритм достаточно прямолинейный. Берем массив длины 110 из булевых значений. Если i-й элемент массива равен true - считаем ячейку, например, белой; если false - соответственно черной. Изначально все элементы равны true. Затем N раз вызываем функцию перекрашивания - примерно такую:
C++
1
2
3
4
5
6
7
8
9
void color(int* arr, size_t a, size_t b, char c)
{
if (c == 'w')
 for (size_t i = a; i < b; ++i)
  arr[i] = true;
else
 for (size_t i = a; i < b; ++i)
  arr[i] = false;
}
Затем проходим по перекрашенному массиву и ищем там белые куски, считая длину каждого. Если длина текущего больше максимальной длины - запоминаем ее (а также начало этого куска) как новое максимальное.
Yandex
Объявления
07.06.2013, 12:36     Нужно сконструировать алгоритм задачи
Ответ Создать тему
Опции темы

Текущее время: 23:03. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru