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

Дед Мороз и Сне­гу­роч­ка при­хо­дят на дет­ские утрен­ни­ки с меш­ком кон­фет. Дед Мороз делит кон­фе­ты по­ров­ну между всеми при­сут­ству­ю­щи­ми детьми (детей на утрен­ни­ке ни­ко­гда не бы­ва­ет боль­ше 100), а остав­ши­е­ся кон­фе­ты от­да­ет Сне­гу­роч­ке. Сне­гу­роч­ка каж­дый раз за­пи­сы­ва­ет в блок­нот ко­ли­че­ство по­лу­чен­ных кон­фет. Если кон­фе­ты раз­де­ли­лись между всеми детьми без остат­ка, Сне­гу­роч­ка ни­че­го не по­лу­ча­ет и ни­че­го не за­пи­сы­ва­ет. Когда утрен­ни­ки за­кон­чи­лись, Деду Мо­ро­зу стало ин­те­рес­но, какое число чаще всего за­пи­сы­ва­ла Сне­гу­роч­ка. Дед Мороз и Сне­гу­роч­ка  — вол­шеб­ные, по­это­му число утрен­ни­ков N, на ко­то­рых они по­бы­ва­ли, может быть очень боль­шим. На­пи­ши­те про­грам­му, ко­то­рая будет ре­шать эту за­да­чу. Перед тек­стом про­грам­мы крат­ко опи­ши­те ал­го­ритм ре­ше­ния за­да­чи и ука­жи­те ис­поль­зу­е­мый язык про­грам­ми­ро­ва­ния и его вер­сию.

 

Вам пред­ла­га­ет­ся два за­да­ния с по­хо­жи­ми усло­ви­я­ми: за­да­ние А и за­да­ние Б. Вы мо­же­те ре­шать оба за­да­ния или одно из них по сво­е­му вы­бо­ру. За­да­ние Б более слож­ное, его ре­ше­ние оце­ни­ва­ет­ся выше. Ито­го­вая оцен­ка вы­став­ля­ет­ся как мак­си­маль­ная из оце­нок за за­да­ния А и Б.

 

За­да­ние А. Име­ет­ся набор чисел, со­сто­я­щий из 10 пар по­ло­жи­тель­ных целых чисел. В этом ва­ри­ан­те за­да­ния оце­ни­ва­ет­ся толь­ко пра­виль­ность про­грам­мы, время ра­бо­ты и раз­мер ис­поль­зо­ван­ной па­мя­ти не имеют зна­че­ния.

Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му – 2 балла.

 

За­да­ние Б. Име­ет­ся набор дан­ных, со­сто­я­щий из пар по­ло­жи­тель­ных целых чисел. По­ста­рай­тесь сде­лать про­грам­му эф­фек­тив­ной по вре­ме­ни и ис­поль­зу­е­мой па­мя­ти (или хотя бы по одной из этих ха­рак­те­ри­стик).

Про­грам­ма счи­та­ет­ся эф­фек­тив­ной по вре­ме­ни, если время ра­бо­ты про­грам­мы про­пор­ци­о­наль­но ко­ли­че­ству пар чисел N, т. е. при уве­ли­че­нии N в k раз время ра­бо­ты про­грам­мы долж­но уве­ли­чи­вать­ся не более чем в k раз.

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

Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, эф­фек­тив­ную по вре­ме­ни и па­мя­ти,  — 4 балла.

Мак­си­маль­ная оцен­ка за пра­виль­ную про­грам­му, эф­фек­тив­ную по вре­ме­ни, но не­эф­фек­тив­ную по па­мя­ти,  — 3 балла.

 

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

В пер­вой стро­ке вво­дит­ся одно целое по­ло­жи­тель­ное число  — ко­ли­че­ство утрен­ни­ков N. Каж­дая из сле­ду­ю­щих N строк со­дер­жит два целых числа: сна­ча­ла D  — ко­ли­че­ство при­шед­ших на оче­ред­ной утрен­ник детей, а затем K – ко­ли­че­ство кон­фет в мешке Деда Мо­ро­за на этом утрен­ни­ке. Га­ран­ти­ру­ет­ся вы­пол­не­ние сле­ду­ю­щих со­от­но­ше­ний:

1 ≤ N ≤ 10000

1 ≤ D ≤ 100 (для каж­до­го D)

D ≤ K ≤ 1000 (для каж­дой пары D, K)

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

Про­грам­ма долж­на вы­ве­сти одно число  — то, ко­то­рое Сне­гу­роч­ка за­пи­сы­ва­ла чаще всего. Если не­сколь­ко чисел за­пи­сы­ва­лись оди­на­ко­во часто, надо вы­ве­сти боль­шее из них. Если Сне­гу­роч­ка ни разу ни­че­го не за­пи­сы­ва­ла, надо вы­ве­сти ноль.

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

7

10 58

15 315

20 408

100 1000

32 63

32 63

11 121

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

31

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

Ре­ше­ние.

По­сколь­ку ко­ли­че­ство детей не пре­вы­ша­ет 100, остать­ся может не боль­ше 99 кон­фет. Можно со­здать мас­сив из 99 эле­мен­тов и ис­поль­зо­вать их в ка­че­стве счётчи­ков, хра­ня­щих ин­фор­ма­цию о ко­ли­че­стве за­пи­сей

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

 

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

 

program c4;

const DMAX=100; {мак­си­маль­но воз­мож­ное ко­ли­че­ство детей}

var

N: integer; {ко­ли­че­ство утрен­ни­ков}

D: integer; {ко­ли­че­ство детей на утрен­ни­ке}

