Разбор лицейской олимпиады 2017

ДЕТАЛИ
[+/-]

Виджеты

Виджеты<bs-widget-edit>

Требуемые страницы
Кто в сети?
Материал из Wiki Лицея
Перейти к: навигация, поиск

Задача А. Выборы жрецов. 50 баллов

Имя входного файла: input.txt

Имя выходного файла: output.txt

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

Используемый объем памяти: 64 Мб

В стране Олимпиадии снова выборы.

Страна состоит из маленьких графств. Графства объединяются в кон¬федерации. Каждая конфедерация раз в год выбирает себе покровителя — одного из 200 жрецов. Этот ритуал называется Великими Перевыборами Жрецов и выглядит так: конфедерации одновременно подают заявления (одно от конфедерации) в Совет Жрецов о том, кого они хотели бы видеть своим покровителем (если заявление не подано, то считают, что конфеде¬рация хочет оставить себе того же покровителя). После этого все заявки удовлетворяются. Если несколько конфедераций выбирают одного и того же Жреца, то они навсегда объединяются в одну. Таким образом, каждый Жрец всегда является покровителем не более чем одной конфедерации. Требуется написать программу, позволяющую Совету Жрецов выяснить номер Жреца-покровителя каждого графства после Великих Перевыбо¬ров. В Совете все графства занумерованы (начиная с 1). Все Жрецы за¬нумерованы числами от 1 до 200 (некоторые из них сейчас могут не быть ни чьими покровителями).

Формат входных данных.

Во входном файле записано число N — количество графств в стране (1 <= N <= 5000), и далее для каждого графства записан номер Жреца- покровителя конфедерации, в которую оно входит (графства считаются по порядку их номеров). Затем указаны заявления от конфедераций. Сначала записано число М — количество поданных заявлений, а затем М пар чисел: первое число — номер текущего Жреца-покровителя, второе — номер желаемого Жреца-покровителя.

Все числа во входном файле разделяются пробелами и (или) символами перевода строки.

Формат выходных данных.

В выходной файл вывести для каждого графства одно число — номер его Жреца-покровителя после Великих Перевыборов. Сначала —для первого графства, затем — для второго и т.д.

Пример

входные данные выходные данные
7

1 1 5 3 1 5 1
2
5 1
1 3

3 3 1 3 3 1 3

Разбор задачи

Задача для начинающих

После внимательного чтения условия задачи становится понятно, что нужно считывать из входного файла (с консоли) номера жрецов-покровителей и затем заменить некоторые из них на новые.

Создаем два одинаковых массива, равных заданному числовому ряду:

1 1 5 3 1 5 1

1 1 5 3 1 5 1

Пробегаем по элементам исходного массива (первого) и при нахождении первого элемента первой пары, меняем найденный элемент на второй, но только во втором массиве. После первой замены массивы будут выглядеть так:

1 1 5 3 1 5 1

1 1 1 3 1 1 1

Аналогично, после второй замены массивы будут выглядеть так:

1 1 5 3 1 5 1

3 3 1 3 3 1 3

И выводим измененный второй массив! Вот как это можно было реализовать.

#include <iostream>
using namespace std;
int main()
{
 int n, m, a, b;
 cin >> n;
 int ms1[n], ms2[n];
 for(int i=0;i<n;i++){
   cin >>ms1[i];
   ms2[i] = ms1[i];
 }
 cin >>m;
  for(int j=0; j<m;j++){
   cin >> a >> b;
    for(int i=0;i<n;i++){
       if (ms1[i]==a) ms2[i] = b;
    }
  }
  for(int i=0;i<n;i++){
   cout << ms2[i]<< " ";
  }
   return 0;
}

Задача B. Призы. 100 баллов

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 1 секунда

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

Алиса и Боб стали победителями телевикторины, и теперь им предстоит выбрать себе призы. На выбор предлагается n призов, пронумерованных от 1 до n.

