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

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

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

Вам пред­ла­га­ет­ся на­пи­сать эф­фек­тив­ную, в том числе по ис­поль­зу­е­мой па­мя­ти, про­грам­му (ука­жи­те ис­поль­зу­е­мую вер­сию языка про­грам­ми­ро­ва­ния, на­при­мер, Borland Pascal 7.0), ко­то­рая будет об­ра­ба­ты­вать ре­зуль­та­ты, при­хо­дя­щие из од­но­го участ­ка, на­хо­дя ос­нов­ное под­мно­же­ство. Перед тек­стом про­грам­мы крат­ко опи­ши­те ис­поль­зу­е­мый Вами ал­го­ритм ре­ше­ния за­да­чи. На вход про­грам­ме в пер­вой стро­ке подаётся ко­ли­че­ство сиг­на­лов N. В каж­дой из по­сле­ду­ю­щих N строк за­пи­са­но одно целое не­от­ри­ца­тель­ное число, не пре­вы­ша­ю­щее 109.

 

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

 

5

123

2

1000

0

10

 

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

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

Ре­ше­ние.

Ос­нов­ное под­мно­же­ство со­сто­ит из всех зна­че­ний сиг­на­лов, кроме 0, если он встре­ча­ет­ся, и кроме ми­ни­маль­но­го нечётного зна­че­ния, если таких зна­че­ний нечётное число.

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

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

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

var n,i,j,k,c,min,a: longint;

begin

readln(n);

min := 1000000001;

k := 0;

j := 0;

c := 0;

for i := 1 to n do

begin

readln(a);

if a = 0 then j := i;

if a mod 2 <> 0 then

begin

c := c + 1;

if a < min then

begin

min := a;

k := i;

end

end

end;

for i :=1 to n do

if (i <> j) and ((c mod 2 = 0) or (i <> k)) then

write(i,' ');

end.

INPUT n

min = 0

k = 0

j = 0

c = 0

FOR i = 1 TO n

INPUT a

IF a = 0 THEN j = i

IF a MOD 2 <> 0 THEN

c = c + 1

IF (min = 0) OR (a < min) THEN

min = a

k = i

END IF

END IF

NEXT i

FOR i = 1 TO n

IF (i <> j) AND ((c MOD 2 = 0) OR (i <> k)) THEN PRINT i

NEXT i

END

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

Кри­те­рии оце­ни­ва­ния вы­пол­не­ния за­да­нияБаллы
Про­грам­ма ра­бо­та­ет для любых вход­ных дан­ных про­из­воль­но­го раз­ме­ра и на­хо­дит ответ, не со­хра­няя вход­ные дан­ные в мас­си­ве, раз­мер ко­то­ро­го со­от­вет­ству­ет числу N (ко­ли­че­ству сиг­на­лов). Про­грам­ма про­смат­ри­ва­ет вход­ные дан­ные один раз, опре­де­ляя номер 0, ко­ли­че­ство нечётных зна­че­ний и ми­ни­маль­ное нечётное число. Затем рас­пе­ча­ты­ва­ют­ся все но­ме­ра сиг­на­лов, кроме сиг­на­ла с ну­ле­вым зна­че­ни­ем, а в слу­чае, когда ко­ли­че­ство нечётных зна­че­ний чётно, и кроме но­ме­ра сиг­на­ла с ми­ни­маль­ным нечётным зна­че­ни­ем. До­пус­ка­ет­ся на­ли­чие в тек­сте про­грам­мы до трёх син­так­си­че­ских оши­бок: про­пу­щен или не­вер­но ука­зан знак пунк­ту­а­ции, не­вер­но на­пи­са­но или про­пу­ще­но за­ре­зер­ви­ро­ван­ное слово языка про­грам­ми­ро­ва­ния, не опи­са­на или не­вер­но опи­са­на пе­ре­мен­ная, при­ме­ня­ет­ся опе­ра­ция, не­до­пу­сти­мая для со­от­вет­ству­ю­ще­го типа дан­ных (если одна и та же ошиб­ка встре­ча­ет­ся не­сколь­ко раз, то это счи­та­ет­ся за одну ошиб­ку) 4
Про­грам­ма ра­бо­та­ет верно, но вход­ные дан­ные за­по­ми­на­ют­ся в мас­си­ве или дру­гой струк­ту­ре дан­ных (на­при­мер, кон­тей­нер priority_queue, vector, set или map в С++), раз­мер ко­то­ро­го со­от­вет­ству­ет числу N. Этот мас­сив, или мас­сив ото­бран­ных но­ме­ров, воз­мож­но, потом сор­ти­ру­ет­ся). При этом общая слож­ность ал­го­рит­ма не пре­вы­ша­ет CN2, где C — кон­стан­та, не за­ви­ся­щая от N. До­пус­ка­ет­ся на­ли­чие до пяти син­так­си­че­ских оши­бок, опи­сан­ных выше. Кроме того, до­пус­ка­ет­ся на­ли­чие одной со­дер­жа­тель­ной ошиб­ки, на­при­мер ошиб­ки из сле­ду­ю­ще­го спис­ка:

 

1) ошиб­ка при вводе дан­ных (при усло­вии, что в целом ввод ор­га­ни­зо­ван пра­виль­но);

2) про­грам­ма не­пра­виль­но ра­бо­та­ет при боль­ших зна­че­ни­ях введённых чисел (на­сту­па­ет пе­ре­пол­не­ние);

3) до­пу­ще­на ошиб­ка в ре­а­ли­за­ции ал­го­рит­ма сор­ти­ров­ки;

4) ис­поль­зу­ет­ся “<” вме­сто “<=”, “AND” вме­сто “OR” и т.п

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

1. Из опи­са­ния ал­го­рит­ма и общей струк­ту­ры про­грам­мы видно, что эк­за­ме­ну­е­мый в целом пра­виль­но пред­став­ля­ет путь ре­ше­ния за­да­чи.

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

1
Не вы­пол­не­ны кри­те­рии, поз­во­ля­ю­щие по­ста­вить 1, 2, 3 или 4 балла0
Мак­си­маль­ный балл4

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

Источник: ЕГЭ по ин­фор­ма­ти­ке 08.07.2013. Вто­рая волна. Ва­ри­ант 502
Спрятать решение · Прототип задания · КритерииСпрятать критерии · Помощь


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