Отправлено: 21.06.14 18:20. Заголовок: Оцените, пожалуйста, решение

Хочу пойти на апелляцию по поводу задания С1, но боюсь, что снизят баллы за С4. Проверьте, пожалуйста, решение и скажите, снизят ли балл за него или нет (Сейчас мне поставили 3).

Условие примерно такое:
На входе программа получает последовательность чисел
(Например: 1 2 3 4 5 6 7 8 9)

Пусть S - сумма квадратов чисел A и B (S = A^2 + B^2). Причем между A и B должно быть не меньше 4 чисел.
Из примера выше числа A и B могут быть равны: 1 и 6, 1 и 7, 1 и 8, 1 и 9, 2 и 7, 2 и 8 и т.д.
Нужно найти максимально возможное значение S для этой последовательности

На вход программе в первой строчке подается число N - количество чисел (N>5)
В следующих N строках записаны вещественные числа
Пример input:
10
11
2.1
12
66
45
1
28
13
35
11

output для этого примера:
5581

Мой ответ:
Описание программы:
1) Создаем массив, в котором будем хранить 6 чисел
a = {0, 0, 0, 0, 0, 0);

2) Заполним его первыми пятью числами. Получим:
a = {0, 10, 11, 2.1, 12, 66}

3) Получаем следующее число и ставим его в конец массива, но перед этим:

4) Проверяем a[0] > a[1], если это так, то a[0] сохраняем, а остальные сдвигаем влево на 1 позицию. Иначе все элементы сдвигаем влево, а первый удаляем
Получим: a = {10, 11, 2.1, 12, 66, 45} (где 45 - полученное число)

5) Считаем (a[0])^2 + (a[5])^2. Если эта сумма больше той, которую получили на прошлых выполнениях цикла, то запоминаем ее. Повторяем действия 3,4,5 до тех пор, пока нам дают новые числа. В конце выводим полученную сумму. Она и будет наибольшей

Массив a[] как бы "пробегает" по последовательности чисел, оставляя в первом элементе максимальное число, до которого "могут дотянуться" новые полученные числа.

Исходный код на C++:

цитата:

#include <iostrem> int main() { int N; //тут будет храниться количество чисел std::cin>>N; double a[6]={0}, n, s=0; //s - переменная для суммы for(int i=1; i<=5; ++i) //заполняем массив первыми 5-ю числами { std::cin>>n; a=n; } N-=5; //Уменьшаем N, т.к. 5 чисел уже записали for(int i=0; i<N; ++i) { if(a[0] < a[1]) //Если первое больше второго, сохраняем первое a[0] = a[1]; a[1]=a[2]; a[2]=a[3]; a[3]=a[4]; a[4]=a[5]; //сдвигаем элементы a[5] = n; if(a[0]*a[0] + a[5]*a[5] > s) // проверяем сумму s = a[0]*a[0] + a[5]*a[5]; } std::cout<<s; return 0; }

В исходном коде нашел 1 грубую ошибку. Не считываю новые числа в переменную n во втором цикле for. Возможно, что работу оценивали по алгоритму на русском языке, либо просто пропустили ошибку. Иначе 3 балла бы не поставили.

 Отправлено: 06.04.15 12:23. Заголовок: оцените решение задачи 48

Коллеги, оцените наше решение 48-й задачи про Тетрис, которое мы с моим учеником Владом придумали вместе.
Вот задание.

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

Вот текст программы.

type
tgamer=record
nik:string;
bal:integer;
end;
var b,c:tgamer;
a : array [1..4] of tgamer;
i,n,k,m :integer;
d,f:string;

function FindNik(nik:string): integer;
var i: integer;
begin
result :=-1;
for i:=1 to 4 do
if a [ i ].nik=nik then
begin
result :=i;
exit
end;
end;

function FindBal(bal:integer): integer;
var i: integer;
begin
result:= -1;
for i:=1 to 4 do
if a[ i ].bal=bal then
begin
result:=i;
exit
end;
end;

procedure Sort;
var
i,j,k,m, max :integer;
temp : tgamer;
begin
for i:=1 to 3 do
begin
max:=a [ i ] .bal;
k:=i;
for j:=i to 4 do
if a[j].bal >max then
begin
max:=a[j].bal;
k:=j;
end;
temp:=a[ i ];
a[ i ]:=a[k];
a[k]:=temp;
end;
end;


begin
readln (n);
for i:=1 to n do
begin
read (k);
readln(d);
d:=Trim(d);
f:='';

// обработать очередной результат
m:= FindNik(d);
if m>0 then begin
if k>a[m].bal then
a[m].bal:=k;
end
else begin
a[4].bal:=k;
a[4].nik:=d
end;
m:=FindBal(k);
if m>0 then
begin
a[m].bal:= a[m].bal+1;
f:=a[m].nik
end;
Sort;
if f<>'' then
begin
m:=FindNik(f);
a[m].bal:=a[m].bal-1;
end;
end;
writeln ('1 место: ',a[1].nik, '(',a[1].bal,')');
writeln ('2 место: ',a[2].nik, '(',a[2].bal,')');
writeln ('3 место: ',a[3].nik, '(',a[3].bal,')');
end.

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