Распределение призов происходит следующим образом. Организаторы телевикторины сообщают победителям целое положительное число k (1 ≤ k ≤ n / 3). Сначала Алиса выбирает себе любые k подряд идущих номеров призов. Потом Боб выбирает себе k подряд идущих номеров призов, при этом он не может выбирать номера, которые уже выбрала Алиса. После этого победители забирают выбранные ими призы.

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

Требуется написать программу, которая по информации о ценности призов и значению k определит, для какого минимального значения x Алиса сможет добиться того, чтобы Боб не смог выбрать призы с суммарной ценностью больше x.

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

Первая строка входного файла содержит два целых числа: n — общее количество призов и k — количество подряд идущих номеров призов, которое должен выбрать каждый из победителей (3 ≤ n ≤ 100 000, 1 ≤ k ≤ n / 3).

Вторая строка содержит n целых положительных чисел: a1, a2, …, an. Для каждого приза указана его ценность для Боба (1 ≤ ai ≤ 109).

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

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

Пример

входные данные выходные данные
10 2

1 2 4 5 2 4 2 2 1 6

7

Пояснение к примеру

В приведенном примере Алиса может, например, выбрать 4-й и 5-й призы. После этого для Боба оптимально выбрать 9-й и 10-й призы с суммарной ценностью 7.

Решение

Еще один пример:

входные данные выходные данные
10 3

8 9 10 7 6 5 4 3 2 1

12

Решение задачи сводится к исключению k призов и поиску наибольшей оставшейся суммы. И из всех наибольших сумм нужно найти наименьшую. Пример решения перебором (31 тест из 48 или 65 баллов из 100):

 #include <iostream>
 using namespace std;
 long long a[100001],mx,mn;
 int n,m,k,i,j;
 int main(){
 cin>>n>>k;
 a[0]=0;
  for(i=1;i<=n;i++) {
 cin>>m;
 a[i]=a[i-1]+m;
   }
  mn=0;
   for(j=1;j<=n-k+1;j++){
     mx=0;
      for(i=j+k;i<=n-k+1;i++)
         if(mx<a[i+k-1]-a[i-1])mx=a[i+k-1]-a[i-1];
      for(i=1;i<=j-k;i++)
            if(mx<a[i+k-1]-a[i-1])mx=a[i+k-1]-a[i-1];
       if(mn==0||mn>mx)mn=mx;
   }
   cout<<mn;
   return 0;
  }
  

Для решения этой подзадачи воспользуемся префиксными суммами и префиксными максимумами.

Сначала научимся за O(1) находить сумму значений ценности для любого отрезка номеров. Для этого вычислим значения

s[i] = a1 + a2 + … + ai

для всех i от 0 до n. Это можно сделать одним линейным проходом.

Теперь сумма значений ai на отрезке от L[eft] до R[ight] вычисляется как s[R] – s[L – 1].

Второй шаг решения: пусть Алиса выбрала отрезок номеров от A до A + k – 1. Теперь Боб может выбрать отрезок длины k с началом от 1 до A – k или с началом от A + k до n – k + 1. Для всех i от 1 до n вычислим следующую величину

pref[i] = max(s[k] – s[0], s[k+1] – s[1], …, s[i] – s[i – k])

и величину

suff[i] = max(s[i + k – 1] – s[i – 1], s[i + k] – s[i], …, s[n] – s[n – k])

Обе этих величины также можно вычислить одним линейным проходом.

Теперь для решения задачи достаточно перебрать ход Алисы, если Алиса выбрала отрезок призов от A до A + k – 1, то максимальное значение, которое может достаться Бобу это

max(pref[A – 1], suff[A + k])

Среди этих значений надо выбрать минимум.

Приведем код решения на С++

cin>>n>>k;
s[0]=0;
 for (int i = 1; i <= n; i++) { 
     cin>>a[i]; 
     s[i] = s[i - 1] + a[i]; 
  } 
 for (int i = k; i <= n; i++) { 
     pref[i] = max(pref[i - 1], s[i] - s[i - k]); 
  } 
suff[n-k+1]=s[n]-s[n-k];
 for (int i = n - k + 1; i >= 1; i--) { 
     suff[i] = max(suff[i + 1], s[i + k - 1] - s[i - 1]); 
  } 
long long best = 2e18; 
 for (int i = 1; i <= n - k + 1; i++) { 
     best = min(best, max(pref[i - 1], suff[i + k])); 
  } 
cout<<best;

Задача С. Робот К-79. 50 баллов

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 3 секунды

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

Петя написал программу движения робота К-79. Программа состоит из следующих команд:

  • S - сделать шаг вперед
  • L - повернуться на 90o влево
  • R - повернуться на 90o вправо

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

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

Во входном файле записана одна строка из заглавных латинских букв S, L, R, описывающая программу для робота. Общее число команд в программе не превышает 200, при этом команд S - не более 50.

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

В выходной файл выведите, сколько шагов будет сделано (то есть выполнено команд S) прежде, чем робот впервые окажется в том месте, через которое он уже проходил. Если такого не произойдет, выведите в выходной файл число -1.

Примеры

входные данные выходные данные
SSLSLSLSSRSRS 5
LSSSS -1

Решение

Представим себе, что робот ходит по большой шахматной доске, каждым ходом перемещаясь на одну клетку влево, вправо, вперед или назад. Мы будем хранить в двумерном массиве путь робота и после каждого очередного хода проверять, не попал ли робот в клетку, в которой он уже был раньше. Чтобы отслеживать передвижения робота, нам нужно в каждый момент времени знать, в какую сторону он смотрит. Обозначим направления цифрами: 0 — направо, 1 — вперед, 2 — налево, 3 — назад. Тогда, если мы храним в переменной dir текущее направление движения, то поворот налево будет соответствовать прибавлению к dir единицы по модулю 4:

dir:= (dir + 1) % 4 {0->1, 1->2, 2->3, 3->0}

Поворот направо, аналогично, будет соответствовать вычитанию единицы по модулю 4 (или прибавление 3).

Заведем два массива:

int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};

Их смысл в следующем: если dir — текущее направление движения робота, то за один ход его координата х изменяется на dx[dir], а коор­дината у на dy [dir].

После этого несложно написать требуемую программу. Будем считать, что мы прочитали последовательность ходов робота в строковую переменную S.

Решение на я.п. Pascal

i:= 1; {номер анализируемого символа} 
step:= 0; {количество сделанных ходов S}
flag := false; {возвратились ли на пройденную ранее клетку}
х:= 0; {текущее	}
у:= 0; {положение робота}
was[0][0] := true; {робот начинает движение в клетке (0,0)} 
repeat 
   case s [i] of
      ’L’: dir:= (dir + 1) mod 4;
      ’R’: dir:= (dir + 3) mod 4;
      ’S’: 
      begin
         inc(step); 
         x:= x + dx;
         у:= у + dy;
         if was[x][y] then flag:= true else was[x][y]:= true;
      end;  end;
      inc(i);
   until (i>length(s)) OR flag; 
 if flag then write(step) else write(-l);

Решение на я.п. С/С++

#include <iostream> 
using namespace std;
char s[201];
int a[101][101]={0};
int n=0,m,k,i=0,j,x=50,y=50,c=0;
int main(){
 cin.getline(s,201);
 a[x][y]=1;
  while(s[i]!='\n'){
    if(s[i]=='L')n=(n+1)%4;
    if(s[i]=='R')n=(n+3)%4;
    if(s[i]=='S'){
      c++;
       if(n==0) x++;
       if(n==1) y++;
       if(n==2) x--;
       if(n==3) y--;
       if(a[x][y]) {
         cout<<c; 
         return 0;
  }
     a[x][y]=1;
   }
      i++;
  }
 cout<<"-1";
 return 0;
 }

Задача D. Реклама. 100 баллов

Имя входного файла: input.txt

Имя выходного файла: output.txt

Ограничение по времени: 5 секунд

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

В супермаркете решили время от времени транслировать рекламу новых товаров. Для того, чтобы составить оптимальное расписание трансляции рекламы, руководство супермаркета провело следующее исследование: в течение дня для каждого покупателя, посетившего супермаркет, было зафиксировано время, когда он пришел в супермаркет, и когда он из него ушел.

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

