Отправлено: 17.03.13 10:53. Заголовок: Решения C4 на Visual C++

Здравствуйте!
Так как я сегодня узнал, что пролетел с результатами по ИТМОшной олимпиаде на заключительном этапе и не получу диплома, который дал бы мне поступление, то теперь начинается двухмесячная наработка ЕГЭ. Собственно, самый сложный номер из всего ЕГЭ для меня - это С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; }

 Отправлено: 17.03.13 11:34. Заголовок: Задача #2 На вход пр..

Задача #2
Скрытый текст

На вход программы подается текст на английском языке, заканчивающийся точкой (другие символы “.” в тексте отсутствуют). Требуется написать программу, которая будет определять и выводить на экран английскую букву, встречающуюся в этом тексте чаще всего, и количество там таких букв. Строчные и прописные буквы при этом считаются не различимыми. Если искомых букв несколько, то программа должна выводить на экран первую из них по алфавиту. Например, пусть файл содержит следующую запись: It is not a simple task. Yes! Чаще всего здесь встречаются буквы I, S и T (слово Yes в подсчете не учитывается, так как расположено после точки). Следовательно, в данном случае программа должна вывести два символа, разделенных пробелом: I 3

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

using namespace std;

int main() {
int alphabet['Z'+1]; // теоретически лишняя память, можно было и каждый раз вычетать 'A' при каждом обращении, но это разве обязательно?
for(int i = 'A'; i <= 'Z'; i++)
alphabet[i] = 0;

char chr;
cin >> chr;
while(chr != '.') {
if(chr >= 'a' && chr <= 'z') chr -= 'a'-'A';
if(chr >= 'A' && chr <= 'Z') alphabet[chr] ++;
cin >> chr;
}

char max_char = 'A';
int max = alphabet['A'];
for(int i = 'A'; i <= 'Z'; i++)
if(max < alphabet[i]) {
max = alphabet[i];
max_char = i;
}

cout << max_char << " " << max;
return 0;
}

 Отправлено: 17.03.13 11:39. Заголовок: Задача #3 (реализаци..

Задача #3 (реализация похожа на #2)

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

На вход программы подаются произвольные алфавитно-цифровые символы. Ввод этих символов заканчивается точкой. Требуется написать программу, которая будет печатать последовательность строчных английских букв ('a' 'b'... 'z') из входной последовательности и частот их повторения. Печать должна происходить в алфавитном порядке. Например, пусть на вход подаются следующие символы: fhb5kbfыshfm. В этом случае программа должна вывести b2 f3 h2 kl ml s1

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

using namespace std;

int main() {
int alphabet['z'+1];
for(int i = 'a'; i <= 'z'; i++)
alphabet[i] = 0;

char chr;
cin >> chr;
while(chr != '.') {
if(chr >= 'a' && chr <= 'z') alphabet[chr]++;
cin >> chr;
}

for(int i = 'a'; i <= 'z'; i++)
if(alphabet[i] > 0) printf("%c%d\n", i, alphabet[i]);
return 0;
}

 Отправлено: 17.03.13 11:51. Заголовок: Задача #4 На вход ..

Задача #4

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

На вход программы подаются фамилии и имена учеников. Известно, что общее количество учеников не превосходит 100. В первой строке вводится количество учеников, принимавших участие в соревнованиях, N. Далее следуют N строк, имеющих следующий формат: <Фамилия> <Имя> Здесь <Фамилия> – строка, состоящая не более чем из 20 символов; <Имя> – строка, состоящая не более чем из 15 символов. При этом <Фамилия> и <Имя> разделены одним пробелом. Примеры входных строк: Иванова Мария Петров Сергей Требуется написать программу, которая формирует и печатает уникальный логин для каждого ученика по следующему правилу: если фамилия встречается первый раз, то логин – это данная фамилия, если фамилия встречается второй раз, то логин – это фамилия, в конец которой приписывается число 2 и т.д. Например, для входной последовательности Иванова Мария Петров Сергей Бойцова Екатерина Петров Иван Иванова Наташа будут сформированы следующие логины: Иванова Петров Бойцова Петров2 Иванова2

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

using namespace std;

int main() {
map<string, int> fios;

int n;
cin >> n;

for(int i = 0; i < n; i++) {
string fn, sn;
cin >> fn >> sn;
if(fios.count(fn) == 0) {
cout << fn << endl;
fios[fn] = 1;
} else {
fios[fn]++;
cout << fn << fios[fn] << endl;
}
}
return 0;
}

 Отправлено: 17.03.13 12:04. Заголовок: Задача #5 На городс..

