ЕГЭ 2011 С4 « Образовательные материалы

Программы, которые эффективно используют память: выбор лучших учеников по набранным баллам, кодирование файловых строк. 10 вариантов задач за 2011 год. Они обозначались как С4

Пример. ЕГЭ 2011 С4 Вариант 1

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

Завуч школы № 50 решила наградить двух учащихся, которые лучше всех в школе сдали информатику.

Программа должна вывести на экран фамилии и имена этих учеников.

Если наибольший балл набрало больше двух человек – вывести количество таких учеников.

Если наибольший балл набрал один человек, а следующий балл набрало несколько человек — нужно вывести только фамилию и имя лучшего.

На вход программе сначала подаётся число учеников, сдававших экзамен. В каждой из следующих N строк находится информация об учениках в формате:

<Фамилия> <Имя> <Номер школы> <Количество баллов>

где <Фамилия> — строка, состоящая не более чем из 30 символов без пробелов, <Имя> — строка, состоящая не более, чем из 20 символов без пробелов, <Номер школы> — целое число в диапазоне от 1 до 99, <Количество баллов> — целое число в диапазоне от 1 до 100. Эти данные записаны через пробел, причём ровно один между каждой парой (то есть, всего по три пробела в каждой строке).

Пример входной строки:
Иванов Иван 50 87
Пример выходных данных:
Круглов Василий Тарасова Дарья
Другой вариант выходных данных:
7
Третий вариант выходных данных:
Гусарский Илья

Решение:

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

	
	Цикл по всем ученикам
		Если ученик из 50-й школы то	
			Выбор лучших

Выбор лучших

Введём переменные:

max1 – максимальный бал или максимум,

max2 – второй максимум,

ball – текущий бал ученика 50-й школы.

Выбор лучших – это алгоритм с вложенным ветвлением. Для простоты рассмотрим его по частям. Их четыре:

Пусть есть возрастающая последовательность чисел, например, такая [1 2 3 4 5]: один максимум(5) и один второй максимум(4). Тогда алгоритм можно написать так:


	max1 = max2 =-1
	цикл для всех из 50-й школы
		если ball > max1 то
			max2 = max1
			max1 = ball

Теперь случай, где два одинаковых максимума(5): [1 5 3 4 5]. Добавим новую ветку условия:


	max1 = max2 =-1
	цикл для всех из 50-й школы
		если ball > max1 то
			max2 = max1
			max1 = ball
		иначе если ball = max1 то
			max2 = ball

т.е. max1 и max2 содержат одинаковые значения.

Второй максимум(4) правее максимума(5): [1 5 3 4 2]. Добавим третью ветку условия:


	max1 = max2 =-1
	цикл для всех из 50-й школы
		если ball > max1 то
			max2 = max1
			max1 = ball
		иначе если ball = max1 то
			max2 = ball
		иначе если ball = max2 то
			max2 = ball

(во 2-м и 3-м условиях стоят одинаковые операторы – можно было бы написать одно сложное условие, однако далее операторы будут меняться).

Последний случай. Количество вторых максимумов(4) может быть более одного: [1 5 4 2 4]; здесь также добавляем условие, в котором подсчитывается их количество.

Наконец, количество максимумов(5) может быть более двух [1 5 2 5 5] – их также нужно подсчитывать. Добавим для них переменные и дополним алгоритм:

n1 – количество максимумов,

n2 – количество вторых максимумов.


	max1 = max2 =-1
	n1 = n2 = 0
	цикл для всех из 50-й школы
		если ball > max1 то
			max2 = max1
			max1 = ball
			n2 = n1
			n1 = 1
		иначе если ball = max1 то
			max2 = ball
			n1 = n1 + 1
		иначе если ball = max2 то
			max2 = ball
			n2 = 1
		иначе если ball = max2 то
			n2 = n2 + 1

Обратим внимание на строку n2=n1. Здесь в n1 сохранено количество «бывших» максимумов: оно может быть либо 1, либо больше 1. И ещё, оператор последнего условия не содержит присваивания переменной max2, дело в том, что в max2 уже было присвоено значение.

Имена

Осталось добавить имена учеников:

s – фамилия и имя ученика из 50-й школы,

s1 – фамилия и имя ученика с максимальным баллом,

s2 – фамилия и имя ученика с вторым максимальным баллом.


	max1 = max2 =-1
	n1 = n2 = 0
	s1 = s2 = ""
	цикл для всех из 50-й школы
		s = Ф. И. ученика из 50-й школы
		если ball > max1 то
			max2 = max1
			max1 = ball
			n2 = n1
			n1 = 1
			s2 = s1
			s1 = s
		иначе если ball = max1 то
			max2 = ball
			n1 = n1 + 1
			s2 = s
		иначе если ball = max2 то
			max2 = ball
			n2 = 1
			s2 = s
		иначе если ball = max2 то
			n2 = n2 + 1

Аналогично, оператор последнего условия не содержит присваивания имени потому, что ранее оно уже было присвоено корректным значением.

Вывод результатов

Двое лучших – это либо два одинаковых максимальных балла, либо один максимум и один второй максимум. Один лучший – это когда один победитель, а количество вторых максимумов более одного. В остальных случаях получим вывод, в котором количество максимумов – больше двух:


	если n1==1 и n2==1 или n1==2 то
		печать s1, s2
	иначе если n1==1 и n2>1 то
		печать s1
	иначе
		печать n1

Цикл по всем ученикам

Переходим на Python. Найдём количество учеников из всех школ. Если данные нашей задачи хранятся в файле, то первая строка файла содержит это значение. Вот как можно подключиться к файлу, а затем извлечь всех учеников в переменную N:

	f = open("имяфайла.txt", encoding='utf-8', mode="r")
	N = f.readline()

N, нам понадобится для организации цикла по всем ученикам:

	for i in range(int(N))

Ученик из 50-й школы

