ReSQL.ru
     
powered by simpleCommunicator - 2.0.60     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Нужна ли программисту высшая математика???
25 сообщений из 83, страница 3 из 4
  3  все
Нужна ли программисту высшая математика???
    #33220497
LeXa NalBat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
LeXa NalBat
Участник
РытСлышь, ЛеХа, а сделай ты и Альфа Код (ссылка в топике
про Криптографию)?Однако это одинаковые задачки. :-О
...
Рейтинг: 0 / 0
17.08.2005, 13:36
| Ответить | Цитировать | Написать  
Нужна ли программисту высшая математика???
    #33226867
NotGonnaGetUs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NotGonnaGetUs
Участник
Рыт..... вот парочка "число-ответ" на любителя:

5555555555555555555555555555555555555555555555555555555555555555555555555
4116875388895471038665169154139430260541408747498524095285973494068264451476229

На Celeron 2.4 время счета ~10 сек.

Сорри плз.

"C:\Program Files\Java\jdk1.5.0_01\bin\java" -Didea.launcher.port=7540 -Didea.launcher.library=C:\IntelliJ-IDEA-4.5\bin\breakgen.dll -Dfile.encoding=UTF-8 ... 4.5\lib\idea_rt.jar" com.intellij.rt.execution.application.AppMain coins.Task
f(5555555555555555555555555555555555555555555555555555555555555555555555555) = 4116875388895471038665169154139430260541408747498524095285973494068264451476229
time: 234 ms <- %)



java5.0,
атлон 2.6+ :)
...
Рейтинг: 0 / 0
21.08.2005, 12:43
| Ответить | Цитировать | Написать  
Нужна ли программисту высшая математика???
    #33226876
NotGonnaGetUs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NotGonnaGetUs
Участник
или у вас опечатка и на самом деле требуется 10 мс, а не секунд?
...
Рейтинг: 0 / 0
21.08.2005, 12:51
| Ответить | Цитировать | Написать  
Нужна ли программисту высшая математика???
    #33226977
Рыт
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рыт
Гость
NotGonnaGetUsили у вас опечатка и на самом деле требуется 10 мс, а не секунд?
Ни фига не опечатка! :) Правда, я на глазок считал.

У тебя сейчас на Сфере время 0.23. У меня - 0.22. Интересно.
В который раз Питон вылазит вперед прямо под нос Джавы.

PS Может у нас алгоритмы очень разные.
...
Рейтинг: 0 / 0
21.08.2005, 21:23
| Ответить | Цитировать | Написать  
Нужна ли программисту высшая математика???
    #33227553
Рыт
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рыт
Гость
NotGonnaGetUs;
Может сравним наши COINS алгоритмы (точнее, подходы к решению)?
Вот мой код на питоне. Даже не знаю почему он притормаживает на
"уж очень" больших числах. В фигурных скобках - это питоновский
map (dictionary, associative array).
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
while  1 :
    try:
        z,d= 0 ,{input(): 1 }
    except:
        break
    while  1 :
        e={}
        for i in d.keys():
            i2,i3,i4=i/ 2 ,i/ 3 ,i/ 4 
            if i<i2+i3+i4:
                if e.has_key(i2):
                    e[i2]+=d[i]
                else:
                    e[i2]=d[i]
                if e.has_key(i3):
                    e[i3]+=d[i]
                else:
                    e[i3]=d[i]
                if e.has_key(i4):
                    e[i4]+=d[i]
                else:
                    e[i4]=d[i]
            else:
                z+=i*d[i]
        if e<>{}:
            d=e
        else:
            break
    print z
...
Рейтинг: 0 / 0
22.08.2005, 12:08
| Ответить | Цитировать | Написать  
Нужна ли программисту высшая математика???
    #33228523
NotGonnaGetUs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NotGonnaGetUs
Участник
У меня было решение "в лоб":

Рекурсия вида f(n) = f(n/2) + f(n/3) + f(n/4), с сохранением промежуточных значений в "map"е + не много математики, чтобы не делать лишних вычислений.

Для работы с "большими" значениями использовался стандартный класс BigInteger.

