powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / C++ [игнор отключен] [закрыт для гостей] / Решение простой задачи. Ошибки с типизацией (вероятно)
109 сообщений из 109, показаны все 5 страниц
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38828716
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Здравствуйте.
Решал сегодня несложную задачу . Не уверен что этот алгоритм оптимален, но он такой.
Код: 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.
int isWin(long long x)
{
	while (x>2)
	{
		long double sq = sqrt((long double)x);
		long double c_sq = ceill(sq);
		if (sq == c_sq) 
			return 1;
		x -= (long long)c_sq;
	}
	if (x != 2)
		return 1;//win
	else
		return 0;//lose
}

int main()
{
	FILE* in = fopen("input.txt", "r");
	long long int t = 0;
	fscanf(in, "%llu", &t);
	fclose(in);

	FILE* out = fopen("output.txt", "w");
	fprintf(out, isWin(t)==1? "WIN" : "LOSE");
	fclose(out);
	
	return 0;
}




Задача проходит, но на 60 тесте валится. Открыл комментарии других товарищей. У них была аналогичная проблема, и они пишут друг другу что проблема в размерности, мол на 10^12 не хватает стандартного int. Но у меня эта проблема не должна вставать. Потому, скорее всего, ошибка связана с типами данных, но не могу понять где она. Подскажите пожалуйста. Если кто-то предложит оптимальный алгоритм, не буду возражать :)
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38828726
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
А чему у тебя равно

Код: plaintext
1.
2.
sizeof(long long)=?
sizeof(long double)=?
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38828766
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Этот алгоритм вообще не соответствует задаче в которой ясно сказано "оба игрока будут
придерживаться оптимальной стратегии".
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38828779
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
По условию - игрок МОЖЕТ брать от 1 до sqrt(K) камней. В этой реализации он всё время снимает
максимально-возможное число.
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38828856
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry SibiryakovЭтот алгоритм вообще не соответствует задаче в которой ясно сказано "оба игрока будут
придерживаться оптимальной стратегии".


вы уверены ? ;)
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38828859
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonПо условию - игрок МОЖЕТ брать от 1 до sqrt(K) камней. В этой реализации он всё время снимает
максимально-возможное число.

Марк, с алгоритмом всё ок. Проблема в другом. У всех висит на 60 тесте, и они пишут что проблема с тем что не хватает памяти, у меня вроде-бы всё нормально.
Сейчас шел по улице, и придумал другой алгоритм. Переоденусь и напишу
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38828860
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
нет, конечно, может быть ошибка в алгоритме. Но это менее всего вероятно, если только опечатка
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38828886
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercurymaytonПо условию - игрок МОЖЕТ брать от 1 до sqrt(K) камней. В этой реализации он всё время снимает
максимально-возможное число.

Марк, с алгоритмом всё ок. Проблема в другом. У всех висит на 60 тесте, и они пишут что проблема с тем что не хватает памяти, у меня вроде-бы всё нормально.

Саша. Ты о чём? Какая память? Где у тебя в этой функции int isWin(long long x) идёт выделение памяти?
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38828897
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Это к тому, что максимальное число 10^12~2^38, люди используют int, значит 2^32 максимум, не хватает памяти для того, чтобы хранить переменную 10^12
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38828915
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
>> SashaMercury,
Код: plaintext
1.
		long double sq = sqrt((long double)x);

хоть опприводись x к long double, sqrt умеет работать только с double, он всё равно обратно к даблу приведёт входной параметр и выходное значение тоже.
Впрочем, дело может и не в этом ))
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38828944
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Есть алгоритм Ньютона для любых чисел. В топике где я флудил по поводу primes
кажется есть реализация для int64. Но разве в этом дело?

Алгоритм-то не торт.
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38828954
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вот алгоритм в лоб, перебираю все плохие варианты. 60 тест снова летит
Код: 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.
long long find_next(long long x)
{
	long double d=1+4*x;
	long double sq_d=ceill(sqrtl(d));
	long long res=ceill((1+2*x+sq_d)/2);
	if(sq_d*sq_d==d)
		res+=1;
	return res;
}