После N идут строки со значениями, значения разделены пробелом. Функция split разбивает каждую прочитанную строку в массив подстрок:

	array = f.readline().split()

Откуда: array[0] – первая подстрока с фамилией, array[1] – вторая подстрока с именем, array[2] – номер школы и наконец, array[3] – набранный балл. Теперь проверить 50-ую школу можно так:

	school = int(array[2])
	if school == 50:

Фамилия и имя получается сложением:

	s = array[0] + " " + array[1]

Полный код на Python

  f = open("11C4v01.txt", encoding='utf-8', mode="r")
  n = int(f.readline())
  max1 = max2 = -1
  n1 = n2 = 0
  s1 = s2 = ""
  for i in range(n):
      a = f.readline().split()
      #a[0] - Фамилия
      #a[1] - Имя
      #a[2] - номер школы [1..99]
      #a[3] - балл ученика(цы)
      s = a[0] + " " + a[1]
      school = int(a[2])
      ball = int(a[3])
      if school == 50:
          if ball > max1:
              max2 = max1
              max1 = ball
              n2 = n1
              n1 = 1
              s2 = s1
              s1 = s
          elif ball == max1:
              max2 = ball
              n1 += 1 
              s2 = s
          elif ball > max2:
              max2 = ball
              n2 = 1
              s2 = s
          elif ball == max2:
              n2 += 1
  # Вывод результатов
  if n1==1 and n2==1 or n1==2:
      print (s1, " ",s2)
  elif n1==1 and n2>1:
      print(s1)
  else:
      print(n1)
  f.close()

Пример. ЕГЭ 2011 С4 Вариант 2

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

Районный методист решила выяснить номер школы, ученики которой набрали наибольший средний балл, с точностью до целых.

Программа должна вывести на экран номер такой школы и её средний балл.

Если наибольший средний балл набрало больше одной школы — вывести количество таких школ.

Напишите эффективную, в том числе и по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая должна вывести на экран требуемую информацию. Известно, что информатику сдавало больше 5-ти учеников района. Также известно, что в районе школы с некоторыми номерами не существуют.

<Фамилия> <Имя> <Номер школы> <Количество баллов>

где <Фамилия> — строка, состоящая не более, чем из 30 символов без пробелов, <Имя> — строка, состоящая не более, чем из 20 символов без пробелов, <Номер школы> — целое число в диапазоне от 1 до 99, <Количество баллов> — целое число диапазоне от 1 до 100. Эти данные записаны через пробел, причём ровно один между каждой парой (то есть, всего по три пробела в каждой строке).

Пример входной строки:
Иванов Иван 50 87
Пример выходных данных:
50 74
Другой вариант выходных данных:
7

Решение:

Сумма баллов

Пусть количество школ 3, а количество учеников 6 (N=6). И пусть будут такими номера школ и баллы учеников:

2 6

3 15

1 8

2 10

3 9

2 7

Просуммировать баллы по каждой школе удобно с помощью массива, размер которого равен количеству школ:

школа №1

школа №2

школа №3

0	0	0

+	+	+
8	6	15
	+	+
	10	9
	+
	7

Получаем такой массив после суммирования:

8	23	24

Алгоритм суммирования массива баллов:


	Цикл для i от 0 до 5 учеников
		m = № школы из i-й строки данных
		ball = балл ученика m-й школы
		sum[m] = sum[m] + ball

Данные массива sum после выполнения алгоритма:

sum[0]=8

sum[1]=23

sum[2]=24

Средний бал

Средний балл = сумма баллов школы/количество учеников школы.

где числитель – это массив из пункта Сумма баллов, а знаменатель – это ещё один массив такого же размера, только каждый элемент этого массива – это количество учеников в конкретной школе. Другими словами, знаменатель – это количество плюсов на схеме из пункта Сумма баллов. Значит, во время суммирования баллов каждой школы, увеличиваем на 1 i-й элемент второго массива:


	Цикл для i от 0 до 5 учеников
		m = № школы из i-й строки данных
		ball = балл ученика m-й школы
		sum[m] = sum[m] + ball
		cnt[m] = cnt[m] + 1

Данные массива sum и cnt после выполнения алгоритма:

sum[0]=8

sum[1]=23

sum[2]=24

cnt[0]=1

cnt[1]=3

cnt[2]=2

Ну, а теперь вычисление среднего балла. Для этого понадобится ещё один цикл, но уже по школам:


	Цикл для i от 0 до 2 школ
		sum[i] = sum[i] / cnt[i]

Данные массива sum после выполнения алгоритма:

sum[0]=8

sum[1]=7,66

sum[2]=12

Однако мы не учли отсутствие номеров некоторых школ. Это значит, что массивы sum и cnt где-то содержат нули – будет деление на ноль. Полный код на Python учтёт это.

Поиск лучших школ

По условию лучших школ может быть либо одна, либо две и более. В первом случае нужно сохранить номер школы и средний балл – это обычный поиск максимума:


	max = sum[0] ;сохраняем в max ср.балл школы №1
	n = 0 ;номер школы, пока 0
	Цикл для i от 1 до 2 школ ;начинаем со школы №2
		если sum[i] > max то
			max = sum[i]
			n = i;сохраняем в n № школы

Во втором случае нужно сохранить количество школ. Это сравнение на равенство среднего балла текущей школы с сохранённым ранее максимальным средним баллом – max :


	max = sum[0] ;сохраняем в max ср.балл школы №1
	n = кол-во = 0 ;номер школы и кол-во учеников, пока 0
	Цикл для i от 1 до 2 школ ;начинаем со школы №2
		если sum[i] > max то
			max = sum[i]
			кол-во = 1
			n = i   ;сохраняем в n № школы
		иначе если sum[i] = max то
			кол-во = кол-во + 1

Нужно написать эффективную по памяти программу, для этого можно исключить переменную n. Тогда в max сохранять не значение среднего балла первой школы(sum[0]), а индекс самой школы, затем произвести изменения в условном операторе. Это будет сделано в полном коде на Python.

