ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1184. Cable Master

Cable Master : I can't find my bug. Here is my code
Послано Badd 21 дек 2002 18:01
// My algorithm is about binary search

#include <stdio.h>
#include <stdlib.h>
#define maxd 10005
float d[maxd],m=0.0;
long k,n;
int check(float w)
{
    long l,s=0;
    for (l=0; l<n; l++)
    {
        if (s>=k) return 1;
        if (w>d[l]) return -1;
        s+=(long)(d[l]/w);
    }
    if (s>=k) return 1;
    return -1;
}
int sort_function(const void*a,const void*b)
{
    if ((*(float*)a)>(*(float*)b)) return -1;
    if ((*(float*)a)==(*(float*)b)) return 0;
    return 1;
}
int main()
{
    long l;
    float a,b,c,tmp;
    FILE* fname=stdin;
    FILE* fout=stdout;
    fscanf(fname,"%ld%ld",&n,&k);
    for (l=0; l<n; l++) fscanf(fname,"%f",&d[l]);
    qsort((void*)d,n,sizeof(d[0]),sort_function);
    c=(float)((long)((long)100*(long)(1+10000)/2))/100.0;
    for (a=1,b=10000; a<=b; c=(float)(a+b)/2.0 )
    {
        if (check(c)==1)
        { if (c>m)
            m=c;
            tmp=a;
            a=c+0.01;
            a=(float)((long)
(100.0*a))/100.0;
            if (a==tmp) break;
        }
        else
        {
            b=c-0.01;
            b=(float)((long)
(100.0*b))/100.0;
        }
    }
    m=((long)(m*100))/100.0;
    fprintf(fout,"%.2f\n",m);
    fclose(fname); fclose(fout);
    return 0;
}