int isWin2(long long x)
{
	for(long long s=2;s<=x;s=find_next(s))
	{
		if(x==s)
			return 0;
	}
	return 1;
}
int main()
{

	FILE* in = fopen("input.txt", "r");
	long long int t = 0;
	fscanf(in, "%llu", &t);
	fclose(in);

	FILE* out = fopen("output.txt", "w");
	fprintf(out, isWin2(t)==1? "WIN" : "LOSE");
	fclose(out);
	return 0;
}
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38828956
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonЕсть алгоритм Ньютона для любых чисел. В топике где я флудил по поводу primes
кажется есть реализация для int64. Но разве в этом дело?

Алгоритм-то не торт.

Хорошо. Сейчас всё проверю. Весь алгоритм.
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38828972
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ребята. Вы не поверите.
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38828988
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если честно, я сомневался, что в моём алгоритме присутствуют ошибки, особенно в алгоритме в лоб, с перебором всех плохих вариантов. Потому я решил воспользоваться советом неизвестного человека(это знаете, как взять конфету у чужого человека, не люблю такое), ну вот,
и там один товарищ написал
один товарищМихаил Леонидович, 21 февраля 2010 г. 15:23:41
Люди на счёт 60 теста: нужно использовать __int64 в С, а в Паскале низнаю как этот тип называется))

Я использовал этот совет
Код: 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.
#include <stdio.h>
#include <math.h>







__int64 find_next(__int64 x)
{
	long double d=1+4*x;
	long double sq_d=ceill(sqrtl(d));
	__int64 res=ceill((1+2*x+sq_d)/2);
	if(sq_d*sq_d==d)
		res+=1;
	return res;
}

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

	FILE* in = fopen("input.txt", "r");
	__int64 t = 0;
	fscanf(in, "%I64d", &t);
	fclose(in);

	FILE* out = fopen("output.txt", "w");
	fprintf(out, isWin2(t)==1? "WIN" : "LOSE");
	fclose(out);
	return 0;
}



и чтобы вы думали
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38828991
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercurymaytonЕсть алгоритм Ньютона для любых чисел. В топике где я флудил по поводу primes
кажется есть реализация для int64. Но разве в этом дело?

Алгоритм-то не торт.

Хорошо. Сейчас всё проверю. Весь алгоритм.
Ох ты и шалун. Да не надо проверять. У тебя весь код покрыт
красными лапмочками. "Warning! Sasha! WTF?!"

Код: plaintext
1.
2.
3.
4.
5.
	long double d=1+4*x; // Warning: потеря точности. 
	long double sq_d=ceill(sqrtl(d)); // Warning: потеря точности. 
	long long res=ceill((1+2*x+sq_d)/2);
	if(sq_d*sq_d==d) // Warning: попытка сравнивать два вещественных через знак ==
		res+=1;



Истинность этих формул нужно ДОКАЗЫВАТЬ в применении к этой задаче. Эта
задача абсолютно точная! Она оперирует целыми числами. Ее выхлоп - целое
число! Резолюция по решению данной задачи не приемлит никаких эпсилонов,
мантисс, экспонент и прочих явлений практической физики.
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829008
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Первый алгоритм тоже принят
Код: 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.
int isWin(__int64 x)
{
	while (x>2)
	{
		long double sq = sqrt((long double)x);
		long double c_sq = ceill(sq);
		if (sq == c_sq) 
			return 1;
		x -= (__int64)c_sq;
	}
	if (x != 2)
		return 1;//win
	else
		return 0;//lose
}

int main()
{
	FILE* in = fopen("input.txt", "r");
	__int64 t = 0;
	fscanf(in, "%I64d", &t);
	fclose(in);

	FILE* out = fopen("output.txt", "w");
	fprintf(out, isWin(t)==1? "WIN" : "LOSE");
	fclose(out);
	
	return 0;
}
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829013
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

