Отправляет email-рассылки с помощью сервиса Sendsay

Информат - алгоритмическое и математическое мышление

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "физика YES" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Апрель 2003   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Автор
ss77_ss77@mail.ru

Статистика

1.523 подписчиков
+1 за неделю
←   Все выпуски   →

Конкурсы и Олимпиады по Машинному программированию (КОМП)


Информационный Канал Subscribe.Ru

Весенняя олимпиада школьников 2003 года.
Разбор второго тура.

Автор задачи профессор А. П. Бельтюков предлагает разбор в виде прокомментированной программы. 

/* А. П. Бельтюков *\

Game-3 Программа жюри (образец решения) для задачи "3 кучки"
олимпиады школьников по программированию (КОМП-2003-весна)

file://belt.uni.udm.ru/alt/AP/edu/oly/mark/sc_3/t_31l_at.c.c
version:31m-4f-h-i

Комментарий

Эта программа выигрывает из всех позиций, в которых в принципе
можно выиграть даже при наилучшей игре противника.
Ход вычисляется. Никаких предвычисленных таблиц в программе нет.
Основная задача, решаемая программой - сделать так, чтобы
        МАКСИМАЛЬНАЯ СТЕПЕНЬ ЧИСЛА 2, НА КОТОРУЮ ДЕЛЯТСЯ
        ЧИСЛА МНОЖИТЕЛЕЙ В РАЗЛОЖЕНИЯХ РАЗМЕРОВ КУЧ НА ПРОСТЫЕ
        ДЕЛИТЕЛИ БЫЛА БЫ ОДНА И ТА ЖЕ
(можно доказать, что все такие позиции в принципе проигрышны,
например: 31 27 32 (1, 3 и 5 множителей, степень 0),
          10201 1000 1024 (2, 6 и 10 множителей, степень 1),
          1210 4096 10240 (4, 12 и 12 множителей, степень 2),
          256 10000 25000 (8, 8 и 8 множителей, степень 3) -
в принципе проигрышные позиции).

Если позиция проигрышна, то программа просто делает некоторый ход,
"не слишком упрощающий позицию", если это возможно
("упрощением" позиции считается уменьшение числа ходов,
которые можно из нее сделать).

Как показало соревнование, подобная программа может при определенном
составе программ-участников претендовать на призовое место.

Эта программа показала точно такие же результаты, как и программа
участника номер 14, хотя эти программы делали разные ходы в
одних и тех же ситуациях.

Программа написана на упрощенном подмножестве языка C ("C--"),
разработанном специально для написания образцов решения
относительно простых задач.

А.П.Бельтюков.
18 апреля 2003 г.
г. Ижевск.


\***/

#include"cmm_m.h" /*стандартные описания program,get,put,putnl*/

int n[3]; /* вводимые числа */
int m[3]; /* количества их простых множителей */
int p[3][15]; /* сами простые множители */
int e[3]; /* номера чисел с количеством простых множителей, */
          /* делящимся на выбранную степень 2*/
program()
{int i,i0,i1; /* номер числа */
 int k; /* частное от деления числа */
 int q; /* кандидат в простые множители */
 int j; /* номер множителя */
 int d; /* степень числа 2 */
 int o; /* номер числа с количеством простых множителей, не */
        /* делящимся на выбранную степень числа 2 */
 int x; /* множитель разлагаемого числа */
 int g; /* количество исходных чисел, число простых множителей */
        /* которых делится на выбранную степень числа 2*/
 n[0]=get();
 n[1]=get();
 n[2]=get();
/* Разложение чисел n на простые множители p */
 i=0;
 while(i<3)
 {k=n[i];
  q=2;
  j=0;
  while(q*q<=k)
   if(k%q==0)
   {p[i][j]=q;
    k=k/q;
    j=j+1;
   }
   else
    q=q+1;
  p[i][j]=k;
  m[i]=j+1;
  i=i+1;
 }
/* Нахождение d - минимальной степени 2, на которую не делится */
/* число простых множителей в разложении хотя бы одного из */
/* исходных чисел (попутно находятся e и o)*/
 d=1;
 g=3;
 while(g==3)
 {i=0;
  g=0;
  while(i<3)
  {if(m[i]/d%2==0)
   {e[g]=i;
    g=g+1;
   }
   else
    o=i;
   i=i+1;
  }
  d=d*2;
 }
 d=d/2;
/* Вычисление и вывод результата */
 if(g==0) /* вообще говоря, противник может выиграть */
 {i0=0;
  i1=0;
  i=1;
  while(i<3)
  {if(m[i0]m[i])
    i1=i;
   i=i+1;
  }
  if(m[i0]<=1) /* Ход невозможен */
   put(2);
  else
  {put(1);
   putnl();
   if(i0==i1)
    i1=1;
   put(i1+1);
   put(i0+1);
   j=0;
   x=1;
   while(2*j+2<=m[i0])
   {x=x*p[i0][j];
    j=j+1;
   }
   put(x);
  }
 }
 else
 {put(1); /*гарантированно выигрышная позиция*/
  putnl();
  if(g==1)
   put(o+1);
  else
   put(e[1]+1);
  i=e[0];
  put(i+1);
  j=0;
  x=1;
  while(j< d)
  {x=x*p[i][j];
   j=j+1;
  }
  put(x);
 }
}

/*A.P.Beltiukov

Header for mini-programs

file://belt.uni.udm.ru/alt/AP/edu/oly/mark/sc_3/cmm_m.h
Version:_34h-i

***/

#include
FILE*inf,*ouf;
get(){int i;fscanf(inf,"%d",&i);return i;}
put(i){fprintf(ouf,"%d ",i);}
putnl(){fprintf(ouf,"\n");}

main()
{inf=fopen("input.txt","r");
 ouf=fopen("output.txt","w");
 program();
 fclose(inf);
 fflush(ouf);
 fclose(ouf);
}

Жюри

http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу
В избранное