Лямбда: Разбор и дорешивание 2-го этапа олимпиады по информатике 2018 г.

Результаты
Ссылка на олимпиаду

логин: brest-rayon-2018-292
пароль:6udan8Wpuw
Задачи

Сегодня у Маши олимпиада по информатике. Как всегда, в школу Маша едет на троллейбусе и покупает билетик. Маша верит, что билетики имеют особую силу, и чем более счастливый ей попадется билет, тем лучше она решит свои задания. Счастьем билета называется максимальное число повторений какой-то цифры в номере билета.

Например, для билета с номером 14533, счастье будет равно 2, потому что цифра 3 повторяется 2 раза.

Маша очень волнуется перед олимпиадой, поэтому никак не может посчитать счастье своего билетика сама. Помогите ей, пожалуйста, в этой задаче.

Формат ввода

В единственной строке содержится одно целое число N (0 ≤ N ≤ 10¹⁸) без лидирующих нулей.

Формат вывода

Выведите единственное число - счастье билета.

Пример 1

Ввод	Вывод
123	1

Пример 2

Ввод	Вывод
7777	4

Пример 3

Ввод	Вывод
14533	2

Решение 1 (100 б.)

#include <fstream>
#include <string>
#include <algorithm>
using namespace std;
ifstream in("input.txt");
ofstream out ("output.txt");

int main(){
string s;
in >> s;

unsigned long long dl, c = 0, max = 0, i;
dl = s.length();
int m[dl];

for (i = 0; i < dl; i++)
m[i] = s[i] - '0';
sort (m, m + dl);

for (i = 0; i < dl; i++){
c = count (m, m + dl, m[i]);
i = i + c - 1;
if (max < c) {max = c;}
}
out << max;
return 0;
}

Решение 2 (100 б)
#include <iostream>
#include <fstream>
using namespace std;

int main() {
ifstream in;
ofstream out;
in.open("input.txt");
out.open("output.txt");
string s;
int a[9] = {0};
int x = 0, i;
in >> s;
for (i = 0; i < s.length(); i++) {
int k = s[i] - 48;
a[k-1]++;
}
for (i = 0; i <= 9; i++)
if (a[i] > x) x = a[i];
out << x;
in.close();
out.close();
}

По дороге в школу Маша смотрела в окно из троллейбуса и заметила, что в ее родном городе, оказывается, очень много фонарных столбов. А именно, она насчитала N столбов с высотами A_i. Маша считает, что отрезок из подряд идущих столбов является красивым, если высота первого и последнего столба в этом отрезке отличается.

Ехать было очень долго, поэтому Маше стало скучно. Ей стало интересно, сколько же в ее городе есть красивых отрезков.

Формат ввода

В первой строке содержится одно целое число N (1 ≤ N ≤ 200 000) Во второй строке - N целых чисел A_i (0 ≤ A_i ≤ 1 000 000 000), разделенных пробелами - высоты столбов.

Формат вывода

Выведите единственное число - количество красивых отрезков из столбов.

Пример 1

Ввод	Вывод
5 1 2 3 4 5	10

Пример 2

Ввод	Вывод
4 2 3 2 3	4

Пример 3

Ввод	Вывод
6 1 2 3 3 2 1	12

Примечания

В первом примере Маша может выбрать любые два столба. Отрезок между ними будет красивым, потому что высота первого и последнего столба будет отличаться.

Во втором примере ей подходит только 4 отрезка (выделены жирным шрифтом):
2 3 2 3, 2 3 2 3, 2 3 2 3 и 2 3 2 3

В третьем примере - 12 отрезков:

1 2 3 3 2 1, 1 2 3 3 2 1, 1 2 3 3 2 1, 1 2 3 3 2 1, 1 2 3 3 2 1, 1 2 3 3 2 1, 1 2 3 3 2 1, 1 2 3 3 2 1, 1 2 3 3 2 1, 1 2 3 3 2 1, 1 2 3 3 2 1, 1 2 3 3 2 1

Решение 1 (100 б)

#include <fstream>
#include <map>
#include <algorithm>
using namespace std;
ifstream in("input.txt");
ofstream out ("output.txt");
int main(){
int n;
in >> n;
int i, v = n;
map <long long, long long> mp;
long long m[n];
unsigned long long kol = 0;
for (i = 0; i < n; i++){
in >> m[i];
mp[m[i]] ++;
}
for (i = 0; i < n; i++){
kol = kol + v - mp[m[i]];
mp[m[i]] --;
v --;
}
out << kol;
return 0;

}