Это решение в приложение. Но оно даёт только 0.30 на дуромере.
0.23 было на оптимизированном варианте того же самого тупого алгоритма (не работает для больших чисел) :)

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

--

Раскладывать "монетки на кучки" интересный подход, надо будет попробовать повторить это решение на java, чтобы сравнить время работы 6)

10сек могут получаться из-за не эффективной реализации больших чисел или {}. Кроме того выхов keys наверняка порождает "массив"-клон ключей, что приводит к лишним операциям.
При вычислении 55...555 порядка 17000 промежуточных значений вычисляется.

Пути для совершенствования тоже есть :)


з.ы.
что действительно достаёт на этом сайте - так это форматирование вывода.

в "приличных" местах на лишний \n наплевать, а тут нужно изголяться по всякому. в приложенном файле это видно :)
...
Рейтинг: 0 / 0
22.08.2005, 17:24
| Ответить | Цитировать | Написать  
Нужна ли программисту высшая математика???
    #33228687
LeXa NalBat
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
LeXa NalBat
Участник
РытNotGonnaGetUs;
Может сравним наши COINS алгоритмы (точнее, подходы к решению)?отличие тут:

for i in d.keys():

my $maxkey = pop_max_key( $struct );

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
sub main {
    my $struct = init_struct();
    while (  1  ) {
        my $maxkey = pop_max_key( $struct );
        if ( end_condition( $maxkey ) ) {
            print_result( $maxkey );
            exit;
        }
        my @newkeys = get_new_keys( $maxkey );
        for my $newkey ( @newkeys ) {
            push_new_key( $struct, $newkey );
        }
    }
}
...
Рейтинг: 0 / 0
22.08.2005, 18:22
| Ответить | Цитировать | Написать  
Нужна ли программисту высшая математика???
    #33228944
Рыт
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рыт
Гость
NotGonna;
Ага. Посмотрел. Почти один к одному. Только я конечно Джаву не знаю совсем (util.Map & util.HashMap - что-то тут наворотов до хрена; то ли дело Питон :) - в нем map - это его базовая структура, не требующая никаких подключений никаких "утилей").
Кстати, рекомендую по свежим следам сделать и #261. TRIPART.

LeXa NalBat;
Чую какой-то хитрый подход. Только не просек пока.
Ушлый народец - эти перлисты. Типа "хохлов" от программиздирования.
...
Рейтинг: 0 / 0
22.08.2005, 21:38
| Ответить | Цитировать | Написать  
Нужна ли программисту высшая математика???
    #33228950
Рыт
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рыт
Гость
НИ **Я СЕБЕ!

235858 2005-08-22 18:48:24 NotGonna Prime Generator accepted 0.46 192384 JAVA

Я так не могу! :)
...
Рейтинг: 0 / 0
22.08.2005, 21:43
| Ответить | Цитировать | Написать  
Нужна ли программисту высшая математика???
    #33228961
ReFleX
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
ReFleX
Участник
авторПрикладному(ну это кто любит готовенькие компонентики покидать на форму) не особо надо...
я бы скорее это назвал программированием интерфейса или дизайном:/
...
Рейтинг: 0 / 0
22.08.2005, 21:56
| Ответить | Цитировать | Написать  
Нужна ли программисту высшая математика???
    #33229312
NotGonnaGetUs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NotGonnaGetUs
Участник
РытNotGonna;
Ага. Посмотрел. Почти один к одному.

У тебя хранитяся монета-количество_штук, у меня
монета-количество_$_которое_за_неё_можно_выручить.
Всё-таки это разные подходы.

--

А prime решается применением алгоритма решето эратосфена.
Но это offtop, т.к. его проходят в начальной школе :)
...
Рейтинг: 0 / 0
23.08.2005, 10:27
| Ответить | Цитировать | Написать  
Нужна ли программисту высшая математика???
    #33232497
NotGonnaGetUs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NotGonnaGetUs
Участник
2Рыт.

Можешь прислать output задачки

https://spoj.sphere.pl/problems/ARITH/

для такого input-а?

7
99+1
999*111
99*9
99*99
999*19
0*1234
1*1234
...
Рейтинг: 0 / 0
24.08.2005, 17:32
| Ответить | Цитировать | Написать  
Нужна ли программисту высшая математика???
    #33232593