Задача #5
Скрытый текст

На городской олимпиаде по информатике участникам было предложено выполнить 3 задания, каждое из которых оценивалось по 25-балльной шкале. Известно, что общее количество участников первого тура олимпиады не превосходит 250 человек. На вход программы подаются сведения о результатах олимпиады. В первой строке вводится количество участников N. Далее следуют N строк, имеющих следующий формат: <Фамилия> <Имя> <Баллы> Здесь <Фамилия> – строка, состоящая не более чем из 20 символов; <Имя> – строка, состоящая не более чем из 15 символов; <Баллы> – строка, содержащая три целых числа, разделенных пробелом, соответствующих баллам, полученным участником за каждое задание первого тура. При этом <Фамилия> и <Имя>, <Имя> и <Баллы> разделены одним пробелом. Примеры входных строк: Петрова Ольга 25 18 16 Калиниченко Иван 14 19 15 Напишите программу, которая будет выводить на экран фамилию и имя участника, набравшего максимальное количество баллов. Если среди остальных участников есть ученики, набравшие такое же количество баллов, то их фамилии и имена также следует вывести. При этом имена и фамилии можно выводить в произвольном порядке.

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

using namespace std;

int main() {
map<string, int> fios;

int n;
cin >> n;

int max = 0;
for(int i = 0; i < n; i++) {
string fn, sn;
int a, b, c;
cin >> fn >> sn >> a >> b >> c;
int sum = a+b+c;
fios[fn + " " + sn] = sum;
if(sum > max) max = sum;
}

map<string, int>::iterator it;
for(it = fios.begin(); it != fios.end(); it++)
if((*it).second == max) cout << (*it).first << endl;
return 0;
}

Так, я лучше остановлюсь, а то до меня не доходит одно: если мне говорят, что память не должна зависеть от количества входных данных, но при этом говорят, что она строго лимитирована, НО при этом нужно писать эффективную по памяти программу, то как поступать: я могу завести два массива со строго определённым лимитом и оно будет занимать места больше, чем то, что использую выше - Map, который будет занимать ровно столько, сколько нужно, но при этом "в худшем случае" будет меньше или равен размеру тех двух массивов.

 Отправлено: 17.03.13 13:19. Заголовок: Задача #48 Соревнов..

Задача #48
Скрытый текст

Соревнования по игре «Тетрис-онлайн» проводятся по следующим правилам. Каждый участник регистрируется на сайте игры под определённым игровым именем. Имена участников не повторяются. Чемпионат проводится в течение определённого времени. В любой момент этого времени любой зарегистрированный участник может зайти на сайт чемпионата и начать зачётную игру. По окончании игры её результат (количество набранных очков) фиксируется и заносится в протокол. Участники имеют право играть несколько раз. Количество попыток одного участника не ограничивается. Окончательный результат участника определяется по одной игре, лучшей для данного участника. Более высокое место в соревнованиях занимает участник, показавший лучший результат. При равенстве результатов более высокое место занимает участник, раньше показавший лучший результат. В ходе соревнований заполняется протокол, каждая строка которого описывает одну игру и содержит результат участника и его игровое имя. Протокол формируется в реальном времени по ходу проведения чемпионата, поэтому строки в нём расположены в порядке проведения игр: чем раньше встречается строка в протоколе, тем раньше закончилась соответствующая этой строке игра. Напишите эффективную, в том числе по памяти, программу, которая по данным протокола определяет победителя и призёров. Гарантируется, что в чемпионате участвует не менее трёх игроков. Перед текстом программы кратко опишите алгоритм решения задачи и укажите используемый язык программирования и его версию. Описание входных данных Первая строка содержит число N- общее количество строк протокола. Каждая из следующих N строк содержит записанные через пробел результат участника (целое неотрицательное число, не превышающее 100 миллионов) и игровое имя (имя не может содержать пробелов). Строки исходных данных соответствуют строкам протокола и расположены в том же порядке, что и в протоколе. Гарантируется, что количество участников соревнований не меньше 3. Описание выходных данных Программа должна вывести имена и результаты трёх лучших игроков по форме, приведённой ниже в примере. Пример входных данных: 9 69485 Jack 95715 qwerty 95715 Alex 83647 М 197128 qwerty 95715 Jack 93289 Alex 95715 Alex 95715 M Пример выходных данных для приведённого выше примера входных данных: 1 место. qwerty (197128) 2 место. Alex (95715) 3 место. Jack (95715)

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

using namespace std;