Напишите программу, которая составит такое расписание трансляции рекламных роликов. Рекламные объявления можно начинать транслировать только в целые моменты времени. Считается, что каждое рекламное объявление заканчивается до наступления следующего целого момента времени. Если рекламное объявление транслируется в тот момент времени, когда покупатель входит в супермаркет или уходит из него, покупатель это объявление услышать успевает.

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

Во входном файле записано сначала число N — количество покупателей, посетивших супермаркет за день(1≤N≤3000). Затем идет N пар натуральных чисел Ai, Bi, задающих соответственно время прихода и время ухода покупателей из супермаркета (0<Ai<Bi<106).

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

В выходной файл выведите сначала количество рекламных объявлений, которое будет протранслировано за день. Затем выведите в возрастающем порядке моменты времени, в которые нужно транслировать рекламные объявления.

Если решений несколько, выведите любое из них.

Пример

входные данные выходные данные
5

1 10
10 12
1 10
1 10
23 24

5

5 10 12 23 24

Решение

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

Пример из условия в такой интерпретации будет выглядеть следующим образом:

реклама-1.png

Отсортируем все отрезки по возрастанию правых границ, а при их равенствепо убыванию левых.

Ограничение на количество отрезков (N≤3000) позволяет применить не только быструю сортировку, но и алгоритм сортировки с квадратичной временной сложностью, например метод «пузырька».

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

Рассмотрим следующий пример. Пусть дано четыре отсортированных отрезка: [1,6], [3,7], [12,14], [14,16].

реклама-2.png

В самом первом отрезке [1,6] должны содержаться две точки. Их необходимо поставить как можно правее, то есть в точках с целочисленными координатами 5 и 6. Почему? Поскольку это отрезок с наименьшей правой границей, то раньше него другие отрезки не могли закончиться. Но могли начаться другие отрезки! А чем правее мы располагаем точки, тем больше шанс, что они одновременно попадут и в другие отрезки – что нам выгодно. Еще раз обратим внимание на факт, что не существует более выгодной расстановки точек, чем данная: поскольку никакой другой отрезок раньше наших точек не заканчивается, то мы не упускаем ни одну потенциальную возможность улучшить расстановку точек.

реклама-3.png

В нашем примере расставленные две точки сразу попали и в отрезок [3,7]. А вот если бы мы поставили точки, например, в координатах 1 и 2, то такая расстановка была бы неэффективной – мы покрыли бы ей только один отрезок, а не два.

Назовем точку 6 последней расставленной точкой, а точку 5предпоследней. Переходим к следующему отрезку [3,7] – но внутри него уже стоят две точки, поскольку левая граница отрезка меньше, чем предпоследняя расставленная точка. Следующий отрезок – [12, 14]. В нем не стоит еще ни одной точки, так как левая граница отрезка больше последней расставленной точки. Из аналогичных соображений ставим в нем две точки как можно правее.

реклама-4.jpg

Последний отрезок – [14, 16]. В нем уже содержится одна из поставленных точек, так как последняя расставленная точка равна левой границе отрезка. Ставим еще одну точку в правую границу отрезка – координата равна 16. При этом предыдущей точкой станет точка 14.

реклама-5.jpg

Легко видеть, что такой алгоритм расстановки точек всегда дает оптимальный результат.

Итак, для каждого отрезка мы смотрим, нужно ли поставить в нем одну или две точки и если да, то ставим их как можно правее.

Если Вы уже поняли алгоритм решения, то для закрепления понимания разберите еще два теста:

Тест 1:
10
88 99
188 190
190 199
162 165
1 52
76 89
99 130
135 153
52 76
165 188

И второй тест:

10
1 900000
3 30000
7 20000
6 25000
4 27000
10 10000
100 5000
1000 3000
1500 2500
2000 2004

Сравните ответы:

Тест 1: 13 точек

Тест 2: 2 точки

Если алгоритм понятен, то предлагаю самостоятельно составить программу!