Решение 2 (100 б)

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;

int main() {
ifstream in;
ofstream out;
in.open("input.txt");
out.open("output.txt");
long long n, i, s = 0, k = 0;
in >> n;
vector <long> a(n), b(n);
int c[200000] = {0};
for (i = 0; i < n; i++)
in >> a[i];
sort(a.begin(), a.end());
b = a;
c[0]++;
for (i = 1; i < b.size(); i++)
if (b[i] == b[i-1]) c[k]++; else c[++k]++;
int f = n;
for (int i = 0; i < n; i++) {
while (c[i]) {
s += f - c[i];
f--;
c[i]--;
}
}
out << s;
in.close();
out.close();

}

Обернувшись, Маша увидела, что прямо за ней сидел ее давний школьный друг Вася. Вася тоже увлекался информатикой, поэтому с радостью выслушал ее идею столбов и красивых отрезков. Более того, Вася даже предложил ее улучшить, и сказал, что красотой набора столбов на самом деле является сумма высот столбов в нем, а разница между первым и последним - на самом деле ни при чем.

Маша задумалась, и решила проверить Васю - предложила ему найти самый красивый отрезок из всех. Вася с легкостью справился с задачей, и сказал, что все столбы с первого по последний - конечно же и есть самый красивый отрезок. А в ответ предложил более интересную задачу: среди всех возможных отрезков найти K-ый по красоте отрезок.

Маша еще быстрее справилась с поставленной задачей. Сможете ли вы?

Формат ввода

В первой строке содержится два целых числа N и K (1 ≤ N ≤ 200 000, 1 ≤ K ≤ 10¹²), разделенные пробелами.
Гарантируется, что K будет не больше, чем возможное число отрезков.

Во второй строке - N целых чисел A_i (0 ≤ A_i ≤ 1 000 000 000), разделенных пробелами - высоты столбов.

Формат вывода

Выведите единственное число - K-ую по величине возможную красоту отрезка.

Пример 1

Ввод	Вывод
5 1 1 2 3 4 5	15

Пример 2

Ввод	Вывод
4 5 2 3 2 3	5

Пример 3

Ввод	Вывод
6 3 1 2 3 3 2 1	11

Примечания

В первом примере Маше нужно выбрать первый по красоте отрезок - то есть самый красивый. Это и будет отрезок 1 2 3 4 5, сумма высот в нем равна 15.

Во втором примере первым по красоте отрезком будет 2 3 2 3, его красота равна 10.

Вторым по красоте - 2 3 2 3, его красота равна 8.

Третьим по красоте - 2 3 2 3, его красота равна 7.

Есть три отрезка с красотой 5 - отрезки 2 3 2 3, 2 3 2 3, 2 3 2 3. Они являются четвертым, пятым и шестым по красоте. Нас интересует красота пятого по красоте отрезка. Значит, ответ - 5.

Частичное решение ( 54 б)

#include <fstream>
#include <algorithm>
using namespace std;
ifstream in("input.txt");
ofstream out ("output.txt");
int main(){
int n, k;
in >> n >> k;
int i, j, I;
unsigned long long m[n], sum, v, d = (n + 1) * n / 2;
long long md[d];
for (i = 0; i < n; i++)
in >> m[i];
I = 0;
for (i = 0; i < n - 1; i++){
v = m[i];
sum = m[i];
md[I] = sum;
I ++;
for (j = i + 1; j < n;j++){
sum += m[j];
md[I] = sum;
I++;
}
}
sort(md, md + I);
out << md[I - k];
return 0;
}

Частичное решение (60 б)

#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
using namespace std;

int main() {
ifstream in;
ofstream out;
in.open("input.txt");
out.open("output.txt");
long long int n, k, l = 0, s;
in >> n >> k;
vector <long long> a(n), b(n*(n+1)/2);
for (int i = 0; i < n; i++)
in >> a[i];
for (int i = 0; i < n; i++) {
b[l] = a[i]; l++; s = a[i];
for (int j = i-1; j >= 0; j--) {
s += a[j]; b[l] = s; l++;
}
}
sort(b.begin(), b.end());
out << b[b.size()-k];
in.close();
out.close();

}

