Задание 1. ЕГЭ-2011 - Архив: все задания

Ответом к заданию по информатике может быть целое число, десятичная дробь (записывайте её через запятую, вот так: 2,5), последовательность цифр или букв (пишите без пробелов: 97531).

Версия для печати

31. Задание#T24414

Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых 3, а во второй 4 камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок или удваивает число камней в какой-то кучке или добавляет 4 камня в какую-то кучку. Игрок, после хода которого общее число камней в двух кучках становится больше 25, проигрывает.

Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход?

Каким должен быть первый ход выигрывающего игрока?

Ответ обоснуйте.

Показать разбор

Содержание верного ответа

(допускаются иные формулировки ответа, не искажающие его смысл)

Выигрывает второй игрок.

Для доказательства рассмотрим неполное дерево игры, оформленное в виде таблицы, где в каждой ячейке записаны пары чисел, разделенные запятой. Эти числа соответствуют количеству камней на каждом этапе игры в первой и второй кучках соответственно.

Таблица содержит все возможные варианты ходов первого игрока. Из нее видно, что при любом ходе первого игрока у второго имеется ход, приводящий к победе.

32. Задание#T24413

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

Если требуемое число составить невозможно, то программа должна вывести на экран слово «NO». А если возможно, то в первой строке следует вывести слово «YES», а во второй – искомое симметричное число. Если таких чисел несколько, то программа должна выводить максимальное из них. Например, пусть на вход подаются следующие символы:

Do not 911 to 09 do.

В данном случае программа должна вывести

YES
91019

Показать разбор

Содержание верного ответа

(допускаются иные формулировки ответа, не искажающие его смысл)

Программа читает все входные символы до точки один раз, подсчитывая в массиве, хранящем 10 целых чисел, количество каждой из цифр. Сами входные символы при этом не запоминаются. Затем проверяется — сколько в этом массиве нечетных элементов. Если больше одного, то задача решения не имеет. При наличии решения сначала печатается половина имеющихся цифр 9 (если таковые имеются, в случае нечетного числа цифр – меньшая половина), затем 8 и т.д. до 0, потом печатается цифра, которая встречается во входных данных нечетное число раз, а затем – оставшаяся половина цифр 0 (если таковые имеются, в случае нечетного числа цифр – меньшая половина), 1, и т.д. до 9. Если никаких цифр, кроме 0, во входных данных нет, то задача имеет решение, только если этот ноль единственный. Если нулей четное число, а ненулевая цифра единственная, то решения не существует.

Баллы начисляются только за программу, которая решает задачу хотя бы для одного частного случая (например, для строк, состоящих не более чем из 255 символов), или которая умеет только определять, имеет ли задача решение.

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

var a:array['0'..'9'] of integer;
  c, c_odd: char;
  i, k: integer;
  f: boolean;
begin
 for c:='0' to '9' do a[c]:=0;
 read(с);
 while c<>'.' do
  begin
   if c in ['0' .. '9'] then a[c] := a[c] + 1;
   read(c);
  end;
 k := 0; {количество цифр, встречающихся нечетное число раз}
 for c := '0' to '9' do
  if a[c] mod 2 = 1 then
   begin
    k := k + 1;
    c_odd := c
   end;
 f := (a['0'] = 1);
 for c := '1' to '9' do
  if (a[c] > 1) or (a[c] = 1) and (a['0'] = 0) then f := true;
 if (k > 1)or not f then writeln('NO') else
 begin
  writeln('YES');
  for c := '9' downto '0' do
   for i := 1 to a[c] div 2 do
    write(c);
  if k = 1 then
   write(c_odd);
  for c := '0' to '9' do
   for i := 1 to a[c] div 2 do
    write(c);
 end
end.

0 баллов сегодня

дней без пропуска

вс

пн

вт

ср

чт

пт

сб