Выведите через пробел N цифр по заданному правилу

@rull · Регистрация: 10.11.2012

Студворк — интернет-сервис помощи студентам

Представим себе бесконечную последовательность цифр, составленную из записанных друг за другом возрастающих степеней десятки. Вот начало этой последовательности: 110100100010000… Всё, что надо — определить, какая цифра находится в такой последовательности на определённом месте.
Исходные данные
В первой строке находится целое число N (1 ≤ N ≤ 65535). В i-й из N последующих строк записано целое число Ki — номер позиции в последовательности (1 ≤ Ki ≤ 2^31 − 1).
Результат
Выведите через пробел N цифр. i-я цифра должна равняться цифре, которая находится в описанной выше последовательности на позиции с номером Ki.

ВВод:
4
3
14
7
6

Ответ:
0 0 1 0

Я так понимаю что первая цифра показывает сколько дальше цифр будет идти, допустим у них цифра 4-значит далее идут 4 цифры 3 14 7 6 это тоже понятно.

Выведите через пробел N цифр. i-я цифра должна равняться цифре, которая находится в описанной выше последовательности на позиции с номером Ki.
выведите через пробел понятно, а вот дальше что то не пойму....
к какой цифре она относится в этой последовательности 110100100010000...?
получается тут к единице относится 1,2,4,7,11 и тд, я правильно понимаю?

@kolorotur · 23.12.2012, 17:23

Сообщение от rull

получается тут к единице относится 1,2,4,7,11 и тд, я правильно понимаю?

Да, вам надо вывести ту цифру, которая стоит на указанном в этой строчке месте.
То есть, если строка будет иметь вид
5
1
2
4
7
11

То ответ будет
1 1 1 1 1

Дам подсказку: внимательно всмотритесь в последовательность - в ней спрятана формула, часто используемая на уроках алгебры.
Так что цикл не нужен.

@rull · 25.12.2012, 09:58 **[ТС]**

