Районная олимпиада 2019-2020 информатика

Задача B. Четные цифры

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

1 секунда

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

256 мегабайт

Дается два целых натуральных числа $L$ и $R$. Нужно посчитать сколько существует чисел от $L$ до $R$, включительно, у которых все цифры в десятичной записи четные. Найдите ответ.

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

В первой строке входных данных дано два натуральных числа $L$ и $R$ $(1 <= L <= R <= 10^{10})$.

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

Выведите одно целое число — ответ на задачу.

Система оценки

Данная задача содержит $10$ тестов. Каждый тест оценивается в $10$ баллов:

1. $1 <= L <= R <= 10^2$. Тесты с номерами 1-2.
2. $1 <= L <= R <= 10^6$. Тесты с номерами 3-4.
3. $1 <= L <= R <= 10^{10}$. Тесты с номерами 5-10.

Пример:

Вход

3 10

Ответ

3

( Aibar Kuanyshbay )

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

Поздно конечно, но надеюсь поможет

показать/скрыть код

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define w(x) cout<<(#x)<<" = "<<x<<endl;

const int N = 2e5 + 7;
const int M = 2e6 + 7;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;

int pos(ll x) {
    int op = 1;;
    while (x) {
        if((x % 10) % 2) return op;
        x = x / 10;
        op = op * 10;
    }
    return -1;
}

int main() {
    ll l, r, ans = 0;
    cin >> l >> r;
    for (l; l <= r; ++l) {
        if(l % 2) continue;
        ll temp = pos(l);
        if(temp == -1) ++ans;
        else l = l + temp - l % temp - 1;
    }
    cout << ans;
    return 0;
}

C++

Copy

показать/скрыть код

count=0
n=[int(input("первое число от: ")),int(input("второе число до:"))]
for i in range(n[0],n[1]+1):
    if i %2==0:print(i);count+=1
    else:continue
print('Ответ: - ',count)

C++

Copy

#include <bits/stdc++.h>

using namespace std;

#define ll long long

#define pb push_back

#define mp make_pair

#define fr first

#define sc second

#define all(x) x.begin(), x.end()

#define rall(x) x.rbegin(), x.rend()

#define w(x) cout<<(#x)<<" = "<<x<<endl;

const int N = 2e5 + 7;

const int M = 2e6 + 7;

const int MOD = 1e9 + 7;

const int INF = 0x3f3f3f3f;

int pos(ll x) {

int op = 1;;

while (x) {

if((x % 10) % 2) return op;

x = x / 10;

op = op * 10;

}

return -1;

}

int main() {

ll l, r, ans = 0;

cin >> l >> r;

for (l; l <= r; ++l) {

if(l % 2) continue;

ll temp = pos(l);

if(temp == -1) ++ans;

else l = l + temp - l % temp - 1;

}

cout << ans;

return 0;

}

показать/скрыть код

#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 <ll, ll> pll;
typedef vector < int > vi;
typedef vector < ll > vll;
typedef set < int > si;
const int N = 2e5 + 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;

ll l, r, x, ans;

bool ade(unsigned long long x)
{
    for (; x != 0; x /= 10)
        if ((x % 10) % 2 != 0)
            return false;

    return true;
}

ll sz(ll a) {
    ll res = 0;
    while(a) {
        res++;
        a /= 10;
    }
    return res;
}

void next() {
    x += 2;
    ll y = 10;
    while(x % y == 0) {
        x += y;
        y *= 10;
    }
}

ll find(ll a) {
    if(ade(a)) {
        return a;
    }
    ll y = pow(10, sz(a) - 1);
    while((a / y) % 2 == 0) {
        y /= 10;
    }
    a /= y;
    a++;
    a *= y;
    return a;
}

int main () {
    start
    cin >> l >> r;
    x = find(l);
    for( ; x <= r; next()) {
        ans++;
    }
    cout << ans;
    return 0;
}

C++

Copy

#include <bits/stdc++.h>

#include <fstream>

using namespace std;

ll l, r;

ll t[12];

int check(ll n) {

int cnt = 0;

while (n) {

if (n % 10 != 8)

break;

else cnt++;

n /= 10;

}

return cnt;

}

ll f(ll n) {

ll i = 2, res = 0, cnt = 0;

while (i <= n) {

res++;

cnt = check(i);

i += t[cnt];

}

return res;

}

void solve() {

cin >> l >> r;

cout << f(r) - f(l-1) << endl;

}

int main() {

ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

cerr << setprecision(10) << fixed;

/*ofstream fout;

ifstream fin;

fin.open("input.txt");

fout.open("output.txt");*/

ll p = 12, cnt = 10;

t[0] = 2;

for (int i = 1; i <= 11; i++) {

t[i] = p;

p = cnt*10 + p;

cnt *= 10;

}

int tt = 1;

//cin >> t;

while (tt--) {

solve();

}

/*fin.close();

fout.close();*/

return 0;

}