Районная олимпиада по информатике. 2018-2019 учебный год. 8-11 классы

Есеп B. Бөлінеді ме

Ограничение по времени:

1 second

Ограничение по памяти:

256 megabytes

ОМА санның 8-ге бөлінгіштігінің өз қасиетін ойлап табуды ұйғарды. Егер берілген санның цифрларының орындарын ауыстрығанда, бастаушы нөлдерсіз және 8-ге бөлінетін сандар тізбегі табылатын болса, ОМА бұл санды 8-ге бөлінеді деп атайды.

Формат входного файла

Бірінші жолда бүтін $n$ саны берілген $(1 \leq n \leq 10^3) $ - санның ұзындығы. $\\$ Екінші жолда цифрлардан тұратын $s$ жолы берілген - тексеру қажет сан.

Формат выходного файла

Егер берілген сан 8-ге бөлінетін болса YES, бөлінбесе NO жазуларын шығарыңыз.

Примеры:

Вход

2
23

Ответ

YES

Вход

3
101

Ответ

NO

Замечание

Сандар тізбегі дегеніміз, берілген жолдағы цифлардың орындарын ауыстыру жолымен алынған тізбек. Мысалы 123 жолынан, цифрларды орын ауыстыру арқылы 321, 312, 213, 231, 132 деген сандар тізбегін алуға болады. Бірінші мысалда 23 санынан 8-ге бөлінетін 32 санын алуға болады жауап YES. Екінші мысалда 101 санынан 8-ге бөлінетін сан алуға болмайды, жауап NO.$\\$ $\\$ Subtask 1: $(n \leq 100)$ $\\$ Subtask 2: $(n \leq 1000)$ ( Nurdaulet Akhanov )

Комментарий/решение

AC

кодты корсету/жасыру

#include<iostream>
#include<string>
#include<vector>
#include<map>
#define ll long long
using namespace std;
void ok(bool q){
	if(q)cout<<"YES";
	else cout<<"NO";
	exit(0);
}
int main(){
	ll n,k;
	string s;
	map<ll,ll>m;
	vector<string>v;
	cin>>n;
	if(n==1){
		cin>>k;
		if(k%8==0)ok(1);
		else ok(0);
	}
	else if(n==2){
		cin>>k;
		if(k%8==0)ok(1);
		else {
		k=(k%10)*10+k/10;
		if(k%8==0)ok(1);
		else ok(0);	
		}
	}
	cin>>s;
	for(int i=0;i<s.size();i++)m[s[i]-'0']++;
	for(int i=0;i<1000;i+=8){
		map<ll,ll>w;
		w[i/100]++;
		w[i%100/10]++;
		w[i%10]++;
		if(m[i/100]>=w[i/100]&&m[i%100/10]>=w[i%100/10]&&m[i%10]>=w[i%10])ok(1);
	}
	ok(0);
}

кодты корсету/жасыру

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
ios::sync_with_stdio(false);
int n, b=0;
cin >> n;
string s;
cin >> s;

if (n == 1) {
    if ( ((s[0])-'0') % 8 == 0) {cout << "YES"; return 0;}
} else if (n == 2) {
    if( ((s[0]-'0')*10 + (s[1])-'0') % 8 == 0) {cout << "YES"; return 0;}
    else if( ((s[1]-'0')*10 + (s[0])-'0') % 8 == 0) {cout << "YES"; return 0;}
}
else{
    
    do{
        if(s[0]!='0'){
            if( ((s[n-3]-'0')*100 + (s[n-2] - '0')*10 + (s[n-1])-'0') % 8 == 0 ){ cout << "YES"; return 0;}
        
            else if(s[n-3] == '0' && s[n-2] == '0' && s[n-1] == '0') {cout << "YES"; return 0;}
            
            
        }
    } while(next_permutation(s.begin(), s.end()));
} 
cout << "NO";
    return 0;
}

кодты корсету/жасыру

#include <bits/stdc++.h>
using namespace std;