int main() {
int max1 = -1, max2 = -1, max3 = -1;
string nick1 = "";
string nick2 = "";
string nick3 = "";
int n;
cin >> n;
for(int i = 0; i < n; i++) {
string nick;
int score;
cin >> score >> nick;
if(score > max1) {
if(nick1 != nick) {
nick3 = nick2;
max3 = max2;
max2 = max1;
nick2 = nick1;
}
max1 = score;
nick1 = nick;
} else if(score > max2 && nick1 != nick) {
if(nick2 != nick) {
max3 = max2;
nick3 = nick2;
}
max2 = score;
nick2 = nick;
} else if(score > max3 && nick2 != nick && nick1 != nick) {
max3 = score;
nick3 = nick;
}
}
cout << "1 место. " << nick1 << " (" << max1 << ")" << endl;
cout << "2 место. " << nick2 << " (" << max2 << ")" << endl;
cout << "3 место. " << nick3 << " (" << max3 << ")" << endl;
return 0;
}

Жуткая задача, я не понимаю, каким образом её можно решить без компьютера на листочке и просчитать всевозможные варианты без тестирования вручную за то время, которое будет у нас на ЕГЭ...

 Отправлено: 17.03.13 14:09. Заголовок: Задача #46 Странная..

Задача #46

Странная задача. Её я писал в своё время на Статграде, но решил только с массивами, поэтому один балл с меня сняли.
Потом уже посидел с учителем, который мне объяснил математический смысл задачи (самая большая площадь - это 1/2 * произведение максимальной длины отрезка (максимальный х минус минимальныйх), который лежит на Ox (y = 0) и максимального y по модулю. х у третьей точки не важен, так как площадь треугольника с любым х у третьей точки будут равны, ибо перпендикуляр одной и той же длины до прямой y = максимальный y по модулю)

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

46) На плоскости дан набор точек с целочисленными координатами. Необходимо найти треугольник наибольшей площади с вершинами в этих точках, одна из сторон которого лежит на оси OX. Напишите эффективную, в том числе по памяти, программу, которая будет решать эту задачу. Размер памяти, которую использует Ваша программа, не должен зависеть от длины переданной последовательности чисел. Укажите используемый язык программирования и его версию. В первой строке вводится одно целое положительное число – количество точек N. Каждая из следующих N строк содержит два целых числа – сначала координата х, затем координата у очередной точки. Программа должна вывести одно число – максимальную площадь треугольника, удовлетворяющего условиям задачи. Если такого треугольника не существует, программа должна вывести ноль. Пример входных данных: 6 0 0 2 0 3 3 5 5 -6 -6 Пример выходных данных для приведенного выше примера входных данных: 6

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

using namespace std;

int main() {
int max_x = 0;
int min_x = 0;
int max_mod_y = 0;

bool mmax_x = false;
bool mmin_x = false;
bool mmax_mod_y = false;

int n;
cin >> n;
for(int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
if(y == 0) {
if(x > max_x || mmax_x == false) {
max_x = x;
mmax_x = true;
} else if(x < min_x || mmin_x == false) {
min_x = x;
mmin_x = true;
}
} else {
if(abs(y) > max_mod_y || mmax_mod_y == false) {
max_mod_y = abs(y);
mmax_mod_y = true;
}
}
}
float s = (max_x-min_x)*max_mod_y/2;
printf("%f", s);
return 0;
}

Вопрос лишь в том, что делает ТАКАЯ задача (она не сложная, но ставит в тупик человека, который не дружит с математикой) на ЕГЭ по информатике - вопрос.

...

И да, вопрос ещё один: возвращает данная программа 6.00000 - неотформатированный float. Будет ли придирка за это? Хотя с другой стороны, в задаче вообще не сказан формат выходных данных (в плане точности).

 Отправлено: 17.03.13 14:36. Заголовок: Задача #45 Сначала ..

Задача #45

Сначала испугался, когда случайно увидел решение, слишком уж объёмное.
Однако C++ уменьшил его раз в 5.

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

