Задания
Версия для печати и копирования в MS Word
Тип Д27 C4 № 26999
i

На вход про­грам­мы по­сту­па­ет по­сле­до­ва­тель­ность из N на­ту­раль­ных чисел. Рас­смат­ри­ва­ют­ся все пары раз­лич­ных эле­мен­тов по­сле­до­ва­тель­но­сти, у ко­то­рых раз­лич­ные остат­ки от де­ле­ния на d  =  160 и хотя бы одно из чисел де­лит­ся на p  =  7. Среди таких пар, не­об­хо­ди­мо найти и вы­ве­сти пару с мак­си­маль­ной сум­мой эле­мен­тов.

Опи­са­ние вход­ных и вы­ход­ных дан­ных.

В пер­вой стро­ке вход­ных дан­ных задаётся ко­ли­че­ство чисел N (1 ≤ N ≤ 1000). В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но одно на­ту­раль­ное число, не пре­вы­ша­ю­щее 10000. В ка­че­стве ре­зуль­та­та про­грам­ма долж­на на­пе­ча­тать эле­мен­ты ис­ко­мой пары. Если среди най­ден­ных пар мак­си­маль­ную сумму имеют не­сколь­ко, то можно на­пе­ча­тать любую из них. Если таких пар нет, то вы­ве­сти два нуля.

При­мер вход­ных дан­ных:

4

168

7

320

328

При­мер вы­ход­ных дан­ных для при­ведённого выше при­ме­ра вход­ных дан­ных:

168 320

По­яс­не­ние: Из 4 чисел можно со­ста­вить 6 пар. В дан­ном слу­чае усло­ви­ям удо­вле­тво­ря­ют пары: 168 и 320, 168 и 7, 320 и 7, 328 и 7. Мак­си­маль­ную сумму дает пара 168 и 320.

Тре­бу­ет­ся на­пи­сать эф­фек­тив­ную по вре­ме­ни и по па­мя­ти про­грам­му для ре­ше­ния опи­сан­ной за­да­чи. Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по вре­ме­ни, если при уве­ли­че­нии ко­ли­че­ства ис­ход­ных чисел N в k раз время ра­бо­ты про­грам­мы уве­ли­чи­ва­ет­ся не более чем в k раз. Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по па­мя­ти, если па­мять, не­об­хо­ди­мая для хра­не­ния всех пе­ре­мен­ных про­грам­мы, не пре­вы­ша­ет 1 Кбайт и не уве­ли­чи­ва­ет­ся с ро­стом N.

Мак­си­маль­ная оцен­ка за пра­виль­ную (не со­дер­жа­щую син­так­си­че­ских оши­бок и да­ю­щую пра­виль­ный ответ при любых до­пу­сти­мых вход­ных дан­ных) про­грам­му, эф­фек­тив­ную по вре­ме­ни и по па­мя­ти,  — 4 балла. Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, эф­фек­тив­ную толь­ко по вре­ме­ни  — 3 балла. Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, не удо­вле­тво­ря­ю­щую тре­бо­ва­ни­ям эф­фек­тив­но­сти,  — 2 балла. Вы мо­же­те сдать одну про­грам­му или две про­грам­мы ре­ше­ния за­да­чи (на­при­мер, одна из про­грамм может быть менее эф­фек­тив­на). Если Вы сда­ди­те две про­грам­мы, то каж­дая из них будет оце­ни­вать­ся не­за­ви­си­мо от дру­гой, ито­го­вой ста­нет бо́льшая из двух оце­нок.

Перед тек­стом про­грам­мы обя­за­тель­но крат­ко опи­ши­те ал­го­ритм ре­ше­ния. Ука­жи­те ис­поль­зу­е­мый язык про­грам­ми­ро­ва­ния и его вер­сию.

Спрятать решение

Ре­ше­ние.

От­ме­тим:

m71 самое боль­шое число крат­ное 7;

m72 вто­рое по ве­ли­чи­не число крат­ное 7 и оста­ток от де­ле­ния на 160 не равен остат­ку от де­ле­ния m71 на 160;

m1 самое боль­шое число не крат­ное 7;

m2 вто­рое по ве­ли­чи­не число не крат­ное 7 и оста­ток от де­ле­ния на 160 не равен остат­ку от де­ле­ния m71 на 160.

 

При­мер 1. Про­грам­ма на языке Пас­каль. Про­грам­ма эф­фек­тив­на по вре­ме­ни и па­мя­ти.

 

var 
    n, i, m71, m72, m1, m2, max1, max2, x: integer;
begin
    readln(N);
    m71:=0;
    m72:=0;
    m1:=0;
    m2:=0;
    max1:=0;
    max2:=0;
