LINUX.ORG.RU

Обратный корень


0

1

Всем привет! Недавно начал изучать си, заглянул на acm.timus.ru и взял задачу «обраьный корень». Она звучит так: Исходные данные Входной поток содержит набор целых чисел Ai (0 ≤ Ai ≤ 10^18), отделённых друг от друга произвольным количеством пробелов и переводов строк. Размер входного потока не превышает 256 КБ. Результат Для каждого числа Ai, начиная с последнего и заканчивая первым, в отдельной строке вывести его квадратный корень не менее чем с четырьмя знаками после десятичной точки.

короч, я понимаю, что в общем мое решение совсем не оптимум, но если запускаю с тестовыми входными данными все работает у меня на компе, а когда отправляю решение - пишет что wrong answer. Нашел в интернете чужое решение, отправил - все работает(((( Не пойму в чем ошибка(((

Вот мой код:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define MAXCHAR 18
#define MAXROOTS 1000000
#define IN 1
#define OUT 0
void clean_buf(char buf[], int length);   //очищать буфер чисел
void print_reverse(double arr[], int length); //вывести в выходной поток обратный массив корней

int main()
{
    int state, counter, digit_counter=0;
    state = OUT;//состояние - находимся ли мы внутри числа или нет
    char numbers[MAXCHAR];
    double roots[MAXROOTS];
    char tmp;
    while ((tmp = getchar()) != EOF) //читаем символы из входного потока
        {
            if ((tmp == ' ' || tmp == '\n')) {  // если символ пробел или переход строки
                    if (state == IN) { //и к тому же мы только что вышли из слова
                        double num;
                        sscanf(numbers, "%lf",&num); //записать текущий буфер в число
                        roots[counter]=sqrt(num); //и найти его корень
                        counter++;
                        state = OUT;
                        clean_buf(numbers, MAXCHAR);
                        digit_counter = 0;
                    }
            }
            else
                    {
                        numbers[digit_counter] = tmp;
                        state = IN;
                        digit_counter++;
                    }

        }
        print_reverse(roots, counter-1);
        return 0;
}

void clean_buf(char buf[], int length)
{
    int i;

    for (i = 0; i < length; ++i)
        buf[i] = ' ';
}

void print_reverse(double arr[], int length)
{
    while (length >= 0)
    {
        printf("%.4lf\n", arr[length]);
        length--;
    }


}

А вот найденный на просторах интернета:

#include <math.h>
#include <stdio.h>

int top = -1;
double stack[131072];

int main()
{
  while(scanf("%lf", &stack[++top]) != EOF );
  for( ; top > 0; printf( "%.4f\n", sqrt( stack[--top] ) ) );
  return 0;
}


Ну зачем, зачем такие сложности городить по чтению, обработке, всему остальному, зачем делать работу за библиотечные функции? Лень разбираться, но как минимум одна ошибка здесь в указании максимума в 18 символов на число, когда 10^18 будет содержать 19 символов, сюрприз! И вообще я считаю, что сишка для практически всех задач на тимусе — оверкилл.

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import sys
import math

for num in reversed(sys.stdin.read().split()):
	print '%.4f' % math.sqrt(float(num))

mix_mix ★★★★★
()
Ответ на: комментарий от mix_mix

Плюсую товарища выше.

Кстати, для этой задачи можно задействовать рекурсию, говнокод, конечно, для в ограничениях задачи должен работать:

#include <stdio.h>
#include <math.h>

int main(void)
{
    double num;

    if(scanf("%lf", &num) == 1)
    {
        main();
        printf("%.4f\n", sqrt(num));
    }

    return 0;
}

theNamelessOne ★★★★★
()

esli ja pravilno vizhu, to ty podrazumevaew, 4to _vse_ 4isla imejut dlinu v 18 simvolov.

dikiy ★★☆☆☆
()
Ответ на: комментарий от mix_mix

А есть сайты где не только можно проверить решение, но ещё и напишут почему оно не прошло проверку? А то надоело ловлей блох вслепую заниматься. Видимо, я хреновый программист.

сишка для практически всех задач на тимусе — оверкилл.

Чёрт, а у меня прога на питоне по времени не пролазит в «1005. Stone Pile» :( Я так понимаю, задача NP-hard и полноё решение можно найти только перебором.

true_admin ★★★★★
()
Ответ на: комментарий от true_admin

А есть сайты где не только можно проверить решение, но ещё и напишут почему оно не прошло проверку? А то надоело ловлей блох вслепую заниматься.

Сайт предназначен для подготовки к спортивному программированию. Если тебе напишут, почему решение не прошло проверку, это может дать тебе подсказку. Поэтому максимум, что пишут, — это номер провалившегося теста, чтобы ты мог связаться с судьями и спросить: «Is test #5 correct?».

Видимо, я хреновый программист.

Спортивное программирование весьма плохо показывает, хороший программист или плохой. ИМХО.

Чёрт, а у меня прога на питоне по времени не пролазит в «1005. Stone Pile» :( Я так понимаю, задача NP-hard и полноё решение можно найти только перебором.

Я, помнится, сначала пытался решить задачу с помощью жадного алгоритма, потом пытался его модифицировать, а в итоге решил с помощью обычной рекурсии. Хотя писал на сишечке, да.

theNamelessOne ★★★★★
()
Ответ на: комментарий от true_admin

Хочу сайт для людей :(

На сайтах для людей таких задач нет :)

Еще можно посмотреть обсуждение задачи на форуме, иногда помогает.

theNamelessOne ★★★★★
()
Ответ на: комментарий от true_admin

http://www.talentbuddy.co/ :)

а вообще то топкодер - в практисруме можно писать - затем прогонять тесты и смотреть начём фэйлишся.

qulinxao ★★☆
()
Ответ на: комментарий от true_admin

эээ там «эвристики»

var  w:array[0..20] of longint;o,n,s:longint;
procedure F(u,t:longint);var i:longint;begin
inc(t,w[u]);
 if 2*t>=s then begin i:=2*t-s;if i<o then o:=i;exit;end;
 for i:=u+1 to n do 
   F(i,t);
end;
var i,j:longint;
begin
read(n);w[0]:=0;
s:=0;for i:=1 to n do begin read(w[i]);inc(s,w[i]);end;
for i:=1 to n-1 do
  for j:=i+1 to n do
    if w[i]<w[j] then begin o:=w[i];w[i]:=w[j];w[j]:=o;end;
o:=s;
F(0,0);
writeln(o);
end.

qulinxao ★★☆
()
Ответ на: комментарий от true_admin

Ну, получается так: нам нужно прочитать числа, записанные во входном потоке, поэтому объявляем переменную которая является индикатором нахождения позиции во входном потоке: если мы находимся в числе, индикатор IN, OUT - если мы в пробеле. Как только встречаем число - мы приравниваем индикатор к IN и записываем каждый символ в буфер numbers, как только выходим из него, значит число закончилось, буфер читаем в число с помощью sscanf, от числа берем корень. Полученное значение забиваем в массив значений корней, который потом выводим на экран в обратном порядке.

artsin
() автор топика
Ответ на: комментарий от artsin

Основная сложность, что числа нужно вывести В ОБРАТНОМ ПОРЯДКЕ

artsin
() автор топика
Ответ на: комментарий от artsin

Хм, теперь я понял, я думал это код к другой задаче. Но спасибо за объяснения. Впрочем, всё равно не могу распарсить это. Нет комментариев, названия переменных из одной буквы, название функции F, несколько statements в одну строку...

true_admin ★★★★★
()
Ответ на: комментарий от true_admin

это объяснение для твоего питон-варианта. 1005

var  w:array[0..20] of longint;o,n,s:longint;

массив w - веса, o-наилучшее приближение к половине, n- число предметов, s - сумма всех предметов

procedure F(u,t:longint);var i:longint;begin

F перебор где u - номер выбранного предмета (имено поэтому w от нуля). t - аккумулированная сумма набранных предметов. i - переменая цикла для перебора.

inc(t,w[u]);

добавили u предмет в набор

 if 2*t>=s then begin i:=2*t-s;if i<o then o:=i;exit;end;

если набор не меньше полусуммы дальше добавлять предметы бес мысленно, так что обновляем если надо наилучшее решение и возвращаемся.

 for i:=u+1 to n do 
   F(i,t);
end;

какой следующий предмет будет выбран(будь необходимость(дальнейшая заточка) то цикл можно и не до n а до такого k <=n где t+s[k...n] отклоняется от полусуммы больше чем на o - но на 20 камнях это не нужно). предпочитаю при переборе такой цикл ( мы выбираем какой камень попадает в набор) - чем вариант когда мы идём по каждому разряду вектора(брать/небрать) и делаем 2 ветки рекурсии - такой вариант ровно в 2 раза медленей чем через цикл где мы выбираем сразу с каким номером следующий камень(платя(вообще то можно было u использовать while(true)begin inc(u)if(u>n)then break;F(u,t);end;) за это местом для переменной цикла на стеке)

var i,j:longint;

локальные переменые для дубовой квадратичной сортировки

begin
read(n);w[0]:=0;
s:=0;for i:=1 to n do begin read(w[i]);inc(s,w[i]);end;

читаем набор, и запоминаем его сумму.

for i:=1 to n-1 do
  for j:=i+1 to n do
    if w[i]<w[j] then begin o:=w[i];w[i]:=w[j];w[j]:=o;end;
o:=s;

сортируем , и в качестве первого приближения берём решение когда все камни в наборе.

F(0,0);

выбираем несуществующий камень.

writeln(o);
end.

ответ.

qulinxao ★★☆
()
Последнее исправление: qulinxao (всего исправлений: 4)

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

piorun
()
Ответ на: комментарий от mazdai

1. у тебя жадное решение. -которое ... - придумай тест сам.

2. как ты исключаеш перекинутый камень при продолжении? никак. что совсем не правильно.

3. порешай задачу составления рюкзака максимальной цености , а потом возвращайся.

qulinxao ★★☆
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.