Команда ФПИ по программированию

В конце учебного года традиционно проводится олимпиада по программированию. Базовый язык программирования Паскаль. В качестве среды программирования используется Turbo Delphi (для тренировок подойдет и Делфи 7 и 2010), но знаний объектно-ориентированного программирования не требуется. Программы создаются в виде консольных приложений, поэтому можно тренироваться в создании кода даже на ABC Pascal. Все программы должны быть организованы так: берут данные из исходного файла input.txt, данные обрабатываются в соответствии с условиями задачи и результат размещается в файл output.txt.
В команде могут участвовать студенты любого курса любой специальности.
_________________________________
В блоге обсуждаются вопросы алгоритмизации «хитрых» задач, поэтому блог, прежде всего, рассчитан на студентов желающих попасть в команду, на студентов 1-х и 2-х курсов, а также будет интересен всем кто интересуется алгоритмизацией. Комментарии опытных старшекурсников приветствуются.
_________________________________
Основные цели блога: подготовка команды, развитие культуры алгоритмизации.
Беляков Андрей Юрьевич, кафедра ИС, ICQ 252614281

Текущий список заданий
(рейтинг сложности задания условный, лежит в диапазоне от 0 до 5, записан в скобках так: CR_4 от — Complexity rating):

Задание №1 (CR_0). Определить оканчивается ли натуральное число на 1.

Задание №2 (CR_1). Переменным (пусть будут целочисленные) А и В присвоены значения (любые, например, А:=3; и В:=5;). Необходимо поменять их местами (то есть в А окажется 5 а в В — 3) не используя других переменных.

Задание №3 (CR_2). Дано целое число (например, 1972). Необходимо его развернуть (то есть из 1972 получится 2791), не используя строковых функций и процедур.

Задание №4 (CR_2). Дано целое число (например, 1972). Необходимо найти сумму кубов нечетных чисел от 0 до заданного числа включительно.
4.1. Выполнить программу обычным перебором.
4.2. Выполнить программу с использованием рекурсии.

Задание №5 (CR_3).
Во входном файле in.txt находится число N.
Заполнить матрицу размерностью NxN последовательными индексами начиная от 1 и заканчивая NxN способом – «по улитке» (по спирали) и вывести её в файл out.txt. Например, для N=5 файл будет таким:
1  2  3  4   5
16 17 18 19  6
15 24 25 20  7
14 23 22 21  8
13 12 11 10  9

Задание №6 (CR_3).
Во входном файле in.txt находится число N. Найти все совершенные числа от 0 до N и вывести их в файл out.txt (в столбик, одно число на каждую строку файла).
P.S. Совершенное число равно сумме своих делителей нацело, например: 28=14+7+4+2+1.

Задание №7 (CR_3).
Разделить N яблок на три кучки так чтобы в каждой было нечётное количество яблок. Посчитать количество неэквивалентных решений. Например: если дано 7 яблок, то всего два решения — (1,3,3) и (1,1,5). Решения (1,3,3), (3,1,3), (3,3,1) — считать эквивалентными, то есть их считать как ОДНО решение.

Задание №8 (CR_2).
В массиве m удалить последнюю группу положительных элементов.
Примечания:
1. Группой называется подряд идущие элементы одного знака, число которых больше или равно 2.
2. Пример: было так [1,3,-4,-5,-6,0,4,-2,-9], а стало так [1,3,-4,-5,-6,-2,-9].
3. Исходный массив можно заполнить псевдослучайными числами.

Задание №9 (CR_2).
Когда-то в давние времена люди одного царства умели писать только нолики и крестики. С помощью длинных слов из крестиков и ноликов они общались между собой. Разгневался их царь и издал приказ — сократить слова по правилам:
1. Пару ХО замени на пару ОХ.
___ Правило 1 примени столько раз, сколько возможно к исходной стоке.
___ К изменившейся строке правило 1 применяй подряд столько раз, сколько возможно.
2. Пару ОО просто удали.
___ Затем правило 2 примени столько раз, сколько возможно к исходной стоке.
3. Пару ХХ просто удали.
___ Затем правило 3 примени столько раз, сколько возможно к исходной стоке.
Например, было так: ОХООХХ, стало так: ОХ; было так: ООХОО, а стало так: Х.
Пусть исходное слово будет во входном файле input.txt:
ХОХОО
Выходной файл output.txt пусть содержит последовательный вывод конечного слова:
ХОХОО
ОХОХО
ООХОХ
ОООХХ
  ОХХ
    О
Дело в том, что если не потребовать последовательный вывод, то решение будет уж совсем тривиальным с рейтингом сложности 1 из 5.

Задание №10 (CR_2).
Идут 12 человек, несут 12 хлебов. Каждый мужчина несёт по 2 хлеба, женщина — по половине хлеба, а ребёнок — по четверти хлеба. Сколько было мужчин, женщин и детей? Вывод решения можно организовать просто на экран.

Похожие записи для топика «Команда ФПИ по программированию»

Комментарии (244) свернуть  |  развернуть

  • avatar
  • belan
  • 15 ноября 2011, 05:21
0
Первые простенькие (рейтинг сложности 1 из 5, такие задачки нужны, чтобы отсеять тех, кто совсем «не в теме») «хитрые» задачки для затравки:
Задание №1. Определить оканчивается ли число на 1.
Задание №2. Переменным (пусть будут целочисленные) А и В присвоены значения (любые, например, А:=3; и В:=5;). Необходимо поменять их местами (то есть в А окажется 5 а в В — 3) не используя других переменных.
0
Ну про первое можно много не говорить: так как не сказано, какое у нас используется число (целое или нет), то использование mod может быть неверным. Для целого — да, но если нужно проверить любое число, в том числе и дробное, то проще перегнать его в строку и проверить последний символ. О_О
Про второе же: A=A+B,B=A-B,A=A-B. Извиняюсь, если не дал кому-то подумать… =D
А вообще, ну хоть что-то же нужно было по первым задачкам написать...))
0
— во второй задачке также есть варианты вичитания и суммирвоания в разные стороны, но смысл один и тот же
— в первой — действительно я некорректно сформулировал, просто писал «на скорую руку», конечно, я предполагал: 1) не используя строковых функций и 2) конечно целые..., эта простая задача нужна для «первого старта»
  • avatar
  • belan
  • 15 ноября 2011, 05:31
0
Задания следующие, чуть посложнее (рейтинг 2 из 5):
Задание №3. Дано целое число (например, 1972). Необходимо его развернуть (то есть из 1972 получится 2791), не используя строковых функций и процедур.
Задание №4. Дано целое число (например, 1972). Необходимо найти сумму кубов нечетных чисел от 0 до заданного числа включительно.
4.1. Выполнить программу обычным перебором.
4.2. Выполнить программу с использованием рекурсии.
0
В задании №4 от 1972 получается 543542396? =)
0
— я и не знаю какой ответ, хотя проверить могу, важно ведь знать не сам ответ, а составить эффективный и красивый алгоритм
— я чуть позже размещу тут свои варианты и анализ, а пока для всех: какой из подходов 4.1 (прямой перебор от 0 до N) или 4.2 (рекурсия) будет эффективнее и почему?
  • avatar
  • Leo
  • 16 ноября 2011, 18:22
+1
Прямой перебор от 0 до N будет эффективнее, т.к. требуется меньше памяти.
Метод с рекурсией ограничивает вводимое число размером стека, который заполняется при каждом вызове функции. При больших вводимых значениях будет ошибка «переполнение стека».
А как лучше оформлять код, прямо здесь вставить, и/или в виде архива?
0
— код лучше прямо тут размещать, чтобы все смогли обсуждать и ваши решения
— и вы сможете смотреть и обсуждать чужие решения
— вместе мы сможем быстрее прогрессировать
_______________________
— я думаю, что можно провести эксперимент и узнать насколько большее N можно посчитать не используя рекурсию
0
Вообще-то 1971 в кубе уже дает 7 657 021 611… Если калькулятор не врет… :)
0
Задание 3:
program P3;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var
  a, b: Integer;
begin
  ReadLn(a);
  b := 0;
  while a <> 0 do
    begin
      b := b * 10 + a mod 10;
      a := a div 10;
    end;
  WriteLn(b);
  ReadLn;
end.


Задание 4:
program P4;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var
  n, s, x, x3: Int64;
begin
  ReadLn(n);
  s := 0;
  x := 1;
  x3 := 1;
  while x <= n do
    begin
      inc(s, x3);
      inc(x3, 6 * x * (x + 2) + 8);
      inc(x, 2);
    end;
  WriteLn(s);
  ReadLn;
end.


С рекурсией попозжа подумаю. О правильности вообще не думал… О.о
-1
— тут уже очередность мессаджей не проследить, но я уже отметил, что задача ставится самостоятельно и без помощи сети разработать алгоритм, например, такой:

 sum:=0;
 i:=1;
 while i<=k do
 begin
   sum:=sum+power(i,3);
   inc(i,2);
 end;

— очевидно, что, тут всё очевидно :)
и чтобы его написать не нужно лезть в сеть и искать хитрые преобразования 6*x*(x+2)+8
0
Ну для начала скажем, что в сеть я не лазил и это «хитрое» преобразование выводиться в 2 секунды. Просто мне нравятся последовательности… :)
0
— у меня просьба — давайте работать без эмоций
— я прочитал от вас «Говорим спасибо Википедии и запоминаем для общего развития» — в ответ на это сообщил вам то о чем, возможно, вы не знали — что других участников просил не использовать наработки из сети только при первичном написании кода
— у меня нет цели уличить кого-то — у меня цель самому развиться и другим дать возможность совершенствоваться
— оставьте ваше мнение по вопросам:
1) какой из обсуждаемых вариантов быстрее напишется (что важно во время соревнований)?
2) какой из вариантов эффективнее работает (что тоже очень важно)?
3) поделитесь скоростным выводом «хитрого» преобразования — может его можно распространить на аналогичные случаи: x^4, x^5 и т.п. — мало ли какие задачи предстоит решать…
0
1. Сложный вопрос, какой именно вариант напишется быстрее. Большинство людей действительно первым делом выведет «стандартный» вариант с использованием функции power(). У меня принцип мышления несколько другой (некоторые, возможно, знают), поэтому можно спокойно абстрагироваться от того, что дано в задаче и представить последовательность чисел как просто-напросто последовательность, в которой каждое последующее число зависит только от предыдущего и ничего больше. Когда я написал последовательность на листе бумаги мне в голову пришел мой вариант, именно его я и написал. Всегда нужно писать первое, что приходит в голову. Да, возможно, в процессе все полностью поменяется, но по крайней мере будет с чего начинать.

2. Путем сравнения выяснилось, что (для N = 3 000 000):
— особой разницы в использовании памяти нет никакой;
— самым быстрым решением является решение «в лоб» с использованием x*x*x ~ 22 мс;
— чуть медленней работает мое решение ~ 25 мс;
— самое медленное решение с использованием функции power() ~ 42 мс.

3. Для любой монотонной последовательности достаточно вычислить f(x) и f(x+dx), чтобы потом не вычислять каждый раз функцию, а просто продолжить последовательность. В данном случае мы имеем x^3 и (x+2)^3 = (x+2)(x^2+4x+4) = x^3 + 2x^2 + 4x^2 + 8x + 4x + 8 = x^3 + 6x^2 + 12x + 8 = x^3 + [ 6x(x+2)+8 ], т.е. сумму предыдущего значения (x^3) и разности (6x(x+2)+8), которую можно использовать для вычисления последующих значений последовательности. Точно так же для любой степени:
— x^4 и (x+n)^4 = (x^2 + 2xn + n^2)(x^2 + 2xn + n^2) = <… простой вывод на страничку ...> = x^4 + 2xn(2x(x+n)+n^2)+n^4 — таким образом получаем разность (2xn(2x(x+n)+n^2)+n^4), в которой используется только умножение и сложение и не нужно использовать функцию power() (n — это число и его степень будет известна).
А вообще, не в выводе дело, а в способе мысли. Не нужно зацикливаться на задаче и решение придет само. Абстракция — это лучшее, что существует в мире… :)
0
— спасибо, познавательно про последовательности
— по поводу power ожидал подобного результата, несмотря на внешне более компактный код, так как сама степень вычисляется через вызов других функций Exp и Ln и ещё кучи условных операторов, смотрим код в модуле Math
function Power(const Base, Exponent: Extended): Extended;
begin
  if Exponent = 0.0 then
    Result := 1.0               { n**0 = 1 }
  else if (Base = 0.0) and (Exponent > 0.0) then
    Result := 0.0               { 0**n = 0, n > 0 }
  else if (Frac(Exponent) = 0.0) and (Abs(Exponent) <= MaxInt) then
    Result := IntPower(Base, Integer(Trunc(Exponent)))
  else
    Result := Exp(Exponent * Ln(Base))
end;
0
Код в Math (Delphi XE):
(* ***** BEGIN LICENSE BLOCK *****
 *
 * The function Power is licensed under the CodeGear license terms.
 *
 * The initial developer of the original code is Fastcode
 *
 * Portions created by the initial developer are Copyright © 2002-2004
 * the initial developer. All Rights Reserved.
 *
 * Contributor(s): John O'Harrow
 *
 * ***** END LICENSE BLOCK ***** *)
function Power(const Base, Exponent: Extended): Extended;
const
  Max  : Double = MaxInt;
var
  IntExp : Integer;
asm // StackAlignSafe
  fld     Exponent
  fld     st             {copy to st(1)}
  fabs                   {abs(exp)}
  fld     Max
  fcompp                 {leave exp in st(0)}
  fstsw   ax
  sahf
  jb      @@RealPower    {exp > MaxInt}
  fld     st             {exp in st(0) and st(1)}
  frndint                {round(exp)}
  fcomp                  {compare exp and round(exp)}
  fstsw   ax
  sahf
  jne     @@RealPower
  fistp   IntExp
  mov     eax, IntExp    {eax=Trunc(Exponent)}
  mov     ecx, eax
  cdq
  fld1                   {Result=1}
  xor     eax, edx
  sub     eax, edx       {abs(exp)}
  jz      @@Exit
  fld     Base
  jmp     @@Entry
@@Loop:
  fmul    st, st         {Base * Base}
@@Entry:
  shr     eax, 1
  jnc     @@Loop
  fmul    st(1), st      {Result * X}
  jnz     @@Loop
  fstp    st
  cmp     ecx, 0
  jge     @@Exit
  fld1
  fdivrp                 {1/Result}
  jmp     @@Exit
@@RealPower:
  fld     Base
  ftst
  fstsw   ax
  sahf
  jz      @@Done
  fldln2
  fxch
  fyl2x
  fxch
  fmulp   st(1), st
  fldl2e
  fmulp   st(1), st
  fld     st(0)
  frndint
  fsub    st(1), st
  fxch    st(1)
  f2xm1
  fld1
  faddp   st(1), st
  fscale
@@Done:
  fstp    st(1)
@@Exit:
end;

                                                                                                                                                       
                                                                                                   
function Power(const Base, Exponent: Double): Double; overload;
const
  Max  : Double = MaxInt;
var
  IntExp : Integer;
asm // StackAlignSafe
  fld     Exponent
  fld     st             {copy to st(1)}
  fabs                   {abs(exp)}
  fld     Max
  fcompp                 {leave exp in st(0)}
  fstsw   ax
  sahf
  jb      @@RealPower    {exp > MaxInt}
  fld     st             {exp in st(0) and st(1)}
  frndint                {round(exp)}
  fcomp                  {compare exp and round(exp)}
  fstsw   ax
  sahf
  jne     @@RealPower
  fistp   IntExp
  mov     eax, IntExp    {eax=Trunc(Exponent)}
  mov     ecx, eax
  cdq
  fld1                   {Result=1}
  xor     eax, edx
  sub     eax, edx       {abs(exp)}
  jz      @@Exit
  fld     Base
  jmp     @@Entry
@@Loop:
  fmul    st, st         {Base * Base}
@@Entry:
  shr     eax, 1
  jnc     @@Loop
  fmul    st(1), st      {Result * X}
  jnz     @@Loop
  fstp    st
  cmp     ecx, 0
  jge     @@Exit
  fld1
  fdivrp                 {1/Result}
  jmp     @@Exit
@@RealPower:
  fld     Base
  ftst
  fstsw   ax
  sahf
  jz      @@Done
  fldln2
  fxch
  fyl2x
  fxch
  fmulp   st(1), st
  fldl2e
  fmulp   st(1), st
  fld     st(0)
  frndint
  fsub    st(1), st
  fxch    st(1)
  f2xm1
  fld1
  faddp   st(1), st
  fscale
@@Done:
  fstp    st(1)
@@Exit:
end;

                                                                                                                                                       
                                                                                                   
function Power(const Base, Exponent: Single): Single; overload;
const
  Max : Double = MaxInt;
var
  IntExp : Integer;
asm // StackAlignSafe
  fld     Exponent
  fld     st             {copy to st(1)}
  fabs                   {abs(exp)}
  fld     Max
  fcompp                 {leave exp in st(0)}
  fstsw   ax
  sahf
  jb      @@RealPower    {exp > MaxInt}
  fld     st             {exp in st(0) and st(1)}
  frndint                {round(exp)}
  fcomp                  {compare exp and round(exp)}
  fstsw   ax
  sahf
  jne     @@RealPower
  fistp   IntExp
  mov     eax, IntExp    {eax=Integer(Exponent)}
  mov     ecx, eax
  cdq
  fld1                   {Result=1}
  xor     eax, edx
  sub     eax, edx       {abs(exp)}
  jz      @@Exit
  fld     Base
  jmp     @@Entry
@@Loop:
  fmul    st, st         {Base * Base}
@@Entry:
  shr     eax, 1
  jnc     @@Loop
  fmul    st(1), st      {Result * X}
  jnz     @@Loop
  fstp    st
  cmp     ecx, 0
  jge     @@Exit
  fld1
  fdivrp                 {1/Result}
  jmp     @@Exit
@@RealPower:
  fld     Base
  ftst
  fstsw   ax
  sahf
  jz      @@Done
  fldln2
  fxch
  fyl2x
  fxch
  fmulp   st(1), st
  fldl2e
  fmulp   st(1), st
  fld     st(0)
  frndint
  fsub    st(1), st
  fxch    st(1)
  f2xm1
  fld1
  faddp   st(1), st
  fscale
@@Done:
  fstp    st(1)
@@Exit:
end;
0
— кстати, провел своё исследование по п.2 по трем вариантам и натолкнулся на:
1) функция power ведь к тому же работает с более трудоемким типом данных Extended, что так же замедляет её работу
2) если всё оставить как есть, то есть " n, s, x, x3: Int64;", то результаты ведь получаются неправильные для N=3 000 000, так как не хватает количества разрядов, начиная уже с N=93 000 и даже немного ранее (я не проверял со скольки)
0
Ну я не смотрел на результаты. Смотрел только на производительность. Насчет Extended — согласен.
0
Еще более «веселое» решение… :)

{$APPTYPE CONSOLE}

var
  n,s,x3,dx,ddx: Extended;
begin
  ReadLn(n);
  s:=0;
  x3:=1;
  dx:=1;
  ddx:=0;
  while n>0 do
    begin
      s:=s+x3;
      ddx:=ddx+12;
      x3:=x3+dx+dx+ddx+ddx;
      dx:=dx+ddx+ddx;
      n:=n-2;
    end;
  WriteLn(s:0:0);
end.
  • avatar
  • belan
  • 16 ноября 2011, 18:42
0
Неслучайный диалог (все имена вымышлены, все совпадения случайны, публикуется для общей пользы, чтобы мне каждому не комментировать одни и те же «грабли»):

— я:
давайте код

— он:
Задание №1
procedure TForm1.Button1Click(Sender: TObject);
var a:integer;
begin
a:=StrToInt(Edit1.Text);
if a mod 10 = 1 then
Label1.Caption:='Оканчивается' else Label1.Caption:='Не оканчивается';
end;

— я:
про mod это верно
но лучше делать в Паскале
я имею ввиду, что в консольном приложении Делфи не будет кнопочных форм

— он:
ну главное пока ведь логика=)

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

— он:
хорошо, в следующий раз буду делать на паскале
пока покажу на дельфи?

Задание №2
procedure TForm1.Edit1Change(Sender: TObject);
var a,b: integer;
begin
a:=StrToInt(Edit1.Text);
b:=StrToInt(Edit2.Text);
a:=a+b;
b:=a-b;
a:=a-b;
label1.Caption:='a='+IntToStr(a)+' b='+IntToStr(b);
end;

— я:
можно прямо сейчас эту прогу попробовать как консольное приложение
в Делфи меню Файл \ Новый \ Другое \ Консольное
и там написать вашу прогу так:

program Project1;

{$APPTYPE CONSOLE}

uses
SysUtils;

var a,b: integer;
begin
a:=4;
b:=7;
writeln('a=',a,' b=',b);
a:=a+b;
b:=a-b;
a:=a-b;
writeln('a=',a,' b=',b);

readln;
end.

попробуйте

— он:
аа, теперь понятно)) работает)

— я: ок
только пока пишите строки англ. буквами
он с русским плохо дружит
или в сети посмотрите

— он:
Задание №3

program Project1;

{$APPTYPE CONSOLE}

uses
SysUtils;
var a,b: integer;

begin
readln(a);
b:=0;
while a<>0 do
begin
b:=b*10+a mod 10;
a:=a div 10;
end;
writeln(IntToStr(b));
readln;
end.

— я:
отлично
можно писать просто writeln(b);

— он:
Задание №4.1

program Project1;

{$APPTYPE CONSOLE}

uses
SysUtils;
var a,i:integer;

begin
a:=0;
readln(i);
for i:=0 to i do
if i mod 2<>0 then a:=a+i*i*i;
writeln(a);
readln;
end.

— я:
тут есть недостатки, три
1) integer только до 32767
2) i*i*i
3) и самый важный с точки зрения эффективности алгоритма — третий недостаток:
цикл идет по всем значениям, даже по четным
а они не нужны
скорость можно повысить в два раза
на олимпиаде даются также тестовые исходные данные на которых проверяют прогу
и если не укладывается во время (1 сек или типа того) то задача не решена или просто снижается балл

— он:
жестко:)

— он:
а вместо integer что лучше использовать? Longint?
возведение в степень возвращает не целочисленный результат

— он:
а второй недостаток… теперь ведь нет специальной функции возведения в степень?
или Power доступен всегда?:)

— я:
надо модуль подключить
Math
как в Паскале было
и выводить форматированным выводом как в Паскале

— он:
недостатки 1 и 2 вроде исправил

program Project1;

{$APPTYPE CONSOLE}

uses
SysUtils,Math;
var i:integer;
a:real;

begin
a:=0;
readln(i);
for i:=0 to i do
if i mod 2<>0 then a:=a+Power(i,3);
writeln(a:2:0);
readln;
end.
а как с третьим?

— я:
тут всё — да
а с третьим подумайте…
я написал наводку

— он:
Я вот так только придумал:

program Project1;

{$APPTYPE CONSOLE}

uses
SysUtils, Math;

var i:integer;
a:real;

begin
a:=0;
readln(i);
if i mod 2 = 0 then dec(i);
while i>0 do
begin
a:=a+Power(i,3);
i:=i-2;
end;
writeln(a:2:0);
readln;
end.

— я:
i:=i-2; лучше писать так dec(i,2);
а так мысль правильная
а можно и в другую сторону перебор организовать снизу вверх
не проверяя if i mod 2 = 0 then dec(i);

sum:=0;
i:=1;
while i<=k do
begin
sum:=sum+power(i,3);
inc(i,2);
end;
writeln('sum3=',sum:4:0);

первое нечетное число ведь известно = 1
  • avatar
  • belan
  • 16 ноября 2011, 19:12
0
Задание №5. (рейтинг сложности 3 из 5)
Во входном файле in.txt находится число N.
Заполнить матрицу размерностью NxN последовательными индексами начиная от 1 и заканчивая NxN способом – «по улитке» (по спирали) и вывести её в файл out.txt. Например, для N=5 файл будет таким:
_1__2__3__4__5
16_17_18_19__6
15_24_25_20__7
14_23_22_21__8
13_12_11_10__9
P.S. Символы подчеркивания в файл выводить не нужно, это я их тут поставил вместо табулятора…

Задание №6. (рейтинг сложности 3 из 5)
Во входном файле in.txt находится число N. Найти все совершенные числа от 0 до N и вывести их в файл out.txt (в столбик, одно число на каждую строку файла).
P.S. Совершенное число равно сумме своих делителей нацело, например: 28=14+7+4+2+1.

Задание №7. (рейтинг сложности 3 из 5)
Разделить N яблок на три кучки так чтобы в каждой было нечётное количество яблок. Посчитать количество неэквивалентных решений. Например: если дано 7 яблок, то всего два решения — (1,3,3) и (1,1,5). Решения (1,3,3), (3,1,3), (3,3,1) — считать эквивалентными, то есть их считать как ОДНО решение.
0
Задание №6.
program z6;
{$APPTYPE CONSOLE}
uses
    SysUtils,Math;
var f,o: textfile;
    n,a,j: integer;
    i: longint;
begin
  assign(f,'D:\in.txt');
  reset(f);
  read(f,n);
  close(f);
  assign(o,'D:\out.txt');
  rewrite(o);
  for i:=0 to n do
  begin
    a:=0;
    for j:=1 to trunc(i/2+1) do
      if i mod j = 0 then a:=a+j;
    if a=i then writeln(o,i);
  end;
  close(o);
end.
0
— всё верно, но…
1) так писать не надо:

  assign(f,'D:\in.txt');
  assign(o,'D:\out.txt');
иначе exe-шник не сработает на другом компе
чтобы файлы брались из текущей папки достаточно так:

  assign(f,'in.txt');
  assign(o,'out.txt');
2) тут не имеет смысла с 0 начинать, лучше с 1:
for i:=0 to n do
а этот код:

    for j:=1 to trunc(i/2+1) do
      if i mod j = 0 then a:=a+j;
точь в точь как везде в сети
— я могу что-то подумать случайно нехорошее…
— кто хочет прокомментируйте почему в этом месте
trunc(i/2+1)
стоит
+1
— зачем там плюс один
_________________
— дополнительное Задание 6.1.: переделать прогу так чтобы она искала первые пять совершенных чисел.
0
— оптимальнее также и внутренний цикл не от 1 начинать, а от 2:
for i:=1 to n do
  begin
    a:=1;
    for j:=2 to trunc(i/2+1) do
      if i mod j = 0 then inc(a,j);
    if a=i then writeln(o,i);
  end;
— кто хочет — прокомментируйте почему…
0
— кстати, заметили, что я использовал inc(a,j) — это может быть спорным решением — можно провести эксперимент на больших числах и сравнить, что выполняется быстрее a:=a+j; или inc(a,j);
— и ещё, кто хочет почему нужно использовать trunc и как написать код без использования trunc?:
for i:=1 to n do
  begin
    a:=1;
    for j:=2 to ******* do
      if i mod j = 0 then inc(a,j);
    if a=i then writeln(o,i);
  end;
0
Провел 5 поочередных испытаний при входном значении 100.000:

Время выполнения inc(a,j)= 57532 мс √
Время выполнения (a:=a+j) = 57922 мс

Время выполнения inc(a,j)= 57546 мс √
Время выполнения (a:=a+j) = 58297 мс

Время выполнения inc(a,j) = 57515 мс
Время выполнения (a:=a+j) = 57187 мс √

Время выполнения inc(a,j) = 57562 мс √
Время выполнения (a:=a+j) = 57672 мс

Время выполнения inc(a,j) = 57531 мс √
Время выполнения (a:=a+j) = 57640 мс

Вывод: только в одном случае из пяти a:=a+j показывает время меньшее, чем inc(a,j).
Но это может быть случайностью: надо выборку или входное значение увеличивать для получения более точных данных.
0
тут не имеет смысла с 0 начинать, лучше с 1
Просто в задании написано начинать с нуля.

+1
потому-что при округлении (1/2) получается ноль, а нужна единица. Если использовать округление в большую сторону, то можно обойтись без неё:
Ceil(i/2)


Задание 6.1

{$APPTYPE CONSOLE}
uses
  SysUtils,Math;
var f,o: textfile;
    n,a,j,z: integer;
    i: longint;
begin
  assign(f,'in.txt');
  reset(f);
  read(f,n);
  close(f);
  assign(o,'out.txt');
  rewrite(o);
  while z < 5 do
  for i:=1 to n do
  begin
    a:=0;
    for j:=1 to Ceil(i/2) do
      if i mod j = 0 then a:=a+j;
    if a=i then
    begin
      writeln(o,i);
      inc(z);
    end;
  end;
  close(o);
end.
0
1) в задании не написано, что цикл for должен начинаться с нуля — программист сам принимает решение откуда ему начать цикл, если заранее понятно, что ноль не входит в список решений, то его и не включаем…
2) вот с этим я не согласен: «потому-что при округлении (1/2) получается ноль, а нужна единица. Если использовать округление в большую сторону, то можно обойтись без неё:» — я предлагаю ещё раз об этом подумать, для какой такой цели нужна единица или округление в большую сторону?
— а что остальные стесняются вступить в диалог? тут все решают одну задачу: совершенствование своей способности к алгоритмизации, приветсвуются любые идеи, даже самые неправильные — на них тоже можно совершенстоваться
кстати:
3) этот код вообще мне не понравился:
while z < 5 do
  for i:=1 to n do
  begin
    a:=0;
    for j:=1 to Ceil(i/2) do
      if i mod j = 0 then a:=a+j;
    if a=i then
    begin
      writeln(o,i);
      inc(z);
    end;
  end;
— тут зачем нужен цикл for i:=1 to n do? если мы ищем первые пять совершенных чисел
0
3) сначала не понял задание.
{$APPTYPE CONSOLE}
uses
    SysUtils,Math;
var f:textfile;
    n,a,j: integer;
    i: longint;
begin
  assign(f,'out.txt');
  rewrite(f);
  n:=0; i:=0;
  while n<5 do
  begin
    inc(i);
    a:=1;
    for j:=2 to trunc(i/2+1) do
      if i mod j = 0 then inc(a,j);
    if a=i then
    begin
      writeln(f,i);
      inc(n);
    end;
  end;
  close(f);
end.
0
— что же будем делать с плюсодином и трунком???
0
ждать… может кто-нибудь подскажет =)
0
— вот тут очень даже согласен — дадим возможность остальным себя проявить…
— или в команде ФПИ будет один только боец?
0
Как ни странно, в программировании и один в поле воин… Причем такой, что может положить всех остальных… :)
0
— ладно отвечу сам, может кто ещё меня поправит
— сходу вижу ситуацию примерно так:
1) нам "+1" не нужен потому как и не нужно переходить половину от числа N, например, если число N=10, то половина = 5, тут пока всё очевидно 6 и не нужно, так как мы ищем делители нацело и в данном случае минимальный делитель нацело это 2; а когда N нечетное, например, N=11, то и тут хватит 5 и по той же причине
2) trunc нужен чтобы в операторе цикла использовалось целочисленное значение верхней границы, но можно и не используя его получить целочисленное значение в один оператор: i div 2 вместо двух: trunc(i/2)
— если я что-то недопонял — подскажите…
0
Для решения задания 6.1 лучше не переделывать программу, а написать новую, воспользовавшись двумя посылками:
1. До сих пор не обнаружено ни одного нечетного совершенного числа, поэтому нет никакого смысла проверять нечетные числа. Даже если такое число существует, то оно явно превосходит пределы всех стандартных числовых типов.
2. Как доказал Эйлер, все четные совершенные числа имеют вид, который до этого предложил Евклид: 2^(p-1)*(2^p-1), при условии, что число 2^p-1 является простым. (Говорим спасибо Википедии и запоминаем для общего развития).

На основании этого пишем гораздо более быстрый алгоритм:
program P61;

{$APPTYPE CONSOLE}

uses
  SysUtils, Math;

var
  i, p, n, t: Cardinal;
  prime: Boolean;
begin
  n := 0;
  p := 2;
  while n < 5 do
    begin
      t := round(power(2, p) - 1);
      prime := true;
      for i := 2 to t div 2 do
        if t mod i = 0 then
          prime := false;
      if prime then
        begin
          WriteLn(round(power(2, p - 1) * (power(2, p) - 1)));
          inc(n);
        end;
      inc(p);
    end;
  ReadLn;
end.
0
— очевидно, что размышления Эйлера полезны для оптимизации решения, но:
1) можно ли во время олимпиады пользоваться Интернетом?
2) я сам прошу не пользоваться интернетом при решении задач, по крайней мере при первичной резработке алгоритма, а после написания работоспособного кода уже можно посмотреть и перенять опыт в сети
0
Насчет Интернета точно сказать не могу, но блокнотиком с записями никто пользоваться не запрещает. Поэтому можно выписать некоторые интересные закономерности, особенно по последовательностям.
0
Оптимальней писать даже не так:
assign(f,'in.txt');
  assign(o,'out.txt');

а так:
assign(input,'in.txt');
  assign(output,'out.txt');


Input и Output — это стандартные идентификаторы для ввода и вывода, имеют тип Text и не нуждаются в предварительном объявлении. Кроме того при их использовании не нужно указывать файл для каждой операции чтения или вывода, а можно просто писать ReadLn(n) или WriteLn('бла-бла'), так, будто происходит чтение с консоли. Кроме того, это очень удобно при отладке: нужно лишь закомментировать строчки с Assign и будет производиться чтение с консоли и больше ничего не нужно будет специально править в программе.
0
— спасибо, удобно
0
Задание 5:
program P5;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var
  n, l, k, i, x, y, dx, dy: Integer;
  m: array of array of Longint;
begin
  assign(input, 'in.txt');
  reset(input);
  assign(output, 'out.txt');
  rewrite(output);

  ReadLn(n);
  SetLength(m, n, n);
  i := 1;
  dx := -1;
  dy := 1;
  y := 0;
  for x := 0 to n - 1 do
    begin
      m[x,y] := i;
      inc(i);
    end;
  x := n - 1;
  while i < n * n do
    begin
      for l := n - 1 downto 1 do
        begin
          for k := 0 to l - 1 do
            begin
              inc(y,dy);
              m[x,y] := i;
              inc(i);
            end;
          for k := 0 to l - 1 do
            begin
              inc(x,dx);
              m[x,y] := i;
              inc(i);
            end;
          dx := dx * -1;
          dy := dy * -1;
        end;
    end;

  for y := 0 to n - 1 do
    begin
      for x := 0 to n - 1 do
        Write(Format('%5d ',[m[x,y]]));
      WriteLn;
    end;

  ReadLn;
