Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Архив ПТ Новый топик    Ответить
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 105 106 107 108 109 110 [111] 112 113 114   вперед  Ctrl
 Re: С++?  [new]
rt555
Member [заблокирован]

Откуда:
Сообщений: 446
clihlt
А вот это ? Я хз с какой стороны тут подойти
http://www.spoj.pl/problems/RUNAWAY/

Я просто подзабыл.
Кажется, я собирался делать триангуляцию Делоне (с подачи мембера White Owl'а, если не ошибаюсь).
Да плюнул. Там слишком много мороки. В архиве есть очень приятный экзешничек. Рекомендую
накликать точек и увидеть что есть такое эта триангуляция.

Сам код триангуляции тоже впечатляет.

К сообщению приложен файл (Delaunay_VB.zip - 17Kb) cкачать
2 фев 08, 08:19    [5235963]     Ответить | Цитировать Сообщить модератору
 Re: С++?  [new]
rt555
Member [заблокирован]

Откуда:
Сообщений: 446
clihlt
Балин... Где взять файл с описанием большого такого графа?
Чото изобретать граф на 5тыс вершин из головы както не очень хочется ))

да зачем 5тысяч?
простеньких тестов с малым количеством вершин (штук 10-20) будет достаточно
2 фев 08, 08:21    [5235965]     Ответить | Цитировать Сообщить модератору
 Re: С++?  [new]
rt555
Member [заблокирован]

Откуда:
Сообщений: 446
млин... похоже, я вчера опять здесь паясничал; хосподи, да когда же это кончится? тварь
2 фев 08, 08:24    [5235966]     Ответить | Цитировать Сообщить модератору
 Re: С++?  [new]
MasterZiv
Member

Откуда: Питер
Сообщений: 33541
Не задрало вас еще клавиатуру долбать ?
3 фев 08, 20:25    [5238136]     Ответить | Цитировать Сообщить модератору
 Re: С++?  [new]
rt555
Member [заблокирован]

Откуда:
Сообщений: 446
хихихи........ Руби, Жаба и Плюсы опять отдыхают: http://www.spoj.pl/ranks/ACFRAC/ первый нах!
3 фев 08, 21:08    [5238244]     Ответить | Цитировать Сообщить модератору
 Re: С++?  [new]
mayton
Member

Откуда: loopback
Сообщений: 35682
rt555
Да плюнул. Там слишком много мороки. В архиве есть очень приятный экзешничек. Рекомендую накликать точек и увидеть что есть такое эта триангуляция.

Иш ты... красиво. Душевено. А я над поиском кратчайшего пути в графе думал. Я имею в виду не канонический алгоритм всяких там Кнутов и Дейкстр. А что-нибудь более серъезное. На пару тысяч вершин (рёбер). Пускай даже и не находит самый короткий путь. Зато сколько направлений оптимизации - ммм.... красота.
3 фев 08, 21:09    [5238246]     Ответить | Цитировать Сообщить модератору
 Re: С++?  [new]
rt555
Member [заблокирован]

Откуда:
Сообщений: 446
мейтон, покажи им кузькину мать: http://www.spoj.pl/ranks/SHPATH/

10000 вершин !! тайм лимит = 5с !!
3 фев 08, 21:35    [5238302]     Ответить | Цитировать Сообщить модератору
 Re: С++?  [new]
mayton
Member

Откуда: loopback
Сообщений: 35682
Впечатляет. А исходник на этом сайте дадут посмотреть?
3 фев 08, 21:42    [5238314]     Ответить | Цитировать Сообщить модератору
 Re: С++?  [new]
rt555
Member [заблокирован]

Откуда:
Сообщений: 446
mayton
Впечатляет. А исходник на этом сайте дадут посмотреть?

низашто :)
3 фев 08, 23:45    [5238540]     Ответить | Цитировать Сообщить модератору
 Re: С++?  [new]
Penkov Vladimir
Member

Откуда: Moscow
Сообщений: 8132
rt555
мейтон, покажи им кузькину мать: http://www.spoj.pl/ranks/SHPATH/

10000 вершин !! тайм лимит = 5с !!


