ReSQL.ru
     
powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / C++ [игнор отключен] [закрыт для гостей] / Решение одной задачи
25 сообщений из 76, страница 2 из 4
  2  все
Решение одной задачи
    #38916853
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
Dima TМой вариант
А, чёрт, точно, я не учёл, что один множитель может повторяться.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
25.03.2015, 18:00
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916886
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Dimitry SibiryakovDima TМой вариант
А, чёрт, точно, я не учёл, что один множитель может повторяться.

еще не учел что всего один множитель может быть (sqrt(a) не в тему)
...
Рейтинг: 0 / 0
25.03.2015, 18:45
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916887
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Можно наверное из цикла выскочить раньше.
...
Рейтинг: 0 / 0
25.03.2015, 18:48
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916888
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
Dimitry Sibiryakovя не учёл, что один множитель может повторяться.

Хотя я тоже лишнее написал:
Код: plaintext
1.
i = 0;


достаточно что i++ не выполняется.
...
Рейтинг: 0 / 0
25.03.2015, 18:49
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38916892
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonМожно наверное из цикла выскочить раньше.
Вроде нет. Крайние варианты (1,7) = 7 и (1,8) = 6
...
Рейтинг: 0 / 0
25.03.2015, 18:54
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917155
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima TSashaMercuryНапример, недавно я увидел код Дмитрия следующего вида
Код: plaintext
1.
2.
3.
	while (smth){
		smth do;
	}



И хотя ранее, я никогда не использовал такую стилистику в своём коде, мне понравилось, потому что я увидел как это выглядит. А теперь использую. Вот и сейчас захотел посмотреть :)
Это основы. Причем любого языка, а не только С. Три вида циклов: for(), while() и do ... while()
Если плохо понимаешь как они работают - потрать время на изучение.



Дима, да при чём тут основы с циклами, стилистика со скобками понравилась, я ведь написал
Ранее, меня беспокоил такой код
Код: plaintext
1.
2.
3.
4.
while(smth)
{
   smth do;//1 строка
}


но я увидел у тебя
Код: plaintext
1.
2.
3.
while(smth) {
   smth do;//1 строка
}


и мне понравилось


И да, я знаю что можно так
Код: plaintext
1.
2.
3.
while(smth) 
   smth do;//1 строка



но мне не нравится :)
...
Рейтинг: 0 / 0
26.03.2015, 01:41
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917156
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima T
SSБесконечного цикла, как мне кажется, быть не должно..
А если подумать головой? Не буду подсказывать, сам догадайся.


не должно быть бесконечного цикла никогда. Он может быть только если на входе 0, этот вариант отсекается
...
Рейтинг: 0 / 0
26.03.2015, 01:46
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917164
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Простых чисел порядка 80000, не очень удобно будет хранить их таким образом (в коде программы)
...
Рейтинг: 0 / 0
26.03.2015, 02:08
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917166
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
SashaMercuryПростых чисел порядка 80000, не очень удобно будет хранить их таким образом (в коде программы)

можно генерировать, это не проблема конечно
...
Рейтинг: 0 / 0
26.03.2015, 02:09
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917198
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryДима, да при чём тут основы с циклами, стилистика со скобками понравилась, я ведь написал
Так и упоминул бы сразу про скобки, я про эту мелочь и не подумал, нафантазировал непонятно чего :)

Так код компактнее, меньше строк со скобками. Вопрос из серии "На вкус и цвет ...".

SashaMercuryИ да, я знаю что можно так
Код: plaintext
1.
2.
3.
while(smth) 
   smth do;//1 строка



но мне не нравится :)
И правильно, не надо так писать, накосячить легко, добавишь так строчку
Код: plaintext
1.
2.
3.
4.
while(smth) 
   smth do;//1 строка
   smth do2;//+1 строка


и визуально кажется что в цикл добавил, а реально за него.
Поэтому без скобок только так
Код: plaintext
1.
while(smth) smth do;


правда так дебагером отлаживать неудобно.
SashaMercuryне должно быть бесконечного цикла никогда. Он может быть только если на входе 0, этот вариант отсекается
Так и не понял чтоли? Если на входе 0, то твой цикл начнет выполнятся и зациклится, если не 0, то цикл не будет выполнятся. Т.к. у тебя на входе 0 быть не может (из-за предварительных проверок), то код в цикле никогда не выполнится. Зачем он тогда написан?
...
Рейтинг: 0 / 0
26.03.2015, 07:17
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917204
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercurySashaMercuryПростых чисел порядка 80000, не очень удобно будет хранить их таким образом (в коде программы)

