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

Задача B. Делимость

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

1 секунда

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

256 мегабайт

ОМА решил придумать свой признак делимости на 8. ОМА будет считать что число делится на 8 если существует перестановка цифр числа такая что новое число было без лидирующих нулей и число делится на 8. Вам надо сказать делится ли число на 8 по правилам ОМЫ.

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

В первой строке дано цело число $n$ $(1 \leq n \leq 10^3) $ - длинна числа. $\\$ Во второй строка дана строка состоящая из цифр $s$ - число которое надо проверить.

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

Выведите YES если число делится на 8 по правилам ОМЫ иначе NO

Примеры:

Вход

2
23

Ответ

YES

Вход

3
101

Ответ

NO

Замечание

Перестановка числа х - это число, состоящее из тех же цифр, что и х, но в другом порядке. Например, числа, которые можно получить путем перестановки цифр числа 123: 132, 213, 231, 312, 321 В первом примере из числа 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')