Тип Д27 C4 № 11327 
Программирование. Поиск основного подмножества экспериментальных значений
i
На вход даны пары чисел. Нужно выбрать из каждой пары по одному числу так, чтобы сумма всех выбранных чисел не была кратна 4 и при этом была максимально возможной. Напишите программу, выводящую такую сумму на экран. Если же ее невозможно получить, выведите 0. Баллы начисляются за ту из подзадач, что решена на большее количество баллов. Задача А дает 2 балла, задача Б - 4 балла. В задаче А приведите неэффективный алгоритм. При решении указывайте, какую подзадачу делаете. За алгоритм, неэффективный по времени ИЛИ памяти, дается 3 балла, по времени И памяти - 2 балла.
Задача А. Количество пар известно заранее и равно 6. Числа не превышают 30 000.
Задача Б. Количество пар N не известно заранее и может принимать значения 2 <= N <= 200 000. На вход подается сначала количество пар, затем сами пары. Числа по модулю не превышают 30 000.
Решение. Из математики известно, что при сложении чисел их остатки от деления на число складываются, а при вычитании — вычитаются. Из каждой пары чисел нужно выбрать максимальное и их сложить.
Если эта сумма будет делиться на 4; одно из слагаемых надо заменить на его пару так, чтобы сумму всё равно не делилась на 4. Найдём сумму S максимальных чисел из пар и наименьшую разность (max - min) не делящуюся на 4. Тогда если сумма делится на 4 достаточно вычесть эту разность. Если и сумму найти не удаётся, выведем 0.
Задание Б.
Приведём пример решения на языке C++
#include <io stream>
using namespace std;
int main()
{ int N;
int s, a, b, raznost, max = -60001;
cin >> N; s = 0;
for(int i=1; i<=N; i++)
{ cin >> a >> b;
if(a > b)
{ s+=a; raznost=b-a;}
else {s+=b; raznost=a-b;}
if((raznost > max)&&(raznost%4!=0))
max = raznost;
}
if(s%4==0)
{if(max==-10001)
count<<0;
else
count << s+max;
}
else count << S;
return 0;
}
Задание Б.
Приведём пример решения на языке Паскаль:
var
i, n, x, y, sum, min_r: longint;
begin
readln(n);
min_r:=10001;
sum:=0;
for i:=1 to n do
begin
readln(x,y);
if x > y then sum:=sum + x else sum:= sum + y;
if (abs(x - y) mod 4 <> 0) and (abs(x - y) < min_r) then min_r:= abs(x - y);
end;
if (sum mod 4 <> 0) then writeln(sum) else
if (sum mod 4 = 0) and (min_r <> 10001) then writeln (sum - min_r) else writeln(0);
end.
Приводим эффективное решение Игоря Кудашева на Python 3.
n = int(input())
d = 30001
s = 0
for i in range(n):
a, b = map(int, input().split())
ma = max(a, b)
mi = min(a, b)
if (ma - mi) % 4 != 0 and ma - mi < d: d = ma - mi
s += ma
if s % 4 == 0:
if d == 30001: s = 0
else: s -= d
print(s)
Критерии проверки:| Критерии оценивания выполнения задания | Баллы |
|---|
Программа правильно работает для любых входных данных произвольного размера и находит ответ, не сохраняя входные данные в массиве. Допускается наличие в тексте программы одной синтаксической ошибки: пропущен или неверно указан знак пунктуации, неверно написано или пропущено зарезервированное слово языка программирования, не описана или неверно описана переменная, применяется операция, недопустимая для соответствующего типа данных (если одна и та же ошибка встречается несколько раз, то это считается за одну ошибку). | 4 |
Не выполнены условия, позволяющие поставить 4 балла, при этом программа работает верно, время работы линейно зависит от N, но размер используемой памяти зависит от количества точек. Например, входные данные запоминаются в массиве или другой структуре данных, размер которой соответствует числу N. Допускается одна из следующих ошибок. 1. Пропущенная или неверная инициализация количества точек. В некоторых языках и системах программирования (например, в Бейсике) все переменные после создания имеют значение 0. В этом случае отсутствие инициализации нельзя считать ошибкой. 2. Неверные сравнения, в результате которых учитываются точки, лежащие на осях координат. 3. Учёт одного треугольника несколько раз из-за разной последовательности перечисления вершин (например, отсутствие деления на 2 в решении, аналогичном приведённому выше). 4. Учёт треугольников, содержащих одну и ту же вершину дважды (например, отсутствие вычитания в решении, аналогичном приведённому выше). Допускается наличие от одной до трёх синтаксических ошибок, описанных в критериях на 4 балла. | 3 |
Не выполнены условия, позволяющие поставить 3 или 4 балла, при этом программа работает верно, эффективно или нет. В частности, в 2 балла оцениваются переборные решения, в которых все исходные данные сохраняются в массиве, рассматриваются все возможные треугольники, из которых выбираются подходящие. Допускается наличие нескольких содержательных ошибок, описанных в критериях на 3 балла, и до пяти синтаксических ошибок, описанных в критериях на 4 балла. | 2 |
| ННе выполнены условия, позволяющие поставить 2, 3 или 4 балла, но программа работает в отдельных частных случаях. | 1 |
| Не выполнены критерии, позволяющие поставить 1, 2, 3 или 4 балла | 0 |
| Максимальный балл | 4 |
PDF-версии: