Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 17.10.2010, 01:37
Новичок

Отправить личное сообщение для wa1k Посмотреть профиль Найти все сообщения от wa1k
 
Регистрация: 17.10.2010
Сообщений: 3

Оптимизация
была задана задача с тимуса
"Time limit = 5 секунд(ы)
На складе имеется N проводов целочисленной длины. Необходимо из них получить K кусков провода одинаковой и как можно большей длины L. Провода нельзя спаивать.
Вход В первой строчке указаны числа N и K, 1 ≤ N, K ≤ 10000. Далее разделенные пробельными символами перечислены N натуральных чисел — длины имеющихся проводов, они не превосходят 10000001.

Выход Выведите целое максимальное число L такое, что можно из имеющихся проводов получить K кусочков длины L.

Вход#1
3 4
1 100 34
Выход#1
33 "

написал следующий код:

#include <stdio.h>
int main ()
{
int N,K,x;
unsigned int Length[10000],y,z,Max,L;
scanf ("%d%d",&N,&K);
Max=0;
for(z=0;z<N;z++)
{
scanf("%d",&Length[z]);
if(Max<Length[z])
Max=Length[z];
}
if(K==1)
{
L=Max;
goto a;
}
if(N==1)
{
L=(Length[0]/K);
goto a;
}
for(z=1; z<=Max ;z++)
{
y=0;
for(x=0;x<N;x++)
{
y=y+(Length[x]/z);
}
if(y>=K)
L=z;
else
{
x=N+1;
z=Max+1;
}

}
a:
printf("%d",L);
return 0;
}

программа заваливается на тесте тимусовской системы проверки с сообщением,что превышен временной лимит выполнения программы.Подскажите пожалуйста варианты оптимизации программы, чтобы временные затраты на выполнение были минимальными.
  #2  
Старый 17.10.2010, 03:43
гость

 
Сообщений: n/a

двоичный поиск т.к. \sum_i \lfloor Length[i]/L \rfloor мототонно убывает с увеличением L
  #3  
Старый 17.10.2010, 04:34
Пользователь

Отправить личное сообщение для lordKelvin Посмотреть профиль Найти все сообщения от lordKelvin
 
Регистрация: 25.01.2010
Сообщений: 51

Код:
#include <stdio.h>

void main()
{
    int N, K, result;

    scanf( "%d %d", &N, &K );

    int *len = new int [ N ];

    for( int i = 0, cur; i < N; i++ )
    {
        scanf( "%d", &cur );

        for( int j = i;; j-- )
        {
            if( j == 0 || len[ j - 1 ] >= cur )
            {
                len[ j ] = cur;
                break;
            }
            else len[ j ] = len[ j - 1 ];
        }
    }
    if( N == 1 || K == 1 )
    {
        result = *len / K;
    }
    else
    {
        for( int f = 0, c = *len; f < c; )
        {
            int S = 0, l = ( f + c + 1 ) / 2;

            for( int i = 0; i < N && S < K; i++ )
                S += len[ i ] / l;

            if( S < K ) c = l;
            else f = l;
        }
        result = c;
    }

    printf( "%d", result );

    delete []len;
}

Последний раз редактировалось lordKelvin, 17.10.2010 в 04:47.
  #4  
Старый 11.11.2010, 21:10
Новичок

Отправить личное сообщение для wa1k Посмотреть профиль Найти все сообщения от wa1k
 
Регистрация: 17.10.2010
Сообщений: 3

Помогите пожалуйста найти косяк в коде.валиться по-прежнему со ссылкой timelimit, но уже на другом тесте =\
lordKelvin,не пашет почему-то =\
Код:
#include <stdio.h>
#include <conio.h>
int main ()
{
unsigned int Length[10000],y,z,Max,L,M,K,P,Min,x,N;
scanf ("%d",&N);
scanf ("%d",&K,"/n");
Max=10000001;
Min=1;
for(x=0;x<N;x++)
{
scanf("%d",&Length[x]);
}
if(N==1)
{
L=(Length[0]/K);
goto a;
}
        y=0;
        M=5000001;
        for(x=0;x<N;x++)
        {
        y=y+(Length[x]/M);
        }
        if(y>=K)
        {
        while(y>=K)
           {
           P=M;
           Min=M+1;
           M=((Max+Min)/2);
           y=0;
           for(x=0;x<N;x++)
           {
           y=y+(Length[x]/M);
           }}
           b:
               for(z=M; z>=P ; z--)
               {
               y=0;
                  for(x=0;x<N;x++)
                  {
                  y=y+(Length[x]/z);
                  }
                  if (y>=K)
                  {
                  L=z;
                  goto a;
                  }
                  }}
				  if(y<K)
				  {
        while(y<K)
           {
           P=M;
           Max=M-1;
           M=((Max+Min)/2);
           y=0;
           for(x=0;x<N;x++)
           {
           y=y+(Length[x]/M);
           }
		   if(Max==1)
		   {
		   M=1;
		   goto e;
		   }}
               e:
               L=M;
               for(z=P; z>=M ; z--)
               {
               y=0;
                  for(x=0;x<N;x++)
                  {
                  y=y+(Length[x]/z);
                  }
                  if (y>=K)
                  {
                  L=z;
                  goto a;
                  }}}
 a:
printf("%d",L);
getch();
return 0;
}
  #5  
Старый 11.11.2010, 23:06
гость

 
Сообщений: n/a

> lordKelvin,не пашет почему-то =\

Дык, естественно что не пашет. Что это у тебя за говно в коде:

...
#include <conio.h>
...
getch();
...

Это борландовское дерьмо, нигде кроме борланда (а это уже разорившийся банкрот) не работает.
  #6  
Старый 11.11.2010, 23:10
Новичок

Отправить личное сообщение для wa1k Посмотреть профиль Найти все сообщения от wa1k
 
Регистрация: 17.10.2010
Сообщений: 3

суть не в этом явно,система проверки заданий гетч тоже не принимает и я его убирал перед отправкой как и подключение конио.
  #7  
Старый 11.11.2010, 23:42
гость

 
Сообщений: n/a

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


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Автоматическая Алгоритмическая Оптимизация A.K. Математические алгоритмы 2 11.08.2009 14:42
Оптимизация сети с помощью ГА Sharky86 Искусственный интеллект, нейронные сети 0 02.06.2009 18:56
Дискретная оптимизация гость Вычислительная геометрия 1 26.05.2009 21:12
Оптимизация функции marain Математические алгоритмы (другое) 1 15.03.2009 14:22
Оптимизация раскроя Skall Вычислительная геометрия 3 24.02.2008 22:52