Решение егэ информатика
 Скачать 0.52 Mb.
|
За да ние 1. Для каж дой из на чаль ных по зи ций (6, 33), (8, 32) ука жи те, кто из иг ро ков имеет вы иг рыш ную стра те гию. В каж дом слу чае опи ши те вы иг рыш ную стра те гию; объ яс ни те, по че му эта стра те гия ведёт к вы иг ры шу, и ука жи те, какое наи боль шее ко ли че ство ходов может по тре бо вать ся по бе ди те лю для вы иг ры ша при этой стра те гии. За да ние 2. Для каж дой из на чаль ных по зи ций (6, 32), (7, 32), (8, 31) ука жи те, кто из иг ро ков имеет вы иг рыш ную стра те гию. В каж дом слу чае опи ши те вы иг рыш ную стра те гию; объ яс ни те, по че му эта стра те гия ведёт к вы иг ры шу, и ука жи те, какое наи боль шее ко ли че ство ходов может по тре бо вать ся по бе ди те лю для вы иг ры ша при этой стра те гии. За да ние 3. Для на чаль ной по зи ции (7, 31) ука жи те, кто из иг ро ков имеет вы иг рыш ную стра те гию. Опи ши те вы иг рыш ную стра те гию; объ яс ни те, по че му эта стра те гия ведёт к вы иг ры шу, и ука жи те, какое наи боль шее ко ли че ство ходов может по тре бо вать ся по бе ди те лю для вы иг ры ша при этой стра те гии. По строй те де ре во всех пар тий, воз мож ных при ука зан ной Вами вы иг рыш ной стра те гии. Пред ставь те де ре во в виде ри сун ка или таб ли цы. По яс не ние.
За да ние 1. В на чаль ных по зи ци ях (6, 33), (8, 32) вы иг рыш ная стра те гия есть у Вани. При на чаль ной по зи ции (6, 33) после пер во го хода Пети может по лу чить ся одна из сле ду ю щих четырёх по зи ций: (7, 33), (12, 33), (6, 34), (6, 66). Каж дая из этих по зи ций со дер жит менее 73 кам ней. При этом из любой из этих по зи ций Ваня может по лу чить по зи цию, со дер жа щую не менее 73 кам ней, удво ив ко ли че ство кам ней во вто рой куче. Для по зи ции (8, 32) после пер во го хода Пети может по лу чить ся одна из сле ду ю щих четырёх по зи ций: (9, 32), (16, 32), (8, 33), (8, 64). Каж дая из этих по зи ций со дер жит менее 73 кам ней. При этом из любой из этих по зи ций Ваня может по лу чить по зи цию, со дер жа щую не менее 73 кам ней, удво ив ко ли че ство кам ней во вто рой куче. Таким об ра зом, Ваня при любом ходе Пети вы иг ры ва ет своим пер вым ходом. За да ние 2. В на чаль ных по зи ци ях (6, 32), (7, 32) и (8, 31) вы иг рыш ная стра те гия есть у Пети. При на чаль ной по зи ции (6, 32) он дол жен пер вым ходом по лу чить по зи цию (6, 33), из на чаль ных по зи ций (7, 32) и (8, 31). Петя после пер во го хода дол жен по лу чить по зи цию (8, 32). По зи ции (6, 33) и (8, 32) рас смот ре ны при раз бо ре за да ния 1. В этих по зи ци ях вы иг рыш ная стра те гия есть у иг ро ка, ко то рый будет хо дить вто рым (те перь это Петя). Эта стра те гия опи са на при раз бо ре за да ния 1. Таким об ра зом, Петя при любой игре Вани вы иг ры ва ет своим вто рым ходом. За да ние 3. В на чаль ной по зи ции (7, 31) вы иг рыш ная стра те гия есть у Вани. После пер во го хода Пети может воз ник нуть одна из четырёх по зи ций: (8, 31), (7, 32), (14, 31) и (7, 62). В по зи ци ях (14, 31) и (7, 62) Ваня может вы иг рать одним ходом, удво ив ко ли че ство кам ней во вто рой куче. По зи ции (8, 31) и (7, 32) были рас смот ре ны при раз бо ре за да ния 2. В этих по зи ци ях у иг ро ка, ко то рый дол жен сде лать ход (те перь это Ваня), есть вы иг рыш ная стра те гия. Эта стра те гия опи са на при раз бо ре за да ния 2. Таким об ра зом, в за ви си мо сти от игры Пети Ваня вы иг ры ва ет на пер вом или вто ром ходу. 27. За да ние В фи зи че ской ла бо ра то рии про во дит ся дол го вре мен ный экс пе ри мент по изу че нию гра ви та ци он но го поля Земли. По ка на лу связи каж дую ми ну ту в ла бо ра то рию пе ре даётся по ло жи тель ное целое число – те ку щее по ка за ние при бо ра «Сигма 2015». Ко ли че ство пе ре да ва е мых чисел в серии из вест но и не пре вы ша ет 10 000. Все числа не пре вы ша ют 1000. Вре ме нем, в те че ние ко то ро го про ис хо дит пе ре да ча, можно пре не бречь. Не об хо ди мо вы чис лить «бета-зна че ние» серии по ка за ний при бо ра – ми ни маль ное чётное про из ве де ние двух по ка за ний, между мо мен та ми пе ре да чи ко то рых про шло не менее 6 минут. Если по лу чить такое про из ве де ние не удаётся, ответ счи та ет ся рав ным –1. Вам пред ла га ет ся два за да ния, свя зан ных с этой за да чей: за да ние А и за да ние Б. Вы мо же те ре шать оба за да ния или одно из них по сво е му вы бо ру. Ито го вая оцен ка вы став ля ет ся как мак си маль ная из оце нок за за да ния А и Б. Если ре ше ние од но го из за да ний не пред став ле но, то счи та ет ся, что оцен ка за это за да ние – 0 бал лов. За да ние Б яв ля ет ся усложнённым ва ри ан том за да ния А, оно со дер жит до пол ни тель ные тре бо ва ния к про грам ме. А. На пи ши те на любом языке про грам ми ро ва ния про грам му для ре ше ния по став лен ной за да чи, в ко то рой вход ные дан ные будут за по ми нать ся в мас си ве, после чего будут про ве ре ны все воз мож ные пары эле мен тов. Перед про грам мой ука жи те вер сию языка про грам ми ро ва ния. ОБЯ ЗА ТЕЛЬ НО ука жи те, что про грам ма яв ля ет ся ре ше ни ем ЗА ДА НИЯ А. Мак си маль ная оцен ка за вы пол не ние за да ния А – 2 балла. Б. На пи ши те про грам му для ре ше ния по став лен ной за да чи, ко то рая будет эф фек тив на как по вре ме ни, так и по па мя ти (или хотя бы по одной из этих ха рак те ри стик). Про грам ма счи та ет ся эф фек тив ной по вре ме ни, если время ра бо ты про грам мы про пор ци о наль но ко ли че ству по лу чен ных по ка за ний при бо ра N, т.е. при уве ли че нии N в k раз время ра бо ты про грам мы долж но уве ли чи вать ся не более чем в k раз. Про грам ма счи та ет ся эф фек тив ной по па мя ти, если раз мер па мя ти, ис поль зо ван ной в про грам ме для хра не ния дан ных, не за ви сит от числа N и не пре вы ша ет 1 ки ло бай та. Перед про грам мой ука жи те вер сию языка про грам ми ро ва ния и крат ко опи ши те ис поль зо ван ный ал го ритм. ОБЯ ЗА ТЕЛЬ НО ука жи те, что про грам ма яв ля ет ся ре ше ни ем ЗА ДА НИЯ Б. Мак си маль ная оцен ка за пра виль ную про грам му, эф фек тив ную по вре ме ни и по па мя ти, – 4 балла. Мак си маль ная оцен ка за пра виль ную про грам му, эф фек тив ную по вре ме ни, но не эф фек тив ную по па мя ти, – 3 балла. НА ПО МИ НА ЕМ! Не за будь те ука зать, к ка ко му за да нию от но сит ся каж дая из пред став лен ных Вами про грамм. Вход ные дан ные пред став ле ны сле ду ю щим об ра зом. В пер вой стро ке задаётся число N – общее ко ли че ство по ка за ний при бо ра. Га ран ти ру ет ся, что N > 6. В каж дой из сле ду ю щих N строк задаётся одно по ло жи тель ное целое число – оче ред ное по ка за ние при бо ра. При мер вход ных дан ных: 11 12 45 5 3 17 23 21 20 19 18 17 Про грам ма долж на вы ве сти одно число – опи сан ное в усло вии про из ве де ние либо –1, если по лу чить такое про из ве де ние не удаётся. При мер вы ход ных дан ных для при ведённого выше при ме ра вход ных дан ных: 54 По яс не ние. За да ние Б (ре ше ние для за да ния А при ве де но ниже, см. про грам му 4). Чтобы про из ве де ние было чётным, хотя бы один со мно жи тель дол жен быть чётным, по это му при по ис ке под хо дя щих про из ве де ний чётные по ка за ния при бо ра можно рас смат ри вать в паре с лю бы ми дру ги ми, а нечётные – толь ко с чётными. Для каж до го по ка за ния с но ме ром k, на чи ная с k = 7, рас смот рим все до пу сти мые по усло ви ям за да чи пары, в ко то рых дан ное по ка за ние по лу че но вто рым. Ми ни маль ное про из ве де ние из всех этих пар будет по лу че но, если пер вым в паре будет взято ми ни маль ное под хо дя щее по ка за ние среди всех, по лу чен ных от на ча ла приёма и до по ка за ния с но ме ром k – 6. Если оче ред ное по ка за ние чётное, ми ни маль ное среди преды ду щих может быть любым, если нечётное – толь ко чётным. Для по лу че ния эф фек тив но го по вре ме ни ре ше ния нужно по мере ввода дан ных пом нить аб со лют ное ми ни маль ное и ми ни маль ное чётное по ка за ние на каж дый мо мент вре ме ни, каж дое вновь по лу чен ное по ка за ние умно жать на со от вет ству ю щий ему ми ни мум, имев ший ся на 6 эле мен тов ранее, и вы брать ми ни маль ное из всех таких про из ве де ний. По сколь ку каж дое те ку щее ми ни маль ное по ка за ние ис поль зу ет ся после ввода ещё 6 эле мен тов и после этого ста но вит ся не нуж ным, до ста точ но хра нить толь ко 6 по след них ми ни му мов. Для этого можно ис поль зо вать мас сив из 6 эле мен тов и цик ли че ски за пол нять его по мере ввода дан ных. Раз мер этого мас си ва не за ви сит от об ще го ко ли че ства введённых по ка за ний, по это му такое ре ше ние будет эф фек тив ным не толь ко по вре ме ни, но и по па мя ти. Чтобы хра нить аб со лют ный и чётный ми ни му мы, нужно ис поль зо вать два таких мас си ва. Ниже при во дит ся при мер такой про грам мы, на пи сан ной на ал го рит ми че ском языке. При мер 1. При мер пра виль ной про грам мы на ал го рит ми че ском языке. Про грам ма эф фек тив на и по вре ме ни, и по па мя ти. алг нач цел s = 6 | тре бу е мое рас сто я ние между по ка за ни я ми цел amax = 1001 | боль ше мак си маль но воз мож но го по ка за ния цел N ввод N цел a | оче ред ное по ка за ние при бо ра цел таб мини[0:s-1] | те ку щие ми ни му мы по след них s эле мен тов цел таб ми ни чет[0:s-1] | чётные ми ни му мы по след них s эле мен тов цел i | вво дим пер вые s по ка за ний, фик си ру ем ми ни му мы цел ма; ма := amax | ми ни маль ное по ка за ние цел мчет; мчет := amax | ми ни маль ное чётное по ка за ние нц для i от 1 до s ввод а ма := imin(ма, a) если mod(a,2) = 0 то мчет := imin(мчет,a) все мини[mod(i, s)] := ма ми ни чет[mod(i, s)] := мчет кц цел мп = amax*amax | ми ни маль ное зна че ние про из ве де ния цел п нц для i от s+1 до N ввод а если mod(a,2)=0 то п := a * мини[mod(i, s)] иначе если мчет < amax то п := a * ми ни чет[mod(i, s)] иначе п := amax*amax; все все мп := imin(мп, п) ма := imin(ма, a) если mod(a,2) = 0 то мчет := imin(мчет,a) все мини[mod(i, s)] := ма ми ни чет[mod(i, s)] := мчет кц если мп = amax*amax то мп:=-1 все вывод мп кон Воз мож ны и дру гие ре а ли за ции. На при мер, вме сто цик ли че ско го за пол не ния мас си ва можно каж дый раз сдви гать его эле мен ты. В при ведённом ниже при ме ре хра нят ся и сдви га ют ся не ми ни му мы, а ис ход ные зна че ния. Это тре бу ет чуть мень ше па мя ти (до ста точ но од но го мас си ва вме сто двух), но по вре ме ни ре ше ние со сдви га ми менее эф фек тив но, чем с цик ли че ским за пол не ни ем. Од на ко время ра бо ты остаётся про пор ци о наль ным N, по это му мак си маль ная оцен ка за такое ре ше ние тоже со став ля ет 4 балла. Про грам ма 2. При мер пра виль ной про грам мы на языке Пас каль. Про грам ма ис поль зу ет сдви ги, но эф фек тив на по вре ме ни и по па мя ти const s = 6; {тре бу е мое рас сто я ние между по ка за ни я ми} amax = 1001; {боль ше мак си маль но воз мож но го по ка за ния} var N: integer; a: array[1..s] of integer; {хра не ние s по ка за ний при бо ра} a_: integer; {ввод оче ред но го по ка за ния} ma: integer; {ми ни маль ное число без s по след них} me: integer; {ми ни маль ное чётное число без s по след них} mp: integer; {ми ни маль ное зна че ние про из ве де ния} p: integer; i, j: integer; begin readln(N); {Ввод пер вых s чисел} for i:=1 to s do readln(a[i]); {Ввод осталь ных зна че ний, поиск ми ни маль но го про из ве де ния} ma := amax; me := amax; mp :=amax*amax; for i := s + 1 to N do begin readln(a_); if a[1] < ma then ma := a[1]; if (a[1] mod 2 = 0) and (a[1] < me) then me := a[1]; if a_ mod 2 = 0 then p := a_ * ma else if me < amax then p := a_ * me else p := amax* amax; if (p < mp) then mp := p; {сдви га ем эле мен ты вспо мо га тель но го мас си ва влево} for j := 1 to s - 1 do a[j] := a[j + 1]; a[s] := a_ end; if mp = amax*amax then mp:=-1; writeln(mp) end. Если вме сто не боль шо го мас си ва фик си ро ван но го раз ме ра (цик ли че ско го или со сдви га ми) хра нят ся все ис ход ные дан ные (или все те ку щие ми ни му мы), про грам ма со хра ня ет эф фек тив ность по вре ме ни, но ста но вит ся не эф фек тив ной по па мя ти, так как тре бу е мая па мять растёт про пор ци о наль но N. Ниже при во дит ся при мер такой про грам мы на языке Пас каль. По доб ные (и ана ло гич ные по сути) про грам мы оце ни ва ют ся не выше 3 бал лов. Про грам ма 3. При мер пра виль ной про грам мы на языке Пас каль. Про грам ма эф фек тив на по вре ме ни, но не эф фек тив на по па мя ти const s = 6; {тре бу е мое рас сто я ние между по ка за ни я ми} amax = 1001; {боль ше мак си маль но воз мож но го по ка за ния} var N, p, i: integer; a: array[1..10000] of integer; {все по ка за ния при бо ра} ma: integer; {ми ни маль ное число без s по след них} me: integer; {ми ни маль ное чётное число без s по след них} mp: integer; {ми ни маль ное зна че ние про из ве де ния} begin readln(N); {Ввод всех по ка за ний при бо ра} for i:=1 to N do readln(a[i]); ma := amax; me := amax; mp := amax*amax; for i := s + 1 to N do begin if a[i-s] < ma then ma := a[i-s]; if (a[i-s] mod 2 = 0) and (a[i-s] < me) then me := a[i-s]; if a[i] mod 2 = 0 then p := a[i] * ma else if me < amax then p := a[i] * me else p := amax * amax; if (p < mp) then mp := p end; if mp = amax*amax then mp := -1; writeln(mp) end. Воз мож но также пе ре бор ное ре ше ние, в ко то ром на хо дят ся про из ве де ния всех воз мож ных пар и из них вы би ра ет ся ми ни маль ное. Ниже (см. про грам му 4) при ведён при мер по доб но го ре ше ния. Это (и ана ло гич ные ему) ре ше ние не эф фек тив но ни по вре ме ни, ни по па мя ти. Оно яв ля ет ся ре ше ни ем за да ния А, но не яв ля ет ся ре ше ни ем за да ния Б. Оцен ка за такое ре ше ние – 2 балла. Про грам ма 4. При мер пра виль ной про грам мы на языке Пас каль. Про грам ма не эф фек тив на ни по вре ме ни, ни по па мя ти const s = 6; {тре бу е мое рас сто я ние между по ка за ни я ми} var N: integer; a: array[1..10000] of integer; {все по ка за ния при бо ра} mp: integer; {ми ни маль ное зна че ние про из ве де ния} i, j: integer; begin readln(N); {Ввод зна че ний при бо ра} for i:=1 to N do readln(a[i]); mp := 1000 * 1000 + 1; for i := 1 to N-s do begin for j := i+s to N do begin if (a[i]*a[j] mod 2 = 0) and (a[i]*a[j] < mp) then mp := a[i]*a[j] end; end; if mp = 1000 * 1000 + 1 then mp := -1; writeln(mp) end. | |||||||||||||||||||||||||||||||||||||||