можно генерировать, это не проблема конечно
Можно, только зачем? Если известно что они нужны, в итоге те же 80000 будут вычислены, просто при каждом запуске проги будет теряться время на этот бесполезный расчет.

Можешь скомбинировать для универсальности: первые брать из массива, как потребуется больше - считать.
...
Рейтинг: 0 / 0
26.03.2015, 07:32
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917231
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima TТ.к. у тебя на входе 0 быть не может (из-за предварительных проверок), то код в цикле никогда не выполнится. Зачем он тогда написан?

Почему код в цикле никогда не выполнится ? Например 8/1=8. Цикл выполнится трижды 8->4, 4->2, 2->1
...
Рейтинг: 0 / 0
26.03.2015, 08:26
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917243
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Я кажется не то написал.. Там должно быть .rem, как у меня тогда до 8 теста программа дошла. Прошу прощение
...
Рейтинг: 0 / 0
26.03.2015, 08:32
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917244
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
А я думаю, что такое, что там не понятного в том цикле :D
...
Рейтинг: 0 / 0
26.03.2015, 08:33
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917252
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryЯ кажется не то написал..
Я на это и намекал :)

SashaMercuryкак у меня тогда до 8 теста программа дошла.
Отлаживать надо лучше. Придумывай нехорошие варианты. Смотри как отработает.
Вот мой набор:
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
(1,1)=0
(-2,-6)=3
(1,8)=6
(2,5)=-1
(1,5)=5
(5,0)=-1
(0,5)=-1
(3,15)=5
(0,0)=0
(2,2)=0
(2,-2)=-1
...
Рейтинг: 0 / 0
26.03.2015, 08:40
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917273
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Код: plaintext
1.
2.
3.
4.
5.
6.
	for (int i = 1; i < 90; ++i)
	{
		int res1=count_op_from_Dima(i, 1);
		int res2=count_op(i, 1);
		printf("%3i   %3i   %3i   %3i\n", i, res1, res2, res1 - res2);
	}


Мой алгоритм не оптимальный


 
1 0 0 0
2 2 2 0
3 3 3 0
4 4 4 0
5 5 5 0
6 5 5 0
7 7 7 0
8 6 6 0
9 6 9 -3
10 7 7 0
11 11 11 0
12 7 7 0
13 13 13 0
14 9 9 0
15 8 15 -7
16 8 8 0
17 17 17 0
18 8 11 -3
19 19 19 0
20 9 9 0
21 10 21 -11
22 13 13 0
23 23 23 0
24 9 9 0
25 10 25 -15
26 15 15 0
27 9 27 -18
28 11 11 0
29 29 29 0
30 10 17 -7
31 31 31 0
32 10 10 0
33 14 33 -19
34 19 19 0
35 12 35 -23
36 10 13 -3
37 37 37 0
38 21 21 0
39 16 39 -23
40 11 11 0
41 41 41 0
42 12 23 -11
43 43 43 0
44 15 15 0
45 11 45 -34
46 25 25 0
47 47 47 0
48 11 11 0
49 14 49 -35
50 12 27 -15
51 20 51 -31
52 17 17 0
53 53 53 0
54 11 29 -18
55 16 55 -39
56 13 13 0
57 22 57 -35
58 31 31 0
59 59 59 0
60 12 19 -7
61 61 61 0
62 33 33 0
63 13 63 -50
64 12 12 0
65 18 65 -47
66 16 35 -19
67 67 67 0
68 21 21 0
69 26 69 -43
70 14 37 -23
71 71 71 0
72 12 15 -3
73 73 73 0
74 39 39 0
75 13 75 -62
76 23 23 0
77 18 77 -59
78 18 41 -23
79 79 79 0
80 13 13 0
81 12 81 -69
82 43 43 0
83 83 83 0
84 14 25 -11
85 22 85 -63
86 45 45 0
87 32 87 -55
88 17 17 0
89 89 89 0
...
Рейтинг: 0 / 0
26.03.2015, 08:58
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917284
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryМой алгоритм не оптимальный
Ожидаемо, ты же только два простых числа взял (1 и 2), совпали только варианты где частное раскладывается на X или X*2^N, где X простое.
3*3 уже не обработалось.
...
Рейтинг: 0 / 0
26.03.2015, 09:08
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917296
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
maytonМожно наверное из цикла выскочить раньше.
Точно, можно, достаточно таблицы до sqrt(10^9) если не путаю