сравнения двух вещественных согласен. А остальное всё ок, задача и её решение обоснованны на бумаге. Если вы порешает её 10 минут на листочке, у вас получится аналогичный алгоритм
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829077
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Если честно, я не понял в чём проблема.. Почему long long ему не нравится, а __int64 свет в окошке
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829094
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я так и не дождался sizeof(...) от твоего чудесного компиллятора семейства *ExpressEdition
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829105
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Да, нужно показать ход рассуждений при решении данной задачи.
Главный критерий рассуждения, есть количество монеток в куче. Все рассуждения ведутся касаемо этого числа x.

Когда победитель выиграет наверняка ? Когда количество монет в куче x будет равным 1. Значит ему нужно сделать так, чтобы количество монет стало 1. Итак, ход победившего человека последний, и этот человек съедает 1 монету.

Но у второго человека, проигравшего, ход будет предпоследний, значит победителю нужно, чтобы проигравший походил так, чтобы в куче наверняка осталось 1 монета. В каком случае в куче останется наверняка одна монета ? Если количество монет в куче будет равно 2. Итак, последний ход победитель съедает 1 монету 1 одной. Предпоследний ход, проигравший съедает 1 монету из двух.

Откручиваем события ещё назад, третий ход с конца, ход победителя, сколько должно быть монет, чтобы победитель смог наверняка оставить проигравшему 2 монеты ? Либо 4(победитель съедает 2 монеты) либо 3(победитель съедает одну монету.)

Вообщем т.д. и т.п., и такими рассуждениями мы получим вот такую таблицу, слева победитель и количество монет перед тем как он будет есть, справа проигравший. Ходы начинаются с левого нижнего угла.

1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829109
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Сейчас допишу, минута
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829118
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
1 2
3,4 5
9..11 8
13..16 12
18..21 17
23..27 22
29..33 28
35..40 34
42..47 41
49..55 48
57..64 56
66..73 65
75..83 74
85..93 84
95..104 105

и т.д и т.п
если x принадлежит левой части, то человек заведомо проиграл при правильной игре



2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829136
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Пусть левый столбец , , тогда
решаем это уравнение, и получаем перебор всех проигрышных вариантов(на решение этого уравнения основан второй алгоритм).

2 алгоритм
Код: 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.
#include <stdio.h>
#include <math.h>







__int64 find_next(__int64 x)
{
	long double d=1+4*x;
	long double sq_d=ceill(sqrtl(d));
	__int64 res=ceill((1+2*x+sq_d)/2);
	if(sq_d*sq_d==d)
		res+=1;
	return res;
}

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

	FILE* in = fopen("input.txt", "r");
	__int64 t = 0;
	fscanf(in, "%I64d", &t);
	fclose(in);

	FILE* out = fopen("output.txt", "w");
	fprintf(out, isWin2(t)==1? "WIN" : "LOSE");
	fclose(out);
	return 0;
}

...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829137
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

8 и 8 :)
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829139
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercurymayton,

8 и 8 :)а sizeof( __int64 ) ?
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829144
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercurymayton,

8 и 8 :)

Если честно, я не понял в чём проблема.. Почему long long ему не нравится, а __int64 свет в окошке
Тоесть с точки зрения компиллятора их длина одинакова. ОК.

Давай докопаемся в чём суть проблемы. Ты можешь сгенерить ассемблерный листинг для

Код: plaintext
1.
2.
long long x = 2;
__int64 y = 3;



?
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829151
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Я прошу прощения, у меня тут полная темнота, и пол монитора не работает, честно. Потому столько косяков. Ходы начинаются с правого нижнего угла
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829165
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну ок. Тогда вспомни что когда-то программеры были настоящие мужчины... и даже умели
держать в руке паяльник.

Бывай.
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829173
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton когда-то программеры были настоящие мужчины... и даже умели держать в руке паяльник. так на свет появилось НЛП
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829182
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
egorych,

тоже 8..

