ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Решение простой задачи. Ошибки с типизацией (вероятно)
25 сообщений из 109, страница 4 из 5
  4  все
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832076
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
SashaMercuryЗдравствуйте. Вот алгоритм. Правильное, в целом подробное, решение данной задачи.А ты уверен, что целая часть 1,414 это двойка???
...
Рейтинг: 0 / 0
12.12.2014, 07:32
| Ответить | Цитировать | Написать  
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832079
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Basil A. SidorovSashaMercuryЗдравствуйте. Вот алгоритм. Правильное, в целом подробное, решение данной задачи.А ты уверен, что целая часть 1,414 это двойка???

Я ведь написал а не . Т.е. имеется ввиду потолок, а не целая часть
...
Рейтинг: 0 / 0
12.12.2014, 07:39
| Ответить | Цитировать | Написать  
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832418
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
SashaMercuryкак бы вы реализовали этот же алгоритм иначе ?
Проверяй:
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
int isWin(__int64 x)
{
  __int64 a = 0;
  for (__int64 i = 1; i<10000000; i++)
  {
   __int64 q = i*i;
   while (a < q)
   {
     a += i;
     if (a >= q) a++;
     if (a == x) return 0;
     if (a > x) return 1;
   }
  }
}


Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
12.12.2014, 13:52
| Ответить | Цитировать | Написать  
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832547
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
И никаких гвоздей корней. Круть.
...
Рейтинг: 0 / 0
12.12.2014, 15:13
| Ответить | Цитировать | Написать  
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832550
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
SashaMercuryТ.е. имеется ввиду потолок, а не целая частьЯ, вообще-то, про условие задачи.
...
Рейтинг: 0 / 0
12.12.2014, 15:16
| Ответить | Цитировать | Написать  
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832566
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dimitry Sibiryakov, принята
...
Рейтинг: 0 / 0
12.12.2014, 15:25
| Ответить | Цитировать | Написать  
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832574
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dimitry Sibiryakov,
объясните, пожалуйста, ваше решение
...
Рейтинг: 0 / 0
12.12.2014, 15:28
| Ответить | Цитировать | Написать  
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832581
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Basil A. SidorovSashaMercuryТ.е. имеется ввиду потолок, а не целая частьЯ, вообще-то, про условие задачи.

вы ведь вроде спросили
Basil A. SidorovА ты уверен, что целая часть 1,414 это двойка???

а что с условием ?
...
Рейтинг: 0 / 0
12.12.2014, 15:32
| Ответить | Цитировать | Написать  
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832603
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Basil A. Sidorov
Участник
SashaMercuryа что с условием ?А перечитать: "игрок может взять из нее от 1 до [sqrt(K)] (целую часть от квадратного корня из K)"?
...
Рейтинг: 0 / 0
12.12.2014, 15:43
| Ответить | Цитировать | Написать  
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832623
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Basil A. SidorovSashaMercuryа что с условием ?А перечитать: "игрок может взять из нее от 1 до [sqrt(K)] (целую часть от квадратного корня из K)"?

но это не имеет отношение к 1,414
...
Рейтинг: 0 / 0
12.12.2014, 15:51
| Ответить | Цитировать | Написать  
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832626
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Пятница однако. Давайте подкидывайте пятничные задачки.
...
Рейтинг: 0 / 0
12.12.2014, 15:52
| Ответить | Цитировать | Написать  
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832663
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
mayton, ещё эту никто не решил :)
SashaMercuryПодскажите пожалуйста, как бы вы расставили типы данных в его реализации ?

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
T find_next(__int64 x)
{
	T sq_d = sqrtl(4 * x + 1);
	T res = floorl(((2 * x + 1 + sq_d) / 2)) + 1;
	return res;
}

int isWin(__int64 x)
{
	for (__int64 s = 2; s <= x; s = find_next(s))
	{
		if (x == s)
			return 0;
	}
	return 1;
}


Либо как бы вы реализовали этот же алгоритм иначе ?
...
Рейтинг: 0 / 0
12.12.2014, 16:09
| Ответить | Цитировать | Написать  
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832668
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
SashaMercury, а зачем? Дмитрий-же предложил более простой и компактный код. И
ты вроде подтвердил что судья принял его. Значит все тесты прошли.
...
Рейтинг: 0 / 0
12.12.2014, 16:11
| Ответить | Цитировать | Написать  
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832712
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
SashaMercuryобъясните, пожалуйста, ваше решение
Эта функция вычисляет последовательность вплоть до члена равного заданному числу или
превышающего его.

Возможные пути оптимизации:
1) Предвычисление и использование массива всех членов ряда
2) Предвычисление и использование массива каждого N-ого члена ряда
3) Анализ последовательности на предмет вывода формулы, позволяющей вычислить
a n как f(n).