гы, паскаль - 2,4 метра и 0,85 сек. ява - 219 метров, 4,61 сек.
3 фев 08, 23:48    [5238547]     Ответить | Цитировать Сообщить модератору
 Re: С++?  [new]
mayton
Member

Откуда: loopback
Сообщений: 35682
rt555
mayton
Впечатляет. А исходник на этом сайте дадут посмотреть?

низашто :)


Абыдна да? (с) Грюзин
4 фев 08, 00:08    [5238567]     Ответить | Цитировать Сообщить модератору
 Re: С++?  [new]
Программизд 02
Member

Откуда: дедофорум
Сообщений: 232416
Deady
rt555
мейтон, покажи им кузькину мать: http://www.spoj.pl/ranks/SHPATH/

10000 вершин !! тайм лимит = 5с !!


гы, паскаль - 2,4 метра и 0,85 сек. ява - 219 метров, 4,61 сек.


Отрадно. А то достали уже эти фанаты "самой быстрой" явы.
4 фев 08, 00:15    [5238569]     Ответить | Цитировать Сообщить модератору
 Re: С++?  [new]
mayton
Member

Откуда: loopback
Сообщений: 35682
Deady
rt555
мейтон, покажи им кузькину мать: http://www.spoj.pl/ranks/SHPATH/

10000 вершин !! тайм лимит = 5с !!


гы, паскаль - 2,4 метра и 0,85 сек. ява - 219 метров, 4,61 сек.


Бьюсь об заклад - Паскалист насовал туда ассеблерных вставок.
4 фев 08, 00:21    [5238570]     Ответить | Цитировать Сообщить модератору
 Re: С++?  [new]
JibSkeart
Member

Откуда: Из далекой галактики
Сообщений: 19873
mayton
Deady
rt555
мейтон, покажи им кузькину мать: http://www.spoj.pl/ranks/SHPATH/

10000 вершин !! тайм лимит = 5с !!


гы, паскаль - 2,4 метра и 0,85 сек. ява - 219 метров, 4,61 сек.


Бьюсь об заклад - Паскалист насовал туда ассеблерных вставок.


а может Дейкстра помог ?
хотя, я может не так понял тему задачку про вершины ?
4 фев 08, 00:24    [5238571]     Ответить | Цитировать Сообщить модератору
 Re: С++?  [new]
JibSkeart
Member

Откуда: Из далекой галактики
Сообщений: 19873
ибо по алгоритму Дейкстры, у меня кратчайший путь при 300*300 вершин искался просто меньше чем за секунду
4 фев 08, 00:25    [5238572]     Ответить | Цитировать Сообщить модератору
 Re: С++?  [new]
Penkov Vladimir
Member

Откуда: Moscow
Сообщений: 8132
Программизд 02

Отрадно. А то достали уже эти фанаты "самой быстрой" явы.

как то странно они яву запускают. такое ощущение, что все время уходит на ввод-вывод.
я 11ую задачу решил сначала рекурсией, потом циклом в отдельном методе (ускорение в 2 раза), потом циклом без отдельного метода (ускорение в 3 раза по сравнению с рекурсией). а у них я продвинулся всего с 2,07 сек до 2,03 сек.

мои результаты в наносекундах (для числа 8735373):


Running Main
2183837 for 10203ns
2183837 for 4684ns
2183837 for 2964ns

ускорение видно невооруженным взглядом.
4 фев 08, 11:18    [5239620]     Ответить | Цитировать Сообщить модератору
 Re: С++?  [new]
rt555
Member [заблокирован]

Откуда:
Сообщений: 446
В 2-3 раза быстрее? Не может быть. Ты можешь в своем коде оставить только чтение и
посмотреть время.
Я на пасе таску http://www.spoj.pl/problems/MATRIOSH/ тоже сделал сначала рекурсией,
а потом циклом, но никакой разницы во времени не заметил (я ее и не ожидал увидеть).

Кстати, рекомендую. Просто приятная задача. Прилагаю входной dataset (1.67мб), с ответами.

К сообщению приложен файл (matriosh.zip - 26Kb) cкачать
4 фев 08, 12:31    [5240187]     Ответить | Цитировать Сообщить модератору
 Re: С++?  [new]