mayton, что-то не то он мне выдал
Код: html
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.
_main	PROC						; COMDAT
; Line 4
  00000	55		 push	 ebp
  00001	8b ec		 mov	 ebp, esp
  00003	81 ec e0 00 00
	00		 sub	 esp, 224		; 000000e0H
  00009	53		 push	 ebx
  0000a	56		 push	 esi
  0000b	57		 push	 edi
  0000c	8d bd 20 ff ff
	ff		 lea	 edi, DWORD PTR [ebp-224]
  00012	b9 38 00 00 00	 mov	 ecx, 56			; 00000038H
  00017	b8 cc cc cc cc	 mov	 eax, -858993460		; ccccccccH
  0001c	f3 ab		 rep stosd
; Line 5
  0001e	c7 45 f4 02 00
	00 00		 mov	 DWORD PTR _x$[ebp], 2
  00025	c7 45 f8 00 00
	00 00		 mov	 DWORD PTR _x$[ebp+4], 0
; Line 6
  0002c	c7 45 e4 03 00
	00 00		 mov	 DWORD PTR _y$[ebp], 3
  00033	c7 45 e8 00 00
	00 00		 mov	 DWORD PTR _y$[ebp+4], 0
; Line 7
  0003a	33 c0		 xor	 eax, eax
; Line 8
  0003c	5f		 pop	 edi
  0003d	5e		 pop	 esi
  0003e	5b		 pop	 ebx
  0003f	8b e5		 mov	 esp, ebp
  00041	5d		 pop	 ebp
  00042	c3		 ret	 0
_main	ENDP
_TEXT	ENDS
END
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829187
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Это у них на сервере скорее косяк, нежели у меня. Как бы вы решали эту задачу, аналогично ? Или по другому ? Я сегодня перед сном ещё подумаю
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829199
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну... похоже что компиллятор рассматривает 64-х битное число как структуру из двух 32х битных.
Типа

Код: plaintext
1.
2.
3.
4.
struct __int64{
   DWORD a;
   DWORD b;
}



А с квадратными корнями и с кастингом в double надо доисследовать еще.

Прошу знающих Ассемблер для VisualC прокомментировать если я ошибся.
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829204
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonДавай докопаемся в чём суть проблемы. Ты можешь сгенерить ассемблерный листинг для

Код: plaintext
1.
2.
long long x = 2;
__int64 y = 3;



?согласно вот этому - тынц , а также Сашиному листингу long long и __int64 это одно и тоже, DWORD
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829208
egorych
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
egorychDWORDдва DWORD, рука дрогнула ))
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829216
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
egorychegorychDWORDдва DWORD, рука дрогнула ))

только вторник, а она уже дрожит. Рановато :D

Вообщем да, это ведь на сервере проверяется, вероятно их косяки(видимо другой компилятор)
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829219
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Загадочный Михаил Леонидович так и остался неопровергнут. Насколько я понял
long long где-то не прокатил?

Но где?
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829230
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonЗагадочный Михаил Леонидович так и остался неопровергнут. Насколько я понял
long long где-то не прокатил?

Но где?

да, после замены всех long long на __int64 всё заработало. Видимо у какого-то компилятора проблемы с long long
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829233
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну дык... раскалывай дальше. Где заработало. На кастинге в (double) или на sqrt() ?
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829240
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonНу дык... раскалывай дальше. Где заработало. На кастинге в (double) или на sqrt() ?

уже завтра..меня гонят..спасибо всем за помощь:) Доброго времени суток
PS
может быть попробовать другой алгоритм ? но мне другие больше в голову не приходят
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829257
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryЕсли честно, я не понял в чём проблема.. Почему long long ему не нравится, а __int64 свет в окошкеЕму скорее "%llu" не нравится.
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829260
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
BarloneSashaMercuryЕсли честно, я не понял в чём проблема.. Почему long long ему не нравится, а __int64 свет в окошкеЕму скорее "%llu" не нравится.
Это мысль. Не зря один модератор говаривал - "Контрольная печать... и еще раз контрольная печать... ть вашу!"
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829265
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
1              2
3,4           5
9..11        8
13..16       12          
18..21       17
23..27       22
29..33       28
35..40       34
42..47       41
49..55       48
57..64       56
66..73       65
75..83       74
85..93       84
95..104   105

