Гость
Войти | Профиль | Очистить
Целевая тема:
Создать новую тему:
Автор:
Действия ...
Форумы / C++ [игнор отключен] [закрыт для гостей] / Решение простой задачи. Ошибки с типизацией (вероятно) / 25 сообщений из 109, страница 1 из 5
  1  все
09.12.2014, 11:21
    #38828716
SashaMercury
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
| Ответить | Цитировать | Написать  
09.12.2014, 11:29
    #38828726
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение простой задачи. Ошибки с типизацией (вероятно)
А чему у тебя равно

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


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

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

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

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

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

Алгоритм-то не торт.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
09.12.2014, 14:04
    #38828954
SashaMercury
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
| Ответить | Цитировать | Написать  
09.12.2014, 14:04
    #38828956
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение простой задачи. Ошибки с типизацией (вероятно)
maytonЕсть алгоритм Ньютона для любых чисел. В топике где я флудил по поводу primes
кажется есть реализация для int64. Но разве в этом дело?

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

Хорошо. Сейчас всё проверю. Весь алгоритм.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
09.12.2014, 14:12
    #38828972
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение простой задачи. Ошибки с типизацией (вероятно)
Ребята. Вы не поверите.
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
09.12.2014, 14:18
    #38828988
SashaMercury
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
| Ответить | Цитировать | Написать  
09.12.2014, 14:19
    #38828991
mayton
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
| Ответить | Цитировать | Написать  
09.12.2014, 14:27
    #38829008
SashaMercury
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
| Ответить | Цитировать | Написать  
09.12.2014, 14:29
    #38829013
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение простой задачи. Ошибки с типизацией (вероятно)
mayton,

сравнения двух вещественных согласен. А остальное всё ок, задача и её решение обоснованны на бумаге. Если вы порешает её 10 минут на листочке, у вас получится аналогичный алгоритм
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
09.12.2014, 15:13
    #38829077
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение простой задачи. Ошибки с типизацией (вероятно)
Если честно, я не понял в чём проблема.. Почему long long ему не нравится, а __int64 свет в окошке
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
09.12.2014, 15:28
    #38829094
mayton
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение простой задачи. Ошибки с типизацией (вероятно)
Я так и не дождался sizeof(...) от твоего чудесного компиллятора семейства *ExpressEdition
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
09.12.2014, 15:36
    #38829105
SashaMercury
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
| Ответить | Цитировать | Написать  
09.12.2014, 15:37
    #38829109
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение простой задачи. Ошибки с типизацией (вероятно)
Сейчас допишу, минута
...
Рейтинг: 0 / 0
| Ответить | Цитировать | Написать  
09.12.2014, 15:41
    #38829118
SashaMercury
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
| Ответить | Цитировать | Написать  
09.12.2014, 15:53
    #38829136
SashaMercury
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
| Ответить | Цитировать | Написать  
09.12.2014, 15:55
    #38829137
SashaMercury
SashaMercury
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Решение простой задачи. Ошибки с типизацией (вероятно)
mayton,

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


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