Вывод результатов

Проверяем количество лучших школ, если лучшая школа одна, то выводим номер школы и её средний балл. В остальных случаях выводим количество:


	если кол-во = 1 то
		печать n max
	иначе
		печать кол-во

Полный код на Python

  f = open("11C4v01.txt", encoding='utf-8', mode="r")
  n = int(f.readline())
  nsch = 99 #кол-во школ [1..99]
  sum = [0] * nsch # массив суммарных баллов по каждой школе
  cnt = [0] * nsch # массив количеств учеников в каждой школе

  #суммируем баллы и считаем кол-во учеников по каждой школе
  for i in range(n):
    #a[0] - Фамилия (она не нужна)
    #a[1] - Имя (оно не нужно)
    #a[2] - номер школы [1..99]
    #a[3] - балл ученика(цы)
      a = f.readline().split()
      isch = int(a[2])-1 # isch - [0..98]
      sum[isch] += int(a[3])
      cnt[isch] += 1

  #средний балл
  for i in range(nsch):
#из-за отсутствия номеров некоторых школ, избегаем деления на 0
      if cnt[i]>0:
          sum[i] = sum[i] / cnt[i]

  #Поиск лучших школ
  max = 0
  n = 0
  for i in range(1,nsch):
      if sum[i] > sum[max]:
          max=i
          n=1
      elif sum[i] == sum[max]:
          n += 1
  
  #Вывод результатов
  if n == 1:
      print(max+1," ",sum[max])
  else:
      print(n)

Пример. ЕГЭ 2011 С4 Вариант 3

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

Районный методист решила выяснить номера школ, ученики которых набрали средний балл по школе, больший, чем районный средний балл (все средние баллы вычисляются с точностью до целых).

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

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

Напишите эффективную, в том числе и по используемой памяти, программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая должна вывести на экран требуемую информацию. Известно, что информатику сдавало больше 5-ти учеников района. Также известно, что в районе школы с некоторыми номерами не существуют.

<Фамилия><Имя><Номер школы><Количество баллов>

где <Фамилия> — строка, состоящая не более чем из 30 символов без пробелов, <Имя> — строка, состоящая не более чем из 20 символов без пробелов, <Номер школы> — целое число в диапазоне от 1 до 99, <Количество баллов> — целое число в диапазоне от 1 до 100. Эти данные записаны через пробел, причём ровно один между каждой парой (то есть, всего по три пробела в каждой строке).

Пример входной строки:
Иванов Иван 50 87
Пример выходных данных:
5 50 74 87
Другой вариант выходных данных:
7
Средний балл = 74

Решение:

Средние баллы по району и школе

Cр.балл по району = Все баллы / N

Средний балл по школе = Сумма баллов по школе / кол-во учеников школы

Сумму баллов по школе получаем как в примере 2011 С4 №2: создаём массив sum из 99 элементов(кол-во школ), заносим сумму баллов школы в каждый элемент. Добавим подсчёт кол-ва учеников в массив cnt:


	Цикл для i от 0 до N-1
		m = № школы из i-й строки данных
		ball = балл ученика m-й школы
		sum[m] = sum[m] + ball ;суммы баллов по m-ой школе
		cnt[m] = cnt[m] + 1 ;кол-во учеников m-ой школы

Заметим, что вместо вычисления всех баллов, можно просуммировать суммы баллов по школе в отдельную переменную. Тем самым избавиться от лишнего суммирования N раз!

Т.к. некоторых номеров школ нет, то соответствующие элементы массивов sum и cnt содержат нули. Для этого нужно следить, чтобы, при вычислении среднего, не было деления на ноль:


	avg = 0 ;переменная для всех баллов
	Цикл для i от 0 до 98 школ
		если sum[i] > 0 то
		avg = avg + sum[i] ;суммируем все баллы
		sum[i] = sum[i] / cnt[i]  ;средний балл по школе

Обратим внимание на две строки условия. Сначала суммируем баллы всех школ. Затем на место суммы баллов по школе, помещаем средний балл по этой же школе – тем самым не создаём лишнюю переменную для среднего значения.

Средний балл по району:

	avg = avg / N

Вывод результатов

Вывод номера или номеров школ проведём с помощью сравнения среднего балла по школе со средним баллом по району. Если балл по школе больше балла по району, то выведем её номер:


	Цикл для i от 0 до 98 школ
		если sum[i] > avg то
			печать i

Ну, а если школа единственная, то нужна переменная n, которая посчитает кол-во сравнений и переменная ball, которая сохранит балл этой единственной школы:

	m=0
	Цикл для i от 0 до 98 школ
		если sum[i] > avg то
			m = m + 1
			ball = sum[i]	
			печать i
	если m = 1 то
		печать "Средний балл:" ball

Полный код на Python

  f = open("11C4v01.txt", encoding='utf-8', mode="r")
  n = int(f.readline())
  nsch=99 # кол-во школ [1..99]
  sum = [0] * nsch # массив суммарных баллов по каждой школе
  cnt = [0] * nsch # массив количеств учеников в каждой школе

  #суммируем баллы и считаем кол-во учеников по каждой школе
  for i in range(n):
      #a[0] - Фамилия (она не нужна)
      #a[1] - Имя (оно не нужно)
      #a[2] - номер школы [1..99]
      #a[3] - балл ученика(цы)
      a = f.readline().split()
      isch = int(a[2])-1 # isch - [0..98]
      sum[isch] += int(a[3])
      cnt[isch] += 1

  #средний балл по школе
  avg = 0
  for i in range(nsch):
    if cnt[i] > 0:
        avg = avg + sum[i]  # суммируем все баллы
        sum[i] = sum[i] / cnt[i] # средний балл по школе

  #средний балл по району
  avg /= n

  #Вывод результатов
  m = 0
  for i in range(nsch):
      if sum[i] > avg:
          m += 1
          ball = sum[i]
          print(i+1, end=' ')
  if m == 1:
      print("Средний балл:",ball)