и т.д и т.п
если x принадлежит левой части, то человек заведомо проиграл при правильной игре
"Правильная игра" заключается в том, чтобы первым же ходом оставить в куче число камней из второй колонки. Всё. после этого от второго игрока уже ничего не зависит. И наоборот.

Соответственно всё решение задачи сводится к одному: проверить не находится ли полученное на вход число в ряде из правой колонки. Ты же математик, выявить закономерность этого ряда для тебя должно быть легко.
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829316
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Цугцванг. Почти.
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829733
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry SibiryakovSashaMercury
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
1              2
3,4           5
9..11        8
13..16       12          
18..21       17
23..27       22
29..33       28
35..40       34
42..47       41
49..55       48
57..64       56
66..73       65
75..83       74
85..93       84
95..104   105

и т.д и т.п
если x принадлежит левой части, то человек заведомо проиграл при правильной игре
"Правильная игра" заключается в том, чтобы первым же ходом оставить в куче число камней из второй колонки. Всё. после этого от второго игрока уже ничего не зависит. И наоборот.

Соответственно всё решение задачи сводится к одному: проверить не находится ли полученное на вход число в ряде из правой колонки. Ты же математик, выявить закономерность этого ряда для тебя должно быть легко.

Это такая шутка ?) Вы мне переобъясняете то что я объяснял ?))
тут нет правильной игры, есть количество монеток в куче до первого хода, если это количество монеток принадлежит правому столбцу, то человек делающий ход, проиграл. Рассуждаете вы не до конца правильно, а вывод правильный

Dimitry Sibiryakovвсё решение задачи сводится к одному: проверить не находится ли полученное на вход число в ряде из правой колонки

а я тут чем занимаюсь ?:D Вы точно любите пошутить )))
Dimitry SibiryakovТы же математик, выявить закономерность этого ряда для тебя должно быть легко\

Да я и написал уже о закономерности

SSПусть левый столбец , , тогда


только опечатался, говорил о правом столбце.
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829734
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonЦугцванг. Почти.

не почти, а именно цугцванг ;)
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829736
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonBarloneпропущено...
Ему скорее "%llu" не нравится.
Это мысль. Не зря один модератор говаривал - "Контрольная печать... и еще раз контрольная печать... ть вашу!"

нет, сделал сейчас lld, то-же самое, 60 тест
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829737
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Кстати, вот такие результаты до 60 теста с long long. Обратите внимание на память и время
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829738
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Хотя нет, с __int64 аналогичные. вчера вечером были намного больше по каждому пункту
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829812
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Разберись пожалуйста с типами данных в твоём компилляторе. Чесслово раздражает. Этож основы мать их так.
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829816
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,

при чём тут мой компилятор ? Программа запускается на сервере и проверяется там
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829818
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
У меня с типами данных принадлежащих классу arithmetic types проблем нет
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38829834
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну дай бох
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38830047
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryа я тут чем занимаюсь ?:DЯ не совсем уверен чем тут занимаетесь Вы, но Ваш код делает совершенно не то, о чём я говорил.

Разве ряды не вычисляются обычно от x 0 к x n ?.. Зачем Вы пытаетесь вычислить его "сверху вниз", да ещё и прибегая к сложной и неточной операции вычисления корня?
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38830297
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry SibiryakovSashaMercuryа я тут чем занимаюсь ?:DЯ не совсем уверен чем тут занимаетесь Вы, но Ваш код делает совершенно не то, о чём я говорил.

Разве ряды не вычисляются обычно от x 0 к x n ?.. Зачем Вы пытаетесь вычислить его "сверху вниз", да ещё и прибегая к сложной и неточной операции вычисления корня?

сверху вниз ? В смысле ? от 2 до x вы имеете ввиду ?
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38830330
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryВ смысле ? от 2 до x вы имеете ввиду ?
Да. Так формула получается без использования чисел с плавающей точкой и корня.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38830334
Barlone
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryнет, сделал сейчас lld, то-же самое, 60 тестТам какой-то древний компилятор, он может не понимать ll (то есть понимать как l). Вот пример какой-то древне1 документации http://www.ceng.metu.edu.tr/~ahmet/Ceng/230.20013/230.20013/Lectures/lec03.scanf.htm.html#size_prefixes
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38830341
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
и это не ряд, а последовательность. Где каждое следующее невыигрышное количество монеток зависит от предыдущего по формуле . Первый элемент, равен 2. Далее, решаем уравнение что я только написал, уравнение не самое простое, но решаемое, и получаем каждое новое значение из предыдущего