NotGonnaGetUs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NotGonnaGetUs
Участник
сорри, за офтоп, просто очень интересно.


Нужен ли ещё один "-" над 4444? :)
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
    2
*2222
-----
    4
   4
  4
 4
 ----
 4444
...
Рейтинг: 0 / 0
24.08.2005, 18:03
| Ответить | Цитировать | Написать  
Нужна ли программисту высшая математика???
    #33232794
*
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
*
Гость
Если еще есть какие тесты, давай сюда.
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
 2 * 2222 
     2 
* 2222 
-----
     4 
    4 
   4 
  4 
 ----
  4444 

 2222 * 2 
 2222 
  * 2 
----
 4444 

 99 + 1 
  99 
 + 1 
---
 100 

 999 * 111 
    999 
  * 111 
  ----
    999 
   999 
  999 
------
 110889 

 99 * 9 
  99 
 * 9 
---
 891 

 99 * 99 
   99 
 * 99 
 ---
  891 
 891 
----
 9801 

 999 * 19 
   999 
  * 19 
 ----
  8991 
  999 
-----
 18981 

>>  0 * 1234  << ALL input numbers are POSITIVE!

 1 * 1234 
     1 
* 1234 
-----
     4 
    3 
   2 
  1 
 ----
  1234
...
Рейтинг: 0 / 0
24.08.2005, 20:19
| Ответить | Цитировать | Написать  
Нужна ли программисту высшая математика???
    #33233628
NotGonnaGetUs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NotGonnaGetUs
Участник
> 999*111
тут была ошибка :)
thnx.
...
Рейтинг: 0 / 0
25.08.2005, 11:47
| Ответить | Цитировать | Написать  
Нужна ли программисту высшая математика???
    #33233793
Рыт
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рыт
Гость
NotGonnaGetUs> 999*111
тут была ошибка :)
thnx.
Уря!!! Поздравляю!
Код: plaintext
1.
accepted   1 . 61    192320   JAVA
...
Рейтинг: 0 / 0
25.08.2005, 12:25
| Ответить | Цитировать | Написать  
Нужна ли программисту высшая математика???
    #33234141
Пользователь
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Пользователь
Участник
Подскажите - как Вьетнам на этом сайте SPOJ - делает все остальные страны?
...
Рейтинг: 0 / 0
25.08.2005, 13:53
| Ответить | Цитировать | Написать  
Нужна ли программисту высшая математика???
    #33234214
Рыт
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рыт
Гость
ПользовательПодскажите - как Вьетнам на этом сайте SPOJ - делает все остальные страны?
Я тоже одно время интересовался причинами этого феномена. :) И даже имел небольшой clash с Адрианом Косовским; типа: что за ***ня на Вашем контестере - наплодили помашь вьетконговцы грязных аккаунтов и ***чат бледнолицых собратьев!
Т.е., под грязным аккаунтом ты тестируешь свой код, а потом сдаешь отлаженное решение под своим Главным (показушном) аккаунтом.

После того, как на Сфере стали применять начисление очков за конкретную задачу по формуле 80/(40+<число юзеров, решивших эту задачу>) число юзеров-вьетнамцев ВРОДЕ БЫ резко поубавилось.

А вообще-то я думаю дело обстоит так:
какой-то их препод-доцент (высокого класса) объясняет "всему классу" как надо делать ту или иную задачу (описывает алгоритм), и "весь класс" садится и начинает кодировать (кстати, даже имея готовый алгоритм, это не всегда очень просто).
А может у них вузы так соревнуются между собой и поэтому "свои" помогают "своим" (делятся кодами).
...
Рейтинг: 0 / 0
25.08.2005, 14:21
| Ответить | Цитировать | Написать  
Нужна ли программисту высшая математика???
    #33234907
NotGonnaGetUs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NotGonnaGetUs
Участник
ПользовательПодскажите - как Вьетнам на этом сайте SPOJ - делает все остальные страны?

Так они мстят американцам :)