int cnt[10]={};

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin >> n;
    int nonzero=0;
    for (int i=1; i<=n; i++) {
        char cur;
        cin >> cur;
        cnt[cur-'0']++;
        if (cur!='0') nonzero++;
    }

    if (n==1) {
        if (cnt[0]==1 || cnt[8]==1) cout << "YES\n";
        else cout << "NO\n";
        return 0;
    }
    else if (n==2) {
        int a=-1,b=-1;
        for (int i=0; i<10; i++) {
            if (cnt[i]==2) {
                if ((10*i + i)%8==0) cout << "YES\n";
                else cout << "NO\n";
                return 0;
            }
            else if (cnt[i]==1) {
                if (a==-1) a = i;
                else b = i;
            }
        }
        if ((10*a+b)%8==0 || (10*b+a)%8==0) cout << "YES\n";
        else cout << "NO\n";
        return 0;
    }

    for (int i=0; i<1000; i++) {
        if (i%8!=0) continue;
        int a = (i/100)%10, b = (i/10)%10, c = i%10;
        if (cnt[a]>0) {
            cnt[a]--;
            if (a!=0) nonzero--;
            if (cnt[b]>0) {
                cnt[b]--;
                if (b!=0) nonzero--;
                if (cnt[c]>0) {
                    cnt[c]--;
                    if (c!=0) nonzero--;
                    if (nonzero==0 && a!=0) {
                        cout << "YES\n";
                        return 0;
                    }
                    if (nonzero>0) {
                        cout << "YES\n";
                        return 0;
                    }
                    cnt[c]++;
                    if (c!=0) nonzero++;
                }
                cnt[b]++;
                if (b!=0) nonzero++;
            }
            cnt[a]++;
            if (a!=0) nonzero++;
        }
    }
    cout << "NO\n";
    return 0;
}

ACCEPTED

кодты корсету/жасыру

// ~maqsat~

// #pragma GCC target ("avx2")
// #pragma GCC optimization ("Ofast")
// #pragma GCC optimization ("unroll-loops")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define F first
#define S second
#define in insert
#define pb push_back
#define eb emplace_back
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
#define count1 __builtin_popcountl
#define debug(x) cerr << (#x) << " = " << (x) << "\n"
#define ACCELERATE ios_base::sync_with_stdio(false),cin.tie(nullptr)
#define fre(f) if(fopen(f".in", "r")) freopen(f".in", "r", stdin),freopen(f".out", "w", stdout)

using namespace std;
using namespace __gnu_pbds;

using ll = long long;
using ull = unsigned long long;
// using big = __int128_t; // -10^38...10^38
using db = double;
using ld = long double;
typedef pair<int,int> ii;
typedef pair<ll,ll> pll;

template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>
template <class T> inline void cmin(T &a, T b) { a = min(a, b); }
template <class T> inline void cmax(T &a, T b) { a = max(a, b); }

const int oo = 0x3f3f3f3f;
const ll N = 1e5 + 345;
const ll MOD = 1e9 + 7;
const ll INF = 1e18 + 9;
const db EPS = 1e-9;
const db PI = acos(-1); // 3.14159265358979323846
const int dx[] = {1, -1, 0, 0, 1, 1, -1, -1};
const int dy[] = {0, 0, 1, -1, 1, -1, -1, 1};

vector <int> v;

inline void go(int x = 0) {
    if(x > 992) return;
    v.eb(x);
    go(x+8);
}