На вход программе подаются сведения о пассажирах, желающих сдать свой багаж в камеру хранения на заранее известное время до полуночи. В первой строке сообщается число пассажиров N, которое не меньше 3, но не превосходит 1000; во второй строке – количество ячеек в камере хранения K, которое не меньше 10, но не превосходит 1000. Каждая из следующих N строк имеет следующий формат: <Фамилия> <время сдачи багажа> <время освобождения ячейки>, где <Фамилия> – строка, состоящая не более чем из 20 непробельных символов; <время сдачи багажа> – через двоеточие два целых числа, соответствующие часам (от 00 до 23 – ровно 2 символа) и минутам (от 00 до 59 – ровно 2 символа); <время освобождения ячейки> имеет тот же формат. <Фамилия> и <время сдачи багажа>, а также <время сдачи багажа> и <время освобождения ячейки> разделены одним пробелом. Время освобождения больше времени сдачи. Сведения отсортированы в порядке времени сдачи багажа. Каждому из пассажиров в камере хранения выделяется свободная ячейка с минимальным номером. Если в момент сдачи багажа свободных ячеек нет, то пассажир уходит, не дожидаясь освобождения одной из них. Требуется написать программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая будет выводить на экран для каждого пассажира номер ему предоставленной ячейки (можно сразу после ввода данных очередного пассажира). Если ячейка пассажиру не предоставлена, то его фамилия не печатается. Пример входных данных: 3 10 Иванов 09:45 12:00 Петров 10:00 11:00 Сидоров 12:00 13:12 Результат работы программы на этих входных данных: Иванов 1 Петров 2 Сидоров 1

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

using namespace std;

int main() {
int k, n;
cin >> n >> k;
int a[1001][2];

for(int i = 0; i < k; i++)
for(int j = 0; j < 2; j++)
a[i][j] = 0;

for(int i = 0; i < n; i++) {
string fn;
int h1,m1,h2,m2;
char temp;

cin >> fn >> h1 >> temp >> m1 >> h2 >> temp >> m2;
for(int j = 0; j < k; j++)
if(h1 >= a[j][0] && m1 >= a[j][1]) {
a[j][0] = h2;
a[j][1] = m2;
cout << fn << " " << (j+1) << endl;
break;
}
}
return 0;
}

 Отправлено: 18.03.13 13:45. Заголовок: Жирно, жирно будет....

Жирно, жирно будет.... Т. е. вам все понятно, вы все знаете и теперь Костантин Юрьевич ЛИЧНО должен быть вашим репетитором.... Слишком жирно...

 Отправлено: 18.03.13 14:51. Заголовок: Репетитор для меня -..

Репетитор для меня - это человек, который, тратя своё время, по списку тем всё разъясняет или с нуля объясняет так, чтобы было человеку понятно.
Здесь же я не прошу тратить очень много времени, тем более я даже не прошу проверять каждую задачу тщательно на предмет багов. Я прошу лишь посмотреть оформление и хочу узнать, какие в каких задачах есть огрехи, за которые бы любой проверяющий снял балл. Да и к тому же, смысл тогда этого форума, если не помощь именно в таких делах? Всё-таки я спрашиваю конкретные вопросы на конкретных примерах и не прошу за меня что-либо делать.

 Отправлено: 18.03.13 15:23. Заголовок: 3ap пишет: лишь пос..

3ap пишет:

цитата:

лишь посмотреть оформление и хочу узнать, какие в каких задачах есть огрехи

И для этого вы планируете выкладывать решения 5 задач ежедневно?

цитата:

эту тему на форуме я хотел бы использовать ТОЛЬКО В СВОИХ ЦЕЛЯХ, то есть: В день я сажусь и решаю 5 задач из набора задач с главной страницы, выкладываю решения тут и прошу указать мне на ошибки в плане оптимизации.

Это и называется - репетиторство (просто бесплатное)

 Отправлено: 18.03.13 15:53. Заголовок: проол пишет: Это и ..

проол пишет:

цитата:

Это и называется - репетиторство (просто бесплатное)

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

Такая формулировка уже не делает из меня наглого типа?

 Отправлено: 18.03.13 16:21. Заголовок: Ну, так уже лучше.....

Ну, так уже лучше... Осталось дождаться внимания тех, кому Вы "делаете доброе дело"... Удачи!

 Отправлено: 18.04.13 20:30. Заголовок: А можно ли?

А можно ли использовать библиотеку map в ЕГЭ&

 Отправлено: 18.04.13 21:05. Заголовок: MerlinKoss пишет: А ..

MerlinKoss пишет:

цитата:

А можно ли использовать библиотеку map в ЕГЭ

В задаче С4 можно использовать любые возможности языка.

 Отправлено: 05.05.13 10:49. Заголовок: Ну, так уже лучше.....

цитата:

Ну, так уже лучше... Осталось дождаться внимания тех, кому Вы "делаете доброе дело"... Удачи!

А вот и я, мне было необходимо посмотреть решения задач на плюсах :)
Только форум убивает пробелы и табуляцию - глаза сломаешь.

 Отправлено: 01.12.13 18:03. Заголовок: егэ

Что насчёт кодировок в консоле?