Блог пользователя PavelKunyavskiy

Codeforces Beta Round #73. Разбор (Div2)
Автор PavelKunyavskiy, 13 лет назад, По-русски
Задача Div2-A. Аккорд.
Нужно понять первым делом простую мысль - ноты по сути являются остатками по модулю 12. А значит минорный аккорд имеет вид {x, x+3, x+7} (mod 12), а мажорный - {x, x+4, x+7}.

Считывать ноты удобно как строки, после чего их лучше тут же заменить на соответствующее число от 0 до 11 - их номером. Для обработки надо было перебрать 6 возможных порядков следования нот в аккорде. Для каждого из 6 порядков проверить, является ли аккорд мажорным или минорным, и если так, то сразу вывести.

Не бывает одновременно минорного и мажорного аккорда - это проверяется перебором шести возможных систем сравнений.



Задача Div2-B. Клавиатура.
Для каждой из букв алфавита в двух вариантах - заглавном и строчном - последовательно проверяем, можно ли ее напечатать одной рукой, если нет, то печатается ли она двумя руками, или же вообще никаким количеством рук не печатается :-)
Для проверки рассматриваем несколько случаев.
Если буква маленькая, то надо просто проверить, есть ли такая буква на клавиатуре, и если нет, то она не печатается.
Если буква большая, то надо проверить для каждой клавиши с соответствующей буквой, если ли поблизости Shift, просто перебрав все пары кнопок на клавиатуре.
Если такой буквы нет ни одной, или нет ни одного Shift, то такая буква тоже не печатается.
Если же такая пара нашлась, но на слишком большом расстоянии, то для набора этой буквы требуется вторая рука.
Просуммируем по всем буквам текста количество рук, требуемых для набора, и вывалимся с -1, если какая-то буква не набирается ну вот совсем. Сложность - |T| + 52 * (n· m)2, и этого вполне достаточно.
Разбор задач Codeforces Beta Round 73 (Div. 2 Only)
  • Проголосовать: нравится
  • +11
  • Проголосовать: не нравится

13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
In Div-2 Problem B , why doesn't current position of our hand plays a role in determining the final answer.
→ Ответить
  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    In this problem letters typed independently.
    → Ответить
    • 9 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      include<bits/stdc++.h> include <ext/pb_ds/assoc_container.hpp> include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; using namespace std;

      int main() { ios_base::sync_with_stdio(false);cin.tie(0); int n, m, x; cin >> n >> m >> x;

      vector<pair<int, int>> shifts; map<char, vector<pair<int, int>>> characters;

      for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { char cell; cin >> cell; if (cell == 'S') { shifts.push_back({i, j}); } else { characters[cell].push_back({i, j}); } } }

      int q; cin >> q;

      long long int cnt = 0; for (int i = 0; i < q; ++i) { char query; cin >> query;

      if (isupper(query) && shifts.empty()) {
    cout << -1 << endl;
    return 0;
}

char lowercase_query = tolower(query);
if (characters.count(lowercase_query)) 
{
    if (isupper(query)) {
        int p=INT_MAX;
        for (auto &char_position : characters[lowercase_query]) {
            int min_dist = INT_MAX;
            for (auto &shift_position : shifts) {
                int dist = abs(char_position.first - shift_position.first)*abs(char_position.first - shift_position.first) + abs(char_position.second - shift_position.second)*abs(char_position.second - shift_position.second);
                min_dist = min(min_dist, dist);
            }
            p=min(p,min_dist);

        }
        if (p > x*x) {
                cnt++;

            }
    }
} 
else {
    cout << -1 << endl;
    return 0;
}

      }

      cout << cnt << endl; return 0; } why i got tle in test51

      → Ответить
13 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Now I understood the solution.
And thanks for the good contest.
→ Ответить
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А в задаче Div2-B кнопки (кроме Shift) могут повторяться?
→ Ответить
»
9 месяцев назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

include<bits/stdc++.h>

include <ext/pb_ds/assoc_container.hpp>

include <ext/pb_ds/tree_policy.hpp>

using namespace std; using namespace __gnu_pbds; using namespace std;

int main() { ios_base::sync_with_stdio(false);cin.tie(0); int n, m, x; cin >> n >> m >> x;

vector<pair<int, int>> shifts;
map<char, vector<pair<int, int>>> characters;

for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
        char cell;
        cin >> cell;
        if (cell == 'S') {
            shifts.push_back({i, j});
        } else {
            characters[cell].push_back({i, j});
        }
    }
}

int q;
cin >> q;

long long int  cnt = 0;
for (int i = 0; i < q; ++i) {
    char query;
    cin >> query;

    if (isupper(query) && shifts.empty()) {
        cout << -1 << endl;
        return 0;
    }

    char lowercase_query = tolower(query);
    if (characters.count(lowercase_query)) 
    {
        if (isupper(query)) {
            int p=INT_MAX;
            for (auto &char_position : characters[lowercase_query]) {
                int min_dist = INT_MAX;
                for (auto &shift_position : shifts) {
                    int dist = abs(char_position.first - shift_position.first)*abs(char_position.first - shift_position.first) + abs(char_position.second - shift_position.second)*abs(char_position.second - shift_position.second);
                    min_dist = min(min_dist, dist);
                }
                p=min(p,min_dist);

            }
            if (p > x*x) {
                    cnt++;

                }
        }
    } 
    else {
        cout << -1 << endl;
        return 0;
    }
}

cout << cnt << endl;
return 0;

} why i got tle in test51

→ Ответить