Где изъян в алгоритме из задачи с Codeforces? PascalABC.NET
На соревновании Codeforces Round #662 (Div. 2) попалась задача "Эпплджек и хранилища". Алгоритм я придумал не самый быстрый, но понятный. Реализовав его на языке PascalABC.NET, я отправил его на проверку. Результат - Неправильный ответ на претест 2. Соревнование закончилось два часа назад, до сих пор не могу понять в чём проблема.
Само задание:
Этот год в Эквестрии выдался урожайным, и Эпплджек захотела построить новые хранилища для яблок. По советам проектировщиков фермы она решила построить два хранилища ненулевой площади: одно в форме квадрата, другое в форме прямоугольника (который, возможно, тоже является квадратом).
Хранилища Эпплджек будет строить из досок, на каждую сторону хранилища она собирается потратить ровно одну доску. Доски она может заказать в одной фирме у своего приятеля. Изначально на складе фирмы есть n досок, длины которых Эпплджек известны. Работа фирмы не стоит на месте, она периодически получает заказы и сама заказывает новые доски. Приятель Эпплджек может предоставить ей информацию о всех операциях. Для удобства он будет сообщать информацию в следующем формате:
+ x — на склад поступила доска с длиной x
− x — со склада отгрузили доску с длиной x (при этом гарантируется, что на складе были какие-то доски длины x)
Эпплджек пока не определилась, когда она будет заказывать доски, поэтому она хочет после каждого события на складе знать, может ли она заказать доски, чтобы построить прямоугольное и квадратное хранилища. Эпплджек занята сбором яблок, поэтому у нее нет времени на подсчеты, и она попросила вас помочь ей!
Напоминаем, что у квадрата все четыре стороны равны, а у прямоугольника две пары равных сторон.
Входные данные Первая строка содержит одно целое число n (1≤n≤105) — изначальное количество досок на складе фирмы, вторая строка содержит n целых чисел a1,a2,…,an (1≤ai≤105) — длины досок.
Третья строка содержит одно целое число q (1≤q≤105) — количество событий в фирме. Каждая из следующих q строк содержит описание событий в данном формате: сначала идет тип события (символ + или −), а затем число x (1≤x≤105).
Выходные данные После каждого события на фирме выведите «YES», если из досок на складе фирмы можно собрать два хранилища нужной формы, и «NO» иначе (без кавычек). Вы можете выводить каждую букву в любом регистре (строчную или заглавную).
Пример входные данные
6
1 1 1 2 1 1
6
+ 2
+ 1
- 1
+ 2
- 1
+ 2
выходные данные
NO
YES
NO
NO
NO
YES
Примечание После второго события Эпплджек может построить прямоугольное хранилище из досок с длинами 1, 2, 1, 2 и квадратное хранилище из досок с длинами 1, 1, 1, 1.
После шестого события Эпплджек может построить прямоугольное хранилище из досок с длинами 1, 1, 1, 1 и квадратное хранилище из досок с длинами 2, 2, 2, 2.
Вот сам код:
var
n,q,i,ones,twos:LongInt;
a:array [1..100000] of LongInt;
query:array [1..100000] of string;
yes:boolean;
begin
readln(n);
for i:=1 to n do
read(a[i]);
readln(q);
for i:=1 to q do
readln(query[i]);
for i:=1 to n do
begin
if (a[i] = 1) then
inc(ones)
else
inc(twos);
end;
for i:=1 to q do
begin
if (query[i][1] = '-') then
begin
if (query[i][3] = '1') then
dec(ones)
else
dec(twos);
end
else
begin
if (query[i][3] = '1') then
inc(ones)
else
inc(twos);
end;
yes:= false;
if (ones - 4 >= 0) then
begin
if ((ones - 6 >= 0) and (twos - 2 >= 0)) then
begin
yes:=true;
end
else if ((ones - 8 >= 0) or (twos - 4 >= 0)) then
begin
yes:=true;
end;
end;
if (twos - 4 >= 0) then
begin
if ((ones - 2 >= 0) and (twos - 6 >= 0)) then
begin
yes:=true;
end
else if ((ones - 4 >= 0) or (twos - 8 >= 0)) then
begin
yes:=true;
end;
end;
if (yes) then
writeln('YES')
else
writeln('NO');
end;
end.
Ответы (2 шт):
У вас не правильное представление о вводных почему-то у вас возможны только 1 либо остальные которые вы инкрементируете на каждом введенном не 1.
Решение простое создайте массив а из 105 элементов и инкрементируете а[i] на каждый приход доски длины i или десрементируйте значение a[i] на каждый уход i длины доски соответственно. В итоге проверять существует ли в массиве a элементы у которых значение больше 4 и больше 2 и 2 либо больше 6 и 2 либо больше 8 вот и все
Да, спасибо Aziz Umarov и MBo за ваши ответы. Я не внимательно прочитал задание, а я каждый раз перепроверял свой алгоритм. Можно сделать с помощью:
for i:=1 to n do
begin
inc(planksLength[a[i]]);
end;