Саша допиливай идею :)
...
Рейтинг: 0 / 0
26.03.2015, 09:21
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917343
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Dima TmaytonМожно наверное из цикла выскочить раньше.
Точно, можно, достаточно таблицы до sqrt(10^9) если не путаю

Саша допиливай идею :)

У меня осталось полчаса сегодня. Вечером компьютера не будет( Сейчас попробую
...
Рейтинг: 0 / 0
26.03.2015, 09:57
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917364
Фотография 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.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
#include <stdio.h>
#include <math.h>

int isPrime(int x)
{
	if (x == 1)    return 0;
	for (int i = 2; i <= (int)sqrt((float)x); ++i){
		if (x%i == 0)    return 0;
	}
	return 1;
}

int get_next_prime(int cur_pr)
{
	while (1){
		if (isPrime(++cur_pr))   return cur_pr;
	}
}

int count_op_from_Dima(int y, int x)
{
	if (x == y) return 0;
	if (x == 0 || y % x != 0) return -1;
	int a = y / x;
	if (a <= 0) return -1;

	int pr = 2;
	int result = 0;
	while (a > 1) {
		if (a % pr == 0) {
			a /= pr;
			result += pr;
		}
		else {
			pr = get_next_prime(pr);
		}
	}
	return result;

}


int main()
{
	int z, s;
	FILE* in = freopen("input.txt", "r", stdin);
	scanf("%i %i", &s, &z);
	fclose(in);
	FILE* out = freopen("output.txt", "w", stdout);
	printf("%i", count_op_from_Dima(z, s));
	fclose(out);
	return 0;
}

...
Рейтинг: 0 / 0
26.03.2015, 10:13
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917385
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
На 7 тесте time limit, хм. Уже нет времени отлаживать, завтра доделаю, мне пора выключать компьютер (
Спасибо :)
...
Рейтинг: 0 / 0
26.03.2015, 10:27
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917390
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
SashaMercuryДополнил
Коряво дополнил, посчитай (1, 982451653) и подумай как еще ускорить.
...
Рейтинг: 0 / 0
26.03.2015, 10:32
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917398
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dima T
Участник
почитай про алгоритмы проверки на простое
http://habrahabr.ru/post/122538/
http://habrahabr.ru/post/133037/
...
Рейтинг: 0 / 0
26.03.2015, 10:38
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917412
m_Sla
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
m_Sla
Участник
допилил код Dima T
с таблицей целых чисел тест проходит
 
Код: 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.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
#include <fstream>
using namespace std;

ifstream cin("input.txt");
ofstream cout("output.txt");
int n,s;

int count_primes(int n, int s)
{
    static int primaries[] = {2,3,5,7,11,13,17,19,23,29,
                              ...
                              31607,31627,31643,31649,31657,31663,31667,31687,31699,31721
                             };

    int c = 0;

    if(s==n)
    {
        //c = 0;
    }
    else if(n==0 || s==0 || s/n<0 || s%n)
    {
        c = -1;
    }
    else
    {
        s = s / n;

        int i=0;
        while(s > 1)
        {
            if(s % primaries[i] == 0)
            {
                s /= primaries[i];
                c += primaries[i];
                i = 0;
            }
            else
            {
                i++;
                if(i >= sizeof(primaries)/sizeof(int)) return c + s;
            }
        }
    }

    return c;
}

int main()
{
    cin>>n>>s;

    cout << count_primes(n, s);

}

...
Рейтинг: 0 / 0
26.03.2015, 10:46
| Ответить | Цитировать | Написать  
Решение одной задачи
    #38917560
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
SashaMercuryНа 7 тесте time limit, хм.
Я же говорил, что без таблицы в одн секунду не уложиться. Не хочется хранить её прямо в
коде - ситай из внешнего файла если это позволено.
Posted via ActualForum NNTP Server 1.5
...
Рейтинг: 0 / 0
26.03.2015, 12:38
| Ответить | Цитировать | Написать  
25 сообщений из 76, страница 2 из 4
  2  все
Форумы / C++ [игнор отключен] [закрыт для гостей] / Решение одной задачи
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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