1071. Nikifor 2
Time limit: 1.0 second
Memory limit: 64 MB
Memory limit: 64 MB
Nikifor has a number x. He doesn't need it. He needs a number y. Nikifor tries to obtain the required number by erasing some digits from x. But he is not lucky in the meanwhile. May be he is to choose an appropriate number system?
Write a program that reads numbers x and y, and determines a minimal radix of a number system that it is possible to obtain in it the number y from x by erasing some digits. If it is impossible, your program should write to an output a message "No solution".
Input
The only line contains integers x and y (1 ≤ y < x ≤ 1 000 000), separated with a space.
Output
Output either the message "No solution", if there is no appropriate number system, or an integer, not less than 2, that is an answer in the problem.
Sample
| input | output |
|---|---|
127 16 |
3 |
Problem Author: Dmitry Filimonenkov
Problem Source: Ural State Univerisity Personal Contest Online February'2001 Students Session
Problem Source: Ural State Univerisity Personal Contest Online February'2001 Students Session
Tags: none (hide tags for unsolved problems)
Difficulty: 568
题意：给出x,y,确定一个最小的进制基数，使在这种进制下,能通过删除x的某些数字，得到y。
分析：仍然是暴力
/**
Create By yzx - stupidboy
*/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <ctime>
#include <iomanip>
using namespace std;
typedef long long LL;
typedef double DB;
#define MIT (2147483647)
#define INF (1000000001)
#define MLL (1000000000000000001LL)
#define sz(x) ((int) (x).size())
#define clr(x, y) memset(x, y, sizeof(x))
#define puf push_front
#define pub push_back
#define pof pop_front
#define pob pop_back
#define ft first
#define sd second
#define mk make_pair inline int Getint()
{
int Ret = ;
char Ch = ' ';
bool Flag = ;
while(!(Ch >= '' && Ch <= ''))
{
if(Ch == '-') Flag ^= ;
Ch = getchar();
}
while(Ch >= '' && Ch <= '')
{
Ret = Ret * + Ch - '';
Ch = getchar();
}
return Flag ? -Ret : Ret;
} const int N = ;
int x, y;
int arr[N], len1, brr[N], len2; inline void Input()
{
cin >> x >> y;
} inline void Change(int *a, int &len, int x, int base)
{
len = ;
while(x)
{
a[len++] = x % base;
x /= base;
}
} inline void Solve()
{
for(int k = ; k <= x; k++)
{
Change(arr, len1, x, k);
Change(brr, len2, y, k); int index = ;
bool flag = ;
for(int j = ; j < len2; j++)
{
while(index < len1 && arr[index] != brr[j])
index++;
if(index < len1) index++;
else
{
flag = ;
break;
}
}
if(flag)
{
printf("%d\n", k);
return;
}
}
printf("No solution\n");
} int main()
{
freopen("c.in", "r", stdin);
Input();
Solve();
return ;
}