end.

Насчет правильности — аналогично предыдущим (т.е. особо не задумывался...).
0
— я позволю себе несколько комментов:
1) эта задача может кому-то покажется скучной (просто она уже избитая, решение её рутинное), но считаю, что она нужна для тех кто ещё только развивается и раньше не сталкивался с ней
— и ещё пару, не претендующих на лучше или хуже, а просто как вариант:
2) вместо:

          dx := dx * -1;
          dy := dy * -1;
можно

          dx := -dx;
          dy := -dy;
3) вместо:
Write(Format('%5d ',[m[x,y]]));
можно
Write(#9,m[x,y]);
0
Задание 6 (и все такая же правильность :) ):
program P6;

{$APPTYPE CONSOLE}

uses
  SysUtils;

var
  i, j, n, s, c: Longint;
begin
  Assign(input, 'in.txt');
  reset(input);
  Assign(output, 'out.txt');
  rewrite(output);

  ReadLn(n);
  for i := 1 to n do
    begin
      s := 1;
      j := 2;
      c := i;
      while j <= c do
        begin
          if i mod j = 0 then
            begin
              if (i div j <> j) then
                begin
                  inc(s, j + (i div j));
                  c := i div j - 1;
                end
              else
                inc(s, j);
            end;
          inc(j);
        end;
      if s = i then
        WriteLn(i);
    end;
  close(input);
  close(output);
end.
0
Задание 7.
Примечание: Сделал вывод вместо простого пересчета. Как сделать пересчет, думаю, всем будет понятно. Алгоритм несложен, причем не нуждается в проверке эквивалентных решений, потому как ищет только неэквиваленты.
Собственно код:
program P7;

{$APPTYPE CONSOLE}

uses
  SysUtils, Math;

var
  a, b, c, n: Longint;
begin
  ReadLn(n);

  a := 1;
  b := 1;
  c := n - 2;

  while c >= a do
    begin
      while c >= b do
        begin
          WriteLn(format('%d %d %d', [a, b, c]));
          inc(b, 2);
          dec(c, 2);
        end;
      inc(a, 2);
      b := a;
      c := n - a - b;
    end;

  ReadLn;
end.

Правильность остается все той же. Мне просто лень дебажить.
0
Ой… Чего-то там Math затесался. Видимо от предыдущих прог. :)
  • avatar
  • Chiliec
  • 19 ноября 2011, 11:04
0
Задание №7.
{$APPTYPE CONSOLE}
uses
  SysUtils;
var
  n,a,b,c:integer;
  q: set of byte;
begin
  readln(n);
  a:=1; b:=1; c:=n-2;
  if (n>=3) and (n mod 2<>0) then //проверка условий выполнимости программы
  begin
    if n=3 then writeln('1 1 1'); //пришлось отдельно рассмотреть этот случай
    while c>1 do
    begin
      inc(b,2);
      dec(c,2);
      q:=q+[c];
      if not(b in q) then writeln(a,' ',b,' ',c,' '); //убираем эквивалентные
    end;
    while b>4 do
    begin
      inc(a,2);
      inc(c,2);
      dec(b,4);
      writeln(a,' ',b,' ',c,' ');
    end;
  end
  else writeln('Incorrect input variable');
  readln;
end.
0
— мне понравился этот оригинальный алгоритм с разнонаправленными шагами, но он не выдает всех решений
— например, для 15 — нет решения 3 5 7; для 21 — нет решения 3 5 13 и т.д.
— я посмотрю этот алгоритм чуть позже, может и этот подход можно довести до ума
  • avatar
  • belan
  • 20 ноября 2011, 15:13
0
— спасибо старшекурсникам за участие в команде и за полезные советы
— я надеюсь, что вы передадите мне и студентам младших курсов накопленный вами опыт
— вы скоро станете уже выпускниками, хотелось бы чтобы была преемственность поколений
— просьба: опубликуйте задачи прошлых олимпиад, чтобы все могли ориентироваться в сложности заданий, осознавать необходимые для их решения навыки и понимать свой уровень
— я не в состоянии охватить всех тем (у меня у самого очень много хобби + работа) — предлагаю всем сюда выкладывать интересные задачи и предлагать свой собственный анализ вариантов их решений — будем обучать друг друга
  • avatar
  • belan
  • 20 ноября 2011, 20:26
0
Сейчас в младших классах школы уже есть информатика. У моей дочки во втором классе уже задачки такие сложные, что их можно брать нам для подготовки. Может и вам покажется это интересным, попробую их сформулировать для нас:

Задание №8. (рейтинг сложности 2 из 5)
В массиве m удалить последнюю группу положительных элементов.
Примечания:
1. Группой называется подряд идущие элементы одного знака, число которых больше или равно 2.
2. Пример: было так [1,3,-4,-5,-6,0,4,-2,-9], а стало так [1,3,-4,-5,-6,-2,-9].
3. Исходный массив можно заполнить псевдослучайными числами.

Задание №9. (рейтинг сложности 2 из 5)
Когда-то в давние времена люди одного царства умели писать только нолики и крестики. С помощью длинных слов из крестиков и ноликов они общались между собой. Разгневался их царь и издал приказ — сократить слова по правилам:
1. Пару ХО замени на пару ОХ.
___ Правило 1 примени столько раз, сколько возможно к исходной стоке.
___ К изменившейся строке правило 1 применяй подряд столько раз, сколько возможно.
2. Пару ОО просто удали.
___ Затем правило 2 примени столько раз, сколько возможно к исходной стоке.
3. Пару ХХ просто удали.
___ Затем правило 3 примени столько раз, сколько возможно к исходной стоке.
Например, было так: ОХООХХ, стало так: ОХ; было так: ООХОО, а стало так: Х.
Пусть исходное слово будет во входном файле in.txt:
ХОХОО
Выходной файл out.txt пусть содержит последовательный вывод конечного слова:

ХОХОО
ОХОХО
ООХОХ
ОООХХ
  ОХХ
    О
Дело в том, что если не потребовать последовательный вывод, то решение будет уж совсем тривиальным с рейтингом сложности 1 из 5.

Задание №10. (рейтинг сложности 2 из 5)
Идут 12 человек, несут 12 хлебов. Каждый мужчина несёт по 2 хлеба, женщина — по половине хлеба, а ребёнок — по четверти хлеба. Сколько было мужчин, женщин и детей? Вывод решения можно организовать просто на экран.

Ну как вам такие задачки?
0
Поднял сервер с автоматической проверкой решений задач Contester 2.4, аналогичный тому, который использовался в прошлом году на олимпиаде. В комплекте идет где-то около сотни задач, так что можно регистрироваться и решать. Заодно можно ознакомиться с системой, чтоб это не было неожиданностью.

Расположено здесь:http://contester.dyndns.org/ru/.
Если вдруг что-то упадет — пишет в аську 420-829-388. Постараюсь поднять. :)
0
— спасибо
— добавлю парочку ресурсов с задачами
acmp.ru/article.asp?id_text=195
algolist.manual.ru/
0
— апробировал систему
— решил одну простеньку арифметическую задачку: «В первой строке записано арифметическое выражение в виде: ЧислоОперацияЧисло. Число это натуральное число, не превышающее 10000. Операция — один из знаков +, -, *. В начале строки, в конце строки, а также между числами и знаком операции пробелов нет. Гарантируется, что длина строки не превышает 200 символов. Необходимо вывести результат вычисления выражения.»

Ввод	Вывод 
154+3	157

— но первая же проверка системой показала мне, что нужно быть внимательнее к оформлению вывода результата — вывод делать только в том формате как указано в задании и внимательнее читать задание — я сначала не обратил внимание, что нет операции деления и делал обработку деления на ноль
— забыл засечь время, но менее 10 мин., при этом затрачено лишнее время по невнимательности
— а как узнать в этой системе во сколько она оценила время выполнения моей программы и объём занимаемой памяти?
0
Конкретных данных по времени выполнения и использовании памяти при верном решении, видимо, не сохраняется. При проверке решения происходит учет этих значений, что может вызывать ошибки Time Limit или Memory Limit. Но скорее всего даже при показе этих ошибок не будет показано конкретных значений времени и используемого объема памяти. По крайней мере в логах ничего такого нет, да и в справке тоже.
+1
Contester работает круглосуточно. Не давайте простаивать машине — решайте. Чем больше решим сейчас, тем проще будет потом. К тому же к системе нужно привыкать.
  • avatar
  • belan
  • 21 ноября 2011, 17:07
0
— я перечитал разные сайты про олимпиады по программированию прошлых лет для школьников, студентов, они все повторяют друг друга с небольшими отклонениями
— например по этой ссылке можно ознакомиться с подробными правилами, я думаю, что полезно будет тем, кто собирается выступать за ФПИ изучить детали: neerc.ifmo.ru/school/russia-team/rules.html
— видимо в команде обычно по три человека
— если наберутся игроки, то можно будет две команды от нас организовать, пока, конечно, рано говорить, просто мне примерный план действий нужно держать в голове
— например, хоты бы пару раз провести очную встречу в рамках спортивного программирования на время для повышения сыгранности игроков
— я фамилии не называю, но текущий список состоит из 6-7 человек, причем пятеро могут решать задачи олимпиадного уровня, а 3-4 могут и меня поучить :)
0
В командах бывает и больше 3-х человек, но лично для меня 3 человека кажется наиболее оптимальным количеством.
Предварительные встречи для совместного решения задач — обязательно. И лучше не пару раз, а чем больше, тем лучше. И главное еще до самой олимпиады четко распределить не только людей по командам (если будет больше одной), но и роли людей в команде, чтобы не начиналось дележка места за компьютером, а то всякое бывает.

— Самое главное правило: не спешить. Внимательно читать задание. Задачи в основном не такие сложные и если не получается решить «с лёту», то можно отложить одну задачу и перейти к другой. И перед тем, как отправить вариант решения на проверку, обязательно проверить, что именно отправляете (и не забывать сохранять изменения).
комментарий был удален
  • avatar
  • Olga
  • 21 ноября 2011, 18:22
0
Задание 5
var A: array [,] of integer;
Motion, Value_Elem_Mas, i, j, n:integer;

begin
  Assign(input,'in.txt');
  Assign(output,'out.txt');
  Readln(n);
  SetLength(A,n,n);
  i:=0; j:=0;

  for Value_Elem_Mas:=1 to n*n do
    begin
      A[i,j]:=Value_Elem_Mas;
      case motion of
{Right}   0: begin
              j:=j+1;
              If j=n-i-1 then motion:=1;
             end;
{Bottom}  1:  begin
                i:=i+1;
                If j=i then motion:=2;
              end;
{Left}    2:  begin
                j:=j-1;
                If i=n-j-1 then motion:=3;
              end;
{top}     3:  begin
                i:=i-1;
                If i=j+1 then motion:=0;
              end;
       end;
    end;

  for i:=0 to n-1 do
     begin
      for j:=0 to n-1 do
        write(A[i,j],'  ');
      writeln;
    end;

end.

         
0
Для начала меня смущает

A: array [,] of integer;

Это действительно работает? Просто я запускаю на Delphi 2010 и у меня на такое ругается. Обычно при использовании динамических массивов пишу так:

A: array of array of integer;

А еще очень странно, что не определено начальное значение переменной motion, в результате чего case может просто ни разу не выполниться (что и происходит у меня на той же Delphi 2010). И это еще не вдумывался в алгоритм работы… Сейчас гляну повнимательнее.
0
А в остальном, все в порядке. Молодец. :)
0
Ах, да… Совсем забыл. Просто смотрел работу без использования файлов.

Если же используются файлы, то:
— после написания assign необходимо открыть файл либо для чтения — reset(input), либо для записи — rewrite(output)
— после завершения работы с файлами необходимо их закрывать — close(input) и close(output), иначе записанные данные могут просто напросто не сохраниться на диск.
0
— спасибо большое за ваши комментарии, вы облегчаете мне жизнь :), время, потраченное мною на команду, я просто отрываю от семьи…
— тем более, что когда комментируешь чужое творение, можно ненароком обидеть и творца
0
Да, все верно. Кстати, если вдруг кого-то обидел или нечаянно обижу — это я не со зла и не специально.
0
Надо посмотреть, какой вариант быстрее и почему.
#include <stdio.h>
#include <iostream>

using namespace std;

void main()
{
	//Открытие файла и считывание размера массива
	FILE *fInput;
	fopen_s(&fInput, "C:\\in.txt", "r");
	int n;
	fscanf_s(fInput, "%i", &n);
	fclose(fInput);
	//Приём, который позволяет динамически задавать размерность многомерного массива
	int **result = new int *[n];
	for(int init = 0; init < n; result[init++] = new int[n]);
	//Ядро решения
	int i = 0, j = 0, dif = 0, value = 0, limit = n;
	do
	{
		for(; j < limit; result[i][j++] = ++value);
		--j;
		++i;
		for(; i < limit; result[i++][j] = ++value);
		--i;
		--j;
		for(; j >= dif; result[i][j--] = ++value);
		j = dif;
		--i;
		for(; i > dif; result[i--][j] = ++value);
		i = ++dif;
		++j;
		limit = n - dif;
	}
	while((i < limit) && (j < limit));
	//Выдача результата
	FILE *fOutput;
	fopen_s(&fOutput, "C:\\out.txt", "w");
	for(i = 0; i < n; ++i)
	{
		for(j = 0; j < n; fprintf_s(fOutput, "%i ", result[i][j++]));
		fprintf_s(fOutput, "\n");
	}
	fclose(fOutput);
}
0
Небольшие изменения. Самое основное — выход из цикла (как вариант оптимизации)
#include <stdio.h>
#include <iostream>

using namespace std;

void main()
{
	//Открытие файла и считывание размера массива
	FILE *fInput;
	fopen_s(&fInput, "C:\\in.txt", "r");
	int n;
	fscanf_s(fInput, "%i", &n);
	fclose(fInput);
	//Приём, который позволяет динамически задавать размерность многомерного массива
	int **result = new int *[n];
	for(int init = 0; init < n; result[init++] = new int[n]);
	//Ядро решения
	int i = 0, j = 0, dif = 0, value = 0, limit = n, N = n*n;
	do
	{
		for(; j < limit; result[i][j++] = ++value);
		--j;
		++i;
		for(; i < limit; result[i++][j] = ++value);
		--i;
		--j;
		for(; j >= dif; result[i][j--] = ++value);
		j = dif;
		--i;
		for(; i > dif; result[i--][j] = ++value);
		i = ++dif;
		++j;
		limit = n - dif;
	}
	while(value < N);
	//Выдача результата
	FILE *fOutput;
	fopen_s(&fOutput, "C:\\out.txt", "w");
	for(i = 0; i < n; ++i)
	{
		for(j = 0; j < n; fprintf_s(fOutput, "%i\t", result[i][j++]));
		fprintf_s(fOutput, "\n");
	}
	fclose(fOutput);
}
0
«Сишка» — это, конечно, красиво. Но, думаю, стоит заранее определиться с языком на каком будем решать задачки. Понятное дело, что алгоритм можно реализовать и на любом языке, но все же.
0
— да, я думаю, что лучше остановиться на Pascal
— основная причина, что специальность ИС у нас умирает и возможно и Си уже не будет, а мне нужно будет вести команду и далее + сейчас у нас только двое могут на Си (хотя можно, конечно, разными командами выступать) + как я уже писал в соседней теме что я делал более 10 лет назал я сам в синтаксисе Си почти на нуле (я ведь официально устроился на ФПИ только с 01.11.11. — а раньше приход сюда был для меня как хобби (зарплата то совсем низкая) — вот теперь как появится свободное время буду развиваться)
0
Не вижу проблем с использованием разных языков. Можно комбинировать. В любом случае, когда вопрос стоит о средствах, то, как говорится, любые хороши
  • avatar
  • Olga
  • 21 ноября 2011, 19:12
0
Я писала на ABC pascal, он позволяет задавать двумерный динамический массив как [,] и значение motion по умолчанию будет 0
0
Ммм… В PascalABC все может быть и так, но реальность более жестока. :)
  • avatar
  • Olga
  • 21 ноября 2011, 19:17
0
Не думаю что в данном случае объявление массива и переменной значительно ужесточает сущность реальности.
0
— у Ольги есть неоспоримый достаток, одновременно являющийся недостатком — Ольга пишет программы не просто быстро, а скорее — стремительно, тут поневоле будут появляться некоторые огрехи
0
Тут еще не только быстро, но и красиво. Мне вот очень понравилось само решение. А что мешает сразу использовать Delphi вместо PascalABC? Заодно и уровень сразу будет повыше и опыт работы со средой появится.
  • avatar
  • Olga
  • 21 ноября 2011, 20:59
0
ничего не мешает, просто abc первый под руку подвернулся. В следующий раз буду использовать Delphi
+1
Задание №9:
Program Z9;

Uses
  SysUtils;

Var
  sSource: String;
  fInput, fOutput: TextFile;

Function PSWO(sSource, sOldPattern, sNewPattern: String): String;
Var
  sTarget: String;
Begin
  sTarget := StringReplace(sSource, sOldPattern, sNewPattern, [rfReplaceAll]);
  While sTarget <> sSource do
   Begin
    sSource := sTarget;
    WriteLn(fOutput, sSource);
    sTarget := StringReplace(sSource, sOldPattern, sNewPattern, [rfReplaceAll]);
   End;
  Result := sSource;
End;

Begin
  //Блок получения исходных данных
  AssignFile(fInput, 'C:\in.txt');
  Reset(fInput);
  ReadLn(fInput, sSource);
  CloseFile(fInput);
  //Ядро решения - криворукое использование функции PSWO
  AssignFile(fOutput, 'C:\out.txt');
  Rewrite(fOutput);
  WriteLn(fOutput, sSource);
  PSWO(PSWO(PSWO(sSource, 'XO', 'OX'), 'OO', ''), 'XX', '');
  CloseFile(fOutput);
End.
0
— я извиняюсь, у меня прямо сейчас по времени запарка и я потом повникаю в детали, но что-то у меня не сработала прога
— + еще всё-таки не стоит писать конкретно 'C:\in.txt' и 'C:\out.txt', удобнее таки 'in.txt' и 'out.txt'…
0
Просто директиву компилятора

{$APPTYPE CONSOLE}

отвечающую за создание консольного приложения пропустили (или писали на Pascal'е)…
0
— спасибо
0
— но, кстати, я вернулся к программе — посмотреть, что да как и обнаружил мой явный промах — я в текстовый входной файл писал символы русским шрифтом — у-ха-ха — конечно, ваша прога с ними и не работала :)
0
— программа у вас получилась достаточно компактная
— а вы не засекали время, потраченное на её написание и отладку?
— я потом постараюсь оценить её красоту
0
— но вот это сразу понравилось:
PSWO(PSWO(PSWO(sSource, 'XO', 'OX'), 'OO', ''), 'XX', '');
:)
— удачное решение
0
По поводу времени, потраченного на отладку — почти совсем не отлаживал (проблема была с русской раскладкой)))
Компактная программа получилась только благодаря StringReplace, на неё совершенно случайно наткнулся, если честно
0
— я рад, значит не зря я формулировал эту задачу!
0
Ты не знал о StringReplace? О_О
А что ты имел в виду, когда говорил, что в Delphi лучше организована работа со строками, если не эти функции?
0
Да, я не знал о StringReplace, поскольку обычно консольные приложения писал в паскале.
Когда я говорил о том, что в Delphi легче работать со строками, я прежде всего имел ввиду удобное объявление строк, ну и разные операции (та же конкатенация через "+"). Может ещё что-то…
0
Я когда писал решение, тоже с этим столкнулся ;)
0
>>— я извиняюсь, у меня прямо сейчас по времени запарка и я потом повникаю в детали, но что-то у меня не сработала прога — не знаю, у меня всё работает. Если что — написано на делфи, поэтому вполне возможно, что ругается на StringReplace (из модуля SysUtils), поскольку в паскале такого чуда нет.
>>— + еще всё-таки не стоит писать конкретно 'C:\in.txt' и 'C:\out.txt', удобнее таки 'in.txt' и 'out.txt'- я видел этот совет (он, бесспорно, абсолютно правильный), но суть в том, что мне проще на компе иметь один файлик в C:\in.txt, чем каждый раз делать его в новых местах, поэтому я так пишу (ну на самом деле, мне так удобно). Естественно, что на олимпиаде никаких абсолютных путей быть не может, но здесь, я полагаю, важен сам алгоритм, а не такие детали.
0
— ясно
0
Задача №8 (не думал, что так страшно получится).
#include <stdio.h>
#include <iostream>
#include <conio.h>
#include <vector>
#include <ctime>

using namespace std;

void main()
{
	int iFirst = -1, iLast = -1, iCandidate = -1;
	//Вектор - один из видов контейнеров
	vector <int> result;
	//Такая интересная конструкция - аналог Randomize в делфи
	srand(time(NULL));
	//Генерирую количество элементов
	int n = rand()%20 + 1, i;
	for(i = 0; i < n; ++i)
	{
		int value = rand()%19 - 9;
		result.push_back(value);
		//Если встретили положительное число
		if(value >= 0)
		{
			switch (iCandidate)
			{
			//-2 означает, что у нас уже есть начало последовательности. В этом случае надо просто подвинуть границу группы
			case -2:
				{
					iLast = i;
					break;
				}
			/*
			-1 означает, что мы встретили первое положительное число, т.е. предыдущее число было отрицательным или предыдущих чисел нет вообще.
			В этом случае нужно записать индекс числа как кандидата на начало последовательности
			*/
			case -1:
				{
					iCandidate = i;
					break;
				}
			/*
			Это случай, если у нас был кандидат на начало последовательности. Тогда надо утвердить кандидата, сделать конечную границу группы и задать флаг,
			что последовательность начата
			*/
			default:
				{
					iFirst = iCandidate;
					iCandidate = -2;
					iLast = i;
					break;
				}
			}
		}
		//В случае, если встретили отрицательное число, нужно задать флаг, что при встрече другого положительного числа нужно заново начинать процедуру создания группы
		else
		{
			iCandidate = -1;
		}
		cout << value << " ";
	}
	cout << "\n";
	//Вывод результата
	if((iFirst == -1) || (iLast == -1))
	{
		cout << "Not exists valid group";
	}
	else
	{
		//Вывожу индексы начала и конца группы. Вывожу элементы, которые не входят в найденную группу.
		cout << iFirst << " " << iLast << "\n";
		for(i = 0; i < iFirst; cout << result[i++] << " ");
		for(i = iLast + 1; i < n; cout << result[i++] << " ");
	}
	getch();
}
  • avatar
  • belan
  • 23 ноября 2011, 15:24
0
— кстати, опять апробировал систему автоматической проверки — очень удобно
— опять столкнулся с небольшой ошибкой — отправил решение, получил такой ответ: Runtime Error, читаю варианты почему такое может быть:
• При проверке произошла runtime-ошибка (исключение).
• Решение содержит работу с файлами (кроме input.txt).
— в моем случае был второй вариант, то есть я входным файлом в тексте проги написал не input.txt, а in.txt
— я считаю, что всем (особенно нашим второкурсникам) обязательно следует тренироваться в этой системе, хотя бы чтобы потом уже не тратить время на исправление мелких, не связанных с логикой программирования, недочетов (мне то выступать не надо, я лишь вас инициализирую :) )
  • avatar
  • belan
  • 23 ноября 2011, 17:14
0
— люди добрые помогите пЭнсионЭру (у меня реально уже есть пенсионное удостоверение и я даже получаю пенсию :) )
— я уже так давно не касался математики и не помню о всяких там интегралах или последовательностях
— но даже в простенькой задачке не могу найти причину непрохождения теста

Вводится число. Напечатать YES, если оно является степенью двойки, NO - иначе.
________________
Ввод 1 	 Ввод 2 
 8	 22
Вывод 1  Вывод 2 
 YES	 NO
________________

— первый раз выслал такую (определяет только положительные степени двойки):
program P2;
{$APPTYPE CONSOLE}
uses  SysUtils,Math;
var s: string;
begin
  assign(input, 'input.txt');
  reset(input);
  ReadLn(s);
  if frac(log2(StrToInt(s)))=0
    then write('YES')
    else write('NO');
  close(input);
end.
мне прислали ответ: Wrong Answer
— второй раз выслал такую (определяет и отрицательные степени двойки тоже, например: на 0,001953125 ответит да, а на 0,001953127 — нет):
program P2;
{$APPTYPE CONSOLE}
uses SysUtils,Math;
var s: string;
    n: real;
begin
  assign(input, 'input.txt');
  reset(input);
  Readln(s);
  n:=StrToFloat(s);
  if frac(log2(n))=0
    then write('YES')
    else write('NO');
  close(input);
end.
результат тот же
— что я не знаю про числа или не понял в задаче?
0
Каюсь, виноват. И виноват вот в чем. На сервере, на котором работает Contester, установлена ОС семейства Linux (а точнее говоря — CentOS), поэтому использование Delphi для компиляции решений невозможно. В связи с этим для рещений на Pascal'е используется свободный компилятор FreePascal, который имеет некоторые особенности.

Например, условие frac(log2(n)) = 0 с некоторой долей вероятности может возвращать ложное значение даже в случаях, когда n является степенью двойки.

Так при использовании Delphi следующая программа

WriteLn(frac(log2(64))=0);
WriteLn(frac(log2(128))=0);
WriteLn(frac(log2(1024))=0);

выведет

TRUE
TRUE
TRUE

А та же самая программа на FreePascal выдает:

TRUE
FALSE
TRUE

Потому что frac(log2(128)) каким-то фантастическим образом возвращает 1 вместо 0… О_о Сейчас буду думать, как решить данную проблему. Для решения задачи пока что можно воспользоваться каким-нибудь другим способом, хотя вцелом решение верное.
0
Все дело даже в функции log2, которая для значения 128 выдает результат ~6,9999999999999999954525..., а не 7,0…
0
В этом случае, похоже, помогает следующая конструкция:

x: Double;
...
x := log2(128);
WriteLn(frac(x));

где Х — переменная типа Double или Real (при использовании Extended ошибочное значение сохраняется). Конечно Double и Real имеют несколько меньшую точность, но сильно повлиять на решение это не должно.
  • avatar
  • belan
  • 03 декабря 2011, 02:58
0
— добавил некоторые рассуждения по поводу мылых чисел
0
— подобный результат встречался мне во многих разных ситуациях — он, конечно, зависит от способа реализации функции в языке
— тут недавно пришлось занятие с заочниками по Exctel`ю вести — там тоже столкнулся с ненулевым значением тригонометрической фонкции в том месте где точно должен быть ноль — она дает результат порядка E-17, но не ноль
0
— любопытно, а на олимпиаде вы не столкнетесь с такой же или подобной проблемой?
0
На сколько помню, там сервер работает на Windows и, соответственно, в роли компилятора используется та же Delphi. Поэтому таких проблем в принципе быть не должно. Хотя запомнить следует на всякий случай.
0
Сам я использовал другой подход к решению этой задачи:

{$APPTYPE CONSOLE}

uses
  SysUtils;

var
  n, i: Integer;
begin
  ReadLn(n);
  i := 1;
  while i < n do
    i := i * 2;
  if i = n then
    WriteLn('YES')
  else
    WriteLn('NO');
end.

Поэтому и не столкнулся с этой проблемой.
0
— я, конечно, прежде чем написать код думал об этом подходе, но сразу от него отказался по понятной причине — я думаю и вы её и без меня знаете, но для начинающих оставлю соё мнение — цикл сработает медленнее
— ну и кстати — обращу ещё внимание на тот факт, что в задаче не указано какие именно могут быть степени двойки — в этой реализации нельза проверить число 0,125, являющееся степенью двойки — "-3"
0
Кстати, заметил, что вы постоянно читаете из файла строку и переводите ее в число. Этого можно не делать, можно сразу же читать числовые значения, т.е. вместо всего этого:

Readln(s);
n:=StrToFloat(s);

просто написать

ReadLn(n);
0
— ага, спасибо :)
— я как-то и не придавал этому значение — типа «читаю строку» — ага, значит надо строковую переменную :)
+1
Еще одно из решений задачи:
#include <iostream>
int main() {
	unsigned x; std::cin>>x;
	std::cout<<(((~x&x-1)==x-1)?"YES":"NO");
	return 0;
}

Как мне кажется, сделано красиво. Правда работает только для целых чисел.
+1
И еще одно… Тоже «экзотика» (о ней и не только поговорим во второй серии «Ненормального программирования», уже скоро):

#include <iostream>
#include <bitset>

int main()
{
  int a; std::cin>>a;
  std::bitset<sizeof(int)*8> b1; b1|=a;
  std::cout<<(b1.count()==1?"YES":"NO")<<"\n";
  return 0;
}

Также работает только для целых.
  • avatar
  • belan
  • 23 ноября 2011, 17:16
0
— я сейчас уезжаю часиков до 23.00 (очередное хобби — теннис), но вечерком обязательно загляну сюда
  • avatar
  • belan
  • 23 ноября 2011, 21:57
0
— у меня есть ощущение, что некоторые из второкурсников немного стесняются сюда писать
— если это вдруг именно так, то уверяю вас тут общаются не «реальные пацаны» — никто не будет кидать помидоры в совершившего оплошность, а в ходе обсуждения мы все прогрессируем
— может просто времени нет свободного, сессия ведь скоро…
0
Стеснять уж точно не нужно. Никто вас не обидит. Напротив, если что — мы всегда рады помочь и поделиться знаниями… ;)
  • avatar
  • belan
  • 24 ноября 2011, 15:45
0
— внимание: теперь текущий список заданий в первом посте под спойлером, на текущий момент там 10 заданий, буду потихоньку пополнять
— на декабрь (перед Новым годом) запланируем первый праздничный battle :)
— тренировки будут проходить в 602 ауд. — я постараюсь обсудить время когда удобнее будет максимальному количеству участников — под всех не подстроиться
— примерный формат такой (пока навскидку): 5 заданий на 2 часа, задания из разных тем (рекурсия, комбинаторика, строки и т.п.) задания средней сложности (на мой субъективный взгляд)
— у нас пока 4 активных + 1 почти в активе + 2-3 не определившихся (возможно к весне будут свежие силы)
— можно для конкуренции и отработки тактики скоростного решения задач в команде с неравным (по силам игроков) составом пока организовать поединок между условными командами — две команды по ~3 игрока (один лидер (у нас есть как раз два лидера :) ) + к нему исполнители)
— тактика в команде такая:
1) пробегаем быстро все задания и примерно сортируем их по сложности,
2) читаем одно несложное (на вскидку) задание, лидер генерирует идею и отдает на реализацию тому кто говорит, что понял и знает какими средстваим реализовать
3) читаем следующее задание, лидер генерирует идею и отдает на реализацию второму игроку
4) лидер берет сложное задание и реализует сам
5) потом, по готовности, снова обсуждается с лидером очередное задание и выполняется
___________
— а, кстати, рабочее место одно на всех?
0
Да, один компьютер на команду.
  • avatar
  • belan
  • 24 ноября 2011, 17:59
+1
— а вот моё решение Задания №5 — про «улитку»:
program P_Ulitka;
{$APPTYPE CONSOLE}
{
- основная идея алгоритма, простая, как бы делал человек:
1) назначаем 4 направления движения по количеству ребер
2) идем по направлению движения до тех пор пока не дойдем до границы
3) граница изначально размерность массива r,
   но с каждой петлей уменьшается на 1
}
uses
  SysUtils;
var a: array of array of integer;
    r,i,j,d,n,sh: integer;
    usl: boolean;
begin
  Assign(input, 'input.txt');   reset(input);
  Assign(output, 'output.txt'); rewrite(output);
  readln( r );    // узнаём размерность
  SetLength(a,r,r); // задаем размерность массива
  d:=0;  // счетчик для заполнения таблицы от 1 до r*r
  i:=0;  // стpока
  j:=-1; // столбец
  n:=1;  // напpавление движения: 1-right, 2-bottom, 3-left, 4-top
  sh:=0; // шагов недохождения до гpаницы массива на очередном витке улитки
       repeat

         inc(d);
         case (n-1) mod 4 +1 of // напpавление от 1 до 4
           1: begin inc(j); usl:=j=r-1-sh; end;
           2: begin inc(i); usl:=i=r-1-sh; end;
           3: begin dec(j); usl:=j=sh; end;
           4: begin dec(i); usl:=i=sh; end;
         end;
         a[i,j]:=d;
         if usl then // уже дошли до границы?
           begin inc(n); sh:=n div 4; end;

       until d=r*r;

  for i:=0 to r-1 do
  begin
    for j:=0 to r-1 do write(a[i,j],#9); // вывод через табулятор
    writeln;
  end;

  close(input); close(output);
end.
— делал не сейчас, а когда-то специально для лабораторной работы №3 по массивам по Алгоритмизации и программированию, кто учился на первом курсе у меня тот должен помнить — можно даже заглянуть на страничку тут лабораторки по АиП на Pascal
0
Что-то тема приутихла, сервер большую часть времени простаивает, хотя и работает круглосуточно. Может стоит несколько «прорекламировать» ссылки на эту тему и сервер с задачами среди студентов 1-3 курсов?
0
— я, по семейным обстоятельствам, не имею сейчас времени свободного
— а студентам эта тема нужна только тем кто, может быть, будет участвовать в команде
— со всего 2-го курса не более 4-х человек способны осилить рассматриваемые задачи
0
— На самом деле можно приглашать сюда не только тех, кто будет в команде, но и всех тех, кто просто хочет проверить и подтянуть свой уровень программирования. Те, кто сейчас и не будут в команде, могут оказаться там уже в следующем году, так что лишним не будет.
— Не столь важно, смогут ли люди осилить все представленные здесь задачи. Главное, чтобы у людей было желание и стремление их решить. Мы не против помочь каждому, кто захочет попробовать свои силы. А на сервере имеются и самые простые задачи. На текущем этапе, лично мне, важно не только понять, кто будет в команде в этом году, но и отметить тех, у кого есть потенциал на будущее.
  • avatar
  • belan
  • 01 декабря 2011, 20:26
0
— я вернулся, правда дел всё равно не в проворот, но хотя бы разок в день могу тут бывать
1) в декабре меня заслали на учебу с 12 по 19 :( — менеджмент какой-то :( :( :(
2) потом много заочки понапихали до 27 декабря :( — так что опять буду занят
3) тем не менее, если найдутся желающие — устроим очную встречу со скоростным программированием (формат обсудим)
4) сегодня у меня с нашим уважаемым деканом состоялся разговор на счет каманды по программированию — зародилось сомнение о возрастном статусе выступления в команде — пока не знаю где уточнить ещё о возможности выступления старшекурсников
0
Вряд ли наш декан в курсе всех деталей олимпиады. По-моему четверокурсники могут выступать
  • avatar
  • belan
  • 03 декабря 2011, 02:22
0
— очень надеюсь на это! :)
  • avatar
  • belan
  • 03 декабря 2011, 21:22
0
— сегодня нашел немного времени и опять апробировал сервер по проверке решения задач
— снава наступал на те же грабли :)
1) выводил в файл output.txt (это выдает ошибку — Presentation Error), а система требует вывод в консоль
2) при выводе в консоль я оставлял оператор readln; — типа для того, чтобы задержать экран и посмотреть результат — это выдает ошибку Runtime Error
— программа то простая, а я потратил на неё 4 лишние попытки, включая два ненужных исправления меняя сначала цикл с for на while, потом проверку на нечетность с odd на mod 2
— вот тут можете посмотреть код с двумя вышеобозначенными ошибками:
program P_chet;
{$APPTYPE CONSOLE}
uses SysUtils;
{Вводится последовательность чисел. Посчитать в ней количество чётных чисел, стоящих на чётных местах.
Ввод: Вводится сначала число N, а затем N чисел - члены последовательности.
Вывод: Выведите количество чётных чисел, стоящих на чётных местах в последовательности.
Ввод 	Вывод
 5
 1 2 4 5 6	 1}

var i,k,n,dig: Int64;
begin
  assign(input, 'input.txt');
  reset(input);
  assign(output, 'output.txt'); rewrite(output);

  n:=0; i:=0;
  Read(k);
  while i<k do
  begin
    inc(i);
    read(dig);
//    if (not odd(i)) and (not odd(dig)) then inc(n);
    if (i mod 2 = 0) and (dig mod 2=0) then inc(n);

  end;
  close(input);
  write(n);
  readln;

  close(output);
end.
, не то что ошибками, но эти неточности не дают пройти тест…
______
— исправив указанные неточности я тест прошел, но потом решил ещё доработать в том смысле, чтобы не перебирать нечетные числа вовсе и итоговый вариант выглядит так:
program P_chet_2;
{$APPTYPE CONSOLE}
uses SysUtils;
var i,k,n,dig: Int64;
begin
  assign(input, 'input.txt');
  reset(input);
  n:=0; i:=0;
  Read(k);
  while i<k-1 do
  begin
    inc(i,2);
    read(dig); read(dig);
    if dig mod 2=0 then inc(n);
  end;
  close(input);
  write(n);
end.

— таким образом один пользователь в системе может проверять несколько вариантов своих решений — очень хорошо!
______
— считаю обязательным ввести некоторый критерий включения игрока в команду — звучит примерно так: «необходимо самостоятельно пройти формализованное тестирование решенных заданий в системе contester в количестве не менее N штук»
— количество N я не знаю, ну хотя бы 10 штук :), что скажете
0
— Поясню один момент. Оставлять в конце ReadLn для того, чтобы приостановить программу для отображения результата можно, но только если осуществляется чтение с консоли. Если же производится чтение из файла, то конечный ReadLn не найдет каких-либо данных в файле (потому что все уже прочитано) и программа вываливается с Runtime Error. Чтобы избежать такой ошибки нужно либо использовать чтение с консоли, либо не оставлять в конце ReadLn.
— Насчет критерия полностью согласен, т.к. это позволит игрокам и лучше ознакомиться с той системой, с какой им предстоит работать (даже если и не с точно такой, то с очень похожей), а это существенно снизит количество неправильных решений из-за подобных же нюансов, и улучшить свои навыки программирования.
  • avatar
  • belan
  • 05 декабря 2011, 21:07
0
— ну вот я прошел нижнюю границу — решил 10 заданий и получил в Contester`е 10 раз — «Accepted!», так что меня уже можно брать в команду :)
— я вообще-то полагаю, что в таком деле как соревнования не я должен быть «мотиватором» и всех палкой загонять на тренировку мне не обязательно — ЕСТЬ У КОГО-НИБУДЬ ПРЕДЛОЖЕНИЯ КАК ПОДНЯТЬ МОТИВАЦИЮ ИГРОКОВ НАШЕЙ КОМАНДЫ
— эпоха обязательных очных встреч для организации учебного процесса уже канула в Лету и сейчас многому (в том числе программированию) можно учиться не выходя из дома — нам нужны будут встречи, как правильно заметил imtec, только для отработки командной тактики
0
>>нам нужны будут встречи, как правильно заметил imtec, только для отработки командной тактики
Это само собой разумеещееся. Не учить же людей программировать за полгода до олимпиады…
  • avatar
  • belan
  • 12 декабря 2011, 20:49