for i:= 1 to n do begin
    readln(x);
    if (x mod 7 = 0) and (x mod 160 = m71 mod 160) and (x > m71) then
        m71 := x
    else if (x mod 7 = 0) and (x mod 160 <> m71 mod 160) and (x > m71) then
    begin
        m72 := m71;
        m71 := x;
    end
    else if (x mod 7 = 0) and (x mod 160 <> m71 mod 160) and (x > m72) then
        m72 := x
    else if (x mod 7 <> 0) and (x mod 160 = m1 mod 160) and (x > m1) then
        m1 := x  
    else if (x mod 7 <> 0) and (x mod 160 <> m1 mod 160) and (x > m1) then
    begin
        m2 := m1;
        m1 := x;
    end
    else if (x mod 7 <> 0) and (x mod 160 <> m1 mod 160) and (x > m2) then
        m2 := x;   
end;
if (m71 = 0) and (m72 = 0) then
    writeln(0, ' ', 0)
else if (m72 = 0) and (m2 = 0) and (m71 mod 160 = m1 mod 160) then
    writeln(0, ' ', 0)
else
begin
    if (m71+m72)>(max1+max2) then
    begin
        max1 := m71;
        max2 := m72;
    end;
    if ((m71+m1)>(max1+max2)) and (m71 mod 160 <> m1 mod 160) then
    begin
        max1 := m71;
        max2 := m1;
    end;
    if ((m71+m2)>(max1+max2)) and (m71 mod 160 <> m2 mod 160) then
    begin
        max1 := m71;
        max2 := m2;
    end;
    if (((m72 + m1) > (max1 + max2)) and ((m72 mod 160) <> (m1 mod 160))) then
    begin
        max1 := m72;
        max2 := m1;
    end;
    writeln(max1, ' ', max2);
end;
end.

 

При­мер 2. Про­грам­ма на языке Python 3. Про­грам­ма эф­фек­тив­на по вре­ме­ни и па­мя­ти.

 

n = int(input())
m71=0
m72=0
m1=0
m2=0
max1=0
max2=0
for i in range (n):
    x = int(input())
    if (x % 7 == 0) and (x % 160 == m71 % 160) and (x > m71):
        m71 = x
    elif (x % 7 == 0) and (x % 160 != m71 % 160) and (x > m71):
        m72 = m71
        m71 = x
    elif (x % 7 == 0) and (x % 160 != m71 % 160) and (x > m72):
        m72 = x
    elif (x % 7 != 0) and (x % 160 == m1 % 160) and (x > m1):
        m1 = x  
    elif (x % 7 != 0) and (x % 160 != m1 % 160) and (x > m1):
        m2 = m1
        m1 = x
    elif (x % 7 != 0) and (x % 160 != m1 % 160) and (x > m2):
        m2 = x    
if (m71 == 0) and (m72 == 0):
    print(0,0)
elif (m72 == 0) and (m2 == 0) and (m71 % 160 == m1 % 160):
    print(0,0)
else:
    if (m71+m72)>(max1+max2):
        max1 = m71
        max2 = m72
    if (m71+m1)>(max1+max2) and (m71 % 160 != m1 % 160):
        max1 = m71
        max2 = m1
    if (m71+m2)>(max1+max2) and (m71 % 160 != m2 % 160):
        max1 = m71
        max2 = m2
    print(max1,max2)
 

Спрятать критерии
Критерии проверки:

По­яс­не­ния для про­ве­ря­ю­щих.

1. За­да­ние Б яв­ля­ет­ся услож­не­ни­ем за­да­ния А. Если в ка­че­стве ре­ше­ния за­да­ния Б пред­став­ле­но ре­ше­ние за­да­ния А, то со­глас­но при­ведённым ниже кри­те­ри­ям, его оцен­ка будет такой же, как если бы это ре­ше­ние было пред­став­ле­но в ка­че­стве ре­ше­ния за­да­ния А.

2. Два за­да­ния и, со­от­вет­ствен­но, воз­мож­ность для эк­за­ме­ну­е­мо­го пред­ста­вить две про­грам­мы дают уче­ни­ку воз­мож­ность (при его же­ла­нии) сна­ча­ла на­пи­сать менее слож­ное и менее эф­фек­тив­ное ре­ше­ние (за­да­ние А), ко­то­рое даёт ему право по­лу­чить два балла, а затем при­сту­пить к по­ис­ку более эф­фек­тив­но­го ре­ше­ния.

3. Каж­дая из про­грамм, пред­став­лен­ных эк­за­ме­ну­е­мым (но не более двух), оце­ни­ва­ет­ся по ни­же­сле­ду­ю­щим кри­те­ри­ям. В ка­че­стве ито­го­вой оцен­ки берётся наи­боль­шая из двух оце­нок.

 

Кри­те­рии оце­ни­ва­ния вы­пол­не­ния за­да­нияБаллы
Про­грам­ма пра­виль­но ра­бо­та­ет для любых вход­ных дан­ных про­из­воль­но­го раз­ме­ра. Ис­поль­зу­е­мая па­мять не за­ви­сит от ко­ли­че­ства про­чи­тан­ных чисел, а время ра­бо­ты про­пор­ци­о­наль­но этому ко­ли­че­ству.

До­пус­ка­ет­ся на­ли­чие в тек­сте про­грам­мы до трех син­так­си­че­ских оши­бок од­но­го из сле­ду­ю­щих видов:

