Ограничение по времени: 1 секунда
Ограничение по памяти: 256 мегабайт
Алиса решила поздравить своего друга с началом нового учебного года. Впереди холодная осень, поэтому она решила связать для него собственными руками шарф.
Незаметно для друга Алиса узнала, что ему большего всего нравятся к различных цветов. Алиса приняла решение связать шарф размером n × m, в котором будут чередоваться полоски различных цветов. Её друг никогда не ищет лёгких путей, поэтому она решила, что шарф с горизонтальными или вертикальными полосками покажется ему слишком примитивным. Алиса решила, что полоски определённо должны быть диагональными!
Закончив вязать шарф, Алиса вспомнила, что один из к цветов её друг считает особенным!
Это цвет с, который, по его мнению, приносит школьникам удачу на олимпиадах по информатике. И Алисе стало невероятно интересно, сколько фрагментов шарфа имеют именно такой цвет. Шарф получился очень большим, Алиса очень устала, пока его вязала, поэтому сама она уже не может ответить на этот вопрос и просит вас о помощи…
Более формально шарф можно представить в виде таблицы размером n х m, каждая клетка которой покрашена в один из k цветов. Цвета нумеруются от 1 до к.
Первая строка таблицы покрашена в цвета 1, 2,…, k, 1, 2, …, k и т.д. Каждая следующая строка получена из предыдущей сдвигом влево на одну клетку. Таким образом, таблица состоит из диагональных полос.
При n = 4, m = 8 и k = 3 таблица будет иметь следующий вид:___
По данным числам n m k и c определите, сколько всего клеток покрашено в цвет c?
1 Ответ
Здесь ответ примерно будет таковым:
- #include <iostream>
- #define ll long long
- using namespace std;
- ll n, m, c, k;
- ll first_part_count() {
- ll max_x = (n — c — 1) / k;
- return (c + 1) * (max_x + 1) + k * (max_x + 1) * max_x / 2;
- }
- ll sec_part_count() {
- ll min_x = (n — c — 1) / k;
- ll max_x = (m — c — 1) / k;
- return n * (max_x — min_x);
- }
- ll third_part_count() {
- ll min_x = (m — 1 — c) / k;
- ll max_x = (n + m — 2 — c) / k;
- return (max_x — min_x) * (n + m — 1 — c) — k * (max_x — min_x) * (min_x + max_x + 1) / 2;
- }
- int main() {
- cin >> n >> m >> k >> c;
- if (n > m) swap(n, m);
- cout << first_part_count() + sec_part_count() + third_part_count() << «\n«;
- }