Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиКалендарьОблакоЗаметкиВсе проекты

Помогите пожалуйста решить задачу (написать программу) на PascalABC.NET Буду очень признателен.

Makar Знаток (256), на голосовании 2 месяца назад
Фонари. Вдоль прямой улицы на равном расстоянии располагаются N домов. Будем считать расстояние между домами за единицу длины.

Около каждого дома можно поставить один фонарь. Всего имеется A фонарей, которые могут освещать дома на расстоянии X (включительно), и B фонарей, которые могут освещать дома на расстоянии Y (включительно). В частности, при X=0 или Y=0 такой фонарь освещает только тот дом, у которого он установлен. Вам необходимо расставить минимальное число фонарей так, чтобы все дома были освещены. Один дом может быть освещён несколькими фонарями. Освещать участки улицы между домами необязательно.

Формат входных данных
Первая строка входных данных содержит целое число N (1≤N≤10^5). Следующие четыре строки содержат целые неотрицательные числа A, X, B и Y соответственно, которые не превосходят 105.

Формат выходных данных
Программа должна вывести столько строк, сколько фонарей необходимо установить. Каждая строка должна содержать два целых числа через пробел координату фонаря и расстояние, которое он освещает (то есть одно из чисел X или Y ). Координаты представляют из себя целые числа от 1 до N, рядом с каждым домом можно поставить только один фонарь. При наличии нескольких правильных ответов можно вывести любой из них. Если ответа не существует, программа должна вывести одно число −1.

Система оценки
Решения, правильно работающие при A=0 или B=0, будут оцениваться в 30 баллов.
Решения, правильно работающие при A≠0, B≠0, n≤1000, будут оцениваться в 40 баллов.

Замечание
В ответе к первому примеру фонарь у дома 2 освещает также дома 1 и 3, фонарь у дома 5 также дома 3, 4, 6 и 7, а фонарь у дома 9 также дома 8 и 10. В результате все дома освещены. Во втором примере фонарей недостаточно.
Ввод
10
3
1
1
2
Вывод
2 1
5 2
9 1
Вывод
10
1
1
1
2
Вывод
-1
Голосование за лучший ответ
Артур Терентьев Знаток (369) 3 месяца назад
Для решения этой задачи необходимо расставить фонари таким образом, чтобы минимальное количество из них покрывало все дома. Поскольку фонари могут иметь разные радиусы освещения, нужно учитывать оба типа фонарей и их количество. Стратегия будет заключаться в том, чтобы попытаться сначала покрыть дома фонарями с большим радиусом, а затем заполнить оставшиеся пробелы фонарями с меньшим радиусом.

Вот пример программы на PascalABC.NET , которая решает эту задачу:

```pascal
program StreetLamps;

uses System, System.Collections.Generic;

type
Lamp = record
position: Integer;
range: Integer;
end;

function PlaceLamps(N, A, X, B, Y: Integer): List<Lamp>;
var
lamps: List<Lamp>;
covered: array of Boolean;
i, j: Integer;
begin
lamps := new List<Lamp>();
SetLength(covered, N + 1);

// Сначала пытаемся расставить фонари с большим радиусом
if X < Y then
begin
Swap(A, B);
Swap(X, Y);
end;

// Расставляем фонари с большим радиусом
for i := 1 to N do
begin
if (not covered[i]) and (A > 0) then
begin
// Устанавливаем фонарь такого типа
lamps.Add(Lamp(position := i, range := X));
for j := Max(1, i - X) to Min(N, i + X) do
covered[j] := True;
Dec(A);
end;
end;

// Расставляем фонари с меньшим радиусом
for i := 1 to N do
begin
if (not covered[i]) and (B > 0) then
begin
// Устанавливаем фонарь такого типа
lamps.Add(Lamp(position := i, range := Y));
for j := Max(1, i - Y) to Min(N, i + Y) do
covered[j] := True;
Dec(B);
end;
end;

// Проверяем, освещены ли все дома
for i := 1 to N do
begin
if not covered[i] then
begin
lamps.Clear;
lamps.Add(Lamp(position := -1, range := 0));
Break;
end;
end;

Result := lamps;
end;

var
N, A, X, B, Y, i: Integer;
lamps: List<Lamp>;

begin
ReadLn(N);
ReadLn(A);
ReadLn(X);
ReadLn(B);
ReadLn(Y);

lamps := PlaceLamps(N, A, X, B, Y);

if (lamps.Count = 1) and (lamps[0].position = -1) then
WriteLn(-1)
else
for i := 0 to lamps.Count - 1 do
WriteLn(lamps[i].position, ' ', lamps[i].range);
end.
```

### Объяснение:
1. **Расстановка фонарей с большим радиусом**: Сначала мы пытаемся покрыть как можно больше домов фонарями с максимальным радиусом. Это позволяет минимизировать количество фонарей, так как один фонарь с большим радиусом может покрыть больше домов.

2. **Заполнение пробелов**: После расстановки фонарей с большим радиусом мы используем оставшиеся фонари с меньшим радиусом для покрытия оставшихся неосвещённых домов.

3. **Проверка покрытия всех домов**: После расстановки всех фонарей проверяется, освещены ли все дома. Если нет, выводится -1, что означает невозможность освещения всех домов с имеющимися фонарями.

4. **Вывод результата**: Если все дома освещены, программа выводит позиции и радиусы установленных фонарей.

Обратите внимание, что программа учитывает ограничение на количество фонарей каждого типа и использует их эффективно.
MakarЗнаток (256) 3 месяца назад
спасибо большое
Артур Терентьев Знаток (369) Makar, без б ;)
Похожие вопросы