Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- #define fi first
- #define f first
- #define se second
- #define s second
- #define vi_a vector<int>a;
- #define p_b push_back
- #define ll long long
- #define ld double
- #define pll pair<ll,ll>
- #define pii pair<int,int>
- #define m_p make_pair
- #define fast_io cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
- #define all(x) x.begin(),x.end()
- #define getfiles ifstream cin("birch.in");ofstream cout("birch.out");
- #define pw(x) (1ll << x)
- #define sz(x) (int)x.size()
- #define endl "\n"
- #define rall(x) x.rbegin(),x.rend()
- #define len(a) (ll)a.size()
- #define rep(x,l,r) for(ll x=l;x<r;x++)
- using namespace std;
- ld eps = (ld)1 / 1e15;
- ll inf = 1e18, mod2 = 998244353, mod1 = 1e9 + 7;
- ll sqr(ll a) { return a * a; }
- ll qb(ll a) { return a * a * a; }
- ll gcd(ll a, ll b) { return !a ? b : gcd(b % a, a); }
- ll binpow(ll a, ll b, ll mod) { return b ? (b % 2 ? (a * (sqr(binpow(a, b / 2, mod)) % mod)) % mod : sqr(binpow(a, b / 2, mod)) % mod) : 1; }
- ll binmult(ll a, ll b, ll mod) { return b ? (b % 2 ? (2 * binmult(a, b / 2, mod) + a) % mod : (2 * binmult(a, b / 2, mod)) % mod) : 0; }
- /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
- //const ll to[5]={0,4,6,7,9};
- const ll N=2*1e3+1;
- const ll R=1e4;
- const ll to[7]={1,2,3,1,3,2,1};
- vector<ll>ans;
- ll mn=LLONG_MAX;
- void brute(vector<ll>a){
- // vector<ll>b=a;
- // cout<<b.back()<<endl;
- string man=to_string(a.back());
- if(len(man)>=2){
- for(ll i=0;i<len(man)-1;i++){
- string cs=man.substr(0,i+1);
- ll f=stoll(cs);
- // cout<<cs<<endl;
- cs=man.substr(i+1,len(man)-i-1);
- ll s=stoll(cs);
- if(s!=f){
- // ll need=
- a.p_b(abs(f-s));
- brute(a);
- a.pop_back();
- }
- }
- }
- if(a.back()<mn){
- ans=a;
- mn=a.back();
- }
- // cout<<sz(a)<<endl;
- // for(auto u : a){
- // cout<<u<<" ";
- // }
- // cout<<"Bruting"<<endl;
- }
- string cut (string s)
- {
- int i = 0;
- int j = len(s) - 1;
- string a = (s.substr(0, 1));
- string b = (s.substr(len(s) - 1, len(s)));
- while (i + 1 != j)
- {
- ll q = stoll(a);
- ll w = stoll(b);
- if (q == w)
- {
- i++;
- a += s[i];
- reverse(all(b));
- }
- else if (q > w)
- {
- j--;
- reverse(all(b));
- b += s[j];
- reverse(all(b));
- }
- else if (q < w)
- {
- i++;
- a[i] += s[i];
- }
- }
- if (a == b)
- return s;
- else
- return to_string(abs(stoll(a) - stoll(b)));
- }
- vector<ll> solve(ll n){
- string s = to_string(n);
- vector <ll> anss;
- anss.push_back(stoll(s));
- while (len(s) != 1)
- {
- int temp_len = len(s);
- s = cut(s);
- if (len(s) == temp_len)
- {
- return anss;
- }
- anss.push_back(stoll(s));
- }
- cout<<sz(anss)<<endl;
- return anss;
- }
- void check(){
- auto bind_f=bind(uniform_int_distribution<ll>(1,1e12),mt19937(time(0)));
- while(1){
- ll n=bind_f();
- vector<ll>pog;
- pog.p_b(n);
- brute(pog);
- vector<ll>lya=ans;
- vector<ll>t=solve(n);
- if(t.back()>lya.back()){
- cout<<"Wrong answer"<<" "<<n<<endl;
- cout<<"Your answer :"<<t.back()<<endl;
- cout<<"Jury's answer :"<<lya.back()<<endl;
- system("pause");
- break;
- }
- else{
- cout<<"Ok's"<<endl;
- }
- ans.clear();
- mn=LLONG_MAX;
- }
- }
- signed main(){
- fast_io;
- // ll t;
- // cin>>t;
- // while(t--){
- // ll n;
- // cin>>n;
- // mn=LLONG_MAX;
- // vector<ll>b;
- // b.p_b(n);
- // brute(b);
- // cout<<sz(ans)<<" ";
- // for(auto u : ans) cout<<u<<" ";
- // cout<<endl;
- // ans.clear();
- // }
- check();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement