Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

Вернуться   Форум программистов > Java программирование > Общие вопросы по Java, Java SE, Kotlin
Регистрация

Восстановить пароль
Повторная активизация e-mail

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 16.01.2013, 18:13   #1
Izobara
Форумчанин
 
Аватар для Izobara
 
Регистрация: 26.12.2012
Сообщений: 227
По умолчанию Объяснить алгоритм поиска семерок

Есть задачка -
Цитата:
Ограничение по времени: 0 .5 секунд
В строке записаны все подряд натуральные числа от некоторого N до нек-рого M
(гарантировано N ≤ M ) . Сколько в этой строке записано копий цифры 7?
16 22
Ответ: 1
43 87
Ответ: 15
Объясните тугодуму алгоритм на пальцах (а лучше на псевдокоде - в джаве не шарю совсем).
Код:
import java.util.*;
import java.io.*;
 
public class B {
 
    final static String InputFile = "dig7.dat";
    final static String OutputFile = "dig7.sol";
    FastScanner in;
    PrintWriter out;
 
    public int[] count(int n) {
        int[] result = new int[10];
        if (n < 10) {
            for (int i = 0 ; i <= n ; i++)
                result[i]++;
            return result;
        }
        int[] tmpRes = count(n / 10 - 1);
        for (int i = 0 ; i < 10 ; i++)
            tmpRes[i] *= 10;
        tmpRes[0] -= 10;
        for (int i = 0 ; i < 10 ; i++)
            tmpRes[i] += n / 10;
        for (int i = 0 ; i <= n % 10 ; i++) {
            int u = n - i;
            while (u > 0) {
                tmpRes[u % 10]++;
                u /= 10;
            }
        }
        return tmpRes;
    }
 
 
    public void solve() throws IOException {
        int n = in.nextInt();
        int m = in.nextInt();
        int[] result = count(m);
        int[] tmp = count(n - 1);
        result[7] -= tmp[7];
        out.println(result[7]);
    }
 
    public void run() {
        try {
            in = new FastScanner(new FileReader(InputFile));
            out = new PrintWriter(OutputFile);
 
            solve();
 
            out.close();
        } catch (IOException e) {
            e.printStackTrace();
        }
    }
 
    class FastScanner {
 
        BufferedReader br;
        StringTokenizer st;
 
        FastScanner(FileReader f) {
            try {
                br = new BufferedReader(f);
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
 
        String next() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt() {
            return Integer.parseInt(next());
        }
 
        double nextDouble() {
            return Double.parseDouble(next());
        }
 
        long nextLong() {
            return Long.parseLong(next());
        }
    }
 
    public static void main(String[] arg) {
        new B().run();
    }
}
"I believe I can fly" - C++, "What do you want from me" - Delphi, "Yesterday" - Pascal, "Let it be" - C#... Программисты-музыканты-полиглоты поймут
Izobara вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Алгоритм поиска Sylar9 Общие вопросы C/C++ 0 03.04.2012 12:38
A* алгоритм поиска Nicko_mt Помощь студентам 2 04.10.2011 02:24
алгоритм поиска незнайка_на_земле Помощь студентам 4 08.03.2011 10:46
Алгоритм поиска!!!! vit1990 Помощь студентам 14 29.01.2011 21:18
Алгоритм поиска... Johnson Общие вопросы Delphi 1 26.10.2008 08:35