0
— итак, на этой неделе я занят — учусь какому-то менеджменту, впрочем я и потом до 27-го числа буду занят, но хочу найти такой день когда бы мы могли собраться вместе и провести очную встречу
— 31-го собираться не будем ;)
— дни когда у меня нет заочки 21 (среда) и 26 (понедельник) — скорее всего в один из этих дней и встретимся, все остальные дни до 27-го у меня идет заочка по пять пар каждый день и они заканчиваются обычно к 20.30 — так что это не вариант
— видимо разбивка на команды будет такая: 1) команда от 4-го курса; 2) команда от 2-го курса
— предлагаю перед встречей, особенно второкурсникам, ознакомиться с материалами: Об опыте участия в соревнованиях по спортивному программированию и О решении олимпиадных задач по программированию
— предлагаю второкурсникам после прочтения материала обдумать и обсудить как вы будете строить свою работу в команде
  • avatar
  • belan
  • 19 декабря 2011, 18:43
0
— предлагаю встречу провести 26 декабря, в понедельник, я завтра буду на кафедре и узнаю о занятости аудиторий в этот день, время встречи обозначу позже…
— желательно быть всем, так как встреча в том числе носит и учебный характер — я кое что приготовил в качестве заданий, то что разберем в этот раз, в следующий раз уже не будет времени обсуждать…
  • avatar
  • belan
  • 21 декабря 2011, 12:07
0
— я предварительно по ICQ пообщался почти со всеми, большинство готовы 26-го (в пн)
— кому во сколько 26-го удобнее, напишите…
— предожу в 14.00 начать (часика на 2-3)…
— аудитория 602
— по окончании желающие и могущие остаются на праздничное чаепитие для обсуждения тактики командного решения задач, перераспределения и сплочения состава — кто с кем может и хочет находиться в команде (так как в команде д.б. не более 3-х игроков, а у нас, возможно, тренирующихся будет ходить на три команды)
— получена информация, что нет ограничения на возраст/курс игроков
0
— Итак, выяснил причину того, почему программа «Почтовые цифры» не проходила проверку. Начиная с 14го теста используются входные данные, по какой-то причине не соответствующие условиям задачи (т.е. во входном файле более чем 10 цифр).
— В коде же используется следующее объявление массива под цифры:
m: array[1..9,1..10] of byte;
w: array[1..10] of byte;

Таким образом под цифры отводится не более 10 позиций. При попытке вписать туда большее количество цифр происходил выход за пределы массива, о чем программа сообщала и зависала, пока не заканчивалось отведенное на ее работу время. Как этот же код работал в других средах — пока что загадка.
— Теоретически (строго по условиям) задача решена верно.
  • avatar
  • belan
  • 27 декабря 2011, 16:31
0
:)
— да уж, спасибо!
— ещё один вывод: на всякий случай использовать массивы динамические
  • avatar
  • belan
  • 24 февраля 2012, 17:28
0
— необходимо провести очередную встречу команды по программированию для поднятия тонуса, отработки навыков и сплочения
— я постараюсь собрать информацию — кому когда удобно — но предварительно сразу после праздников… то есть 9 марта и далее
— например, можно собраться 12 марта с 17.00 на 2 часа…
+1
Поддерживаю, пора собираться…
+2
— подтверждаю место и время встречи: 602 аудитория 12 марта с 17.00 на 2 часа, аудитория заказана, будет интернет — надеюсь апробировать командный подход к формализованному решению задач из контестера…
— к imtec — возьмите своих (4 курс) — кто хочет и сможет…
— будут ещё со 2 и 1 курсов
+2
— напоминаю, что не все полностью решили задания с первой встречи… будет частичный возврат к одной из задач с усложнением её формулировки…
— возможно будет разделение отдельных команд по уровню сложности с целью максимальной эффективности затрат времени на встрече — кому-то нужны задачи попроще…
— возможно будут три отдельные команды…
— я напоминаю (для младших курсов), что цель не просто выполнить задания, а в ограниченное время выполнить максимальное количество заданий — для чего, при примерно равных силах игроков, начальный этап решения каждой задачи можно осуществлять индивидуально — продумать основу алгоритма и накидать на бумаге код без детализации, а по мере освобождения компьютера можно апробировать код и обсуждать баги вместе…
— по завершении тренировки, после 19.00, желающих могу подбросить (центр, Мотовилиха, Южный, Садовый)
+2
— пока не забылось — отпишу впечатления от встречи…
— до мая будем по возможности встречаться почаще, 1-2 раза в месяц
— обсуждая вместе решение задачи — работоспособная программа порождается быстрее
— каждый может сделать ошибку, глаз на свою программу «замылен» и не видит очивидных промахов
— написал на скорую руку код лучше вернуться к тексту задания и снова его внимательно оценить… очень вероятно, что обнаружатся детали, которые при первоначальном вникании в задачу не были учтены
— нужно приводить «под общий знаменатель» стили программирования игроков в одной команде — иначе возникают ненужные затраты времени на притирку и понимание написанного кода другим игроком
— не забываем обнулять переменные
— если в строковую переменную s записана пустая строка, то фактическая её длина = 0 и заполнять строку посимвольно, например так s[12]:='*' и потом печатать s не правильно
— вот такая конструкция возможна — c:=IntToStr(25)[1];
в переменную c типа char присвоится символ '2' — первый символ строки, которую вернула функция IntToStr, строка тут выступает в роли массива символов
+3
— такс, возможно к нам таки присоединится и третий курс — гражданин Сорха получил сегодня от меня информацию и должен сюда заглянуть… на него я вышел по наводке от 4-го курса :)
0
Решил все же порешать еще задачки. Заодно поглядел, что такое Ruby. Одно могу сказать точно — веселый и заразный язык… Ну, а с чего можно начинать знакомство с языком, как не с «хеловорлда»?.. Вот поэтому решение строковой задачки №9:

$stdin = File.open("input.txt")
$stdout = File.open("output.txt", "w")

puts str = gets
while str.include?("XO")
  puts str = str.gsub("XO", "OX")
end
while str.include?("OO")
  puts str = ("  " * str.scan("OO").size + str).gsub("OO", "")
end
while str.include?("XX")
  puts str = ("  " * str.scan("XX").size + str).gsub("XX", "")
end

Не судите строго, одна из моих первых программ… Ну не считая одного веб-квайна… О_о
0
Глупый-глупый-глупый я наставил лишние циклы…
$stdin = File.open("input.txt")
$stdout = File.open("output.txt", "w")

puts str = gets
while str.include?("XO")
  puts str = str.gsub("XO", "OX")
end
puts str = ("  " * str.scan("OO").size + str).gsub("OO", "")
puts str = ("  " * str.scan("XX").size + str).gsub("XX", "")
0
Или я не глупый и они там были нужны? Совсем уже не соображаю… %(
0
Ты глупый, второй вариант правильней… Думай дальше…
0
А еще в последней строке присваивание уже можно не делать… Вот… :)
  • avatar
  • belan
  • 26 марта 2012, 19:31
+1
:0
:)
0
Продолжаем изучать это произведение искусства… По другому и не сказать, и вот почему — решение задачи №2:

a = 3; b = 5; a, b = b, a
puts "a = " + a.to_s + ", b = " + b.to_s

Меня все больше поражает это чудо… %)
0
Задача №10:

1.upto(11) { |m| 1.upto(11) { |w| 1.upto(11) { |c|
  if m + w + c == 12 && m * 2 + w * 0.5 + c * 0.25 == 12
    puts "Men: #{m}, women: #{w}, children: #{c}"
  end
} } }

Циклы красивы… Эх…
0
Ну и немного оптимизируем решение…

1.upto(11) { |m| 1.upto(12-m) { |w| 1.upto(12-m-w) { |c|
  if m + w + c == 12 && m * 2 + w * 0.5 + c * 0.25 == 12
    puts "Men: #{m}, women: #{w}, children: #{c}"
  end
} } }
0
И еще чуть-чуть…

1.upto(11) { |m| 1.upto(11-m) { |w| c = 12-m-w
  if m * 2 + w * 0.5 + c * 0.25 == 12
    puts "Men: #{m}, women: #{w}, children: #{c}"
  end
} }
0
— ой, а там в условии ошибка с моей стороны, там д.б. мужчины несут по 4 хлеба
0
— просто так решение получается одно, а при условии, что М*2 — получается два возможных решения
0
Странно, у меня и в том, и в другом случае выводится по одному решению:
— если несут по 2 — Men: 5, women: 1, children: 6
— если несут по 4 — Men: 2, women: 6, children: 4
0
И еще первый цикл нужно лишь до 10 делать…
0
— Пролог мне дает такие решения при условии, что m*2:
М=4 Ж=8 Д=0
М=5 Ж=1 Д=6
0
А, ну тогда все понятно… Просто я не учитываю решения, где есть нули. Делаю с учетом того, что имеется хотя бы по одному мужчине, женщине и ребенку…
0
— а почему цикл «1.upto(11)» от 1 до 11?
— там вроде нигде не стоит запрет, что не может быть людей одного сорта = 0
— тогда уж можно заранее перебор по М и Ж ограничить ещё более: для случая когда несут по 4 — Мужчин не может быть более 3, Женщин — более 6…
— но не выдает решение по какой-то иной причине
— а нет там такого, что первый же puts прерывает перебор?
0
:)
0
— а еще есть занятный вариант просто генерировать случайные числа до выполнения условия — тоже проходит хорошо!!!
0
— я тут кое-кому (3 курсу) — на прологе-Д прямо на лекции токое придумал и реализовал:
— только на прологе-Д (он под виновс) выглядит более громоздко, чем на ТурбоПрологе (тот что под ДОС):
% ИДУТ 12 ЧЕЛОВЕК, НЕСУТ 12 БУЛОК ХЛЕБА
% МУЖЧИНЫ НЕСУТ ПО 4...     ЖЕНЩИНЫ ПО ПОЛОВИНКЕ...   ДЕТИ ПО ЧЕТВЕРТИНКЕ...
% НАЙТИ СКОЛЬКО ИДУТ М Ж Д
         % БАЗА ПРАВИЛ
  повтор.
  повтор:-повтор.
  печать(М,Ж,Д):-
                повтор,
                СЛУЧ(a),  СЛУЧ(b), СЛУЧ(c),
                УМНОЖЕНИЕ(э,10,М,a), УМНОЖЕНИЕ(ю,10,Ж,b), УМНОЖЕНИЕ(я,10,Д,c),  
   
                УМНОЖЕНИЕ(4,М,0,m), УМНОЖЕНИЕ(0.5,Ж,0,g), УМНОЖЕНИЕ(0.25,Д,0,d),
                СЛОЖЕНИЕ(m,g,W), СЛОЖЕНИЕ(W,d,Х),  РАВНО(Х,12),
                
                СЛОЖЕНИЕ(М,Ж,e), СЛОЖЕНИЕ(e,Д,Л),  РАВНО(Л,12), !.

? печать(М,Ж,Д).

— обратите внимание, что громоздко выглядит только арифметическая часть, а часть логики перебора почти вообще отсутствует :), ну а на ТурбоПрологе арифметическая часть сравнения пишется нормально-компактно-обычно «m+g+c=12, 4*m+0.5*g+0.25*c=12»
0
— то есть фактически примерно так (я тут уже без соблюдения правил, но фактически код):

  повтор.
  повтор:-повтор.
  печать(М,Ж,Д):-
                повтор,
                СЛУЧ(М), СЛУЧ(Ж), СЛУЧ(Д),
                М+Ж+Д=12, 4*М+0.5*Ж+0.25*Д=12.»
0
— ну чтобы не генерировал долго следует конечно указать диапазон генерации случайного целого числа до 12 :)
0
— Цикл должен быть до 10, если не учитывать нулевые решения и до 12, если учитывать. 11 — это мой глюк.
— Не выдает решение именно по той причине, что ни m, ни w ни c никогда не устанавливаются в ноль.
— puts — это стандартный оператор вывода, он не прерывает работу.
0
Вот такое решение выводит в том числе и нулевое решение…

0.upto(12) { |m| 0.upto(12-m) { |w| 0.upto(12-m-w) { |c|
  if m + w + c == 12 && m * 2 + w * 0.5 + c * 0.25 == 12
    puts "Men: #{m}, women: #{w}, children: #{c}"
  end
} } }
0
— про путс — это я конечно понял — так просто, мало ли…
— а про М и Ж — они то и не в нуле для второго решения, а всё равно не выдает ???
0
Во втором решении c=12-m-w, а m+w никогда не доходят до 12, следовательно c не обращается в ноль.
0
— чилдрен от 0 должен как в последнем коде
— а вот в этом
1.upto(11) { |m| 1.upto(11-m) { |w| c = 12-m-w
вроде нет запретов чилдрену быть нулевым, а не выдает
  • avatar
  • belan
  • 31 марта 2012, 17:36
+2
— на ближайшей неделе у меня много заочки
— предлагаю на неделе, которая начинается с 09.04 провести встречу — хотелось бы собрать на встречу максимальное кол-во игроков — для совместного решения задач средней сложности (на одну задачу 20-30 мин.) — для сближения стилей программирования внутри команд
— напишите дни кому когда удобно — мне нужно будет заранее застолбить аудиторию — чтобы туда заочку не поставили
— мне удобнее всего в понедельник с 17.00
— по средам не могу
— могу в четверг с 17.00
— сб и вск — семья, дети, животные, родственники, спорт, туризм :)
0
Могу выделить время, в принципе, в любой день, но в понедельник так же удобнее всего.
Надеюсь в этот раз все же в последний момент не загрузят работой…
0
Могу в любой день, но если в понедельник, то хотелось бы попозже — у меня пары до 17:10.
0
— у меня тоже до 17.10 :), если у вас пары в нашем же корпусе, то это не проблема — первые минут 10-15 кто-то задерживается — мы ждем, беседуем…
— у нас заочное отделение планирует занятия на следущую неделю только в субботу и в сеть выкладывают к вечеру субботы — так что я могу неожиданно 07.04. узнать, что мне поставили в понедельник 09.04 занятия на заочке — я надеюсь, что именно так не будет
0
— итак, я уже спрашивал и у 1-го курса и у 3-го и у остальных — конечно под всех очень трудно день подобрать, но очередная встреча предварительно назначается на 09.04.2012 — аудитория 602 — время с 17.15 и далее… полагаю, что часа на 2 :)
0
На завтра все остается в силе? :)
0
Вроде как да, завтра в 17:15
  • avatar
  • belan
  • 09 апреля 2012, 09:18
+1
— да, в силе, надеюсь будут и 3-й и 1-й курс, 1-й опоздает минут на 20
0
Кажется первый курс так и не пришел…
+2
— ну с первым курсом я завтра встречусь, поговорю — задачи я с наших встреч ему отдаю и он их решает в одиночку
— сегодня порадовала сборная команда 223 — второго-второго-третьего курса: 1) им/вам удалось таки работать вместе, 2) им/вам удалось решить задачи не медленнее, чем четвертому курсу
— задачи я, конечно, намеренно не стал придумывать архисложные — но четвертый курс (команда 44, так как четвертый-четвертый) и в них нашел возможность проявить креативный подход по написанию классов шахматного поля и фигур :)
— у команды 223 опять есть тенденция писать код длинным, излишним кодом и потом в нем искать ошибки — в одной программе встречаются 2-3 места где можно кодить короче, прозрачнее
— намечается рождение новой команды — 441 (четвертого-четвертого-первого курсов) — я только рад — мне кажется молодой Еремин (1-й курс) очень органично впишется, он активен, но требует присмотра и направления
+1
— Команда «223» — однозначно молодцы, у них есть достаточно большой потенциал, есть куда развиваться и есть хорошая база для этого развития. Кстати, куда же пропадали еще две буквы?..
— По поводу объектно-ориентированного подхода при решении 2ой задачи: при таком подходе код решение настолько прост и прозрачен, что ошибок просто не может возникнуть. А вот как и с чем работать в том или ином языке забыть можно… Поэтому — тренировка, тренировка и еще раз тренировка!
— Команду «441» нужно попробовать собрать и посмотреть, как они сработаются. Девчонки без нас могут впасть в апатичное состояние, поэтому за них тоже нужно будет взяться посерьезнее, чтобы не унывали. Главное — дать им понять, что все получится.
+2
Чтобы развеять мнения, что что-то зависит от выбора языка для решения задач, публикую наше с Денисом оригинальное решение (на С++) и то же самое решение на Delphi. Как говорится, найдите отличия… :)

C++:
#include <stdio.h>

struct Point
{
	int x, y;

	Point operator +(Point& source)
	{
		Point result;
		result.x = x + source.x;
		result.y = y + source.y;
		return result;
	}
};

class CCell
{
public:
	char value;

	CCell(const char & source)
	{
		value = source;
	}

	int Rang()
	{
		switch(value)
		{
		case 'п': return 1;
		case 'к': return 2;
		case 'с': return 3;
		case 'л': return 4;
		case 'ф': return 5;
		case 'р': return 6;
		case 'П': return -1;
		case 'К': return -2;
		case 'С': return -3;
		case 'Л': return -4;
		case 'Ф': return -5;
		case 'Р': return -6;
		default: return 0;
		}
	}
};

class CBoard
{
public:
	Point BlackHorsePoint;
	CCell** cells;

	CBoard()
	{
		cells = new CCell*[8];
		for(int i = 0; i < 8; cells[i++] = new CCell('0'));
	}

	void Set(const int & x, const int & y, const char & value) 
	{
		cells[x][y].value = value;
		if(value == 'К')
		{
			BlackHorsePoint.x = x;
			BlackHorsePoint.y = y;
		}
			
	}
};

void main()
{
	Point relevantPoints[8] = { {-1, -2}, {1, -2}, {2, -1}, {2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1} };
	
	FILE* fInput;
	int r = fopen_s(&fInput, "input.txt", "r");
	CBoard board;
	for(int i = 0; i < 8; ++i)
	{
		char c[9];
		fread(c, sizeof(char), 9, fInput);
		for(int j = 0; j < 8; j++)
		{
			board.Set(i, j, c[j]);
		}
	}
	fclose(fInput);
	
	Point MaxRangFigPoint;
	int MaxRang = 0;
	for(int i = 0; i < 8; i++)
	{
		Point currentPoint = board.BlackHorsePoint + relevantPoints[i];
		if(currentPoint.x >= 0 && currentPoint.y >= 0 && currentPoint.x < 8 && currentPoint.y < 8) 
		{
			if(MaxRang < board.cells[currentPoint.x][currentPoint.y].Rang())
			{
				MaxRang = board.cells[currentPoint.x][currentPoint.y].Rang();
				MaxRangFigPoint = currentPoint;
			}
		}
	}

	if(MaxRang != 0)
	{
		board.cells[board.BlackHorsePoint.x][board.BlackHorsePoint.y] = '0';
		board.cells[MaxRangFigPoint.x][MaxRangFigPoint.y] = 'К';
	}


	FILE* fOutput;
	fopen_s(&fOutput, "output.txt", "w");
	for(int i = 0; i < 8; i++)
	{
		for(int j = 0; j < 8; j++)
			fwrite(&board.cells[i][j].value, sizeof(char), 1, fOutput);
		fwrite("\n", sizeof(char), 1, fOutput);
	}
	fclose(fOutput);
}


Delphi:
{$APPTYPE CONSOLE}

uses
  SysUtils;

type
  TPoint = record
    public
      x: Integer;
      y: Integer;
      class operator Add(a, b: TPoint): TPoint;
  end;

  TCell = class
    public
      value: Char;
      constructor Create(source: Char);
      function Rang: Integer;
  end;

  TBoard = class
    public
      BlackHorsePoint: TPoint;
      cells: array [0..7,0..7] of TCell;
      constructor Create;
      procedure SetValue(x, y: Integer; value: Char);
  end;

{ TPoint }

class operator TPoint.Add(a, b: TPoint): TPoint;
begin
  result.x := a.x + b.x;
  result.y := a.y + b.y;
end;

{ TCell }

constructor TCell.Create(source: Char);
begin
  value := source;
end;

function TCell.Rang: Integer;
begin
  case value of
		'п': result := 1;
		'к': result := 2;
		'с': result := 3;
		'л': result := 4;
		'ф': result := 5;
		'р': result := 6;
		'П': result := -1;
		'К': result := -2;
		'С': result := -3;
		'Л': result := -4;
		'Ф': result := -5;
		'Р': result := -6;
  else
    result := 0;
  end;
end;

{ TBoard }

constructor TBoard.Create;
var
  i, j: Integer;
begin
  for i := 0 to 7 do
    for j := 0 to 7 do
      cells[i,j] := TCell.Create('0');
end;

procedure TBoard.SetValue(x, y: Integer; value: Char);
begin
  cells[x,y].value := value;
  if value = 'К' then
    begin
      BlackHorsePoint.x := x;
      BlackHorsePoint.y := y;
    end;
end;

{ Main program }

const
  RelativePoints: array [0..7] of TPoint = (
    (x: -1; y: -2),
    (x:  1; y: -2),
    (x:  2; y: -1),
    (x:  2; y:  1),
    (x:  1; y:  2),
    (x: -1; y:  2),
    (x: -2; y:  1),
    (x: -2; y: -1)
  );

var
  board: TBoard;
  CurrentPoint, MaxRangFigPoint: TPoint;
  i, j, MaxRang: Integer;
  s: String;
begin
  AssignFile(input, 'input.txt');
  Reset(input);
  board := TBoard.Create;
  for i := 0 to 7 do
    begin
      ReadLn(s);
      for j := 0 to 7 do
        board.SetValue(i, j, s[j+1]);
    end;
  Close(input);

  MaxRang := 0;
  for i := 0 to 7 do
    begin
      CurrentPoint := board.BlackHorsePoint + RelativePoints[i];
  		if (CurrentPoint.x >= 0) and (CurrentPoint.y >= 0) and (CurrentPoint.x < 8) and (CurrentPoint.y < 8) then
        if MaxRang < board.cells[CurrentPoint.x, CurrentPoint.y].Rang then
          begin
            MaxRang := board.cells[CurrentPoint.x, CurrentPoint.y].Rang;
            MaxRangFigPoint := CurrentPoint;
          end;
    end;

  if MaxRang <> 0 then
    begin
      board.cells[board.BlackHorsePoint.x, board.BlackHorsePoint.y].value := '0';
      board.cells[MaxRangFigPoint.x, MaxRangFigPoint.y].value := 'К';
    end;

  AssignFile(output, 'output.txt');
  Rewrite(output);
  for i := 0 to 7 do
    begin
      for j := 0 to 7 do
        Write(board.cells[i,j].value);
      WriteLn;
    end;
  Close(output);
end.


Так что выбор того или иного языка программирования при решении задач зависит только от того, какой язык вам наиболее знаком.
+1
— моё решение:
program P_shahmat;
{$APPTYPE CONSOLE}
uses
  SysUtils;
const f='пкслфр';  // ценность фигур по возрастанию
type pn=record
  x,y,z: byte;
end;
var s: string;
    x,y,d,i,max,imax: byte;
    m: array of pn;
    ms: array[1..8] of string;
    b1,b2: boolean;
begin
  assign(input,'input.txt');   reset(input);
  assign(output,'output.txt'); rewrite(output);
  x:=0; d:=1; SetLength(m,d);
  while not eof(input) do
  begin
    inc(x); readln(input, s); ms[x]:=s;
    for y:=1 to length(s) do
    begin
      if s[y]='К' then
      begin m[0].x:=x; m[0].y:=y; end;
      if pos(s[y],f)<>0 then
      begin // если белая фигура
        inc(d); SetLength(m,d);
        m[d-1].x:=x; m[d-1].y:=y; m[d-1].z:=pos(s[y],f);
      end;
    end;
  end;

  max:=0; // текущий максимум
  for i:=1 to high(m) do with m[i] do
  begin
    b1:=(abs(x-m[0].x) = 2) and (abs(y-m[0].y) = 1);
    b2:=(abs(y-m[0].y) = 2) and (abs(x-m[0].x) = 1);
    if (b1 or b2) and (z>max) then begin imax:=i; max:=z; end;
  end;

  if max>0 then  // есть фигура под боем
  begin
    ms[m[0].x][m[0].y]:='0'; ms[m[imax].x][m[imax].y]:='К';
  end;

  for i:=1 to 8 do writeln(output,ms[i]);
  close(input); close(output);
end.
0
Здесь получается, что проверяются все белые фигуры, которые вообще имеются на доске, даже если они и не могут подпасть под бой коня. Когда этих фигур меньше 8, это еще как-то можно простить, но если их будет 63?..
0
— Замечание к решению на Delphi: именно такое решение будет работать в Delphi 2005 и выше.
— Для компиляции в более ранних версиях необходимо убрать перегрузку оператора сложения (Add) из записи и вместо этого использовать просто функцию.
  • avatar
  • belan
  • 10 апреля 2012, 18:38
+1
— писал-писал… что-то всё сбросилось… после некоторой паузы/бездействия видимо страница сама обновляется
— всё уж лень снова восстанавливать, только штрихами основные мысли:
1) спасибо за примеры красивого решения — будем учиться :)
2) для спортивного программирования важна скорость — она, конечно, зависит от «набитости руки» при использовании разных подходов — если классы писать проще с точки зрения безошибочности кода — то да… видимо оправдывает себя, но так визуально мой код компактнее — в условиях олимпиады я бы выбрал мой подход
вот сама обсуждаемая задача:
Задание 2.
Во входном текстовом файле находится шахматная позиция. Кодировка фигур и позиций: р – король, ф – ферзь, л – ладья, с – слон, к – конь, п – пешка, 0 – пустое поле. Чёрные фигуры кодируются заглавными буквами, а белые – строчными. Сделать ход чёрным конём на наиболее выгодную позицию. Выгодность определяется исходя из ценности срубаемых фигур. Ценность фигур по убыванию: р, ф, л, с, к, п. Чёрный конь в исходной позиции один. Если в пределах досягаемости коня нет фигур противника, то позицию оставить без изменений. Если найдется более чем один ход, удовлетворяющий условию задачи, то в выходной файл разместить любой из «выгодных».

Примеры:
Входной файл:
Л00Р0000
00К00000
0000л000
0П0к0000
00000000
00000000
0000пф00
000р0000
Выходной файл:
Л00Р0000
00000000
0000К000
0П0к0000
00000000
00000000
0000пф00
000р0000
Входной файл:
Л000РФ0Л
ПП00ПППП
000К0000
0л000000
00с0п000
00000000
п00п0ппп
000рф00л
Выходной файл:
Л000РФ0Л
ПП00ПППП
00000000
0К000000
00с0п000
00000000
п00п0ппп
000рф00л
+2
1) Визуально выглядит действительно короче. Но у нас выглядит побольше ввиду:
— Переменным давали осмысленные имена, они состоят более, чем из одной буквы.
— Ставили отступы и старались не писать в одной строке более одной операции
— На C++ ещё имеются строчки вспомогательного кода, такого как объявление динамического двумерного массива.
2) На деле наше решение работает в основном быстрее ввиду следующих моментов:
— Мы проверяем 8 возможных ходов чёрного коня. У Вас же проверяются все белые фигуры на возможность попадания в 8 шагов коня и это может работать намного дольше, если всё поле будет усеяно белыми фигурами.
— Судя по Вашему коду, возможен неоднокрытный вызов «SetLength(m,d);». Не знаю, насколько быстро работает выделение свободной памяти, но кажется, что это не самая быстрая операция.
3) В условиях олимпиады мы не придерживаемся какой-либо парадигмы программирования. Эту задачу мы решили с использованием ООП, потому что при правильной организации классов трудно допустить логическую ошибку в программировании. Задача не такая сложная с точки зрения логики, но достаточная для того, чтобы реализованная логика с первого раза не заработала. Взвесив все за и против, мы сделали вывод, что мы меньше времени потратим на написание классов, чем на поиск ошибок в реализованной логике. И, честно сказать, с выбором не ошиблись, поскольку на отлаживание мы нисколько не потратили (про ввод/вывод из/в файл речи не веду, потому что это к алгоритмистике уже не относится).
0
— Мы проверяем 8 возможных ходов чёрного коня. У Вас же проверяются все белые фигуры на возможность попадания в 8 шагов коня и это может работать намного дольше, если всё поле будет усеяно белыми фигурами.
— Судя по Вашему коду, возможен неоднокрытный вызов «SetLength(m,d);». Не знаю, насколько быстро работает выделение свободной памяти, но кажется, что это не самая быстрая операция.
— согласен, писал программу в лоб и не занимался оптимизацией, просто нет свободного времени — прямо сейчас параллельно решаю задачки школьные с дочкой, готовлюсь к завтрашним занятиям и тут :) ещё параллельно видео идет про тактику китайских игроков в настольном теннисе :) готовлюсь к соревнованиям :)
0
— Хмм… да нет, вроде ничего не должно само обновляться. Для подгрузки новых комментариев есть специальная кнопочка справа, но она делает это без перезагрузки страницы.
— Предлагаю для каждой встречи (месяца/группы заданий) создавать отдельный топик, в котором будут сами задания, а обсуждать их решения уже будем в комментариях. Как считаете?
0
Почему текущий вариант не устраивает?
0
Если продолжать здесь — скоро будет слишком много информации на одной странице. Будет трудно ориентироваться в старых комментариях даже тем, кто участвует с самого начала, а уж новичкам разобраться будет вообще нереально. Уже сейчас нужно постараться, чтобы найти условие новой задачи.
+1
Да, так было бы лучше. Здесь комментариев уже многовато. Разбираться что где не всегда удобно.
+3
— кстати было бы неплохо посмотреть и на код команды «223» — поработаем над ошибками и поищем кто-же там кушает фигруры кроме «коня»
— а Насте с Юлей из «441» — было бы неплохо довести до завершения программу «про коня» и обнародовать свой вариант — мы обсудим — ладно?
0
— По поводу кода команды «223»: нам с Денисом тоже очень хотелось посмотреть на их код, но спрашивал у Владимира — у него код не сохранился (есть ли у кого-то еще — не знаю). Если даже не осталось — может попробовать восстановить?
— Кстати, про пропадающие буквы — чисто теоретически задача не решена (Contester бы посчитал именно так), так что нужно привыкать доводить решение задачи до логического завершения.
+1
К сожалению компьютер наотрез отказался воспринимать мою флешку, поэтому той программы больше нет. Но я попытался её воссоздать по памяти. Специально не стал ничего оптимизировать, чтобы воссоздать максимально приближено к тому варианту. Ошибка с пропадающими символами реализована в том же виде.
Скрытый текст (нажмите сюда чтобы открыть!)
{$APPTYPE CONSOLE}
uses
  SysUtils;
var
  i,j,ki,kj,t,ti,tj: integer;
  f,k: array[1..8,1..8] of char;
begin
  assign(input,'input.txt');
  assign(output,'output.txt');
  for i:=1 to 8 do
  begin
    for j:=1 to 8 do
    begin
      read(f[i,j]);
      if f[i,j]='К' then begin ki:=i; kj:=j; end;
    end;
    readln;
  end;
 k[ki-2,kj+1]:=f[ki-2,kj+1];
 k[ki-1,kj+2]:=f[ki-1,kj+2];
 k[ki+1,kj+2]:=f[ki+1,kj+2];
 k[ki+2,kj+1]:=f[ki+2,kj+1];
 k[ki+2,kj-1]:=f[ki+2,kj-1];
 k[ki+1,kj-2]:=f[ki+1,kj-2];
 k[ki-1,kj-2]:=f[ki-1,kj-2];
 k[ki-2,kj-1]:=f[ki-2,kj-1];
 for i:=1 to 8 do
  begin
    for j:=1 to 8 do
      case k[i,j] of
      'р': begin t:=7; ti:=i; tj:=j; end;
      'ф': if t<6 then begin t:=6; ti:=i; tj:=j; end;
      'л': if t<5 then begin t:=5; ti:=i; tj:=j; end;
      'с': if t<4 then begin t:=4; ti:=i; tj:=j; end;
      'к': if t<3 then begin t:=3; ti:=i; tj:=j; end;
      'п': if t<2 then begin t:=2; ti:=i; tj:=j; end;
      '0': if t<1 then begin t:=1; ti:=i; tj:=j; end;
      end;
  end;
  f[ki,kj]:='0';
  f[ti,tj]:='К';
 for i:=1 to 8 do
  begin
    for j:=1 to 8 do
      write(f[i,j]);
    writeln;
  end;
  close(input);
  close(output);
end.
0
Попробуй в качестве входного файла:

Л000РФ0р
ПП00ПППП
00000000
Кл000000
00с0п000
00000000
п00п0ппп
000рф00л

Возможности Коня просто не ограничены… =D
0
Еще как вариант чудес:
00000000
00000000
00000000
00000000
0000К000
00000000
00000000
00000000
0
В дополнение, объяви массивы наоборот (не «f,k», а «k,f») и увидишь чудо… ;)
+1
Очередное мое извращенное решение, но без классов… Алгоритм не отличается, конечно, но не мог просто так пройти мимо… =D

{$APPTYPE CONSOLE}

uses
  SysUtils,
  Classes;

const
  RelativePoints: array [0..7] of Integer = (-21, -19, -12, -8, 8, 12, 19, 21);
  Figures = 'пкслфр';

var
  input, output: TFileStream;
  i: integer;
  buf: array [0..77] of AnsiChar;
  HorsePoint, MaxRang, MaxRangPoint: Integer;
begin
  input := TFileStream.Create('input.txt', fmOpenRead);
  input.Seek(0, soFromBeginning);
  input.Read(buf, SizeOf(buf));
  input.Free;

  HorsePoint := Pos('К', buf) - 1;
  MaxRang := 0;
  for i := 0 to 7 do
    begin
      if HorsePoint + RelativePoints[i] < 0 then Continue;
      if MaxRang < Pos(buf[HorsePoint + RelativePoints[i]], Figures) then
        begin
          MaxRangPoint := HorsePoint + RelativePoints[i];
          MaxRang := Pos(buf[HorsePoint + RelativePoints[i]], Figures);
          if MaxRang = Length(Figures) then Break;
        end;
    end;

  if MaxRang > 0 then
    begin
      buf[HorsePoint] := '0';
      buf[MaxRangPoint] := 'К';
    end;

  output := TFileStream.Create('output.txt', fmCreate);
  output.Write(buf, SizeOf(buf));
  output.Free;
end.
+2
Оформил большую часть опубликованных здесь задач в сборник в системе Contester: http://contester.dyndns.org/ru/volume-vid-1389-sh-1?ps=29&smt=5.
Обсудить задачи также можно и там. Чекеры и тесты формировал сам, так что возможны некоторые глюки. Если вдруг ваше решение не проходит — пишите, посмотрим, что не так.
+1
— круто!
0
— но кодировка там какой страницы? для тестов задачи про коня используются файлы с какой кодировкой?
0
Все стандартно (ANSI). Ваша проблема в другом. Выдержка из правил оформления кода на Pascal'е:
Входные данные допускается читать как с консоли, так и из файла input.txt, выходные данные необходимо выводить в консоль.
У вас данные выводятся в файл. Ответы на некоторые вопросы тут: http://contester.dyndns.org/ru/help.
PS: Ваше решение я проверял, должно работать, после изменения вывода.
0
Также в разделе помощи описаны практически все причины для возникновения тех или иных ошибок, для Presentation Error это:
• Решение вывело данные не в требуемом формате, не вывело данные целиком или вывело лишние данные.
• Файл не сохранён в среде разработки или на проверку отправлен ошибочный файл.
• Решение содержит неинициализированные переменные.
• Используется значение итерационной переменной после цикла for.
Решение выводит данные в файл output.txt (должно в консоль).
• Если решение на Delphi, возможно отсутствует строка uses SysUtils;.


Рядом с формой отправки кода для каждой задачи имеются ссылки:
Как оформлять код? и Что означают результаты проверки решений?.
+1
— одолел, спасибо!
0
Подкорректировал некоторые чеккеры. Но учитывая, как часто кто-то решает задачи, они могут и не понадобиться… :(
0
Кстати, остается не так уж много времени — нужно собираться, нужно готовиться.
Думаю, стоит собраться, например, в следующий понедельник 23.04 в то же время. Кто за?
0
— я согласен на 23-е число :)
0
Предлагаю в следующий понедельник провести своего рода «турнир», чтобы смоделировать реальные условия олимпиады. Будет дано определенное время на решение и, к примеру, 5 задач, которые можно будет решать в любом порядке — кому какая задача нравится, тот с той и начинает.
+1
— 1-й и 3-й курс я оповестил — все будут
— осталось собрать 2-й и 4-й
0
2-й курс тоже оповещен :)
0
Юле и Насте также сообщил. Должны будут подойти. Денис пока что думает, но попытаюсь все же и его вытащить.
  • avatar
  • Foxy
  • 18 апреля 2012, 18:57
0
У меня в самой элементарнейшей задаче выходит ошибка Runtime Error. Кто-нибудь может пояснить в каких случаях она вылетает? Смешно, конечно, но текст вот (говорила, что задача элементарная :) ):
{$APPTYPE CONSOLE}

uses
SysUtils;

var A: longint;
begin
ReadLn(A);
if (A mod 10 = 1) then WriteLn('YES')
else WriteLn('NO');
ReadLn;
end.
  • avatar
  • Foxy
  • 18 апреля 2012, 19:22
0
Косяк найден, нужен был тип longword
0
— странно, но мне не кажется, что ошибка вызвана типом данных — у меня эта программа работает со всеми целочисленными типами данных как беззнаковыми так и со знаковыми…
— может ещё раз проверите?
0
http://contester.dyndns.org/ru/problem-pid-c351?ps=29&smt=7&smpwid=0
В условии я указал, что 0 <= A <= 4294967295 и в одном из тестов на входе верхняя граница.
Это сделано специально, чтобы чуть усложнить задачу и заставить подумать о стандартных типах.
  • avatar
  • belan
  • 18 апреля 2012, 20:03
0
— ну вы блин даёте — это я к фокси — вы уж пишите, что решение в контстере проверяете, а не просто запускаете у себя в среде программирования и пишите условие задачи полностью (я про указанный в условии задачи диапазон целых чисел)
  • avatar
  • Foxy
  • 18 апреля 2012, 20:56
0
Ну мне показалось, что это будет понятным (что запускаю в контестере) :) Хотя бы до одного человека дошло.
0
Я просто мониторю контестер периодически.
  • avatar
  • Foxy
  • 18 апреля 2012, 21:05
0
Печаль…
+1
В решениях задач часто используются циклы. И многие задачи содержат в своем условии то, что на входе может предельное значение какого-либо из стандартных типов. В связи с этим задаю пару простых вопросов, ответы на которые должен знать каждый! Точнее даже вопрос один, но примера два. Вопрос: сколько раз выполнится цикл в каждом из примеров?

1.
for i := -MaxInt-1 to MaxInt+1 do
  WriteLn(i);


2.
i := 0;
while i <= MaxInt do
  begin
    WriteLn(i);
    inc(i);
  end;

Примечание: MaxInt — это максимальное значение для типа Integer, которое равно 2 147 483 647. Переменная i типа Integer.
+1
Предполагается, что отвечать будете сами, а не запустив этот код. И хотелось бы увидеть объяснение вашего ответа.
  • avatar
  • Foxy
  • 19 апреля 2012, 23:28