Пример. ЕГЭ 2011 С4 Вариант 4

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

Районный методист решила выяснить фамилии учеников, которые набрали наибольший балл, по каждой школе в отдельности, но только если из школы информатику сдавало не меньше трёх человек. Если в школе информатику сдавало меньше трёх человек, информацию по этой школе выводить не нужно. Если наибольший балл в какой-то школе набрали несколько человек, нужно вывести на экран их количество.

Программа должна вывести на экран информацию в виде:

<Номер школы> <Фамилия ученика>

в отдельной строке для каждой школы.

<Фамилия> <Имя> <Номер школы> <Количество баллов>

где <Фамилия> — строка, состоящая не более чем из 30 символов без пробелов, <Имя> — строка, состоящая не более чем из 20 символов без пробелов, <Номер школы> — целое число в диапазоне от 1 до 99, <Количество баллов> — целое число в диапазоне от 0 до 100. Эти данные записаны через пробел, причём ровно один между каждой парой (то есть всего по три пробела в каждой строке).

Пример входной строки:
Иванов Иван 50 87
Пример выходных данных:
5 Иванов
50 10
74 Сидоров

Решение:

Количество учеников сдававших экзамен в школе

Каждая строка данных содержит номер школы, который мы присвоим в переменную m. Эта m будет индексом массива cnt, который будем использовать для хранения кол-ва учеников в школе номером m:


    cnt [99] ;кол-во учеников в школе
    Цикл для i от 0 до N-1 ;цикл по строкам данных
        m = № школы из i-й строки данных
        ;считаем кол-во учеников в m-й школе
        cnt[m] = cnt[m] + 1

Т.о., каждый элемент массива cnt – это кол-во учеников в школе, номер которой есть индекс элемента

Наибольший балл

Вспомним пример ЕГЭ 2011 С4 №1, первая часть пункта Выбор лучших. Только здесь понадобится сохранять не одно лучшее значение, а лучшие значения для каждой школы: в массиве bal:


    bal [99] ;кол-во учеников в школе
    Цикл для i от 0 до N-1 ;цикл по строкам данных
        m = № школы из i-й строки данных
        ball = балл ученика m-й школы
        если ball > bal[m] то
            bal[m] = ball

Количество лучших учеников

Продолжаем воспоминания примера ЕГЭ 2011 С4 №1 второй части пункта Выбор лучших, и добавим вторую ветку нашему алгоритму. В ней, в массиве amt, будем считать количество одинаковых максимальных баллов школы номером m.


    bal [99] ;кол-во учеников в школе
    amt [99] ;кол-во лучших в школе
    Цикл для i от 0 до N-1 ;цикл по строкам данных
        m = № школы из i-й строки данных
        ball = балл ученика m-й школы
        если ball > bal[m] то
            bal[m] = ball
            amt[m] = 1 ;кол-во лучших в школе m пока 1
        иначе если ball = bal[m] то
            amt[m] = amt[m] + 1 ;считаем кол-во лучших в школе m

Имена

Такой же пункт Имена как в примере ЕГЭ 2011 С4 №1, а в нашей задаче нужно учесть только фамилию, если лучший в школе единственный:


    bal [99] ;наибольший балл в школе
    amt [99] ;кол-во лучших в школе
    nam [99] ;фамилия одного лучшего в школе
    Цикл для i от 0 до N-1
        m = № школы из i-й строки данных
        ball = балл ученика m-й школы
        s = фамилия ученика m-й школы
        если ball > bal[m] то
            bal[m] = ball
            amt[m] = 1
            nam[m] = s
        иначе если ball = bal[m] то
            amt[m] = amt[m] + 1

Алгоритмы, которые мы рассмотрели, выполняются в одном цикле. В полном коде мы их объединим в один.

Вывод результатов

Нужно вывести два значения: номер школы и либо фамилию, в случае одного лучшего в школе, либо количество лучших, если таковых несколько:


	Цикл для i от 0 до 98 школ
        если сnt[i] > 2 то
            если amt[i] = 1 то
                печать i nam[i] ;номер школы и имя лучшего
            иначе
                печать i amt[i] ;номер школы и кол-во лучших

Полный код на Python


  f = open("11C4v01.txt", encoding='utf-8', mode="r")
  n = int(f.readline())
  nsch = 99 #кол-во школ [1..99]
  cnt = [0] * nsch #кол-во учеников в школе
  bal = [0] * nsch #наибольший балл в школе
  amt = [0] * nsch #кол-во лучших учеников в школе
  nam = [''] * nsch #фамилия одного лучшего в школе

#суммируем баллы и считаем кол-во учеников по каждой школе
  for i in range(n):
      #a[0] - Фамилия
      #a[1] - Имя, оно не нужно
      #a[2] - номер школы [1..99]
      #a[3] - балл ученика(цы)
     a = f.readline().split()
     m = int(a[2])-1 #isch - [0..98]
     ball = int(a[3])
     if  ball > bal[m]:
        bal[m] = ball
        amt[m] = 1
        nam[m] = a[0]
    else:
        amt[m] += 1
    #считаем кол-во учеников в m-й школе
    cnt[m] += 1

#Вывод результатов
  m = 0
  for i in range(nsch):
     if cnt[i] >= 3:
        if amt[i] == 1:
           print(i+1," ", nam[i])
        else:
           print(i+1, " ", amt[i])

Пример. ЕГЭ 2011 С4 Вариант 5

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

В районе считается подозрительной ситуация, когда в школе более двух учащихся набирают одинаковый наибольший балл по школе.

Районный методист решила выяснить номера таких школ.

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

Если такая школа окажется одна, нужно вывести наибольший балл в этой школе, с указанием того, что это наибольший балл.

Если таких школ не окажется, нужно вывести об этом сообщение.

