Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Интересные и занимательные задачи по программированию > [C++||Pascal]

Автор: Strannik 14.2.2007, 12:23

Задача следующая: Нечётное количество носков заданы своими массами. Ясно что носки из одной пары имеют одинаковый вес. Т.к. носков нечётное кол-во - то один из них - непарный. Необходимо определить номер и вес непарного носка. Массы носков - вещественные числа(до 4 знаков после запятой), количество носков не более 9999.
Пример:

Ввод
7
1.0001 1.0001 1.0002 1.0002 3.230 2.200 2.200

Вывод
5 {номер}
3.230 {вес}

П.С. Хорошее решение укладывается в 4 строчки...

Автор: V.A.KeRneL 14.2.2007, 16:18

Цитата(Strannik @ 14.2.2007, 12:23

)

количество носков не более 9999.

И не менее 1, имхо, а то случай отдельный с нулём придётся рассматривать, тогда точно в 4 (!) строчки никак не уложиться.

Цитата(Strannik @ 14.2.2007, 12:23

)

Вывод
5
3.230

Всё-таки, формат вывода неаккуратно описан. Надо тогда уж либо 3.23 ("%lf"), либо 3.2300 ("%.4lf").

Цитата(Strannik @ 14.2.2007, 12:23

)

П.С. Хорошее решение укладывается в 4 строчки...

Значит мои решения заведомо «плохие» smile

(зато эффективные)

Не удержался:

Код


#!/usr/bin/env ruby

gets
socks_weights = gets.split.map { |s| s.to_f }
sw_hashes = socks_weights.map { |sw| sw.hash }
us_hash = sw_hashes.inject(0) { |ush, h| ush^h }
usw_idx = sw_hashes.index(us_hash)
us_weight = socks_weights[usw_idx]
printf "%d\n%.4f\n", usw_idx + 1, us_weight

А вот и на допустимых Сях:

Код


#include <stdio.h>

#define ARR_SIZE   10000

double socks_weights[ARR_SIZE];

int 
main(void) 
{ 
    int nsocks, i;
    unsigned long long us_hash = 0;
    unsigned long long *sw_hashes = (unsigned long long *) socks_weights;
    
    scanf("%d", &nsocks);
    for (i = 0; i < nsocks; ++i) { 
        scanf("%lf", &socks_weights[i]);
        us_hash ^= sw_hashes[i];
    }
    for (i = 0; sw_hashes[i] != us_hash; ++i) 
        ;
    printf("%d\n%.4lf\n", i + 1, socks_weights[i]);
    
    return (0);
}

З.Ы. В принципе, как и Фсе, я могу написать на Ruby в 1 строку, на C — в 2 (если без доп. опций компилятора, из-за #include).

З.З.Ы. Strannik, сам ты, я полагаю, её решил. «Хорошим» способом? Если да, то приведи решение. Если нет, то кто тебе об нём сказал?

З.З.З.Ы. Задачка — модификация классики (с целыми). Откуда брал?

Автор: sergejzr 14.2.2007, 16:27

Уже пару задач у нас в этом разделе на XOR было smile

Код


double[] socks_weights{1.0001 1.0001 1.0002 1.0002 3.230 2.200 2.200};int nsocks, i, us_hash = 0;
for (i = 0; i < nsocks; ++i,us_hash ^= (int)(sw_hashes[i]*10000));for (i = 0; sw_hashes[i] != us_hash/10000; ++i);
printf("%d\n%.4lf\n", i + 1, socks_weights[i]);

Никогда не понимал смысла измерения кода количеством строк smile

))

Автор: Kuvaldis 14.2.2007, 16:33

Strannik,

Код


//---------------------------------------------------------------------------
#include <stdio.h>
#include <stdlib.h>
//---------------------------------------------------------------------------
#define MAX 9999
//---------------------------------------------------------------------------
int cmp(const void* a, const void* b);
//---------------------------------------------------------------------------
int main(int argc, char* argv[])
{
    FILE*  in;
    FILE*  out;
    int    i, n;
    float  socks[MAX][2];
    int    found;
    int    len;   // длина текущей подпоследовательности

    in = fopen("socks.in", "r");
    out = fopen("socks.out", "w");

    fscanf(in, "%d", &n);
    for (i = 0; i < n; i++)
    {
        fscanf(in, "%f", &socks[i][0] );
        socks[i][1] = i + 1; 
    }
    qsort(socks, n, sizeof(socks[0]), cmp);   // сортировка
    found = 0;

    found = i = 0;
    while (! found)
    {
        len = 0;
        while ( socks[i][0] == socks[i + 1][0] )  //
        {
            i++;
            len++;
        }
        if (len == 0)  // нет пары
            found = 1;
        else
            i++;       // перейти к следующему носку
    }

    fprintf(out, "%0.0f \n%0.4f", socks[i][1], socks[i][0] );
    fclose(in);
    fclose(out);
    return 0;
}
//---------------------------------------------------------------------------
int cmp(const void* a, const void* b)
{
    return *(float*) a - *(float*) b;
}
//---------------------------------------------------------------------------

Автор: V.A.KeRneL 14.2.2007, 16:37

Ах да, sergejzr, совсем запамятовал. На сколько я понимаю, формат названия темы не совсем соответствует желаемому.
Может переименовать топик: «C++||Pascal, Задача "Непарный носок"» -> «[C++||Pascal] Задача "Непарный носок"» ?

Автор: sergejzr 14.2.2007, 16:39

Угумс

Автор: V.A.KeRneL 14.2.2007, 16:40

Цитата(Strannik @ 14.2.2007, 12:23

)

П.С. Хорошее решение укладывается в 4 строчки...

Kuvaldis, нарочно? smile

Добавлено @ 16:43

Цитата(sergejzr @ 14.2.2007, 16:39

)

Угумс

Извиняюсь за возможно излишнюю педантичность, а то, что весь смысл (название задачи) остался лишь в разъяснении (мелким шрифтом), это нормально? smile

(Я про запятую.)

Автор: Strannik 14.2.2007, 18:08

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

Цитата

Уже пару задач у нас в этом разделе на XOR было smile

И тем не менее... никто не написал до этого...

Цитата

Никогда не понимал смысла измерения кода количеством строк smile))

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

Автор: sergejzr 14.2.2007, 18:12

Цитата(Strannik @ 14.2.2007, 17:08

)

И тем не менее... никто не написал до этого...

До чего?

Автор: Strannik 14.2.2007, 18:23

До вот этого поста:

Цитата

Уже пару задач у нас в этом разделе на XOR было smile

Решения с XOR не постились.

Автор: sergejzr 14.2.2007, 18:34

А это?

Цитата(V.A.KeRneL @ 14.2.2007, 15:18

)

us_hash ^= sw_hashes[i];

Автор: Strannik 14.2.2007, 18:50

Да.. не увидел... ну раз было и никто не возражает - тему можно удалить...

Автор: V.A.KeRneL 15.2.2007, 08:01

Цитата(Strannik @ 14.2.2007, 18:50

)

Да.. не увидел... ну раз было и никто не возражает - тему можно удалить...

Не, удалять не надо. Зачем? Вполне себе интересная задачка. Я привёл хорошее решение... Просто, пометь решённой.

З.Ы. Да, Strannik, ты ж так и не сказал откуда задачка. Сам придумал?

Автор: MBo 15.2.2007, 11:28

Для гурманов - усложнение задачи:

Дан массив целых, в котором все числа парные, за исключением двух (например, [2,7,4,2,1,7])
Найти эти непарные числа за линейное время с использованием только O(1) дополнительной памяти.