Тесты и решения

Правила проведения олимпиады, условия задач и комментарии к ним, результаты олимпиады и апелляции. Руководители: к.ф-м.н., профессор Пирогов Владислав Юрьевич, ник - Vladislav_133; к.п.н, доцент Слинкин Дмитрий Анатольевич, ник - xdsl

Модератор: xdsl

Тесты и решения

Сообщение Vladislav_133 25 мар 2010, 22:44

Проверка в самом разгаре. Публикую несколько тестов для задачи о игре в числа.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Очная олимпиада по программированию

Сообщение Vladislav_133 25 мар 2010, 22:46

40
1 1
0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
5 0 4 2 1 2 2 2 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
8 0 1 3 7 3 3 1 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
1 7 3 3 6 7 4 5 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
3 0 7 2 7 6 5 1 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
3 0 6 5 4 4 6 1 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
3 1 7 1 4 2 1 5 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
9 2 3 1 5 6 8 6 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
9 2 3 1 5 6 8 6 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
9 2 3 1 5 6 8 6 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
5 0 4 2 1 2 2 2 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
8 0 1 3 7 3 3 1 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
1 7 3 3 6 7 4 5 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
3 0 7 2 7 6 5 1 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
3 0 6 5 4 4 6 1 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
3 1 7 1 4 2 1 5 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
9 2 3 1 5 6 8 6 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
9 2 3 1 5 6 8 6 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
9 2 3 1 5 6 8 6 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
5 0 4 2 1 2 2 2 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
8 0 1 3 7 3 3 1 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
1 7 3 3 6 7 4 5 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
3 0 7 2 7 6 5 1 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
3 0 6 5 4 4 6 1 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
3 1 7 1 4 2 1 5 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
9 2 3 1 5 6 8 6 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
9 2 3 1 5 6 8 6 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
9 2 3 1 5 6 8 6 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
5 0 4 2 1 2 2 2 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
8 0 1 3 7 3 3 1 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
1 7 3 3 6 7 4 5 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
3 0 7 2 7 6 5 1 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
3 0 6 5 4 4 6 1 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
3 1 7 1 4 2 1 5 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
9 2 3 1 5 6 8 6 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
9 2 3 1 5 6 8 6 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5
1 2 3 1 5 6 8 6 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 5 0 8 1 3 7 8 1 3 4 0

Total 1480197
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Очная олимпиада по программированию

Сообщение Vladislav_133 25 мар 2010, 22:49

2
1 1
8 2
3 2

Total 0

1
1 1
2

Total 0

3
1 1
0 1 1
1 1 1
1 1 1

Total 12

4
2 1
1 2 3 4
4 3 2 1
1 2 3 4
4 3 2 1

Total 8

5
2 2
1 2 3 1 2
2 22 2 1 4
2 3 6 7 10
1 1 1 1 11
11 12 12 22 1

Total 1

3
3 3
0 0 0
0 0 0
1 2 1

Total 2
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Очная олимпиада по программированию

Сообщение Vladislav_133 26 мар 2010, 11:11

Программа, решающая задачу Игра в числа

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#include <errno.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <math.h>

//A -- ходит по строкам
//B -- ходит по столбцам
//вариант - 5 ходов максимум
const int max=40;
int n; //размерность
int nx, ny; //начальный ход
int *num;
void rec(int, int, int);
int suma,sumb;
int mx[10000];
int my[10000];
int sh;
unsigned int no;
unsigned int asu;
int fg,er;
int vy();
int main()
{
int i,j;
//читаем размерность
fscanf(stdin,"%d",&n);
if(n>max)
{
fprintf(stdout,"Error 1!\n");
return 1;
}
//начальный ход nx ny
fscanf(stdin,"%d%d",&nx,&ny);
if(nx<1||ny<1||nx>n||ny>n)
{
fprintf(stdout,"Error 2!\n");
return 2;
}
//выделяем память для массива чисел
num = (int*)malloc(sizeof(int)*n*n);
asu=0;
//читаем квадрат
for(i=1; i<=n*n; i++)
{
er=fscanf(stdin,"%d",&num[i-1]);
if(er<=0)break;
// fprintf(stderr,"%d",num[i-1]);
asu=asu+num[i-1];
}
if(i<=n*n)
{
fprintf(stdout,"Error 3!\n");
return 3;
}
//приступаем к анализу
suma=0;sumb=0;sh=0;no=0;fg=0;
rec(nx,ny,0);
fprintf(stdout,"Total %d\n",no);
//конец
free(num);
return 0;
}

void rec(int x, int y, int pr)
{
int zn,k1,k2,u;
if(fg==1)return;
u=0;sh++;
if(sh>5)
{
sh--;
return;
}
zn=*(num + (x-1)*n + y-1);
*(num + (x-1)*n + y-1) = -1;
mx[sh-1]=x; my[sh-1]=y;
if(!pr)
{
//ход сделал A (по строкам)
suma=suma+zn;
asu=asu-zn;
// if(suma+suma<=asu)
{
for(k1=1; k1<=n; k1++)
{
if(*(num + (k1-1)*n + y-1)>=0)
{
u=1;
rec(k1,y,1);
}
}
}
}
else
{
//ход сделал B (по столбцам)
sumb=sumb+zn;
asu=asu-zn;
for(k2=1; k2<=n; k2++)
{
if(*(num + (x-1)*n + k2-1)>=0)
{
u=1;
rec(x,k2,0);
}
}

}
*(num + (x-1)*n + y-1) = zn;
asu=asu+zn;
if(!u||sh==5) vy();
sh--;
if(!pr)suma=suma-zn;else sumb=sumb-zn;

}
//
int vy()
{
int h;
if(sumb>=suma)
{
// for(h=0; h<sh; h++)
// {
// fprintf(stdout,"(%d,%d)",mx[h],my[h]);
// }
// fprintf(stdout,"a-%d b-%d \n",suma,sumb);
no++; //fg=1;
return 1;
}
return 0;
}
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

Re: Тесты и решения

Сообщение xdsl 26 мар 2010, 13:22

Мои задачи были третья и пятая. Ниже приведены тесты для 3-й задачи. К сожалению, 5-ю задачу решить никто не смог, т.е. студенческие решения не проходят даже базовый тест, приведенный в примере.
Вложения
tests.tar.gz
(927 байт) Скачиваний: 387
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.


Вернуться в Олимпиада по программированию

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 0

cron