Напишите эффективную, в том числе и по используемой памяти, программу, которая должна вывести на экран требуемую информацию. Известно, что информатику сдавало больше 5-ти учеников района. Также известно, что в районе школы с некоторыми номерами не существуют.

<Фамилия> <Имя> <Номер школы> <Количество баллов>

где <Фамилия> — строка, состоящая не более чем из 30 символов без пробелов, <Имя> — строка, состоящая не более, чем из 20 символов без пробелов, <Номер школы> — целое число в диапазоне от 1 до 99, <Количество баллов> — целое число в диапазоне от 0 до 100. Эти данные записаны через пробел, причём ровно один между каждой парой (то есть, всего по три пробела в каждой строке).

Пример входной строки:
Иванов Иван 50 87
Пример выходных данных:
5 50 74 87
Другой вариант выходных данных:
7
Наибольший балл = 74
Третий вариант выходных данных:
Нет таких школ

Решение:

Поиск максимума в каждой школе и подсчёт их совпадений

Подобное было в С4 2011 №1 и №4. Каждая строка данных содержит номер школы, который мы присвоим переменной m. Её значение будет индексом массивов bal и amt. Массив bal хранит наибольший балл школы номером m, а массив amt – кол-во учеников школы номером m с наибольшим баллом:


    bal [99] ;наибольший балл в школе
    amt [99] ;кол-во одинаковых лучших учеников в школе
    Цикл для i от 0 до N-1 ;по строкам данных
        m = № школы из i-й строки данных
        ball = балл ученика m-й школы
        если ball > bal[m] то
            bal[m] = ball
            amt[m] = 1
        иначе если ball = bal[m] то
            amt[m] = amt[m] + 1

Вывод результатов

Массивы bal и amt заполнили, теперь посчитаем кол-во «подозрительных» школ: если их несколько, то выведем их номера; если их нет, то выведем сообщение; если она одна, то выведем номер школы и наибольший балл. Подсчёт «подозрительных» школ будем вести в переменную k:


    k = 0 ;кол-во подозрительных школ
    Цикл для i от 0 до 99 ; по всем школам
        если amt[i] > 2 то
            ball = bal[i] ;для случая когда k=1
            печать i " " ;номер подозрительной школы и пробел
            k = k + 1
    ;после того как прошлись по школам, рассмотрим два случая
    если k = 0 то ;когда подозрительных школ нет
        печать "таких школ нет"
    иначе если k = 1 то ;и когда подозрительная школа одна
        печать  ;перешли на следующую строку
        печать "Наибольший балл:" ball

Полный код на Python


  f = open("11C4v01.txt", encoding='utf-8', mode="r")
  n = f.readline()
   nsch = 99 #кол-во школ [1..99]
   bal = [0] * nsch #массив наибольших баллов по каждой школе
   #массив количеств одинаковых лучших учеников в школе
   amt = [0] * nsch 

   #суммируем баллы и считаем кол-во учеников по каждой школе
   for i in range(int(n)):  
      #a[0] - Фамилия (она не нужна)
      #a[1] - Имя (оно не нужно)
      #a[2] - номер школы [1..99]
      #a[3] - балл ученика(цы)
  
  
  a = f.readline().split()
  m = int(a[2])-1 #m - [0..98]
  ball = int(a[3])

  if ball > bal[m]:
     bal[m] = ball
     amt[m] = 1
  elif ball == bal[m]:
     amt[m] += 1
   #Вывод результатов
   k = 0
   for i in range(nsch):
   if amt[i] > 2:
       ball = bal[i]
  print(i + 1, end=' ') #номер подозрительной школы
  k += 1
   if k == 0:
       print(" Таких школ нет")
   elif k == 1:
       print() #перешли на следующую строку
       print("Наибольший балл:", ball)

Пример. ЕГЭ 2011 С4 Вариант 6

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

Каждая строка файла кодируется отдельно.

В каждой строке ищутся отдельные слова, и все символы слова сдвигаются по алфавиту циклически вправо на длину слова.

Словом считается любая последовательность подряд идущих символов латинского алфавита, строчных и прописных.

Циклический сдвиг символа по алфавиту вправо на X — замена символа на символ, стоящий в алфавите на X позиций дальше. Если при этом происходит выход за пределы алфавита, счёт начинается с начала алфавита.

Пример циклического сдвига символов на 3 позиции: буква «Е» превращается в букву «Н», буква «t» — в букву «w» буква «Y» — в букву «В».

Напишите эффективную, в том числе и по используемой памяти, программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая должна закодировать строку по указанному алгоритму.

На вход программе подается строка, состоящая из не более чем 250 символов латинского алфавита, пробелов, знаков препинания, разного рода скобок, кавычек и других символов. Строка заканчивается символом «#». Других символов «#» в строке нет.

Программа должна вывести закодированную по указанному алгоритму строку.

Пример входных данных:
Day, mice. «Year» — a mistake#
Пример выходных данных:
Gdb, qmgi. «Ciev» — b tpzahrl#

Решение:

Длина слова

Чтобы сдвинуть символы на длину слова, нужно знать её величину. Посчитаем длину каждого слова строки s:


    s = "…" ;строка со словами и другими символами
    n = длина строки s
    flag = ЛОЖЬ
    Для i от 1 до n ;по каждому символу строки s
        если s[i] буква то;буква-не буква
            если flag то
                len = len + 1
            иначе
                len = 1
                flag = ИСТИНА

После этого алгоритма значение len будет иметь длину слова, а значение i – позицию последнего символа слова. Так что, в стиле Python – [(i-len):i] будет слово из массива.

Двигаем символы

Когда мы достигли последнего символа в слове, самое время сдвинуть каждый его символ:


    …
        если s[i] буква то;буква-не буква
            …
        иначе
            если flag то
                flag = ЛОЖЬ
                Для k от 1 до len ;по каждому символу слова
                    если s[i-k] + len  выходит за алфавит то 
                        s[i-k] = s[i-k] + len – 26 
                    иначе 
                        s[i-k] = s[i-k] + len
    печать s