int main() {
	fre("");
	ACCELERATE;
    // clock_t start = clock();
    
    int n;
    cin >> n;
    string s;
    cin >> s;
    
    if(n <= 3) {
        sort(all(s));
        do {
            int x = 0;
            for(int i = 0; i < n; i++)
                x *= 10, x += s[i] - 48;
            if(x % 8 == 0) return cout << "YES", 0;
        } while(next_permutation(all(s)));
        cout << "NO";
    }
    else {
        go();
        vector <int> cnt(10, 0), ctr(10, 0);
        for(int i = 0; i < n; i++) cnt[s[i]-48]++;
        
        int m = sz(v);
        for(int i = 0; i < m; i++) {
            int x = v[i];
            while(x) {
                ctr[x%10]++;
                x /= 10;
            }
            
            bool f = 0;
            for(int i = 0; i <= 9; i++) {
                if(cnt[i] < ctr[i]) { f = 1; break; }
            }
            if(!f) return cout << "YES", 0;
        }
        cout << "NO";
    }
    
    // cerr << '\n' << ( clock() - start ) / (double) CLOCKS_PER_SEC;
	return 0;
}

Жадное решение. Идея: если число из последних трех цифр числа делится на 8 то и само число делится на 8.

кодты корсету/жасыру

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define max3(a, b, c) max(a, max(b, c))
#define min3(a, b, c) min(a, min(b, c))
#define mp make_pair
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define F first
#define S second
#define start ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define y1 asdasd

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef unsigned long long ull;
typedef pair <int, int> pii;
typedef pair < pii, int > piii;
typedef pair <ll, ll> pll;
typedef pair < pll, ll > plll;
typedef vector < int > vi;
typedef vector < pii > vii;
typedef vector < ll > vl;
typedef vector < pll > vll;
typedef set < int > si;
const int N = 1e5 + 123;
const int N2 = 1e6 + 123;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll VERYINF = 1e18 + 5;
const double pi = 3.141592653589;

struct digit {
	int a[10];
	digit(){};
	digit(int b[]) {
		for(int i = 0; i < 10; i++) {
			a[i] = b[i];
		}
	}
} cnt;

int n;
string s;
vector < digit > num;

void precalc() {
	for(int i = 0; i < 1000; i += 8) {
		int b[10] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
		digit kol = digit(b);
		kol.a[i / 100]++;
		kol.a[(i % 100) / 10]++;
		kol.a[i % 10]++;
		num.pb(kol);
	}
}

void solve() {
	cin >> n >> s;
	precalc();
	for(int i = 0; i < n; i++) {
		cnt.a[s[i] - '0']++;
	}
	if(n == 2) {
		cnt.a[0]++;
	}
	if(n == 1) {
		cnt.a[0] += 2;
	}
	/*for(auto d : num) {
		for(int i = 0; i < 10; i++) {
			cout << d.a[i] << ' ';
		}
		cout << "\n";
	}*/
	for(auto d : num) {
		bool ok = true;
		for(int i = 0; i < 10; i++) {
			if(d.a[i] > cnt.a[i]) {
				ok = false;
				//cout << i << "\n";
				break;
			}
		}
		if(ok) {
			cout << "YES";
			return;
		}
	}
	cout << "NO";
}

int main () {
	start
	solve();
	return 0;
}

input()

a=input()

s=''

s1=a[::-1]

s+=s1

if int(s)%8==0:

print('YES')

else:

print('NO')

import itertools as it

n=input()

s=input()

a = it.permutations(s)

for i in a:

i=''.join(i)

if i[0]!=0 and int(i)%8==0:

print('YES')

break

else:

print('NO')

кодты корсету/жасыру

n = int(input())
a = int(input())
if n == len(str(a)):
    print("1. Right")

    def reverse(num):
        s = []

        # добовляем всё в список "s"
        for i in num:
            s.append(i)
        print(f"2. Right -> {s}")

        # переворот
        s.reverse()

        # преобразуем в слитное число
        s_reversed = int(''.join(map(str, s)))
        print(f"3. Right -> {s_reversed}")

        # делаем ответ для проверки делимости ОМА(то есть делимость на 8)
        oma = s_reversed / 8
        if str(oma)[-1] == "0":
            print("YES")
        else:
            print("NO")

    # Выводим
    reverse(str(a))
else:
    print("1. Wrong")

input()

if int(input()[::-1])%8==0:print('YES')

else:print('NO')