Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/5: Рейтинг темы: голосов - 5, средняя оценка - 5.00
0 / 0 / 0
Регистрация: 19.06.2016
Сообщений: 5
1

Вывод последних k цифр искомого количества последовательностей

01.09.2017, 10:40. Показов 1022. Ответов 1
Метки нет (Все метки)

Никак не могу понять как решить данную задачу. Если сказать точнее, я не понимаю как она должна работать. Мне не очень понятно как формируются выходные данные, и если бы кто нибудь сказал мне как например сформировалась тройка в первом примере, и почему во втором примере на выходе 1, я бы все понял. Спасибо!

Кликните здесь для просмотра всего текста
Решая задачу по информатике, Вова в очередной раз допустил ошибку. Он снова вывел в выходной файл числа, забыв разделить их пробелами. Увидев полученный результат, Вова сначала огорчился, а потом задумался над следующим вопросом: сколько существует различных последовательностей неотрицательных целых чисел, таких что, если выписать их без пробелов, то получится тот же результат, что и у него. Он вспомнил также, что его программа смогла вывести не произвольные числа, а только те, что не превосходят C и не имеют ведущих нулей.

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

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

Входные данные
Первая строка входного файла содержит три целых числа — n, C и k (1 ≤ n ≤ 50000, 1 ≤ C ≤ 10^8, 1 ≤ k ≤ 18). Во второй строке этого файла содержится результат работы Вовиной программы, состоящий из n цифр.

Выходные данные
В выходной файл выведите последние k цифр искомого количества последовательностей (без ведущих нулей).

входные данные
3 11 2
111
выходные данные
3
входные данные
19 9 1
0123456789876543210
выходные данные
1
входные данные
1 8 3
9
выходные данные
0
0

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.09.2017, 10:40
Ответы с готовыми решениями:

Составить функцию для подсчета количества числовых констант (последовательностей цифр)
Составить функцию для подсчета количества числовых констант (последовательностей цифр) в...

Определение количества шестизначных счастливых билетов, у которых сумма первых 3 цифр равна сумме 3 последних
Помогите, пожалуйста, написать программу в MathLab. Само задание звучит так: Напишите программу...

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

Сумма цифр искомого числа равна произведению цифр заданного
помогите , пожалуйста, с этим заданием. Нужно составит блок-схему и программу на паскале....

1
600 / 357 / 198
Регистрация: 02.06.2016
Сообщений: 604
01.09.2017, 16:01 2
Лучший ответ Сообщение было отмечено ShadeWe как решение

Решение

Цитата Сообщение от ShadeWe Посмотреть сообщение
как например сформировалась тройка в первом примере
111 можно собрать из 1.1.1, 11.1 и 1.11 - три варианта, ответ - 3.
Цитата Сообщение от ShadeWe Посмотреть сообщение
почему во втором примере на выходе 1
поскольку C=9, то все числа последовательности должны быть "однозначными" (меньше 10), значит подходит только два варианта:
0.1.2.3.4.5.6.7.8.9.8.7.6.5.4.3.2.1.0
01.2.3.4.5.6.7.8.9.8.7.6.5.4.3.2.1.0
но, по условию, числа в последовательности должны быть без ведущих нулей, значит второй вариант тоже не походит, остается только первый. Ответ - 1.
решение (если нужны объяснения, можете спросить)
C#
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
using System;
using System.IO;
using System.Linq;
 
class Program
{
    static int Solve(int n, int c, int k, int[] seq)
    {
        k = (int)Math.Pow(10, k);
 
        int[] a = new int[n];
        int[] b = new int[n];
        for (int i = n - 1; i >= 0; i--)
        {
            if (seq[i] == 0) a[i] = 1;
            else
                for (int x = 0, j = i; j < n && x <= c; j++)
                {
                    x = x * 10 + seq[j];
                    if (x <= c) a[i]++;
                }
 
            if (i + a[i] >= n) b[i] = 1;
            for (int j = i + 1; j < i + a[i] + 1 && j < n; j++)
                b[i] = (b[i] + b[j]) % k;
        }
 
        return b[0];
    }
 
    static void Main()
    {
        var input = File.ReadAllLines("input.txt");
        var nck = input[0].Split().Take(3).Select(x => int.Parse(x)).ToArray();
        var seq = input[1].Select(x => x - '0').ToArray();
        var slv = Solve(nck[0], nck[1], nck[2], seq);
        File.WriteAllText("output.txt", slv.ToString());
    }
}
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
01.09.2017, 16:01

Составить два числа: из четных и нечетных цифр искомого
Дано натуральное число. Получить из негодна числа: первое, состоящее из четных цифр числа, а...

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

Вывод искомого слова в контексте в label
по заданию, нужно найти искомое слово, вывести его в label и еще -50 и +50 символов от его...

Работа со строками. Вывод искомого слова
Программа находит в тексте слово red. вот текст файла: red bred brred bread skinred...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.