Dimitry Sibiryakov Да. Так формула получается без использования чисел с плавающей точкой и корня.

Как так ?Вот выше уравнение, решите его без корней и чисел с плавающей точкой :)
Дмитрий, я вероятно вас не понимаю. Покажите пожалуйста, как вы бы решали эту задачу, до меня с трудом доходят ваши намеки, но это скорее моя необразованность в программировании
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38830342
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
BarloneSashaMercuryнет, сделал сейчас lld, то-же самое, 60 тестТам какой-то древний компилятор, он может не понимать ll (то есть понимать как l). Вот пример какой-то древне1 документации http://www.ceng.metu.edu.tr/~ahmet/Ceng/230.20013/230.20013/Lectures/lec03.scanf.htm.html#size_prefixes

но 60 тестов как-то прошел и понял..интересно, почему так. Нужно написать их администраторам
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38830348
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Barlone,
а, понял вас. Скорее всего так и есть
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38830357
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryКак так ?Вот выше уравнение, решите его без корней и чисел с плавающей
точкой :)
Дмитрий, я вероятно вас не понимаю. Покажите пожалуйста, как вы бы решали эту задачу, до
меня с трудом доходят ваши намеки, но это скорее моя необразованность в программировании

Если я правильно угадал последовательность (всё же не математик), то будет как-то так:
Код: sql
1.
2.
3.
4.
5.
6.
7.
8.
x = 2;
for (int i = 2; i < 10000000000; i++)
   for (int j = 1; j < i; j++)
   {
     if (x == a) return "проиграл";
     if (x > a) return "выграл";
     x += i;
   }


Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38830392
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov,

а откуда тут 'a' ? Можно полностью программу пожалуйста :)
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38830690
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryа откуда тут 'a' ?
Из входного файла. Это и есть "заданное число".
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38830822
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Аналогично будет если все типы заменить на __int64
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38830823
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Второй тест, число 5
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38831225
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury, как ты тестируешь? Сравниваешь output.txt с эталонным?
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38831482
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonSashaMercury, как ты тестируешь? Сравниваешь output.txt с эталонным?

я никак не тестирую, тестирует сервер acmp.ru. Но алгоритм вероятно такой, как вы написали
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38831541
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
И ты чтобы проверить - каждый раз деплоишь исходник?
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38831548
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Код выше был изначально неправильный, и мне не требовалось загружать его на сервер чтобы проверить, но боюсь что моим выводам могли бы не поверить. Потому я его загрузил, и показал результат
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38831658
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryКод выше был изначально неправильный
Он и не претендовал на правильность. Он всего лишь показывал способ вычисления
последовательности из задачи по возрастанию, что делается быстрее и без использования
чисел с плавающей точкой.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832030
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov,

Хорошо.
Может быть кто-нибудь может предложить другой работающий способ решения задачи ?
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832060
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Здравствуйте. Вот алгоритм. Правильное, в целом подробное, решение данной задачи.
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832061
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Вот алгоритм
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832062
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Подскажите пожалуйста, как бы вы расставили типы данных в его реализации ?

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
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832063
Фотография 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
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832076
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryЗдравствуйте. Вот алгоритм. Правильное, в целом подробное, решение данной задачи.А ты уверен, что целая часть 1,414 это двойка???
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832079
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Basil A. SidorovSashaMercuryЗдравствуйте. Вот алгоритм. Правильное, в целом подробное, решение данной задачи.А ты уверен, что целая часть 1,414 это двойка???