Придя в школу, Маша поняла, что совершенно не знает дороги до кабинета информатики. Проходившая мимо первоклассница объяснила ей, что надо просто пройти от столовой до другой столовой, а сразу за ней будет кабинет информатики. Посмотрев по сторонам, Маша поняла, что в школе есть много столовых, а вот от какой и до какой именно ей надо пройти, она наверняка не знает. Поэтому она решила выбрать такие две столовых, что время на проход между ними будет минимально.

Школа представляет собой N комнат, между M парами из которых можно пройти напрямую. Kиз них являются столовыми. Задача Маши заключается в том, чтобы найти такие 2 столовых, что время на проход между ними будет минимально. Именно этим путем она пойдет искать кабинет информатики.

Помогите Маше найти кратчайшее такое расстояние.

Формат ввода

В первой строке содержится три целых числа N, M и K (2 ≤ N ≤ 100 000, 1 ≤ M ≤ 200 000, 2 ≤ K ≤ N), разделенные пробелами.

Во второй строке - K различных целых чисел S_i (1 ≤ S_i ≤ N), разделенных пробелами - номера комнат, являющихся столовыми.

В следующих M строках содержится описание переходов между комнатами. Каждая строка содержит три числа A_i, B_i (1 ≤ A_i, B_i ≤ N), C_i (1 ≤ C_i ≤ 10⁹), разделенных пробелами, и означает, что между комнатами A_i и B_i можно пройти в обе стороны за C_i секунд. Между парой комнат может быть несколько разных переходов с разными C_i.

Гарантируется, что между хотя бы одной парой столовых существует путь.

Формат вывода

Выведите единственное число - минимально возможное время на проход между парой столовых.

Пример 1

Ввод	Вывод
4 3 3 1 3 4 1 2 10 3 2 2 2 4 3	5

Пример 2

Ввод	Вывод
4 4 2 1 2 3 1 3 1 2 10 3 4 3 4 2 1	7

Примечания

В 40% тестов K=2, C_i = 1.

Частичное решение (66 б.)

Даник Качаловский

#include <fstream>
#include <vector>
#include <queue>
#include <map>
using namespace std;
ifstream in("input.txt");
ofstream out ("output.txt");
int main(){
int n, m, k, i, j, ij, a, b, c, w;
long long min = 2000000000000000000;
in >> n >> m >> k;
int inf = 1000000001;
int kol[k], mas[n][n];
map<int, vector <int> > sm;

queue <int> Queue;

for (ij = 0; ij < k; ij++)
in >> kol[ij];

for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
mas[i][j] = 0;

vector <int> vrem;
for (ij = 0; ij < m; ij++){
in >> a >> b >> c;
mas[a - 1][b - 1] = c;
mas[b - 1][a - 1] = c;
vrem = sm[a - 1];
vrem.push_back(b - 1);
sm[a - 1] = vrem;
vrem = sm[b - 1];
vrem.push_back(a - 1);
sm[b - 1] = vrem;
}
for (ij = 0; ij < k - 1; ij++){
vector <long long> v (n, 2000000000000000000);
vector <int> pos(n, 0);
v[kol[ij] - 1] = 0;
Queue.push(kol[ij] - 1);
pos[kol[ij] - 1] = 1;
while (!Queue.empty()){
w = Queue.front();
Queue.pop();
if(!sm[w].empty())
for(i = 0; i < sm[w].size(); i++){
if (v[sm[w][i]] > v[w] + mas[w][sm[w][i]])
v[sm[w][i]] = v[w] + mas[w][sm[w][i]];
if (pos[sm [w][i]] == 0 && v[sm[w][i]] < min)
Queue.push(sm[w][i]);
pos[sm[w][i]] = 1;
}
}
for (i = 0; i < k; i++)
if (min > v[kol[i] - 1] && v[kol[i] - 1] != 0)
min = v[kol[i] - 1];
}
out << min;
return 0;
}

Разбор от Тротюка

Счастливые билеты

#include <fstream> // для файлового ввода-вывода

#include <iostream>

#include <string>

#include <vector>

using namespace std;

// для файлового ввода-вывода

// ifstream in("input.txt");

// ofstream out("output.txt");

int main() {

string s;

// in >> s;

cin >> s;

vector <int> n(10,0);

for (int z = 0; z < s.length(); z++) n[s[z] - '0']++;

int maxn = 0;

for (int z = 0; z < 10; z++) if (maxn < n[z]) maxn = n[z];

cout << maxn;

// out << maxn;

return 0;

}

