ЕГЭ С4, 26, 27

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

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

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

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

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

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

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

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

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

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

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

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

Решение:

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

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

Выбор лучших

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

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

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

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

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

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

	max1 = max2 =-1
	цикл для всех из 50-й школы
		если ball > max1 то
			max2 = max1
			max1 = ball
	
  1. Теперь случай, где два одинаковых максимума(5): [1 5 3 4 5]. Добавим новую ветку условия:

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

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

  1. Второй максимум(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-м условиях стоят одинаковые операторы – можно было бы написать одно сложное условие, однако далее, операторы будут меняться ).

  1. Последний случай. Количество вторых максимумов(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()
      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-ти учеников района. Также известно, что в районе школы с некоторыми номерами не существуют.

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

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

где <Фамилия> — строка, состоящая не более, чем из 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-ти учеников района. Также известно, что в районе школы с некоторыми номерами не существуют.

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

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

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

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

Решение:

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

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

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

Сумму баллов по школе получаем как в примере второго варианта 2011 С4 – создаём массив 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, <Количество баллов> — целое число в диапазоне от 1 до 100. Эти данные записаны через пробел, причём ровно один между каждой парой (то есть, всего по три пробела в каждой строке).

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

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

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

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

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

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

Решение:

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

Каждая строка данных содержит номер школы, который мы присвоим в переменную 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-ти учеников района. Также известно, что в районе школы с некоторыми номерами не существуют.

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

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

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

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

Решение:

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

Подобное было в С4 2011 №1 и №4. Каждая строка данных содержит номер школы, который мы присвоим в переменную m. Эта 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, проверим их содержимое: значение элементов массива amt будем сравнивать с «подозрительной ситуацией», а массив bal сохранит значение балла в переменную ball, если «подозрительная» школа будет одна. Подсчёт «подозрительных» школ будем вести в переменной 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)

0 Responses to “ЕГЭ С4, 26, 27”


Comments are currently closed.



Яндекс.Метрика
Топ Разработка игр