rt555
Member [заблокирован]

Откуда:
Сообщений: 446
mayton
... Бьюсь об заклад - Паскалист насовал туда ассеблерных вставок.

Самая загадочная страница об Паскале: http://www.spoj.pl/ranks/ALIENS/ прям тайна..
4 фев 08, 12:36    [5240235]     Ответить | Цитировать Сообщить модератору
 Re: С++?  [new]
Penkov Vladimir
Member

Откуда: Moscow
Сообщений: 8132
rt555
В 2-3 раза быстрее? Не может быть. Ты можешь в своем коде оставить только чтение и
посмотреть время.


это точно связано в чтением.

мой первый вариант:
public class Main {
	
	public static void main(String[] args) throws java.lang.Exception {
		int a, ch, res3;
		java.io.BufferedReader r = new java.io.BufferedReader(new java.io.InputStreamReader (System.in));
		String s=r.readLine();
		int count = Integer.parseInt(s);
		for (int i=0; i<count; i++) {
			a = Integer.parseInt(r.readLine());
			//алгоритм
			System.out.println(res3);
		}
 
	}
}  
2.03 сек

2ой вариант:
import java.util.*; 
import java.io.*;
 
public class Main {
	
	public static void main(String[] args) throws java.lang.Exception {
		int a, ch, res3;
		Scanner cin = new Scanner(System.in);
		int count = cin.nextInt();
		for (int i=0; i<count; i++) {
			a = cin.nextInt();
			//алгоритм
			System.out.println(res3);
		}
 
	}
}  

3.96 сек.

алгоритм в обоих случаях одинаковый
4 фев 08, 12:42    [5240271]     Ответить | Цитировать Сообщить модератору
 Re: С++?  [new]
Penkov Vladimir
Member

Откуда: Moscow
Сообщений: 8132
rt555

Я на пасе таску http://www.spoj.pl/problems/MATRIOSH/ тоже сделал сначала рекурсией,
а потом циклом, но никакой разницы во времени не заметил (я ее и не ожидал увидеть).

Кстати, рекомендую. Просто приятная задача. Прилагаю входной dataset (1.67мб), с ответами.


я не въехал в условие. что означают отрицательные числа?
4 фев 08, 13:06    [5240472]     Ответить | Цитировать Сообщить модератору
 Re: С++?  [new]
rt555
Member [заблокирован]

Откуда:
Сообщений: 446
-k -- это левая граница любой матрешки, k>0

+k -- это правая граница

(-100         (-80   (-50 +50)   (-25 +25)   +80)           (-10    +10)           +100)

в матрешке №100 сидят две меньшие матрешки: №80 и №10

а в матрешке №80 -- матрешки №50 и №25

100 > 80 + 10
и
80 > 50 +25

значит это правильная матрьйёшко
4 фев 08, 13:31    [5240662]     Ответить | Цитировать Сообщить модератору
 Re: С++?  [new]
rt555
Member [заблокирован]

Откуда:
Сообщений: 446
Deady

хочешь впасть в истерику? тогда присоединяйся: http://www.spoj.pl/status/MKMONEY/
Я такого еще не видел; хотя.. хоть задача ваще элементарная, но нервы может попортить будь здоров.
Я сам на ней получил 3 wrong answers.
7 фев 08, 10:53    [5255758]     Ответить | Цитировать Сообщить модератору
 Re: С++?  [new]
Penkov Vladimir
Member

Откуда: Moscow
Сообщений: 8132
rt555
Deady

хочешь впасть в истерику? тогда присоединяйся: http://www.spoj.pl/status/MKMONEY/
Я такого еще не видел; хотя.. хоть задача ваще элементарная, но нервы может попортить будь здоров.
Я сам на ней получил 3 wrong answers.


я ее еще не проверял у judge, но тестовая версия дает правильные результаты на тех примерах, что приведены в тексте задачи. единственное, формат у них кривой, надо педалировать.
Compiling Main.java

Note: Main.java uses or overrides a deprecated API.
Note: Recompile with -Xlint:deprecation for details.