Столбы

#include <fstream> // для файлового ввода-вывода

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

// для файлового ввода-вывода

// ifstream in("input.txt");

// ofstream out("output.txt");

int main() {

int n;

cin >> n;

// in >> n;

vector <int> st(n);

for (int z = 0; z < n; z++) cin >> st[z]; // in >> st[z];

if (n == 1) {

cout << 0; return 0;

} // нет красивых отрезков

sort(st.begin(), st.end());

vector <int> kvo;

int KVO = 1, hst = st[1]; // количество одинаковых столбов и их высота

for (int z = 1; z < st.size(); z++)

if (st[z]==st[z-1]) KVO++; // подсчитываем одинаковые столбы

else {

kvo.push_back(KVO); // начинаем новый отсчет

KVO = 1;

}

kvo.push_back(KVO); // последний подсчет

if (kvo.size()==1) {

cout << 0; return 0;

} // нет красивых отрезков

long long kras = 0; // число красивых отрезков

for (int z = 0; z < kvo.size() - 1; z++) {

kras += kvo[z] * (n - kvo[z]);

n -= kvo[z];

}

cout << kras;

// out << kras;

return 0;

}

#include <fstream>

#include <map>

using namespace std;

ifstream in("input.txt");

ofstream out("output.txt");

int main() {

long long ans = 0;

long long n, k, l=0;

in>>n;

map<int, int>a;

for(long long i=0;i<n;i++){in>>k; a[k]++;l++;ans=ans+(l-a[k]);}

out<<ans;

return 0;

}

Неожиданная встреча

#include <fstream> // для файлового ввода-вывода

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

// для файлового ввода-вывода

// ifstream in("input.txt");

// ofstream out("output.txt");

int main() {

int n; long long k;

cin >> n >> k;

// in >> n >> k;

vector <int> st(n);

for (int z = 0; z < n; z++) cin >> st[z]; // in >> st[z];

if (n == 1) {

cout << st[0]; return 0;

// out << st[0]; return 0;

} // типа - единственный столб. Возможно, выводить нужно 0.

vector <long long> kras;

long long KRAS;

for (int z = 0; z < n; z++) {

KRAS = 0;

for (int x = z; x < n; x++) {

KRAS += st[x];

kras.push_back(KRAS);

}

sort(kras.begin(), kras.end());

cout << kras[kras.size()-k];

// out << kras[kras.size()-k];

return 0;

}

Задачи 20172018 года
Разбор

Лямбда

четверг, 13 декабря 2018 г.

Разбор и дорешивание 2-го этапа олимпиады по информатике 2018 г.

A. Счастливые билеты

Формат ввода

Формат вывода

Пример 1

Пример 2

Пример 3

B. Столбы

Формат ввода

Формат вывода

Пример 1

Пример 2

Пример 3

Примечания

C. Неожиданная встреча

Формат ввода

Формат вывода

Пример 1

Пример 2

Пример 3

Примечания

D. Запутанная школа

Формат ввода

Формат вывода

Пример 1

Пример 2

Примечания

Комментариев нет:

Отправить комментарий

Количество·просмотров

Постоянные читатели

Ограничение времени	1 секунда
Ограничение памяти	256Mb
Ввод	input.txt
Вывод	output.txt

Ограничение времени	1 секунда
Ограничение памяти	256Mb
Ввод	input.txt
Вывод	output.txt

Ограничение времени	1 секунда
Ограничение памяти	256Mb
Ввод	input.txt
Вывод	output.txt

Ограничение времени	1 секунда
Ограничение памяти	256Mb
Ввод	input.txt
Вывод	output.txt

четверг, 13 декабря 2018 г.

Разбор и дорешивание 2-го этапа олимпиады по информатике 2018 г.

A. Счастливые билеты

Формат ввода

Формат вывода

Пример 1

Пример 2

Пример 3

B. Столбы

Формат ввода

Формат вывода

Пример 1

Пример 2

Пример 3

Примечания

C. Неожиданная встреча

Формат ввода

Формат вывода

Пример 1

Пример 2

Пример 3

Примечания

D. Запутанная школа

Формат ввода

Формат вывода

Пример 1

Пример 2

Примечания

Комментариев нет:

Отправить комментарий

четверг, 13 декабря 2018 г.