1) про­пу­щен или не­вер­но ука­зан знак пунк­ту­а­ции;

2) не­вер­но на­пи­са­но или про­пу­ще­но за­ре­зер­ви­ро­ван­ное слово языка про­грам­ми­ро­ва­ния;

3) не опи­са­на или не­вер­но опи­са­на пе­ре­мен­ная;

4) при­ме­ня­ет­ся опе­ра­ция, не­до­пу­сти­мая для со­от­вет­ству­ю­ще­го типа дан­ных.

Если одна и та же ошиб­ка встре­ча­ет­ся не­сколь­ко раз, это счи­та­ет­ся за одну ошиб­ку.

4
Не вы­пол­не­ны усло­вия, поз­во­ля­ю­щие по­ста­вить 4 балла. Про­грам­ма в целом ра­бо­та­ет пра­виль­но для любых вход­ных дан­ных про­из­воль­но­го раз­ме­ра. Время ра­бо­ты про­пор­ци­о­наль­но ко­ли­че­ству введённых чисел, пра­виль­но ука­за­но, какие ве­ли­чи­ны долж­ны вы­чис­лять­ся по ходу чте­ния эле­мен­тов по­сле­до­ва­тель­но­сти чисел.

Ко­ли­че­ство син­так­си­че­ских оши­бок (опи­сок) ука­зан­ных выше видов — не более пяти.

Ис­поль­зу­е­мая па­мять, воз­мож­но, за­ви­сит от ко­ли­че­ства про­чи­тан­ных чисел (на­при­мер, вход­ные дан­ные за­по­ми­на­ют­ся в мас­си­ве или дру­гой струк­ту­ре дан­ных (кон­тей­нер priority_queue, vector, set или map в С++)).

До­пус­ка­ет­ся ошиб­ка при вводе дан­ных, не­вер­ный или не­пол­ный вывод ре­зуль­та­тов или не­вер­ная ра­бо­та про­грам­мы

в «эк­зо­ти­че­ских» си­ту­а­ци­ях. Кроме того, до­пус­ка­ет­ся на­ли­чие одной ошиб­ки, при­над­ле­жа­щей к од­но­му из сле­ду­ю­щих видов оши­бок:

1) ошиб­ка при ини­ци­а­ли­за­ции ми­ни­му­мов;

2) не­вер­но об­ра­ба­ты­ва­ет­ся си­ту­а­ция, когда один или не­сколь­ко ми­ни­и­му­мов не опре­де­ле­ны;

3) до­пу­щен выход за гра­ни­цу мас­си­ва;

4) ис­поль­зу­ет­ся знак < вме­сто <=, or вме­сто and и т. п.

3
Не вы­пол­не­ны усло­вия, поз­во­ля­ю­щие по­ста­вить 3 или 4 балла. Про­грам­ма ра­бо­та­ет в целом верно, эф­фек­тив­но или нет, но, в ре­а­ли­за­ции ал­го­рит­ма есть до двух со­дер­жа­тель­ных оши­бок, до­пу­сти­мые виды оши­бок пе­ре­чис­ле­ны в кри­те­ри­ях на 3 балла. Ко­ли­че­ство син­так­си­че­ских опи­сок не долж­но быть более де­вя­ти. Про­грам­ма может быть не­эф­фек­тив­на по вре­ме­ни. На­при­мер, все числа за­по­ми­на­ют­ся в мас­си­ве и пе­ре­би­ра­ют­ся все воз­мож­ные пары эле­мен­тов по­сле­до­ва­тель­но­сти:

min := 2001;

for i := 1 to N - 1 do begin

for j := i + 1 to N do begin

if ((a[i]+a[j]) mod 2 = 1) and

(a[i]+a[j] < min) then min := a[i]+a[j];

end

end;

2
Не вы­пол­не­ны усло­вия, поз­во­ля­ю­щие по­ста­вить 2, 3 или 4 балла. Из опи­са­ния ал­го­рит­ма или общей струк­ту­ры про­грам­мы видно, что эк­за­ме­ну­е­мый в целом пра­виль­но пред­став­ля­ет путь ре­ше­ния за­да­чи не­за­ви­си­мо от эф­фек­тив­но­сти. При этом про­грам­ма может от­сут­ство­вать или быть пред­став­лен­ной от­дель­ны­ми фраг­мен­та­ми, без огра­ни­че­ний на ко­ли­че­ство оши­бок.1
Не вы­пол­не­ны кри­те­рии, поз­во­ля­ю­щие по­ста­вить 1, 2, 3 или 4 балла0
Мак­си­маль­ный балл4
Источники:
ре­ше­ние Има­е­ва−Зу­бо­вой «Ко­то­лис».
Спрятать решение · КритерииСпрятать критерии · Помощь


О про­ек­те · Ре­дак­ция · Пра­во­вая ин­фор­ма­ция · О ре­кла­ме
© Гущин Д. Д., 2011—2026