m:=FindBal(k);
if m>0 then
begin
a[m].bal:= a[m].bal+1;
f:=a[m].nik
end;
и увеличиваем ему результат на 1, чтобы при сортировке он гарантированно встал на лучшее место. После сортировки мы у него эту 1 забираем.
if f<>'' then
begin
m:=FindNik(f);
a[m].bal:=a[m].bal-1;
end;
end;

Что скажете?

 Отправлено: 07.04.15 04:30. Заголовок: и увеличиваем ему ре..

цитата:

и увеличиваем ему результат на 1, чтобы при сортировке он гарантированно встал на лучшее место. После сортировки мы у него эту 1 забираем.

А если первые три участника имели равное количество баллов. 1 добавится только к первому из равных. Прием +1, -1 может привести к ошибке.

 Отправлено: 07.04.15 16:23. Заголовок: Проверил, работает. ..

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

1 место: Jack(69485)
2 место: Nik(69485)
3 место: OK(69485)

Вводил: Jack, Nik, OK, GK, IK

 Отправлено: 07.04.15 20:40. Заголовок: SergJP пишет: Провер..

SergJP пишет:

цитата:

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

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

 Отправлено: 07.04.15 16:50. Заголовок: a : array of tgame..

цитата:

a : array [1..4] of tgamer; function FindNik(nik:string): integer; var i: integer; begin result :=-1; for i:=1 to 4 do if a.nik=nik then begin result :=i; exit end; end;

Ваша версия программы отличается от приведенной здесь. Эта не компилируется.

 Отправлено: 07.04.15 16:55. Заголовок: Прошу прощения, движ..

Прошу прощения, движок форума воспринимает [ i ] как символ форматирования шрифта. Замените a.nik на a [ i ].nik. сам только что заметил.

Вроде все поправил.

 Отправлено: 07.04.15 18:26. Заголовок: Тест: 6 40 a 39 b 39..

Тест:
6
40 a
39 b
39 c
38 e
40 f
41 k
1 место: k(41)
2 место: f(40)
3 место: a(40)

Участник f обошел участника a

 Отправлено: 07.04.15 19:32. Заголовок: 6 40 a 39 b 39 c 38 ..

6
40 a
39 b
39 c
38 e
40 f
41 k
1 место: k(41)
2 место: a(40)
3 место: f(40)

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

Текст программы:

//Вот текст программы.

type
tgamer=record
nik:string;
bal:integer;
cnt : integer;
end;
var b,c:tgamer;
a : array [1..4] of tgamer;
i,n,k,m :integer;
d,f:string;

function FindNik(nik:string): integer;
var i: integer;
begin
result :=-1;
for i:=1 to 4 do
if a [ i ].nik=nik then
begin
result :=i;
exit
end;
end;

function FindBal(bal:integer): integer;
var i: integer;
begin
result:= -1;
for i:=1 to 4 do
if a[ i ].bal=bal then
begin
result:=i;
exit
end;
end;

procedure Sort;
var
i,j,k,m, max :integer;
temp : tgamer;
begin
for i:=1 to 3 do
begin
max:=a [ i ] .bal;
k:=i;
for j:=i to 4 do
if a[j].bal >max then
begin
max:=a[j].bal;
k:=j;
end
else if a[j].bal = max then begin
if a[j].cnt < a[k].cnt then begin
max:=a[j].bal;
k:=j;
end;
end;
temp:=a[ i ];
a[ i ]:=a[k];
a[k]:=temp;
end;
end;


begin
readln (n);
for i:=1 to n do
begin
read (k);
readln(d);
d:=Trim(d);
f:='';

// обработать очередной результат
m:= FindNik(d);
if m>0 then begin
if k>a[m].bal then
a[m].bal:=k;
end
else begin
a[4].bal:=k;
a[4].nik:=d;
a[4].cnt:=i;
end;
m:=FindBal(k);
if m>0 then
begin
a[m].bal:= a[m].bal+1;
f:=a[m].nik
end;
Sort;
if f<>'' then
begin
m:=FindNik(f);
a[m].bal:=a[m].bal-1;
end;
end;
writeln ('1 место: ',a[1].nik, '(',a[1].bal,')');
writeln ('2 место: ',a[2].nik, '(',a[2].bal,')');
writeln ('3 место: ',a[3].nik, '(',a[3].bal,')');
end. //

 Отправлено: 07.04.15 20:26. Заголовок: Но мне кажется, что ..

Но мне кажется, что идея с "+1 " потом "-1" это не лучший вариант. Доверия не вызывает. И полагаю, что надо продолжить анализ и тестирование.

 Отправлено: 18.04.15 08:43. Заголовок: Прошу прокомментировать

Здравствуйте!
Есть задача:
Для заданной последовательности целых чисел необходимо найти
максимальную сумму квадратов двух её элементов, номера которых
различаются не менее чем на 10. Значение каждого элемента
последовательности не превышает 100. Количество элементов
последовательности не превышает 10000.