з.ы.
1.09 %)
...
Рейтинг: 0 / 0
25.08.2005, 18:50
| Ответить | Цитировать | Написать  
Нужна ли программисту высшая математика???
    #33237362
Рыт
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рыт
Гость
NotGonnaGetUsТак они мстят американцам :)
Похоже, что не только американцам: http://spoj.sphere.pl/users/putin/
...
Рейтинг: 0 / 0
27.08.2005, 15:02
| Ответить | Цитировать | Написать  
Нужна ли программисту высшая математика???
    #33244500
NotGonnaGetUs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NotGonnaGetUs
Участник
2Рыт.
Сдаюсь.

Что всё это значит? :)

https://spoj.sphere.pl/forum/viewtopic.php?t=140&highlight=sorting+bank+accounts

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
3
2
00 00000000 0000 0000 0000 0053
00 00000000 0000 0000 0000 0077

2
00 00000000 0000 0000 0000 0077
00 00000000 0000 0000 0000 0016

3
00 00000000 0000 0000 0000 0053
00 00000000 0000 0000 0000 0077
00 00000000 0000 0000 0000 0016

резалт: 
00 00000000 0000 0000 0000 0053 1
00 00000000 0000 0000 0000 0077 1

00 00000000 0000 0000 0000 0016 1
00 00000000 0000 0000 0000 0077 1

00 00000000 0000 0000 0000 0016 1
00 00000000 0000 0000 0000 0053 1
00 00000000 0000 0000 0000 0077 1
- Это корректный формат вывода результата? :)
- Может ли быть пропущена вторая двойка?
- "Пробелы" - где они могут быть, а где нет?


з.ы.
- Почему бы тоже самое не спросить на выше упомянутом форуме?
- Хочу всех тут достать :)
...
Рейтинг: 0 / 0
31.08.2005, 20:00
| Ответить | Цитировать | Написать  
Нужна ли программисту высшая математика???
    #33244506
NotGonnaGetUs
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
NotGonnaGetUs
Участник
пустые строки почему-то съелись :(
...
Рейтинг: 0 / 0
31.08.2005, 20:03
| Ответить | Цитировать | Написать  
Нужна ли программисту высшая математика???
    #33244602
Рыт
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рыт
Гость
Что-то я не помню каких-то особенных трудностей в этой таске.
Пустые строки важны напр. для Питона, но не для С и Паскаля.
Глянул свой код. Вот как я читал инпут:

readln(n);
for i:=0 to n-1 do begin readln(s); new(a ); a^:=s; end;
sort(0,n-1);

Т.е. читал целиком строки (как стринги), а потом квик-сортом
сортировал указатели на эти стринги. Вот ответ на твой инпут:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
00   00000000   0000   0000   0000   0053   1 
 00   00000000   0000   0000   0000   0077   1 

 00   00000000   0000   0000   0000   0016   1 
 00   00000000   0000   0000   0000   0077   1 

 00   00000000   0000   0000   0000   0016   1 
 00   00000000   0000   0000   0000   0053   1 
 00   00000000   0000   0000   0000   0077   1
...
Рейтинг: 0 / 0
31.08.2005, 22:49
| Ответить | Цитировать | Написать  
Нужна ли программисту высшая математика???
    #33244605
Рыт
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рыт
Гость
Квадратные скобки пожевались. Должно быть:

Код: plaintext
1.
2.
3.
4.
readln(n);
for i:= 0  to n- 1  do begin readln(s); new(a[i]); a[i]^:=s; end;
sort( 0 ,n- 1 );
...
Рейтинг: 0 / 0
31.08.2005, 22:52
| Ответить | Цитировать | Написать  
Нужна ли программисту высшая математика???
    #33244612
Рыт
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Рыт
Гость
Насчет твоего линка: не бери в голову.
Это я просто хотел - на дурницу - сделать эту задачу на питоне.
Но похоже они специально налепили в инпут ненужных пустых строк и/или юниксовых окончаний строк. Для питона это гроб. Или NZEC, говоря по-русски.
...
Рейтинг: 0 / 0
31.08.2005, 23:00
| Ответить | Цитировать | Написать  
25 сообщений из 83, страница 3 из 4
  3  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Нужна ли программисту высшая математика???
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]