K: integer; {ко­ли­че­ство кон­фет}

r: integer; {оста­ток}

c: array[1..DMAX-1] of integer; {счет­чи­ки остат­ков}

i: integer;

imax: integer;

begin

{пред­ва­ри­тель­ная очист­ка счет­чи­ков}

for i:=1 to DMAX-1 do c[i]:=0;

readln(N);

{ввод дан­ных, под­счет ко­ли­че­ства каж­до­го остат­ка}

for i:=1 to N do begin

readln(D, K);

r := K mod D;

if r>0 then c[r]:=c[r]+1;

end;

{выбор са­мо­го ча­сто­го остат­ка}

imax:=1;

for i:=2 to DMAX-1 do begin

if c[i]>=c[imax] then imax:=i;

end;

if c[imax]=0 then imax:=0;

writeln(imax);

end.

 

При­мер ре­ше­ния за­да­чи А на языке Пас­каль.

 

var
  D: integer; {ко­ли­че­ство детей на утрен­ни­ке}
  K: integer; {ко­ли­че­ство кон­фет}
  r: array[1..10] of integer; {остат­ки}
  inf: array[1..10, 1..2] of integer; {ис­ход­ные дан­ные}
  val: integer; {самый ча­стый оста­ток}
  max_lenght: integer;
  i, j, c, lenght: integer;
begin
  for i := 1 to 10 do begin
    read(D, K);
    inf[i, 1] := D;
    inf[i, 2] := K;
  end;
  for i := 1 to 10 do r[i] := inf[i, 2] mod inf[i, 1];
  for i := 1 to 10 do
    for j := 1 to 10-i do
      if r[j]      c := r[j];
      r[j] := r[j+1];
      r[j+1] := c;
    end;
  max_lenght := 0;
  lenght := 1;
  val := r[1];
  for i := 1 to 9 do
    if r[i]=r[i+1] then
      lenght := lenght + 1
    else begin
      if lenght>max_lenght then begin
        max_lenght := lenght;
        val := r[i];
      end;
      lenght := 1;
    end;
  writeln(val);
end.
Спрятать критерии
Критерии проверки:

Кри­те­рии оце­ни­ва­ния вы­пол­не­ния за­да­нияБаллы
По­яс­не­ния для про­ве­ря­ю­щих.

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

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

3. При­ведённые в п. 2.1–2.5 пра­ви­ла имеют целью из­бе­жать сни­же­ния оцен­ки из-за того, что уче­ник пе­ре­пу­тал обо­зна­че­ния за­да­ний

Кри­те­рии оце­ни­ва­ния за­да­ния А
При ре­ше­нии за­да­чи A про­грам­ма верно на­хо­дит тре­бу­е­мую сумму

для любых 6 пар ис­ход­ных дан­ных. До­пус­ка­ет­ся до пяти син­так­си­че­ских и при­рав­нен­ных к ним оши­бок (см. кри­те­рии оце­ни­ва­ния за­да­ния Б на 4 балла)

2
Не вы­пол­не­ны усло­вия, поз­во­ля­ю­щие по­ста­вить 2 балла. Из опи­са­ния ал­го­рит­ма и общей струк­ту­ры про­грам­мы видно, что эк­за­ме­ну­е­мый в целом пра­виль­но пред­став­ля­ет путь ре­ше­ния за­да­чи. До­пус­ка­ет­ся любое ко­ли­че­ство «опи­сок»1
Не вы­пол­не­ны кри­те­рии, поз­во­ля­ю­щие по­ста­вить 1 или 2 балла0
Мак­си­маль­ный балл для за­да­ния А2

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

Про­грам­ма может со­дер­жать не более трёх син­так­си­че­ских оши­бок сле­ду­ю­щих видов:

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

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

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

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

К син­так­си­че­ским ошиб­кам при­рав­ни­ва­ет­ся ис­поль­зо­ва­ние не­вер­но­го типа дан­ных. Если одна и та же ошиб­ка встре­ча­ет­ся не­сколь­ко раз, она счи­та­ет­ся за одну ошиб­ку

4
Не вы­пол­не­ны усло­вия, поз­во­ля­ю­щие по­ста­вить 4 балла.

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

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

До­пус­ка­ет­ся ошиб­ка при вводе и вы­во­де дан­ных, не вли­я­ю­щая на со­дер­жа­ние ре­ше­ния.

Про­грам­ма может со­дер­жать не более пяти син­так­си­че­ских и при­рав­нен­ных к ним оши­бок, опи­сан­ных в кри­те­ри­ях на 4 балла.

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

1) ошиб­ка ини­ци­а­ли­за­ции, в том числе от­сут­ствие ини­ци­а­ли­за­ции;

2) не вы­во­дит­ся ре­зуль­тат, рав­ный 0, или вме­сто 0 вы­во­дит­ся не­вер­ное зна­че­ние;

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

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

3
Не вы­пол­не­ны усло­вия, поз­во­ля­ю­щие по­ста­вить 3 или 4 балла.

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

Ко­ли­че­ство син­так­си­че­ских «опи­сок» не долж­но быть более семи. Про­грам­ма может быть не­эф­фек­тив­на по вре­ме­ни, на­при­мер все числа за­по­ми­на­ют­ся в мас­си­ве и пе­ре­би­ра­ют­ся все воз­мож­ные суммы, т.е., по сути, ре­а­ли­зо­ва­но ре­ше­ние за­да­чи А без огра­ни­че­ний на ко­ли­че­ство ввёден­ных пар

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

Аналоги к заданию № 6792: 6824 Все

Спрятать решение · КритерииСпрятать критерии · Помощь


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