Это математическая прогрессия вроде, но вот проблема, я даже и не знаю как реализовывать в коде.
Я с циклами сделал, у меня теперь по времени не проходит((((
Напишите про эту формулу, почитаю на МСДН

C#
1
2
3
4
5
6
7
8
9
10
11
            string[] input = new string[5] { "4", "3", "14", "7", "6" };
            int o=1;
            for (int j = 1; j <= int.Parse(input[0]); j++, o = 1)
            {
                for (int i = 1; o < int.Parse(input[j]); i++)
                    o += i;
                if (o != int.Parse(input[j]))
                    Console.WriteLine(0);
                else
                    Console.WriteLine(1);
            }

@kolorotur · 25.12.2012, 11:18

Сообщение от rull

Напишите про эту формулу, почитаю на МСДН

А причем тут MSDN?

Я в качестве основы использовал формулу нахождения одного из корней квадратного уравнения:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{x}_{+}=\frac{-b + \sqrt{{b}^{2}-4ac}}{2a}$

Попробуйте сами определить, чему в задаче равны a, b и c.

Если результат вычисления этого выражения является целым числом, то на позиции n находится единица, в противном случае - ноль.

Результат теста был что-то около сотни мс и 2Мб памяти.
На сях вышло бы еще лучше.

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

@rull · 25.12.2012, 12:27 **[ТС]**

ну и задачка....
Попробуйте сами определить, чему в задаче равны a, b и c, это каким образом?
Я знаю только 2 стартовых параметра,
первый:с какой цифры начинается, допустим 1
второй:какую цифру проверяем(1,2,4,7,11 и тд,) допустим 7.
а третий то параметр для чего?

Добавлено через 37 минут
я даже формулы такой не могу найти в глобальной свалке, как я что должен подставить если не знаю как вообще она работает, я даже незнаю как она называется.
Скажите пожалуйста просто название этой конкретной прогрессии. та которая 1 2 4 7 11 16
Меня уже раздражать начинает "искать ничего"

@kolorotur · 25.12.2012, 14:01

$https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{\sqrt{8n - 7} - 1}{2}$

В коде выглядит так:

C#
1
(Math.Sqrt(8 * n - 7) - 1) / 2;

Если результат - целое число, то на позиции n стоит единица.

@rull · 25.12.2012, 15:46 **[ТС]**

Заранее извиняюсь про всё ниженаписанное, никого нехочу обидеть, просто нужно разобраться...
В числах фибоначи и в тех формулах еслиб так было просто разобраться уже сам сделал бы наверное всё сделал, не могу разобраться-пишу на форум..
есть формула
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{x}_{+}=\frac{-b + \sqrt{{b}^{2}-4ac}}{2a}$
в этой формуле 3 переменные
b-это что?
a-это что?
c-это что?
x+ - я так поолагаю ответ.

в формуле
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{\sqrt{8n - 7} - 1}{2}$
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\frac{\sqrt{.....}}{2}$ судя по формуле там в делителе 2=2*1=2a, значит а=1;
после $https://www.cyberforum.ru/cgi-bin/latex.cgi?sqrt{8n - 7}$ стоит $https://www.cyberforum.ru/cgi-bin/latex.cgi?- 1$ значит b=1,
а если b=1 то как получается
$https://www.cyberforum.ru/cgi-bin/latex.cgi?sqrt{8n - 7}$ так как по формуле $https://www.cyberforum.ru/cgi-bin/latex.cgi?sqrt{{b}^{2}-4ac}$ знак "-" делит $https://www.cyberforum.ru/cgi-bin/latex.cgi?{b}^{2}$ и $https://www.cyberforum.ru/cgi-bin/latex.cgi?4ac$ у нас $https://www.cyberforum.ru/cgi-bin/latex.cgi?{1}^{2}$ != (-7 && 8n)
даже и незнаю как дальше продолжать?
Хотелось узнать откуда цифры взялись или эта формула совсем другая?

Сообщение от kolorotur

В коде выглядит так:

C#
1
(Math.Sqrt(8 * n - 7) - 1) / 2;

Если результат - целое число, то на позиции n стоит единица.

Чтобы мне проверить цифру 11 её надо вставить в "n"?

Добавлено через 1 час 1 минуту
Неверно, в чем ошибка, их бот непонимает, всё время неправильный ответ

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
    class Program
    {
        static void Main(string[] args)
        {
            string[] input = Console.In.ReadToEnd().Split(new char[] { ' ', '\t', '\n', '\r' }, StringSplitOptions.RemoveEmptyEntries);
           
            double  o;
            for (int j = 1; j <= int.Parse(input[0]); j++)
            {
                 o = (Math.Sqrt(8 * int.Parse(input[j]) - 7) - 1) / 2;
                if (o == (int)o)
                    Console.Write("{0} ", 1);
                else
                    Console.Write("{0} ", 0);
            }
            Console.ReadLine();
        }
    }

@kolorotur · 26.12.2012, 01:13

Опишу свой ход мыслей во время решения этой задачи. Возможно, к решению пришел через одно место и все можно сделать намного проще. Если кто-то знает как именно - было бы здорово прочитать.
Опишу по шагам, чтобы по возможности не было вопросов в стиле "а это здесь откуда?"

Условие:
Дана бесконечная последовательность единиц и нулей, образованная восходящими степенями десяти, начиная с нулевой, стоящими друг за другом:
110100100010000100000100000010000000…

Задание:
Определить, какая цифра находится на заданной позиции $https://www.cyberforum.ru/cgi-bin/latex.cgi?x\in [1;{2}^{31}-1]$

Решение:
Я решил сначала описать последовательность, состоящую из позиций, на которых находятся единицы (т.к. единиц здесь явно будет меньше, чем нулей), а потом просто проверить, принадлежит ли заданная x этой последовательности.
Если принадлежит, значит на данной позиции находится единица, в противном случае - ноль.

Итак, начало последовательности:
1, 2, 4, 7, 11, 16, 22, 29, 37 и т.д.

Но так как строка может быть бесконечной, а заданная x может достигать значения 2 147 483 647, то фактически генерировать всю последовательность - нецелесообразно, а потому лучше найти формулу, которая определит, какое значение будет соответствовать указанной позиции в этой последовательности.

Первый метод, который приходит в голову - это, конечно же, цикл или рекурсия:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{y}_{x}={y}_{x-1}+x$
Но рекурсия отпадает сразу, а цикл - слишком долго.

Следующий вариант, которым я и воспользовался - это представление последовательности полиномом такого вида:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?y = {a}_{0}+{a}_{1}x+{a}_{2}{x}^{2}+...+{a}_{n-1}{x}^{n-1}$
Где y - значение последовательности, х - порядковый номер этого значения, а a - константа.

Перво-наперво нужно найти порядок полинома. Делаем через вычисление разности смежных значений:
1 2 4 7 11

11 - 7 = 4
7 - 4 = 3
4 - 2 = 2
2 - 1 = 1

4 - 3 = 1
3 - 2 = 1
2 - 1 = 1
Дошли до единиц на втором шаге, значит порядок полинома = 2, следовательно выглядеть он будет так:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?y=a{x}^{2}+bx+c$

Осталось найти константы a, b и c.
Как сказано выше, y - это значение последовательности, а x - порядковый номер (начиная с нуля).
У нас три неизвестных константы, потому возьмем первые три значения последовательности и подставим их в выражение:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix} 1 = a{\left(0 \right)}^{2}+b\left(0 \right)+c\\ 2 = a{\left(1 \right)}^{2}+b\left(1 \right)+c\\ 4 = a{\left(2 \right)}^{2}+b\left(2 \right)+c \end{matrix}\right.$

Решаем систему уравнений методом Гаусса:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\left( \left.\begin{matrix} 0 & 0 & 1\\ 1 & 1 & 1\\ 4 & 2 & 1 \end{matrix}\right|\begin{matrix} 1\\ 2\\ 4 \end{matrix}\right)$

Вторую строку множим на -4 и прибавляем к третьей:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\left( \left.\begin{matrix} 0 & 0 & 1\\ 1 & 1 & 1\\ 0 & -2 & -3 \end{matrix}\right|\begin{matrix} 1\\ 2\\ -4 \end{matrix}\right)$

Меняем вторую и третью строку местами:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\left( \left.\begin{matrix} 0 & 0 & 1\\ 0 & -2 & -3\\ 1 & 1 & 1 \end{matrix}\right|\begin{matrix} 1\\ -4\\ 2 \end{matrix}\right)$

Получился заветный "треугольник". Возвращаемся к системе:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix} 0a + 0b + c = 1 & \\ 0a - 2b - 3c = -4 & \Rightarrow \\ 1a + 1b + 1c = 2 & \end{matrix}\right.$ $https://www.cyberforum.ru/cgi-bin/latex.cgi?\left\{\begin{matrix} c = 1 \\ - 2b - 3c = -4 \\ a + b + c = 2 \end{matrix}\right.$

Подставляем С во второе уравнение:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?- 2b - 3c = -4$

$https://www.cyberforum.ru/cgi-bin/latex.cgi?-2b - 3(1) = -4$

$https://www.cyberforum.ru/cgi-bin/latex.cgi?-2b = -4 + 3$

$https://www.cyberforum.ru/cgi-bin/latex.cgi?-2b = -1$

$https://www.cyberforum.ru/cgi-bin/latex.cgi?b = \frac{1}{2}$

Подставляем C и B в третье уравнение:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?1a + 1\left( \frac{1}{2}\right) + 1\left( 1\right) = 2$

$https://www.cyberforum.ru/cgi-bin/latex.cgi?a + \frac{1}{2} + 1 = 2$

$https://www.cyberforum.ru/cgi-bin/latex.cgi?a = 2 - 1 - \frac{1}{2}$

$https://www.cyberforum.ru/cgi-bin/latex.cgi?a=\frac{1}{2}$

Результат: $https://www.cyberforum.ru/cgi-bin/latex.cgi?a=\frac{1}{2},b=\frac{1}{2},c=1$

Подставляем значения констант в полином:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?y=\frac{1}{2}{x}^{2}+\frac{1}{2}x+1$

$https://www.cyberforum.ru/cgi-bin/latex.cgi?y=\frac{{x}^{2}+x}{2}+1$

Это и есть формула для нахождения элемента последовательности y на позиции x.
Дело за малым - решить это уравнение.

Сначала избавляемся от дроби, умножая обе стороны на двойку:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?2y = {x}^{2}+x+2$

Переносим 2y в правую часть, чтобы получилось красивое квадратное уравнение:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{x}^{2}+x+2 - 2y = 0$

Имеем квадратное уравнение вида $https://www.cyberforum.ru/cgi-bin/latex.cgi?a{x}^{2}+bx+c$ , где в качестве C служит выражение 2 - 2y:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?1{x}^{2}+1x+(2 - 2y) = 0$

Ну и, собственно, находим корни этого уравнения, а точнее - один из корней, т.к. отрицательных значений x у нас не предвидится по условию.
Со школы помним (надеюсь), что корни квадратного уравнения подобного рода можно найти с помощью вот такой формулы:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?{x}_{+}=\frac{-b+\sqrt{{b}^{2}-4ac}}{2a}$

Подставляем значения:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?x=\frac{-1+\sqrt{{1}^{2}-4(1)(2-2y)}}{2(1)}$

Раскрываем скобки:
$https://www.cyberforum.ru/cgi-bin/latex.cgi?x=\frac{-1+\sqrt{1-4*2-(-4)*2y}}{2}\Rightarrow x=\frac{-1+\sqrt{1-8-(-8y)}}{2}\Rightarrow x=\frac{-1+\sqrt{-7+8y}}{2}\Rightarrow x=\frac{\sqrt{8y-7}-1}{2}$

Собственно, вот она и формула.
Напомню, что у - это порядковый номер элемента в строчке (то, что мы получаем в качестве входящих данных), а х - это номер из последовательности, соответствующий этому элементу, или, говоря проще, какая по счету единица находится на этой позиции. Если число получилось дробным, то на этом месте в строчке находится ноль.

В качестве проверки можно попытаться сгенерировать последовательность единиц и нулей, используя эту формулу:

C#
1
2
3
4
5
6
7
static void Main()
{
    for (int i = 1; i <= 50; i++) {
        double x = (Math.Sqrt(8 * i - 7) - 1) / 2;
        Console.Write(x == (int)x ? 1 : 0);
    }
}

1101001000100001000001000000100000001000 0000010000

Вроде как похоже.

Вывод: задачи на тимусе - это больше задачи по математике с использованием языка программирования, нежели задачи по программированию как таковому.

@rull · 26.12.2012, 09:31 **[ТС]**

Круто! ...нет слов....
Математика у Вас на высоком уровне

Я уже перестал понимать после "Решаем систему уравнений методом Гаусса:", но всеравно спасибо!
Да, я вчера уже наконецто заметил что тимус не просто задания, а олимпиадные, соответственно хорошо подготовленные чтобы расплавить собственный мозг

Мне тут посоветовали не останавливать обучение, всю книгу(видео) пройти до конца чтобы представлять(хотябы в общем) как это работает и уже начать свой проект. ещё сказал: "я так и сделал когда учился, много гуглил, было очень много вопросов, но на своем усваивается лучше".
А идея на проект уже есть, если интересно могу отписать, там уже скажете возможно ли это)

Новые блоги и статьи Все статьи Все блоги /
Ритм жизни kumehtar 27.02.2026 Иногда приходится жить в ритме, где дел становится всё больше, а вовлечения в происходящее — всё меньше. Плотный график не даёт вниманию закрепиться ни на одном событии. Утро начинается с быстрых,. . .	SDL3 для Web (WebAssembly): Сборка библиотек SDL3 и Box2D из исходников с помощью CMake и Emscripten 8Observer8 27.02.2026 Недавно вышла версия SDL 3. 4. 2 библиотеки SDL3. На странице официальной релиза доступны исходники, готовые DLL (для x86, x64, arm64), а также библиотеки для разработки под Android, MinGW и Visual. . .	SDL3 для Web (WebAssembly): Реализация движения на Box2D v3 - трение и коллизии с повёрнутыми стенами 8Observer8 20.02.2026 Содержание блога Box2D позволяет легко создать главного героя, который не проходит сквозь стены и перемещается с заданным трением о препятствия, которые можно располагать под углом, как верхнее. . .	Конвертировать закладки radiotray-ng в m3u-плейлист damix 19.02.2026 Это можно сделать скриптом для PowerShell. Использование . \СonvertRadiotrayToM3U. ps1 <path_to_bookmarks. json> Рядом с файлом bookmarks. json появится файл bookmarks. m3u с результатом. # Check if. . .
Семь CDC на одном интерфейсе: 5 U[S]ARTов, 1 CAN и 1 SSI Eddy_Em 18.02.2026 Постепенно допиливаю свою "многоинтерфейсную плату". Выглядит вот так: https:/ / www. cyberforum. ru/ blog_attachment. php?attachmentid=11617&stc=1&d=1771445347 Основана на STM32F303RBT6. На борту пять. . .	Камера Toupcam IUA500KMA Eddy_Em 12.02.2026 Т. к. у всяких "хикроботов" слишком уж мелкий пиксель, для подсмотра в ESPriF они вообще плохо годятся: уже 14 величину можно рассмотреть еле-еле лишь на экспозициях под 3 секунды (а то и больше),. . .	И ясному Солнцу zbw 12.02.2026 И ясному Солнцу, и светлой Луне. В мире покоя нет и люди не могут жить в тишине. А жить им немного лет.	«Знание-Сила» zbw 12.02.2026 «Знание-Сила» «Время-Деньги» «Деньги -Пуля»

@rull 21 / 20 / 3 Регистрация: 10.11.2012 Сообщений: 240 Записей в блоге: 1

	Выведите через пробел N цифр по заданному правилу 23.12.2012, 15:32. Показов 6313. Ответов 8 Метки нет (Все метки) Представим себе бесконечную последовательность цифр, составленную из записанных друг за другом возрастающих степеней десятки. Вот начало этой последовательности: 110100100010000… Всё, что надо — определить, какая цифра находится в такой последовательности на определённом месте. Исходные данные В первой строке находится целое число N (1 ≤ N ≤ 65535). В i-й из N последующих строк записано целое число Ki — номер позиции в последовательности (1 ≤ Ki ≤ 2^31 − 1). Результат Выведите через пробел N цифр. i-я цифра должна равняться цифре, которая находится в описанной выше последовательности на позиции с номером Ki. ВВод: 4 3 14 7 6 Ответ: 0 0 1 0 Я так понимаю что первая цифра показывает сколько дальше цифр будет идти, допустим у них цифра 4-значит далее идут 4 цифры 3 14 7 6 это тоже понятно. Выведите через пробел N цифр. i-я цифра должна равняться цифре, которая находится в описанной выше последовательности на позиции с номером Ki. выведите через пробел понятно, а вот дальше что то не пойму.... к какой цифре она относится в этой последовательности 110100100010000...? получается тут к единице относится 1,2,4,7,11 и тд, я правильно понимаю? 0

@rull 21 / 20 / 3 Регистрация: 10.11.2012 Сообщений: 240 Записей в блоге: 1
	25.12.2012, 12:27 [ТС]
	ну и задачка.... Попробуйте сами определить, чему в задаче равны a, b и c, это каким образом? Я знаю только 2 стартовых параметра, первый:с какой цифры начинается, допустим 1 второй:какую цифру проверяем(1,2,4,7,11 и тд,) допустим 7. а третий то параметр для чего? Добавлено через 37 минут я даже формулы такой не могу найти в глобальной свалке, как я что должен подставить если не знаю как вообще она работает, я даже незнаю как она называется. Скажите пожалуйста просто название этой конкретной прогрессии. та которая 1 2 4 7 11 16 Меня уже раздражать начинает "искать ничего" 0

@rull 21 / 20 / 3 Регистрация: 10.11.2012 Сообщений: 240 Записей в блоге: 1
	26.12.2012, 09:31 [ТС]
	Круто! ...нет слов.... Математика у Вас на высоком уровне Я уже перестал понимать после "Решаем систему уравнений методом Гаусса:", но всеравно спасибо! Да, я вчера уже наконецто заметил что тимус не просто задания, а олимпиадные, соответственно хорошо подготовленные чтобы расплавить собственный мозг Мне тут посоветовали не останавливать обучение, всю книгу(видео) пройти до конца чтобы представлять(хотябы в общем) как это работает и уже начать свой проект. ещё сказал: "я так и сделал когда учился, много гуглил, было очень много вопросов, но на своем усваивается лучше". А идея на проект уже есть, если интересно могу отписать, там уже скажете возможно ли это) 0