Задача.Интересные числа.Помогите решить задачку.

→ Обратите внимание

До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
13:26:12
Зарегистрироваться »

*есть доп. регистрация

→ Трансляции

Leetcode BiWeekly Contest 144 — Solution Discussion

Shayan

До начала 14:56:11

Codeforces CodeTON Round 9 (Div 1 + Div 2) — Solution Discussion

Shayan

До начала 16:26:11

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя dnazirzhanov05

Задача.Интересные числа.Помогите решить задачку.

Автор dnazirzhanov05, история, 5 лет назад, По-русски

ИНТЕРЕСНЫЕ ЧИСЛА. Назовём натуральное число X (X > 9) "интересным", если цифры в его десятичной записи ненулевые, попарно взаимно простые и их попарные суммы — простые числа. Например, число 114 является интересным, а числа 115, 124 — нет.
Найдите N-ое (1 <= N <= 2018) интересное число. Пример: 3 -> 14

dnazirzhanov05
5 лет назад
9

Комментарии (9)

Написать комментарий?

veschii_nevstrui

5 лет назад, # |

Напишем простой перебор, который покажет все интересные числа до $$$10^7$$$. Заметим, что все интересные числа либо двузначные, либо удовлетворяют регулярному выражению 1*[1246]1*. Скорее всего, это можно строго доказать, но мне лень(

Руками выкинем все двузначные. Из общего вида интересных чисел следует, что количество интересных чисел длины $$$n$$$ Равно $$$3 \cdot n + 1$$$. Из этой информации вы можете получить длину числа. В вашем случае сработает простой линейный перебор, однако для больших ограничений можно было бы использовать бинпоиск, или даже придумать явную формулу.

Затем осталось понять, какое именно у вас число, если известна его длина. Вы можете его явно перебрать, однако опять же, при больших ограничениях работал бы бинпоиск или явная формула.

Асимптотика решения: $$$O(n)$$$ если все просто перебирать, $$$O(\log{n})$$$, если придумать бинпоиск и $$$O(1)$$$, если придумать формулу.

→ Ответить

veschii_nevstrui

5 лет назад, # ^ |

Строгое доказательство такое. Пусть есть интересное число, в котором больше одной не единичной цифры. Заметим, что если выкидывать цифры из числа, то это на интересность никак не влияет — она не может исчезнуть, только появиться. Будем выкидывать единицы либо пока они есть, либо пока число не станет трехзначным. Если кончились единицы, то будем выкидывать что угодно, пока число не останется трехзначным. Итого мы получили трехзначное интересное число, в котором хотя бы две не единичные цифры, а наш перебор показал, что таких чисел нет, противоречие.

Аналогичное рассуждение работает, если предположить, что в числе оказалась цифра не из множества $$$[1246]$$$.

→ Ответить

dnazirzhanov05

5 лет назад, # ^ |

← Rev. 2 →

-8

Спасибо большое за вашу помощь.

→ Ответить

veschii_nevstrui

5 лет назад, # ^ |

Я то могу, но какой в этом смысл? Для меня обучающей ценности эта задача не несет — я уже легко умею реализовывать подобное. Если я дам вам свой код, то вы, скорее всего, просто его сдадите в систему, возможно предварительно прочитав, но ничего не запомнив из этого полотна кода.

Гораздо лучше будет, если вы сами его напишете. Во-первых, я не потрачу свое бесценное время на простую задачу, а во-вторых, вы научитесь ее решать. Поверьте, так будет эффективней.

Если хотите, могу скинуть код моего перебора. Вот он:

Перебор

#include <bits/stdc++.h>

using namespace std;

vector <bool> p = {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1};

int gcd(int a, int b) {
	if (b == 0) {
		return a;
	}
	return gcd(b, a % b);
}

bool check(int a) {
	vector <int> v;
	while (a > 0) {
		v.push_back(a % 10);
		if (a % 10 == 0) {
			return 0;
		}
		a /= 10;
	}
	for (int i = 0; i < v.size(); ++i) {
		for (int j = i + 1; j < v.size(); ++j) {
			if (gcd(v[i], v[j]) > 1 || !p[v[i] + v[j]]) {
				return 0;
			}
		}
	}
	return 1;
}

int main()
{
	ios_base::sync_with_stdio(0); 
	cin.tie(0); 
	cout.tie(0);
	cout.setf(ios::fixed);
	cout.precision(10);

	int n;
	cin >> n;

	for (int i = 10; i < 10000000; ++i) {
		if (check(i)) {
			cout << i << endl;
			--n;
		}
		if (n == 0) {
			cout << i << endl;
			return 0;
		}
	}
	cout << "FAIL" << endl << n << endl;
}

→ Ответить

dnazirzhanov05

5 лет назад, # ^ |

Огромное спасибо! Можете объяснить

vector p = {0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1};

→ Ответить

gmusya

5 лет назад, # ^ |

← Rev. 3 →

$$$p[i] = 0$$$, если число $$$i$$$ составное; $$$p[i] = 1$$$, если $$$i$$$ простое.

UPD. Ошибся, разумеется $$$0$$$ и $$$1$$$ не являются составными числами.

→ Ответить

veschii_nevstrui

5 лет назад, # ^ |

Формально говоря, не так. $$$p[i] = 1$$$, если $$$i$$$ простое, и $$$p[i] = 0$$$ если $$$i$$$ не простое.

Вообще мне нужна была таблица простых чисел до $$$20$$$, но было очень лень реализовывать Эратосфена, поэтому я ее руками вбил.

→ Ответить

orangeorange

5 лет назад, # |

Можно ссылку на задачу?

→ Ответить

dnazirzhanov05

5 лет назад, # ^ |

https://olymp.krsu.edu.kg/ContestProblemset.aspx?contest=151 Задача Е.Кызыктуу сандар = Интересные числа. Если открыть задачу с формата (pdf).На первом листе киргизский вариант , а на следующем листе имеется русский вариант.

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 23.11.2024 04:08:49 (k2).

Десктопная версия, переключиться на мобильную.

При поддержке