Переменная flag отвечает за начало подсчёта символов слова в первой ветке условия – «буква-не буква», а во второй ветке – за то, чтобы сдвиг символов в слове был только один раз.

Полный код на Python

   s = "Bike, Zip, Roller, 1345asdfads#"
   total = len(s)
   n = 0
   flag = False

   for i in range(total):
      c = s[i]
      if c.isalpha():
         if flag == False:
            len = 1
            flag = True
          else:
             len += 1
      elif flag == True:
         flag = False
         stmp = ""
         for k in range(len):
            #i-len - возврат к первому симолу слова
            if ord(s[i-len + k].upper()) - ord("A") + len > 25:
               stmp += chr(ord(s[i - len + k]) + len - 26 )
            else:
               stmp += chr(ord(s[i - len + k]) + len )
      #замена одной подстроки на другую
      s = s.replace(s[i - len:i], stmp) 

   print (s)

Пример. ЕГЭ 2011 С4 Вариант 7

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

Районный методист решила, что оценку «отлично» должны получить 20% участников (целое число, с отбрасыванием дробной части).

Для этого она должна определить, какой балл должен был набрать ученик, чтобы получить «отлично».

Если невозможно определить такой балл, чтобы «отлично» получили ровно 20% участников, «отлично» должно получить меньше участников, чем 20%.

Если таких участников не окажется (наибольший балл набрали больше 20% участников) — эти и только эти ученики должны получить «отлично».

Напишите эффективную, в том числе и по используемой памяти, программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая должна вывести на экран наименьший балл, который набрали участники, получившие «отлично». Известно, что информатику сдавало больше 5-ти учеников. Также известно, что есть такое количество баллов, которое не получил ни один участник.

<Фамилия> <Имя> <Номер школы> <Количество баллов>

где <Фамилия> — строка, состоящая не более чем из 30 символов без пробелов, <Имя> — строка, состоящая не более чем из 20 символов без пробелов, <Номер школы> — целое число в диапазоне от 1 до 99, <Количество баллов> — целое число в диапазоне от 1до 100. Эти данные записаны через пробел, причём ровно один между каждой парой (то есть всего по три пробела в каждой строке).

Пример входных данных:
Иванов Иван 50 87
Пример выходных данных:
78

Решение:

Количество оценок

Посчитаем кол-во каждых оценок:


	k[100] ;кол-во оценок
	Для i от 0 до N-1 ;цикл по строкам данных
		ball = оценка из i-й строки данных 
		k[ball] = k[ball] + 1 ;считаем кол-во оценок

Индекс массива k – это конкретная оценка, а его элемент будет хранить кол-во этих оценок.

Количество лучших из 20% участников

Критерий – это 20% от N. Если суммировать оценки, например, в переменную s, то можно получить кол-во лучших оценок равное 20% или более


	s = 0 ;кол-во оценок
	i = 99 ;начинаем с самой высокой оценки, её индекс = 99
	p = N DIV 5 ;p – 20% от N
	Пока s < p  ;цикл по
		s = s + k[i]
		i = i – 1 ;спускаемся к следующей оценке

После этого цикла i будет содержать значение оценки

Возможные варианты

Рассмотрим некоторые варианты разного количества лучших оценок. Для простоты, диапазон оценок [1;5].

N=10 (p=2) из них две пятёрки: k = [? ? ? ? 2] или одна пятёрка, и одна четвёрка: k = [? ? ? 1 1]. В 1-м случае нужно вывести оценку 5, а во 2-м – 4. После алгоритма выше, s = 2. Тогда, для нужного вывода, достаточно условия на равенства p с s :


	s = 0 ;кол-во оценок
	i = 99 ;начинаем с самой высокой оценки, её индекс = 99
	p = N DIV 5 ;p – 20% от N
	Пока s < p  ;цикл по
		s = s + k[i]
		i = i – 1 ;спускаемся к следующей оценке
	если s = p то
		печать i

аналогично, для N=20 (p=4) получим такие выводы для соответствующих последовательностей:

k = [? ? ? ? 4] печать 5

k = [? ? ? 3 1] = [? ? ? 2 2] = [? ? ? 1 3] печать 4

k = [? ? 2 1 1] = [? ? 2 2 0] = [? ? 2 0 2] печать 3

и т. д.

N=20 (p=4) из них три пятёрки и две четвёрки: k = [? ? ? 2 3] или наоборот [? ? ? 3 2]. s = 5, т.е. больше p. По условию нужно выводить либо ровно 20%, либо меньше чем 20%. Тогда для этих двух последовательностей, выводим не четвёрку, а пятёрку. Значит, увеличим i на 1:


	s = 0 ;кол-во оценок
	i = 99 ;начинаем с самой высокой оценки, её индекс = 99
	p = N DIV 5 ;p – 20% от N
	Пока s < p  ;цикл по
		s = s + k[i]
		i = i – 1 ;спускаемся к следующей оценке
	если s = p то
		печать i
	иначе
		i = i + 1 ;возвращаемся к пятёркам
		печать i

По условию некоторых баллов не набрал никто, например, четвёрок: k = [? ? 2 0 3]. Новый алгоритм выше на выводе даст значение 0. Исключим нулевое/вые вхождения:


	иначе
		i = i + 1 ;возвращаемся к пятёркам
		Пока k[i]=0 ;встретили нулевую оценку
			i = i + 1 ;уходим от нулевой оценки
		печать i

Последнее, когда одно значение баллов, и оно больше 20%: N=10 (p=2) k = [? ? ? ? 3] печать 5. Здесь значение s должно быть равно k[i]:


	иначе
		если s=k[i] то
			печать i
		иначе
			i = i + 1
			Пока k[i]=0
				i = i + 1
			печать i

