ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Решение простой задачи. Ошибки с типизацией (вероятно)
25 сообщений из 109, страница 1 из 5
  1  все
Решение простой задачи. Ошибки с типизацией (вероятно)
    #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:21
| Ответить | Цитировать | Написать  
Решение простой задачи. Ошибки с типизацией (вероятно)
    #38828726
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
А чему у тебя равно

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


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

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

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

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

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

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

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

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


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