Форум: «ЕГЭ по информатике»

Здравствуйте!
Так как я сегодня узнал, что пролетел с результатами по ИТМОшной олимпиаде на заключительном этапе и не получу диплома, который дал бы мне поступление, то теперь начинается двухмесячная наработка ЕГЭ. Собственно, самый сложный номер из всего ЕГЭ для меня - это С4. Сложность заключается в том, что нельзя использовать привычные для любого программиста инструменты (например, динамические массивы), нужно всё делать налету и продумывать сложность алгоритма. Для меня это хоть и не ново (какое-то время занимался олимпиадным программированием), но всё же такие простые задачи решать "эффективно" нецелесообразно, на мой взгляд, как минимум потому, что на дворе 2013 год и затраты на просчёт и хранение информации в памяти уже не являются существенными. Но у каждого ЕГЭ свои причуды, так что делать нечего...

Так вот, эту тему на форуме я хотел бы использовать только в своих целях, то есть:
В день я сажусь и решаю 5 задач из набора задач с главной страницы, выкладываю решения тут и прошу указать мне на ошибки в плане оптимизации.
Было бы очень хорошо, если бы Константин Юрьевич самолично называл мне их, но я думаю, для меня это будет слишком жирно, да и несколько задач за раз изучать и прописывать все проблемы - это геморрой.
Я думаю, что это будет продуктивно по двум причинам: во-первых, я сам переключусь на программирование под ЕГЭ и уловлю принцип, во-вторых, потом можно будет составить целый сборник решённых задач и возможные проблемы на другом языке, да и остальным можно будет поучиться на моих ошибках :3

К тому же, объясню, почему я не хочу этого делать сам по ответам. Во-первых, язык другой и инструменты разные. Хоть я и понимаю, что излюбленный Паскаль проще проверять учителям\преподавателям, но я категорически его перестал воспринимать после изучения C\C++. Во-вторых, не всегда углядишь что не так и только опытный глаз сможет сразу увидеть неправильное.

Начал я с задачи, которая была на каком-то из Статградов, потому что уже изучал её:
В списке она значится под номером 44.

Скрытый текст

На электронную почту Вам пришло письмо, подписанное аббревиатурой (первыми буквами фамилии, имени и отчества (далее - ФИО) отправителя). Аббревиатура оказалась Вам незнакома. У Вас есть список всех предполагаемых отправителей, взятый из ранее полученных писем, среди которых различных людей с такой аббревиатурой не больше 10.
Вам предлагается написать эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка, например Borland Pascal 7.0), которая определит всех вероятных адресатов – людей, ФИО которых можно сократить до нужной аббревиатуры. ФИО следует выдать в порядке убывания частоты их встречаемости в списке.
На вход программе в первой строке подается аббревиатура – строка, состоящая из трех заглавных латинских букв. Во второй строке находится число N – количество ФИО, полученных в результате анализа почты, не все из них подходят под указанную аббревиатуру. Значение N может быть очень велико. В каждой из следующих N строк записано три слова: Фамилия Имя Отчество соответствующего человека. Слова разделяются одним пробелом. В конце и в начале строки пробелов нет. Все слова записаны заглавными латинскими буквами. Длина ФИО не превышает 100 символов. Гарантируется, что хотя бы один человек с нужной аббревиатурой есть.

#include <stdio.h>
#include <map>
#include <string>
#include <iostream>

using namespace std;

int main() {
string abbr;
int n;
map<string, int> fios;
cin >> abbr >> n;
for(int i = 0; i < n; i++) {
string fn,sn,mn;
cin >> fn >> sn >> mn;
if(fn[0] == abbr[0] && sn[0] == abbr[1] && mn[0] == abbr[2]) {
string fio = fn + ' ' + sn + ' ' + mn;
if(fios.count(fio) == 0) fios[fio] = 1;
else fios[fio] ++;
}
}

map<string, int>::iterator it;
for(int i = 10; i >= 1; i--)
for(it = fios.begin(); it != fios.end(); it++)
if((*it).second == i) cout << (*it).first << ' ' << (*it).second << endl;

return 0;
}

Скрытый текст

Не потерять задачу:

#include <stdio.h>
#include <string>
#include <iostream>

using namespace std;

int main() {
freopen("input.txt", "rt", stdin);
freopen("output.txt", "wt", stdout);
int n;
const int pre = 60001;

int amin1 = pre;
int amin2 = pre;
int bmin1 = pre;
int bmin2 = pre;

cin >> n;
for(int i = 0; i < n; i++) {
int v;
cin >> v;
if(v%2==0) {
if(amin1 > v) {
amin2 = amin1;
amin1 = v;
} else if(amin2 > v)
amin2 = v;
} else {
if(bmin1 > v) {
bmin2 = bmin1;
bmin1 = v;
} else if(bmin2 > v)
bmin2 = v;
}
}

int sum1 = amin1+amin2;
int sum2 = bmin1+bmin2;
int sum3 = amin1+bmin1;

if(sum1 > pre && sum2 > pre) cout << sum3;
else if(sum1 < pre && sum2 > pre) cout << sum1;
else if(sum1 < pre && sum2 < pre) cout << min(sum1,sum2);
else if(sum1 > pre && sum2 < pre) cout << sum2;

return 0;
}