Полный код на Python

   f = open("11C4v01.txt", encoding='utf-8', mode="r")
   n = int(f.readline())
   k = [0] * 100 #кол-во оценок
   for i in range(n):
      #a[0] - Фамилия (она не нужна)
      #a[1] - Имя (оно не нужно)
      #a[2] - номер школы [1..99] (он не нужен)
      #a[3] - балл ученика(цы)	  
      a = f.readline().split()
      iball = int(a[3]) - 1 #iball - [0..99]
      k[iball] += 1

   p = n // 5
   s = 0
   i = 100
   while s &lt p:
      i = i - 1
      s = s + k[i]
   if s == p:
      print(i+1)
   else:
      if k[i] == s:
         print(i+1)
      else:
         i = i + 1
         while k[i] == 0:
            i = i + 1
         print(i+1)

Пример. ЕГЭ 2011 С4 Вариант 8

После единых выпускных экзаменов по информатике в район пришла информация о том, какой ученик какой школы сколько баллов набрал. По положению об экзамене оценку “2” (неудовлетворительно) получают ученики, набравшие меньше 40 баллов. Оценку “3” (удовлетворительно) получают 30% учеников среди оставшихся, за исключением тех из них, кто набрал больше 60 баллов.

Если количество “троечников” оказывается больше 30%, то следует выбрать меньшую границу для оценки “4” (но только если при этом “3” получит хоть кто-нибудь).

Напишите эффективную, в том числе и по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая должна вывести на экран наибольший балл, который набрали участники, получившие “удовлетворительно” и количество таких учеников. Известно, что информатику сдавало больше 50-ти учеников. Также известно, что есть такое количество баллов, которое не получил ни один участник.

<Фамилия> <Имя> <Номер школы> <Количество баллов>

где <Фамилия> — строка, состоящая не более, чем из 30 символов без пробелов, <Имя> — строка, состоящая не более, чем из 20 символов без пробелов, <Номер школы> — целое число в диапазоне от 1 до 99, <Количество баллов> — целое число диапазоне от 1 до 100. Эти данные записаны через пробел, причем ровно один между каждой парой (то есть, всего по три пробела в каждой строке).

Пример входных данных:
Иванов Иван 50 87
Пример выходных данных:
78

Решение:

Количество оценок

Аналогично 2011 С4 № 7 – посчитаем кол-во каждых оценок:


	k[100] ;[1..100] кол-во оценок
	Для i от 0 до N-1 ;цикл по строкам данных
		ball = оценка из i-й строки данных 
		k[ball] = k[ball] + 1 ;считаем кол-во оценок

Индекс массива k – это конкретная оценка, а элемент этого индекса будет хранить кол-во этих оценок.

Количество двоечников и 30% от не двоечников

Посчитаем кол-во двоечников, затем мы их исключим из общего кол-ва учеников:


	s = 0 ;кол-во двоечников
	Для i от 1 до 39 ;первые 39 строк массива с оценками
		s = s + k[i] ;суммируем всех двоечников
	p = (N - s) * 30 DIV 100 ;30% от не двоечников

Кол-во троечников

В 2011 С4 №7 мы искали только 20% лучших, значит критерий поиска был простым: s &lt p. Теперь нужно искать не более 30% троечников и у них максимальный балл 60, значит критерий будет составным:


	s = 0 i = 40 ;сбрасываем сумму и начинаем с троечников
	Пока s < p И i < 61  ;составной критерий для троечников
		i = i + 1 ;переходим к следующей оценке
		s = s + k[i];суммируем всех троечников

Возможные варианты

Рассмотрим некоторые варианты разного количества троечников.

Кол-во троечников составляет ровно 30%, и их максимальный балл меньше 60:


	Пока s < p И i < 61  ;составной критерий для троечников
		i = i + 1 ;переходим к следующей оценке
		s = s + k[i];суммируем всех троечников
	если s = p то ;кол-во 3-ков 30% и их макс балл < 60
		;максимальная оценка и кол-во таких оценок
		печать i s

Кол-во троечников меньше 30%, и их максимальный балл равен 60:

	иначе если i = 60 И s < p то
		;максимальная оценка и кол-во таких оценок
		печать 60 s

Но! Если максимальный балл будет меньше чем 60, программа всё равно выведет 60… (в этом место нужно доработать).

Троечники набравшие более 30% и какой-то один одинаковый:

	иначе если  s = k[i] то
		;максимальная оценка и кол-во таких оценок
		печать i s

Остальные троечники набравшие более 30% неодинаковые баллы:


	;убираем троечников, которые вышли за допустимую границу
	s = s - k[i]
	i = i – 1
	Пока k[i]=0
		i = i - 1
	печать i s ;максимальная оценка и кол-во таких оценок

Подобный алгоритм описан в В 2011 С4 v07, только там, для избавления от отсутствующих оценок, нужно перемещаться в другую сторону массива оценок.

Полный код на Python

  f = open("11C4v01.txt", encoding='utf-8', mode="r")
  n = int(f.readline())
  k = [0] * 100 #кол-во оценок
  for i in range(n):
	#a[0] - Фамилия (она не нужна)
	#a[1] - Имя (оно не нужно)
	#a[2] - номер школы [1..99] (он не нужен)
	#a[3] - балл ученика(цы)
	a = f.readline().split()
	iball = int(a[3]) - 1 #iball - [0..99]
	k[iball] += 1
  s = 0
  i = 0
  for i in range(39): #[0..38] т.е. первые 39 баллов
	s = s + k[i]
  print("i:",i," s:",s)
  p = (n-s)*30 // 100
  s = 0
  
  #старое значение i=38, а троечники начинаются с 39,
  зн. увеличим i на 1 до обращения к массиву k:
  while s < p and i < 59: #здесь 60 это индекс 61-го балла!
	i = i + 1
	s = s + k[i]

  if s == p:
	print(i+1," ",s)

  elif i == 59 and s < p:
	#выведет 60 даже если максимальный балл троечников < 60
	print("60", s)

  elif s == k[i]:
	print(i + 1, " ", s)
  else:
	s -= k[i]
	i -= 1
  while k[i] == 0:
	i -= 1
  print(i + 1, " ", s)