И есть решение, которое эффективно по времени, но не эффективно по использованию памяти (3 балла):

const d = 10;
var
N: integer;
a: array[1..10000] of integer; {хранение всех
элементов последовательности}
mn:integer; {максимальное введенное число, не считаяd последних}
m:integer; {максимальное значение суммы квадратов}
i: integer;
begin
readln(N);{Ввод всех элементов последовательности}
for i:=1 to N do readln(a);
mn := 0;
m := 0;
for i := d + 1 to N do
begin
if a[i-d] > mn then mn := a[i-d];
if a*a+mn*mn > m then m := a*a+mn*mn
end;
writeln(m)
end.


Вопросы:

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

2) Почему не учитывается, что квадрат отрицательного может быть больше квадрата положительного?

3)Почему переменная m имеет тип integer, а не longint, учитывая резкое увеличение чисел при возведении в степень?

По пунктам 1-2 (для Borland Pascal 7.0).

Предлагаю заменить строку программы:

mn := 0;
на
mn:=-maxint;


ИЛИ, учитывая особенность результата, строку


if a[i-d] > mn then mn := a[i-d];

на

if abs(a[i-d])> mn then mn := a[i-d];

Ваше мнение?

 Отправлено: 18.04.15 08:53. Заголовок: tavabar пишет: если ..

tavabar пишет:

цитата:

если последовательность состоит только из отрицательных целых чисел

Нужно внимательно посмотреть условие оригинала. Наверное, указано, что там положительные числа. Если есть отрицательные, то, конечно, неверно.

цитата:

не учитывается, что квадрат отрицательного может быть больше квадрата положительного?

См. выше.

цитата:

mn:=-maxint;

Это нехорошо. Лучше mn:=a[1];

цитата:

if abs(a[i-d])> mn then mn := a[i-d];

Это вполне разумно.

 Отправлено: 18.04.15 09:17. Заголовок: Поляков пишет: Нужн..

Поляков пишет:

цитата:

Нужно внимательно посмотреть условие оригинала. Наверное, указано, что там положительные числа.

Условие скопировано.

 Отправлено: 08.05.15 22:19. Заголовок: Оцените, пожалуйста, решение задачи №42

42) На ускорителе для большого числа частиц производятся замеры скорости каждой из них. Чтобы в документации качественно отличать одну серию от другой, каждую серию решили характеризовать числом, равным минимальному произведению из всех произведений пар скоростей различных частиц. Вам предлагается написать эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например Borland Pascal 7.0), которая будет обрабатывать результаты эксперимента, находя искомую величину. В нашей модели скорость частицы - это величина, которая может принимать как положительные, так и отрицательные значения. Следует учитывать, что частиц, скорость которых измерена, может быть очень много, но не может быть меньше двух.
Перед текстом задачи кратко опишите используемый вами алгоритм решения задачи.
На вход программе в первой строке подается количество частиц N. В каждой из последующих N строк записано одно целое число со знаком (плюс или минус), по абсолютной величине не превосходящее 10000.
Пример входных данных:
5
+123
+2000
+10
+3716
+10
Программа должна вывести одно число - минимальное произведение из всех произведений пар скоростей различных частиц.
Пример выходных данных для приведенного выше примера входных данных:
100

var 
   n, max, min, pmin1, pmin2, nmax1, nmax2, m, i : integer; 
   f1, f2 : boolean; 
 begin 
   f1 := false; f2 := false;  
   max := -100001; min := 100001; 
   nmax1 := -100001; nmax2 := -100001; 
   pmin1 := 100001; pmin2 := 100001; 
   readln(n); 
   for i := 1 to n do begin 
     readln(m); 
     if (m >= 0) then f1 := true; 
     if (m < 0) then f2 := true; 
     if (m > max) then max := m; 
     if (m < min) then min := m; 
     if (m >= 0) and (m <= pmin1) then begin 
       pmin2 := pmin1; pmin1 := m; 
     end; 
     if (m >= 0) and (m > pmin1) and (m <= pmin2) then pmin2 := m; 
     if (m < 0) and (m >= nmax1) then begin 
       nmax2 := nmax1; nmax1 := m; 
     end; 
     if (m < 0) and (m < nmax1) and (m >= nmax2) then nmax2 := m; 
   end; 
   if (f1 = f2) then writeln(max*min) 
   else if (f1 = true) then writeln(pmin1*pmin2) 
   else if (f2 = true) then writeln(nmax1*nmax2); 
 end. 
 

 Отправлено: 08.05.15 22:49. Заголовок: OlgaChe пишет: Оцени..

OlgaChe пишет:

цитата:

Оцените, пожалуйста, решение задачи №42

В целом решение правильное и эффективное, на полный балл. Только вместо

   if (f1 = true) then ...

лучше писать

   if f1 then ...

А ещё лучше называть флаги как-то более информативно, чем f1 и f2. Хотя это не ошибка, за это баллы на ЕГЭ не снижают.