0
1. не будет выполняться, потому что i выйдет за границы типа.
2. Выполнится maxint раз и вылетит с той же ошибкой, что и в первом случае.
А вообще :) Может и бред, но после прочтения Сашкиной статьи про память, рискну предположить, что в дельфе и без ошибок может обойтись.
0
Действительно, ошибок не будет. Но, что интересно, не только в Delphi… :)
0
— предположу, что в цикле «пока» (это второй пример) повторений будет MaxInt+1 (от 0 до MaxInt) и слом произойдет только на процедуре inc(i) при попытке добавить к MaxInt единицу, а вот в цикле «для» не будет повторений, так как ДЛЯ переменной i (типа интеджер) нельзя организовать такой перебор (то есть до значения MaxInt+1), насколько я понимаю от -MaxInt-1 до MaxInt — можно
0
Не уверен конечно, но предположу, что:
1. Ошибка из-за переполнения переменной i
2. MaxInt раз выполнится, потом опять переполнение :)
0
Так уж получилось, что верного ответа не дал никто.
Можете проверить код и, если хотите, объяснить поведение.
0
— а я всё же повторю свой ответ:
"— предположу, что в цикле «пока» (это второй пример) повторений будет MaxInt+1 (от 0 до MaxInt) и слом произойдет только на процедуре inc(i) при попытке добавить к MaxInt единицу, а вот в цикле «для» не будет повторений, так как ДЛЯ переменной i (типа интеджер) нельзя организовать такой перебор (то есть до значения MaxInt+1), насколько я понимаю от -MaxInt-1 до MaxInt — можно"
— испытал только что на FreePascal — но с ситуацией встречался многократно ранее не раз в разных языках и разных трансляторах — по поводу цикла «пока» и «для»
— ваш ответ тоже правильный (видимо в ABCPascal, в Delphi — сейчас не испытывал), предполагаю для той среды программирования где по умолчанию включена какая-то директива комплилятора (типа: отключить контроль диапазона) — моё объяснение: суть ситуации сводится к тому что при использовании знакового типа данных прибавление 1 к самому большому числу (буду рассматривать для краткости 4-х битное) 7, которое в двоичной системе 0111, получаем 1000 в двоичной, что является в десятичной самым маленьким числом, то есть это не «8», а "-8" — последовательное прибавление далее приведет когда-то к числу 1111 в двоичной, что является -1 в десятичной, следующее прибавление 1 смещает все переносы за пределы разрядной сетки и получается просто 0
— сейчас еще испытал на TP7.0 — там цикл for тоже не запускается, а вот как раз while работает без останова, то есть прибавление к самому максимальному значению 1 дает самое минимальное
— видимо всё же в разных средах по разному, как считаете?
0
вот заглянул в сеть это для Delphi какой-то ранней версии:
5) Директивы компилятора, включающие и выключающие проверку переполнения при целочисленных операциях — по умолчанию {$Q-} или {$OVERFLOWCHECKS OFF}
Директивы компилятора $Q включают или выключают проверку переполнения при целочисленных операциях. Под переполнением понимается получение результата, который не может сохраняться в регистре компьютера. При включенной директиве {$Q+} проверяется переполнение при целочисленных операциях +, -, *, Abs, Sqr, Succ, Pred, Inc и Dec. После каждой из этих операций размещается код, осуществляющий соответствующую проверку. Если обнаружено переполнение, то генерируется исключение EIntOverflow. Если это исключение не может быть обработано, выполнение программы завершается.
Директивы $Q проверяют только результат арифметических операций. Обычно они используются совместно с директивами {$R}, проверяющими диапазон значений при присваивании. Директива {$Q+} замедляет выполнение программы и увеличивает ее размер. Поэтому обычно она используется только во время отладки программы. Однако, надо отдавать себе отчет, что отключение этой директивы приведет к появлению ошибочных результатов расчета в случаях, если переполнение действительно произойдет во время выполнении программы. Причем сообщений о подобных ошибках не будет.
0
— ну еще может у всех по разному в настройках среды выставлены директивы комплилятора :) — не уверен, что у меня выставлено так как должно быть по умолчанию — думаю, что работа программы должна зависеть от контекстных условий
0
Да, я нехороший человек, не указал, под что был написан код и в каких условиях.
К сожалению у меня нет TP7, чтобы проверить работу в нем. Проверял на Delphi 2010, XE, XE2 и С++.
В любом случае все начали говорить о том, что возникнут ошибки переполнения, но никто не вспомнил о том, что они могут и не возникать. Большое спасибо за развернутый ответ. Меня больше всего интересовал именно второй цикл.
0
Можно сказать, в чем то были правы все… :)
Все же стоит не забывать, что иногда типы «бегают по кругу»…
0
— да я предлагаю на основе такого ньюанса «замутить» какую-нибудь интересную задачу по программированию — сходу пока не могу придумать — кто что-то изобретет — не поленитесь, пож., поделиться с нами — а мы дружно порешаем эту задачку :)
0
— ну нет, как раз у imtec`а и была задача, которую мы все лишь частично одолели
— может просто можно придумать оригинальный способ использования «бегания по кругу» — какой-нибудь бесконечный цикл — типа: организованный постоянный последовательный (вместо псевдослучайного) перебор вариантов в условиях когда исследуемое поле вариантов перманентно меняется, или что-то с «масками» на основе побитного представления этого числа…
  • avatar
  • belan
  • 22 апреля 2012, 20:29
0
— на завтра всё в силе, после 17.00 в 602 ауд., интернет будет :)
0
Отлично. Задачи уже подготовлены. Осталось оформить их в турнир, чем сейчас и займусь.
0
Все готово. Теперь самое главное, чтобы люди подошли.
  • avatar
  • belan
  • 23 апреля 2012, 22:55
+3
— спасибо всем за участие
— спасибо Александру за потраченное время и проделанную работу
— я тоже прорешаю задачи как будет свободное время, постараюсь не откладывать, прямо сейчас сходу «Магнитные бури» — с первой попытки прошло проверку, потрачено менее 20 минут
— постараюсь сделать задачу «Охота на зайцев» — так как мне кажется у меня будет немного оригинальный алгоритм, придумал его прямо на встрече
— всё идет к тому, что у нас останутся две команды
— сегодня некоторые удивляли! кстати, на мой взгляд, у команды «Ольга-Володя», если бы можно было бы все другие параметры считать равными, проклевывался более оптимальный подход (в частности Ольга это доказала) — один сидит пишет код за компьютером, а другой в это время кодит другую программу на бумаге, потом меняются — моё мнение субъективно
— полагаю, что если бы я участвовал, то я бы вчитывался в задачу, придумывал алгоритм, кодил, если проходит сразу, то УРА и уступаешь место другому… если не проходит, но есть ощущение, что ошибку можно найти и исправить, то сделал бы 1-2 попытки исправить, потом бы подключал партнера по команде… если бы становилось понятно, что проблема слишком отнимает время — то отложил бы и передал бы компьютер следующему участнику — при наличии трех игроков вполне может даже получиться плавная зацикленная смена позиций :)
  • avatar
  • belan
  • 02 мая 2012, 22:57
+2
— сегодня был в политехе на орг.собрании по олимпиаде
— некоторые штрихи скажу при личной встрече…
— а так есть только примерная информация (представитель организаторов пока сам ещё толком не знает ньансов — поточнее пришлет инфу потом мне на почту):
1) будет ~10 задач, решение каждой задачи оценивается в один балл (все задачи ценятся одинаково, ЗНАЧИТ НУЖНО СРАЗУ ВЫДЕЛЯТЬ ТЕ, КОТОРЫЕ МОЖЕТЕ РЕШИТЬ БЫСТРЕЕ!), за каждую неудачную попытку штраф 20 мин., при одинаковом количестве решенных задач между командами лучшей признается та, которая раньше сдала задачи (учитывая и штрфы)
2) можно от одной команды программы посылать на проверку сделанные в разных средах — для Паскалевиков будет ТурбоДелфи (проверяющий компилятор ФриПаскаль)
3) место проведения: Факультет ЭлектроТехнический ПНИПУ / корпус А / 229 аудитория
4) время проведения: 26 мая (суббота), в 09.30 открытие, с 10.00 до 13.00 — соревнование, с 13.00 до 15.30 — работа оргкомитета (туда входят все преподаватели, то есть и я)
5) мне нужно от вас: собрать про всех информацию — ФИО / группа / курс / специальность / номер сотика — это я за неделю до соревнований должен предоставить организаторам — ПРИСЫЛАЙТЕ МНЕ НА ПОЧТУ tt@59.ru
0
Интересно, в этот раз какие-то новые правила выдумали. Раньше и штрафов в 20 минут не было, и задачи в разное количество баллов оценивались…
0
Все было точно так же. Штрафы за каждую неудачную попытку были. Задачи одинаковые по оценке.
0
— получил по почте регламент соревнований, организаторы совсем обленились — мне прислали просто 4 фотографии с распечатанных листочков — предполагаю, что листочки с прошлых лет — я приложил усилия и установил ФайнРидер и перевел в текст (могут быть небольшие оЧеПятки):
Регламент соревнований:
В Олимпиаде могут участвовать студенты вузов любых специальностей и форм обучения вузов. Состав команды — 1-3 человека. Количество команд от каждого вуза, порядок подготовки заданий олимпиады и правила подведения итогов в командном зачете принимаются на первом заседании жюри.
Олимпиадное соревнование проводится по схеме Международного студенческого чемпионата мира по программированию (ACM ICPC).
Каждая команда получает в свое распоряжение один IBM PC совместимый компьютер, работающий под управлением операционной системы Windows ХР. Для составления исходных текстов решений и их отладки участникам предоставляются следующие среды программирования: Microsoft Visual Studio 2008 — для языка С++, Borland Developer Studio 2006 — для языка Pascal.
Соревнование длится 3 астрономических часа. Жюри имеет право продлить тур в случае непредвиденных обстоятельств: отключение электричества или сбой в работе сервера. Во время соревнования командам предлагается для решения от 6 до 10 задач на русском языке. Жюри принимает решения на языках программирования С++, Pascal. Отправка решений осуществляется во время соревнования с помощью программного обеспечения соревнования. Через 1-2 секунды (максимум — 1 мин.) после отправки команде становится доступен результат проверки. После окончания соревнования решения не принимаются.
Запрещается использование любых справочных материалов, кроме установленных на предоставленном компьютере, любых вычислительных устройств или средств передачи информации: портативных компьютеров, калькуляторов, съемных носителей, мобильных телефонов и других коммуникационных устройств.
Команды могут быть дисквалифицированы за несоблюдение данных правил, а также за совершение действий, которые могут нарушить работу программного обеспечения соревнования.
Решением задачи является программа (файл с исходным текстом), написанная на одном из разрешенных языков программирования. Команда может решать разные задачи на различных языках программирования. Размер исходного текста одной программы с решением не может превышать 64 кБ.
Входные данные подаются программе в файле input.txt, расположенном в текущем каталоге. Программа должна выводить ответ в файл output.txt, который должен быть сохранен также в текущем каталоге.
В решениях задач запрещается:
— работа с любыми файлами, за исключением файлов input.txt и output.txt;
— выполнение внешних программ и создание новых процессов;
— ввод с клавиатуры и вывод на экран;
— работа с GUI-элементами (окнами, диалогами и т.д.);
— работа с внешними устройствами (принтером, звуковой картой и т.д.);
— использование сетевых средств.
Решение проверяется путем последовательного запуска на наборе тестов, который недоступен участникам и является одинаковым для всех команд. Решение засчитывается в том случае, если оно выдает верные ответы на все тесты. Тестирование производится автоматически, поэтому программы должны в точности соблюдать форматы входных и выходных файлов, описанные в условии каждой задачи. Все входные данные предполагаются корректными и удовлетворяющими всем ограничениям, указанным в условии задачи. Набор тестов не предоставляется участникам даже после окончания соревнования. Для каждой задачи определены максимальное время выполнения и объем доступной памяти для одного теста. Если на одном из тестов программа превысила это время или выделила больше памяти, решение считается неверным.
После проверки команде сообщается о том, зачтено решение или нет. Если решение не зачтено, сообщается информация о первой случившейся ошибке: тип ошибки и номер теста, на котором она произошла. В этом случае решение не проверяется на последующих тестах. Сообщение от проверяющей системы может быть одним из следующих:
___сообщение_____номер теста_____когда возникает_____возможная причина
1) Accepted_____не сообщается_____решение зачтено_____программа работает верно
2) Compilation error_____не сообщается_____компиляция программы завершилась с ошибкой_____в программе допущена синтаксическая ошибка; неправильно указан язык; размер исходного файла превышает 64КБ
3) Wrong answer_____сообщается_____ответ программы неверен_____ошибка в программе; неверный алгоритм
4) Runtime error_____сообщается_____программа аварийно завершила работу_____деление на ноль; бесконечная рекурсия; Массивы имеют недостаточный размер; программа завершилась с ненулевым кодом возврата
5) Time limit exceeded_____сообщается_____программа не закончила работу за установленное время_____ошибка в программе; программа ожидает ввода с клавиатуры; неэффективное решение
6) Memory limit exceeded_____сообщается_____программа превысила установленный предел памяти_____ошибка в программе; утечка памяти; неэффективное решение
При возникновении ошибки Compilation error программа не запускается ни на одном тесте. При возникновении ошибок Runtime error, Memory limit exceeded. Time limit exceeded, Presentation error вывод программы не проверяется.
Первыми тестами в наборе тестов всегда являются тесты из условия задачи. Тесты идут в том же порядке, в котором они приведены в условии задачи. Тесты нумеруются, начиная с единицы.
Команды ранжируются по числу решенных (т.е. зачтенных) задач. Команды, решившие одинаковое число задач, ранжируются по суммарному времени решения. Суммарное время решения определяется как сумма времени решения каждой зачтенной задачи. Время решения задачи определяется как время от начала тура до момента посылки решения, признанного правильным, плюс 20 штрафных минут за каждое решение, признанное неправильным. Задачи, не признанные решенными к моменту окончания тура, никакого вклада в суммарное время не дают (в том числе, и в виде штрафов за неправильные решения).
=========================
— у нас часть игроков с 10 по 15 мая уезжают из города…
— таким образом остаются дни с 16 по 25 — я полагаю, что есть смысл ещё разок встретиться и окончательно определиться с составом команд… вроде бы есть команда ВОВ = Вадим-Ольга-Володя :), а вот с командой постарше совсем не ясно… вы выскажете своё мнение, может быть это будет старый и испытанный вариант Александр-Настя-Юля?
0
Встретиться нужно обязательно. Насчет старого варианта — крайне маловероятно, что он возможен. Смогу ли я вообще — неизвестно, Юля скорее всего не сможет из-за работы, ну а Настя одна никуда. Здесь скорее стоит думать над двумя возможными вариантами: либо сделать одну команду (Владимир, Вадим, Ольга), либо две (объединив Вадима с Настей и оставить Владимира с Ольгой).
+1
— одну команду не хотелось бы оставлять, если все согласятся, то пусть лучше будут две: Владимир-Ольга и Вадим-Настя
0
Меня такой вариант устраивает. Главное, чтобы и остальных тоже…
  • avatar
  • belan
  • 21 мая 2012, 09:41
0
— уже не помню, что и когда постил, есть ощущение, что, в связи с переносами форума последние посты потерялись
— сегодня 21-го мая встречаемся в 602-й аудитории
0
— сегодня кворума не было, поэтому командного решения задач не проводили :(
— я предложил к решению свою задачу — порешали — если есть желание, то опубликуйте своё решение…
— была найдена неточность формулировки исходного условия
— организационные моменты — так как многих не было, то тут пишу примерно:
1) в субботу начало состоится по адресу Профессора Поздеева, 7 — это Электротехнический факультет — аудитория 229 — откытие олимпиады в 09.30
2) я могу по пути (еду с Садового) с собой забрать 4-х человек — Александр, Настя (у Цирка, в 08.50), Володя (у Галереи, 09.05) и ещё одного (смотрите кому удобно — Вадим/Оля — сообщите мне где удобно)
3) с собой возьмите карандаш, ручку, бумагу, воду
4) делиться на команды будем уже в машине :)
5) обязательно сразу после получения задач разделитесь и читайте задания по отдельности — ищите те задачи, которые можете самостоятельно сделать, из них выбирайте те, которые предположительно можете сделать быстро — когда решились, то один сразу садится за клавиатуру и кодит, второй пишет на бумажке — дома повторите как организуется ввод и вывод (не все активно пользовались формализованной проверкой программ и могут быть ляпы — настаиваю, что для тех кто сделал менее 10 задач на контестере нужно до олимпиады хотя бы парочку простых провести через контестер)
6) напомню №1, что задач будет не более 10 — в 2008 году их было восемь — время на решение задач 3 часа — и лучше решить и сдать 5 задач с 20-ю неудачными попытками, чем решить 4, но с 0 неудачных попыток, однако не стоит злоупотреблять и просто так тыкаться — к исправлению ошибок старайтись подходить адекватно: __1) если долго не получается, то может быть имеет смысл провести следующую задачу — это удобно, когда в команде 2-3 человека ведущие свои разные задачи, а не когда все решают одну и __2) все же при равном количестве решенных задач победит та команда у, которой меньше штрафного времени (время от начала соревнований до сдачи решения + 20 минут * количество попыток)
7) напомню №2 — не самая сильная, но организованная команда Словакии (хоккей, ЧМ-2012) выбила многих, включая и Канаду!!! и заняла второе место
+1
— завтра едем
-1) Вадим (3 курс) появился — едет — не последней тренировке не был, но возможно по причине того, что наш форум как раз не работал некоторое время и Вадим не понял, что встреча будет, а по сотику он был недоступен…
-2) Ольга (2 курс) — ???
-3) Александр (4 курс) — всегда был, завтра быть собирается, но есть некоторая вероятность, что он не сможет…
-4) Володя (2 курс) — всегда был, всю информацию знает, едет точно
-5) Настя (4 курс) — завтра будет
— итого, в идеале 5 человек
— декан, настаивает чтобы были использованы все места, то есть чтобы было 6 человек…
— я же в свою очередь сам заинтересован, чтобы была преемственность поколений — но очень мало на 1-м курсе претендентов…
— да и на эти соревнования не было уверенности сколько же человек точно едут — получалось, что едут от 3 до 5… — поэтому я был в поиске…
— еще раз говорил с Ереминым — он, конечно, оказался в такой ситуации, что уже обещал давно-давно участвовать в иностранном языке и только потом столкнулся со мной — поэтому уже отказаться не смог — но со следующего семестра будет с нами — он за этот семестр очень сильно вырос — очень много интересного делает сам — жаль, что пропускает этот раз :(
— однако удалось мне обнаружить ещё одного претендента — Кривощеков Сергей (1 курс) — он на хорошем уровне пишет несложные программы и может на ходу импровизировать, у него пока нет опыта решения хитрых или трудоемких задач, но способности точно есть — жаль, что сразу к нам не попал — у меня просьба к участникам: я включил его в список, если всё получиться, то он завтра будет с нами — я не хочу кого-то ущемлять, постарайтесь принять нового участника в команду без каких-то психологических для себя неудобств — вклад каждого отдельного участника в успех команды, конечно, разный и мы все более менее понимаем кто на что способен…
— сегодня к вечеру нужно бы определиться кто же едет со мной, а кто добирается своим ходом — пока могу сказать, что точно со мной едут Настя (от цирка) и Володя (от Галереи) — то есть ещё два места есть…
0
— места в машине уже исчерпались — сами добираются Вадим и Сергей (если будут) — мою аську все знают, но на связь видимо нет времени выйти…
0
— где то у меня произошел сбой — не Кривощеков Сергей, а Киприянов Вадим — сорри — в голове Очепятки — то есть два Вадима добираются автобусом :)
  • avatar
  • belan
  • 26 февраля 2013, 22:58
+1
не за горами конец учебного года
кто-то должен будет выступить на Олимпиаде по программирования
я очень надеюсь на самостоятельный рост всех кто участвовал ранее
попрошу, конечно, всех поучаствовать, но, естественно, всё это по желанию
чтобы как-то стимулировать вас предлагаю на время решить несложную задачку — из серии «моя дочка ходит в 3-й класс и там им такОЕ задают...»
вот устовие:
«В семи кружках расставлены числа от 1 до 7 так, что сумма четырёх чисел, расположенных в вершинах каждого четырёхугольника, составляет 13. Расставь эти же числа так, чтобы сумма четырёх чисел в вершине каждого четырёхугольника была равна 14, 15, 16, 17.»
вот картинка:
от меня: ну то есть это четыре разных независимых решения…
решайте на время… нужно ведь в условиях ограничений тренироваться…
я затратил около 12-ти минут… ну решение состряпалось «налету» — неоптимальное… ответы все нужные выдало… за то же время моя дочка успела выдать 2 из 4 решений :)
при таком писании допустил одну значимую ошибку, но быстро её обнаружил и исправил, думаю на исправление ушло менее минуты…
я думаю можно пока не выкладывать сюда решения… просто каждый для себя потренируется… просто отпишите, что вы живы и тренируетесь :)
0
Мы живы и тренируемся :) Почти написали решение. Единственное, что осталось — как-то отсеять лишние варианты и определиться с форматом вывода. Лично мне задачка показалась сложной — на бумаге вроде легко, а вот написать алгоритм…
  • avatar
  • belan
  • 28 февраля 2013, 14:48
0
— я очень рад, что есть на кого опереться :)
— по задаче: ну я то сильно не заморачивался и выводил просто в строчку первое найденное решение, например, для картинки в условии задачи так — 6214735
— лишних вариантов нет и вывод очень простой
— а по поиску решений я пошёл на хитрость и крайнее упрощение логики поиска в ущерб показателю скорости… ну для данной задачи это было не критично… именно отсутсвие какой-то сложности в алгоритме позволило мне написать всё сразу без остановки, правда с одной существенной ошибкой…
— входной файл, ну тут понятно, просто в столбик условия 4-х задач
14
15
16
17
— выходной файл — четыре соответсвующие строчки циферок решения…
  • avatar
  • belan
  • 28 февраля 2013, 14:52
0
— да, я не делал последовательный перебор…
— просто подобный безхитростный подход (я пока не признался какой, но может кто-то и так догадался :) ) за свою жизнь применял уже не раз… вот и вышло всё сразу…
  • avatar
  • belan
  • 10 мая 2013, 15:51
+1
— Олимпиада по программированию состоится 25-го мая
— место/время: комплекс ПНИПУ, Электротехнический факультет, корпус «А», 229 ауд., начало в 09.30 — думаю реально само решение будет с 10.00 до 13.00
— предлагаю в следующие 2 недели 1-2 раза встретиться… сам я сильно загружен… возможные мои дни:
1) пт 17 мая с 12.00 и до…
2) пн 20 мая с 17.00 и до…
3) ср 22 мая с 17.00 и до…
4) пт 24 мая с 13.30 и до…
— я подготовил чуточку интересных, сравнительно несложных заданий — просто для отработки совместных действий…
— напомним себе как правильно подавать готовые решения в контестер, чтобы он их принял как верные
— сообщите мне кто и когда сможет — у нас быть может даже две команды пойдут, я точно не знаю… пока точно знаю про троих: Настя, Володя и Еремин… быть может ещё Сорха Вадим и может Еремин решится выступить отдельной командой с Киприяновым…
— свяжитесь по возможности друг с другом, так как я не всех смогу достать
— если не получится сразу всем вместе встретиться, то хотя бы предполагаемыми командами — например Настя+Володя (или Настя+Володя+Вадим) могут прийти в один день, Еремин+Киприянов в другой… в идеале бы лучше встретиться вместе
— ну и мне нужно знать когда на работе задерживаться и когда нужно ноутбук достать — у нас на компьютерах в классах контестер не хочет нормально работать, поэтому будем запускать не с общественных компьютеров, если у кого есть возможность с собой принести комп — несите — контестер можете сами поставить (или я вам дам), а задачи нужные поставлю прямо в день встречи…
— на Олимпиаду по желанию можно будет поехать со мной в авто — 4 посадочных места есть (туда и обратно)…

Прокомментировать