Пример. ЕГЭ 2011 С4 Вариант 9

На вход программе подается последовательность символов, заканчивающаяся символом #. Другие символы # во входной последовательности отсутствуют.

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

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

Строчные и прописные буквы не различаются.

Напишите эффективную, в том числе и по используемой памяти, программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая должна решать поставленную задачу.

Пример входных данных:
Day, mice. «Year» — a mistake#
Пример выходных данных:
A
4

Решение:

Количество каждой буквы в строке


    s = "…" ;строка со словами и другими символами
    n = длина строки s
    num[26] ;массив количества латинских букв алфавита
    Для i от 1 до n ;по каждому символу строки s
        если s[i] буква то ;буква-не буква
            k = номер буквы
            ;увеличиваем счётчик количества таких букв
            num[k] = num[k] + 1

Найдём максимум и их количество

Найдём буквы, встречающиеся наибольшее количество раз, и число этих раз в массиве s:


    ic = 0 ;индекс первой буквы ('A') в массиве num
    k = 1 ;счётчик количества максимумов в массиве num
    Для i от 1 до 26 ;от 'B' до 'Z'
        если num[i] > num[ic] то ; находим максимум
            ic = i ;индекс первой буквы меняем на индекс второй
            k = 1
        иначе если num[i] = num[ic] то ;такой же максимум
            k = k + 1 ;увеличиваем счётчик кол-ва максимумов

Вывод результатов


    если k = 1 то ;если максимум один
        печать ic ;символ ic
    иначе
    Для i от 0 до 26 ;от 'A' до 'Z'
        если num[i] = num[ic] то
            печать i ' ' ;символ i
    печать num[ic] ;кол-во максимумов

Полный код на Python

   #s = "Day, mice. 'Year' - a mistake#"
   s = "ABCD ABCE ABCF#"
   num = [0] * 26 #массив кол-ва букв алфавита

   for c in s:
      if c.isalpha():
         k = ord(c.upper()) - ord('A')
         num[k] += 1
   k = 1
   ic = 0
   for i in range(1,len(num)):
      if num[i] > num[ic]:
         ic = i
         k = 1
      elif num[i] == num[ic]:
         k += 1

   if k == 1:
      print (chr(ic + ord('A')))
   else:
      for i in range(0, len(num)):
         if num[i] == num[ic]:
            print(chr(i + ord('A')),end=" ")
         print()
   print(num[ic])

Пример. ЕГЭ 2011 С4 Вариант 10

Программа должна вывести на экран символы латинского алфавита, в порядке увеличения частоты встречаемости во входной последовательности.

Если буква во входной последовательности не встречается, её выводить не нужно.

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

Строчные и прописные буквы не различаются.

Пример входных данных:
Aced, ccedaa f#
Пример выходных данных:
FDEAC

Решение:

Количество каждой буквы в строке

Для вывода букв, в порядке увеличения частоты встречаемости, нужен массив количества букв алфавита:


    s = "…" ;строка со словами и другими символами
    n = длина строки s
    num[26] ;массив количества латинских букв алфавита
    Для i от 1 до n ;по каждому символу строки s
        если s[i] буква то ;буква-не буква
            k = номер буквы
          ;увеличиваем счётчик количества таких букв
            num[k] = num[k] + 1

Сортировка

Отсортируем массив num по возрастанию:


    Для i от 1 до 25 ;от 'A' до 'Y'
        Для j от 25-i
            если num[j] > num[j+1] то
                t = num[j]
                num[j] = num[j+1]
                num[j+1] = t ;

Получили отсортированную по возрастанию, частоту встречаемости символов, но неизвестно какие это будут символы – индексы будут утеряны.

Выход такой: завести массив символов по алфавиту sym. Далее, одновременно с сортировкой массива num, будут перестановки элементов массива sym с теми же индексами, что и индексы массива num:


    …
    sym = [a,b,c,…,z]
    Для i от 1 до 25 ;от 'A' до 'Y'
        Для j от 25-i ;
            если num[j] > num[j+1] то
                t = num[j]              c = sym[y]
                num[j] = num[j+1]       sym[j] = sym[j+1]
                num[j+1] = t            sym[j+1] = c

Вывод результатов

Если дана строка Aced, ccedaa f , то после сортировки массивы num и sym будут такими:

num — [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 2 2 3 3]

sym — [b g h I j k l m n o p q r s t u v w x y z f d e a c]

Выводим символы массива sym, начиная с символа f:


    j = 22 ;индекс символа 'f'
    Для i от j до 26 ;от 22 до 26
        печать sym[i]

Найти значение первого символа легко: если посмотреть на массив num, то в нём 21 нуль:


    j = 0 ;индекс символа 'f'
    Пока num[j] = 0 ; после цикла j будет равно 22
        j = j + 1
    Для i от j до 26 ;от 22 до 26
        печать sym[i]

Полный код на Python

   s = "Aced, ccedaa f#" #символ '#' в этом коде не нужен
   num = [0] * 26 #массив кол-ва латинских букв алфавита
   sym = [0] * 26 #массив латинских букв алфавита ('a'.. 'z')

   for i in range(26):
      sym[i] = chr(i+65)

   for c in s:
      if c.isalpha():
         k = ord(c.upper()) - ord('A')
         num[k] += 1

   for i in range(26 - 1):
      for j in range(26 - i - 1):
         if num[j] > num[j + 1]:
            num[j], num[j + 1] = num[j + 1], num[j]
            sym[j], sym[j + 1] = sym[j + 1], sym[j]

   j=0
   while num[j] == 0:
      j += 1
   for i in range(j, 26):
      print(sym[i],end=" ")

ЕГЭ 2011 С4

0 Responses to “ЕГЭ 2011 С4”

Мета

Разделы