Running Main
100.00 6.00 1
07.02.2008 11:36:36 Main main
INFO: inc=10000, prcPerPeriod=0.06, count=1
07.02.2008 11:36:36 Main main
INFO: 1: current deposit=10600(added for this period: 600)
07.02.2008 11:36:36 Main main
[b]INFO: Case 1. $100 at 6% APR compounded 1 times yields $106[/b]
100.00 6.00 12
07.02.2008 11:36:49 Main main
INFO: inc=10000, prcPerPeriod=0.0050, count=12
07.02.2008 11:36:49 Main main
INFO: 1: current deposit=10050(added for this period: 50)
07.02.2008 11:36:49 Main main
INFO: 2: current deposit=10100(added for this period: 50)
07.02.2008 11:36:49 Main main
INFO: 3: current deposit=10150(added for this period: 50)
07.02.2008 11:36:49 Main main
INFO: 4: current deposit=10200(added for this period: 50)
07.02.2008 11:36:49 Main main
INFO: 5: current deposit=10251(added for this period: 51)
07.02.2008 11:36:49 Main main
INFO: 6: current deposit=10302(added for this period: 51)
07.02.2008 11:36:49 Main main
INFO: 7: current deposit=10353(added for this period: 51)
07.02.2008 11:36:49 Main main
INFO: 8: current deposit=10404(added for this period: 51)
07.02.2008 11:36:49 Main main
INFO: 9: current deposit=10456(added for this period: 52)
07.02.2008 11:36:49 Main main
INFO: 10: current deposit=10508(added for this period: 52)
07.02.2008 11:36:49 Main main
INFO: 11: current deposit=10560(added for this period: 52)
07.02.2008 11:36:49 Main main
INFO: 12: current deposit=10612(added for this period: 52)
07.02.2008 11:36:49 Main main
[b]INFO: Case 2. $100 at 6% APR compounded 12 times yields $106,12[/b]
1000.00 6.00 12
07.02.2008 11:36:58 Main main
INFO: inc=100000, prcPerPeriod=0.0050, count=12
07.02.2008 11:36:58 Main main
INFO: 1: current deposit=100500(added for this period: 500)
07.02.2008 11:36:58 Main main
INFO: 2: current deposit=101002(added for this period: 502)
07.02.2008 11:36:58 Main main
INFO: 3: current deposit=101507(added for this period: 505)
07.02.2008 11:36:58 Main main
INFO: 4: current deposit=102014(added for this period: 507)
07.02.2008 11:36:58 Main main
INFO: 5: current deposit=102524(added for this period: 510)
07.02.2008 11:36:58 Main main
INFO: 6: current deposit=103036(added for this period: 512)
07.02.2008 11:36:58 Main main
INFO: 7: current deposit=103551(added for this period: 515)
07.02.2008 11:36:58 Main main
INFO: 8: current deposit=104068(added for this period: 517)
07.02.2008 11:36:58 Main main
INFO: 9: current deposit=104588(added for this period: 520)
07.02.2008 11:36:58 Main main
INFO: 10: current deposit=105110(added for this period: 522)
07.02.2008 11:36:58 Main main
INFO: 11: current deposit=105635(added for this period: 525)
07.02.2008 11:36:58 Main main
INFO: 12: current deposit=106163(added for this period: 528)
07.02.2008 11:36:58 Main main
[b]INFO: Case 3. $1 000 at 6% APR compounded 12 times yields $1 061,63[/b]

хотя я циклом решил, думаю он в тайм лимит не уложится )))
7 фев 08, 11:40    [5256251]     Ответить | Цитировать Сообщить модератору
 Re: С++?  [new]
rt555
Member [заблокирован]

Откуда:
Сообщений: 446
уложится
7 фев 08, 17:10    [5259172]     Ответить | Цитировать Сообщить модератору
 Re: С++?  [new]
rt555
Member [заблокирован]

Откуда:
Сообщений: 446
тэк-с, один WA уже есть; ждем следующий ...

1300389    2008-02-07 15:29:50     deady    Making Money    wrong answer     0.32     221M     JAVA  
7 фев 08, 17:32    [5259343]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: Ctrl  назад   1 .. 105 106 107 108 109 110 [111] 112 113 114   вперед  Ctrl
Все форумы / Архив ПТ Ответить