Я ведь написал а не . Т.е. имеется ввиду потолок, а не целая часть
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832418
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
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832547
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
И никаких гвоздей корней. Круть.
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832550
Basil A. Sidorov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryТ.е. имеется ввиду потолок, а не целая частьЯ, вообще-то, про условие задачи.
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832566
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov, принята
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832574
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry Sibiryakov,
объясните, пожалуйста, ваше решение
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832581
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Basil A. SidorovSashaMercuryТ.е. имеется ввиду потолок, а не целая частьЯ, вообще-то, про условие задачи.

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

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

но это не имеет отношение к 1,414
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832626
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Пятница однако. Давайте подкидывайте пятничные задачки.
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832663
Фотография 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
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832668
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury, а зачем? Дмитрий-же предложил более простой и компактный код. И
ты вроде подтвердил что судья принял его. Значит все тесты прошли.
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832712
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
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832730
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonДмитрий-же предложил более простой и компактный код.
Он может не пройти в лимит быстродействия. Поэтому выше и расписаны варианты оптимизации.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832743
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Думаю что школа не просто так вводит limitations

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

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

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

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


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

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

PS: Я вообще не понимаю как оно работает, это чистая эмпирика.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832814
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
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832818
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry SibiryakovИли просто выбрали 12 цифр чтобы выйти за пределы точности int, но остаться в пределах
double (даже обычного, без long).
Да это мысль.
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832823
Фотография 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
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832857
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonА я по другому думал. Сашкин вариант разложить. С квадратным корнем.
Его, кстати, тоже, наверное, можно разложить. Только надо отказаться от функции sqrt и
перейти на вычитания. Но это ядрёные математические выкрутасы, мне не по зубам.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38832956
Mozok
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38833015
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Дело в том, что я тоже не понимаю как она работает, потому попросил блок-схему. Впрочем, могу сам её построить, но она не сильно поможет
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38833095
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Ну вот и потренируйся в чтении программ, тебе полезно.

Это вычисление последовательности a i =a i-1 +[sqrt(a i )], как я уже говорил ранее.
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38833681
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry SibiryakovНу вот и потренируйся в чтении программ, тебе полезно.

Это вычисление последовательности a i =a i-1 +[sqrt(a i )], как я уже говорил ранее.

я бы конечно разобрался, но меня смутило ваше сообщение о том, что и вы не понимаете. Либо я не так вас понял.

Dimitry SibiryakovSashaMercuryможно блок-схему пожалуйста ?
Чо? Какая ещё, нафиг, блок-схема для десяти строчек?.. Мы же не на первом курсе института.

PS: Я вообще не понимаю как оно работает, это чистая эмпирика.
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38833683
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryя бы конечно разобрался, но меня смутило ваше сообщение о том, что и вы
не понимаете.
И чем оно Вас смутило? Программист не обязан знать как работают его программы. Достаточно
того, что он способен заставить их работать так, как требуется.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38833684
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry SibiryakovSashaMercuryя бы конечно разобрался, но меня смутило ваше сообщение о том, что и вы
не понимаете.
И чем оно Вас смутило? Программист не обязан знать как работают его программы. Достаточно
того, что он способен заставить их работать так, как требуется.


вы горазды пошутить :D
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38833697
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercury,

Правильно все сказано. Программист чаще всего работает с интерфейсами к черным ящикам, про которые известно что они делают, но не как они это делают.
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38833705
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Anatoly Moskovsky,

так разговор не про это. А про то, что человек написал интуитивный код, и не знает как он работает. Мне это не понятно

Мы не говорим о темах связанных с инкапсуляцией. А говорим о конкретном коде, написанным автором(с кем я веду диалог)
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38834022
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
SashaMercuryчеловек написал интуитивный код, и не знает как он работает. Мне это не
понятно
Стохастические методы Вам в математике определённо встречались. В программировании они
используются тоже. Чаще всего на примитивном уровне в виде "метода тыка".
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38834041
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dimitry SibiryakovSashaMercuryчеловек написал интуитивный код, и не знает как он работает. Мне это не
понятно
Стохастические методы Вам в математике определённо встречались. В программировании они
используются тоже. Чаще всего на примитивном уровне в виде "метода тыка".

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


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