Решение задачи Игра с калькулятором с Меньшиков

Без пояснения   Просмотров: 51


В калькулятор вводится натуральное число K и нажимается клавиша "+". Калькулятор всё ещё показывает K. Цель игры: получить на экране число, состоящее из одинаковых цифр. Для её достижения можно производить только одно действие - нажимать на клавишу "=" (возможно, 0 раз). После первого нажатия получается результат K + K, после очередного нажатия результат увеличивается на K. Требуется определить, удастся ли достичь цели, а если удастся, то какое число, состоящее из одинаковых цифр, будет получено первым. Количество отображаемых калькулятором цифр считать неограниченным, время работы батареек - тоже.

1 <= K <= 999.

Код

#include <iostream>
#include <cstdio>
#include <vector>
 
using namespace std;
 
const int MAX_VALUE = 1e9;
int k;
vector<bool> mem(1000);
int resD = MAX_VALUE, resL = MAX_VALUE;
void input()
{
    cin>>k;
}
void solve()
{
    int prev,cur;
    for (int d = 1; d <= 9; d++) {
        fill(mem.begin(), mem.end(), 0);
 
        int prev = d % k;
 
        if (prev == 0) {
            resD = d; resL = 1;
            return;
        }
        mem[prev] = true;
        for (int len = 2; len <= k + 1; len++) {
            cur = (prev * 10 + d) % k;
            if (cur == 0) {
                if (len < resL) {
                    resL = len;
                    resD = d;
                }
            }
            prev = cur;
            mem[cur] = true;
        }
    }
}
void output() {
    if (resD == MAX_VALUE)
        cout<<"Impossible";
    else
        cout<<resD<<' '<<resL;
}
int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
 
    input();
    solve();
    output();
   
    return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться