Авторські розв'язки задач другого туру у вищій лізі
Задача 1. "Аеропорт"
#include <iostream>
using namespace std;
// структура, що являє собою рейс
// мітить час початку та закінчення рейсу
// час вимірюється в хвилинах від початку доби
struct Flight { int Begin, End; };
// структура, що являє собою момент часу -- початок або кінець рейсу
// Time -- момент часу, що вимірюється в хвилинах від початку доби
// Type містить значення 1, якщо це початок рейсу, та -1, якщо це кінець рейсу
struct TimePoint { int Time; int Type; };
// функція, що пропускає всі пробільні символи в потоці s
void SkipSpaces(istream& s)
{
while(s.peek() <= ' ')
s.get();
}
// функція, що зчитує з потоку s значення часу
// у форматі, який відповдає умові задачі
// повертає значення часу в хвилинах від початку доби
int GetTime(istream& s)
{
SkipSpaces(s);
char h1 = s.get() - '0';
char h2 = s.get() - '0';
char separator = s.get();
char m1 = s.get() - '0';
char m2 = s.get() - '0';
return (h1 * 10 + h2) * 60 + (m1 * 10) + m2;
}
int main()
{
// прочитаємо з вхідного потоку значення кількості рейсів
int n;
cin >> n;
// створимо масив рейсів відповідного розміру
Flight* Schedule = new Flight[n];
// прочитаємо з вхідного потоку розклад
// та розмістимо його в масиві рейсів
// замінимо закінчення рейсу о 00:00 на 24:00
for(int i = 0; i < n; i++)
{
Schedule[i].Begin = GetTime(cin);
SkipSpaces(cin);
char separator = cin.get();
Schedule[i].End = GetTime(cin);
if (Schedule[i].End == 0)
Schedule[i].End = 24 * 60;
}
// підрахуємо кількість літаків в повітрі опівночі (в момент часу 00:00)
// фактично ця кількість дорівнює кількості рейсів, у яких значення часу
// початку рейсу перевищує значення часу закінчення рейсу
int c = 0;
for(int i = 0; i < n; i++)
if(Schedule[i].End < Schedule[i].Begin)
c++;
// створимо масив моментів часу відповідного розміру
TimePoint* A = new TimePoint[2*n];
// заповнимо масив моментів часу
// розмістимо в ньому всі початки та закінчення рейсів встановивши
// відповідне значення поля Type
for(int i = 0; i < n; i++)
{
A[2*i].Time = Schedule[i].Begin;
A[2*i].Type = 1;
A[2*i + 1].Time = Schedule[i].End;
A[2*i + 1].Type = -1;
}
// відсортуємо масив моментів часу за зростанням
// важливо, якщо моменти часу співпадають, то раніше
// повинні йти моменти закінчення рейсів, а потім початки
for(int i = 0; i < 2*n; i++)
{
int min = i;
for(int j = i + 1; j < 2*n; j++)
if(A[min].Time > A[j].Time)
min = j;
else if(A[min].Time == A[j].Time && A[min].Type == 1 && A[j].Type == -1)
min = j;
TimePoint t = A[i];
A[i] = A[min];
A[min] = t;
}
// переглядаючи моменти часу послідовно за зростанням будемо
// збільшувати кількість літаків в повітрі, якщо зустрічаємо
// початок рейсу, та зменшувати, якщо зустрічаємо закінчення рейсу
// дякуючи значенням поля Type це можна зробити простим додавання
// значення поля Type до кількості літаків в повітрі
// знайдемо максимальне значення, якого сягає кількість літаків в повітрі
// це і є мінімально необхідна кількість літаків для обслуговування всіх
// рейсів за заданим розкладом
int max_c = c;
for(int i = 0; i < 2*n; i++)
{
c += A[i].Type;
if (c > max_c) max_c = c;
}
// виведемо отриманий результат в вихідний потік
cout << max_c << endl;
return 0;
}
Задача 2. "Центральна точка"
#include <iostream>
using namespace std;
// структрура, що являє собою точку з координатами (x,y)
struct Point { int x, y; };
int main()
{
// прочитаємо з вхідного потоку значення кількості точок
int n;
cin >> n;
// створимо масив точок відповідного розміру
Point* P = new Point[n];
// прочитаємо з вхідного потоку координати точок
// та розмістимо їх у масиві
for(int i = 0; i < n; i++)
cin >> P[i].x >> P[i].y;
// видалимо з масива точки, координати яких співпадають
// таким чином, щоб залишалася лише одна точка з кожної групи точкок,
// координати яких співпадають
int new_n = 1;
for(int i = 1; i < n; i++)
{
int j;
for(j = 0; j < i; j++)
if(P[j].x == P[i].x && P[j].y == P[i].y)
break;
if (j == i)
P[new_n++] = P[i];
}
n = new_n;
// обчислимо координати точки, у якої координата x є середньоарифметичним
// координат усіх даних точок по х
// для y відповідно те ж саме
// після вилучення точок, що співпадають, центральна точка може
// знаходитися лише в цих координатах
Point aveP;
aveP.x = 0;
aveP.y = 0;
for(int i = 0; i < n; i++)
{
aveP.x += P[i].x;
aveP.y += P[i].y;
}
// якщо сума відповідних координат точок не ділиться на n,
// то центральна точка повинна знаходитися в дробових координатах
// таких точок у нас немає, виводимо '-'
if (aveP.x % n != 0 || aveP.y % n != 0)
{
cout << '-' << endl;
return 0;
}
// обчислимо середньоарифметичне значення
aveP.x /= n;
aveP.y /= n;
// перевіримо, чи існує серед заданих точка з такими координатами
for(int i = 0; i < n; i++)
if(P[i].x == aveP.x && P[i].y == aveP.y)
{
// якщо така точка існує, то визначимо, чи вона дійсно є центральною
// для цього перевіримо, чи для кожної даної точки існує симетрична їй
// точка відносно знайденої
for(int i = 0; i < n; i++)
{
Point s;
s.x = 2 * aveP.x - P[i].x;
s.y = 2 * aveP.y - P[i].y;
int j;
for(j = 0; j < n; j++)
if(P[j].x == s.x && P[j].y == s.y)
break;
// якщо для будь-якої точки не існує симетричної їй точки
// то відповідно знайдена точка не є центральною
// а отже, центральної точки не існує
if(j == n)
{
cout << '-' << endl;
return 0;
}
}
// якщо у кожної точки існує симетрична їй точка,
// то знайдена точка є центральною
cout << aveP.x << ' ' << aveP.y << endl;
return 0;
}
// якщо ж не існує, то дані точки не містять центральної точки
// виведемо у вихідний потік '-'
cout << '-' << endl;
return 0;
}
Задача 3. "Послідовність 01"
#include <iostream>
using namespace std;
// послідовність довжини n може бути утворена:
// 1) записом 0 та будь-якої послідовності довжини n-1
// 2) записом 10 та будь-якої послідовності довжини n-2
// якщо позначити кількість послідовностей довжини n через F(n),
// то F(n) = F(n-1) + F(n-2)
// розв'язок задачі фактично зводиться до обчислення відповідного
// числа Фібоначі
int main()
{
int n;
cin >> n;
int a = 1, b = 1;
for(int i = 0; i < n; i++)
{
int t = b;
b = a + b;
a = t;
}
cout << b << endl;
return 0;
}