VPF::[C++||Pascal] - Форум программистов

Strannik

Дата 14.2.2007, 12:23 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 154
Регистрация: 25.1.2007

Репутация: нет
Всего: 2

Задача следующая: Нечётное количество носков заданы своими массами. Ясно что носки из одной пары имеют одинаковый вес. Т.к. носков нечётное кол-во - то один из них - непарный. Необходимо определить номер и вес непарного носка. Массы носков - вещественные числа(до 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 (ссылка)

(нет голосов)

Загрузка ...

Vadim A. Kazantsev

Профиль
Группа: Участник
Сообщений: 291
Регистрация: 3.12.2006
Где: Moscow, Russia

Репутация: нет
Всего: 14

Цитата(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, сам ты, я полагаю, её решил. «Хорошим» способом? Если да, то приведи решение. Если нет, то кто тебе об нём сказал?

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

Это сообщение отредактировал(а) V.A.KeRneL - 16.2.2007, 19:52

--------------------

«C'est un pense-creux d'ici. C'est le meilleur et le plus irascible homme du monde...» © Ф.М. Достоевский, «Бесы»
---/)/)---(\.../)---(\(\
--(':'=)---(=';'=)---(=':')
(")(")..)-(").--.(")-(..(")(")

sergejzr

Дата 14.2.2007, 16:27 (ссылка)

(нет голосов)

Загрузка ...

Un salsero
Group Icon

Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: нет
Всего: 360

Уже пару задач у нас в этом разделе на 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

))

--------------------

Me.
FB.
LinkedIn.
ORCID.
YT.

Kuvaldis

Дата 14.2.2007, 16:33 (ссылка)

(нет голосов)

Загрузка ...

механик-вредитель

Профиль
Группа: Участник Клуба
Сообщений: 1189
Регистрация: 16.6.2006
Где: Минск

Репутация: нет
Всего: 61

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 (ссылка)

(нет голосов)

Загрузка ...

Vadim A. Kazantsev

Профиль
Группа: Участник
Сообщений: 291
Регистрация: 3.12.2006
Где: Moscow, Russia

Репутация: нет
Всего: 14

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

Это сообщение отредактировал(а) V.A.KeRneL - 15.2.2007, 21:27

--------------------

sergejzr

Дата 14.2.2007, 16:39 (ссылка)

(нет голосов)

Загрузка ...

Un salsero
Group Icon

Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: нет
Всего: 360

Угумс

--------------------

Me.
FB.
LinkedIn.
ORCID.
YT.

V.A.KeRneL

Дата 14.2.2007, 16:40 (ссылка)

(нет голосов)

Загрузка ...

Vadim A. Kazantsev

Профиль
Группа: Участник
Сообщений: 291
Регистрация: 3.12.2006
Где: Moscow, Russia

Репутация: нет
Всего: 14

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

)

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

Kuvaldis, нарочно? smile

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

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

)

Угумс

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

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

Это сообщение отредактировал(а) V.A.KeRneL - 15.2.2007, 08:02

--------------------

Strannik

Дата 14.2.2007, 18:08 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 154
Регистрация: 25.1.2007

Репутация: нет
Всего: 2

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

Цитата

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

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

Цитата

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

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

sergejzr

Дата 14.2.2007, 18:12 (ссылка)

(нет голосов)

Загрузка ...

Un salsero
Group Icon

Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: нет
Всего: 360

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

)

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

До чего?

--------------------

Me.
FB.
LinkedIn.
ORCID.
YT.

Strannik

Дата 14.2.2007, 18:23 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 154
Регистрация: 25.1.2007

Репутация: нет
Всего: 2

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

Цитата

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

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

sergejzr

Дата 14.2.2007, 18:34 (ссылка)

(нет голосов)

Загрузка ...

Un salsero
Group Icon

Профиль
Группа: Админ
Сообщений: 13285
Регистрация: 10.2.2004
Где: Германия г .Ганновер

Репутация: нет
Всего: 360

А это?

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

)

us_hash ^= sw_hashes[i];

--------------------

Me.
FB.
LinkedIn.
ORCID.
YT.

Strannik

Дата 14.2.2007, 18:50 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 154
Регистрация: 25.1.2007

Репутация: нет
Всего: 2

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

V.A.KeRneL

Дата 15.2.2007, 08:01 (ссылка)

(нет голосов)

Загрузка ...

Vadim A. Kazantsev

Профиль
Группа: Участник
Сообщений: 291
Регистрация: 3.12.2006
Где: Moscow, Russia

Репутация: нет
Всего: 14

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

)

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

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

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

Это сообщение отредактировал(а) V.A.KeRneL - 15.2.2007, 08:03

--------------------

MBo

Дата 15.2.2007, 11:28 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 234
Регистрация: 10.6.2002

Репутация: 1
Всего: 18

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

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

1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Интересные и занимательные задачи по программированию \| Следующая тема »