Вариант 1 для диапазона 10^12 ориентировочно потребует 16мб памяти, что не уложится в
лимит, но обеспечит высокое быстродействие.
Вариант 3 идеален, но маловероятен.
Вариант 2 - разумный компромисс.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
12.12.2014, 16:25
| Ответить | Цитировать | Написать  
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832730
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
maytonДмитрий-же предложил более простой и компактный код.
Он может не пройти в лимит быстродействия. Поэтому выше и расписаны варианты оптимизации.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
12.12.2014, 16:33
| Ответить | Цитировать | Написать  
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832743
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Думаю что школа не просто так вводит limitations

Входной файл INPUT.TXT содержит натуральное число N – число камней в кучке (N <= 10^12).
Скорее всего они допускают что участники хитрят и могут на низкой разрядности
выдавить из ничего - "нечто".

А на каком месте исходник Дмитрия? По скорости.
...
Рейтинг: 0 / 0
12.12.2014, 16:41
| Ответить | Цитировать | Написать  
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832758
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
maytonСкорее всего они допускают что участники хитрят и могут на низкой разрядности
выдавить из ничего - "нечто".
Или просто выбрали 12 цифр чтобы выйти за пределы точности int, но остаться в пределах
double (даже обычного, без long).
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
12.12.2014, 16:51
| Ответить | Цитировать | Написать  
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832761
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dimitry SibiryakovSashaMercuryобъясните, пожалуйста, ваше решение
Эта функция вычисляет последовательность вплоть до члена равного заданному числу или
превышающего его.

Возможные пути оптимизации:
1) Предвычисление и использование массива всех членов ряда
2) Предвычисление и использование массива каждого N-ого члена ряда
3) Анализ последовательности на предмет вывода формулы, позволяющей вычислить
a n как f(n).

Вариант 1 для диапазона 10^12 ориентировочно потребует 16мб памяти, что не уложится в
лимит, но обеспечит высокое быстродействие.
Вариант 3 идеален, но маловероятен.
Вариант 2 - разумный компромисс.


можно блок-схему пожалуйста ? Я так понял, уравнение для решения этой задачи вам вообще не потребовалось ?

Марк, скорость лучше чем у меня, по местам касаемо скорости нет выборки. По памяти пишет 56Кб
...
Рейтинг: 0 / 0
12.12.2014, 16:54
| Ответить | Цитировать | Написать  
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832764
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
На планке в 10^17 отпал бы double и началась бы веселуха, поскольку, судя по __int64,
компилятором у них работает BCC в котором нет long double.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
12.12.2014, 16:54
| Ответить | Цитировать | Написать  
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832779
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
SashaMercuryможно блок-схему пожалуйста ?
Чо? Какая ещё, нафиг, блок-схема для десяти строчек?.. Мы же не на первом курсе института.

PS: Я вообще не понимаю как оно работает, это чистая эмпирика.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
12.12.2014, 17:00
| Ответить | Цитировать | Написать  
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832814
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Кстати, ещё немного бреда и из процедуры исчезает умножение. Быстродействие повышается:
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
int isWin(__int64 x)
{
  __int64 a = 0;
  __int64 q = 1;
  for (__int64 i = 1; i<10000000;)
  {
   while (a < q)
   {
     a += i;
     if (a >= q) a++;
     if (a == x) return 0;
     if (a > x) return 1;
   }
   q += i;
   q += ++i;
  }
}


Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
12.12.2014, 17:26
| Ответить | Цитировать | Написать  
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832818
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dimitry SibiryakovИли просто выбрали 12 цифр чтобы выйти за пределы точности int, но остаться в пределах
double (даже обычного, без long).
Да это мысль.
...
Рейтинг: 0 / 0
12.12.2014, 17:29
| Ответить | Цитировать | Написать  
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832823
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Dimitry SibiryakovКстати, ещё немного бреда и из процедуры исчезает умножение. Быстродействие повышается:
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
int isWin(__int64 x)
{
  __int64 a = 0;
  __int64 q = 1;
  for (__int64 i = 1; i<10000000;)
  {
   while (a < q)
   {
     a += i;
     if (a >= q) a++;
     if (a == x) return 0;
     if (a > x) return 1;
   }
   q += i;
   q += ++i;
  }
}



Старик Брезенхейм смахнул слезу. А я по другому думал. Сашкин вариант разложить. С квадратным корнем.
...
Рейтинг: 0 / 0
12.12.2014, 17:36
| Ответить | Цитировать | Написать  
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832857
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
maytonА я по другому думал. Сашкин вариант разложить. С квадратным корнем.
Его, кстати, тоже, наверное, можно разложить. Только надо отказаться от функции sqrt и
перейти на вычитания. Но это ядрёные математические выкрутасы, мне не по зубам.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
12.12.2014, 18:09
| Ответить | Цитировать | Написать  
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832956
Mozok
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Mozok
Участник
Dimitry Sibiryakov,

все уже украдено до нас .
...
Рейтинг: 0 / 0
12.12.2014, 21:18
| Ответить | Цитировать | Написать  
25 сообщений из 109, страница 4 из 5
  4  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Решение простой задачи. Ошибки с типизацией (вероятно)
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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