разбор 13.09.2018


Чтобы посмотреть этот PDF файл с форматированием и разметкой, скачайте его и откройте на своем компьютере.
A. Театральная площадь

Театральная площадь в столице Берляндии представляет собой
прямоугольник

n
 × 
m

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

a
 × 
a
.

Како
е наименьшее количество плит понадобится для замощения площади? Разрешено
покрыть плитами большую поверхность, чем театральная площадь, но она должна быть
покрыта обязательно. Гранитные плиты нельзя ломать или дробить, а разрешено
использовать только целик
ом. Границы плит должны быть параллельны границам площади.

Входные данные

В первой строке записано три целых натуральных числа

n
, 
m

и

a

(
1 ≤ 
n
, 
m
, 
a
 ≤ 10
9
).

Выходные данные

Выведите искомое количество плит.

Примеры

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

6 6 4

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

4


Р
ешение


Координаты разделяются, и ответ равен произведению количества плиток, необходимых
для закрытия по вертикали, на количество плиток, необходимых по горизонтали.

т
.
е
. answer = ceil (m/a) * ceil (n/a)

где ceil
-

наименьшее целое, большее или равное арг
ументу. В целых числах обычно
ceil(a/b) заменяется на ((a+b
-
1)/b)
--

внешние скобки нужны для задания порядка
операций.


long

long

n, m, a;

cin
��

n
��

m
��

a;

cout


((n + a
-

1) / a)*((m + a
-

1) / a);






B. Дело о нулях и единицах

Андроид Андреид


известный на всю галактику детектив. В свободное от работы время он
размышляет о строках из нулей и единиц.

Как
-
то раз ему в голову пришла строка длины

n
, состоящая из нулей и единиц. Рассмотрим
следующую операцию


мы выбираем любые две

соседние

позиции в

строке, и если в одной
из них ноль, а в другой


единица, то разрешается удалить обе эти цифры, в результате чего
строка строка становится длины

n

-
 2
.

Андреид задумался


какой минимальной длины строка может остаться, если примененить
описанную операции
некоторое (возможно, нулевое) количество раз?

Входные данные

В первой строке входных данных задано целое число

n

(
1 ≤ 
n
 ≤ 2·10
5
)


длина строки,
которая пришла в голову Андреиду.

Во второй строке записана строка длины

n
, состоящая из нулей и единиц.

Выходн
ые данные

Выведите единственное целое число


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

Примеры

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

Скопировать

4

1100

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

0

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

5

01010

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

1

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

8

11101111

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

6

Примечание

В первом тесте из условия строка может меняться следующим
образом:

.

Во втором тесте из условия строка может меняться следующим
образом:

.

В третьем тесте из условия строка может меняться сл
едующим
образом:

.



Решение


Если в последовательности остались хотя бы одни единица и ноль, тогда существует
подстрока
01

или
10
, которую можно удалить. При этом порядок удаления не важен: в
любом случае мы сделаем
min
(#
единиц
, #
нулей
)

операций, так как

за раз удаляется один
ноль и одна единица. Поэтому ответ:
#
единиц
 + #
нулей

-
 2
min
(#
единиц
, #
нулей
) = |#
единиц

-
 #
нулей
|
.

Время:
O
(
n
)
.


#include

iostream&#x-6i6;&#xo-6s;t-6;&#xr6e-;j-6;&#xm600;

#include

string&#x-6s6;&#xt-6r;i-6;&#xn6g-;怀


using

namespace

std;


int

main(
void
) {


int

n, c;


string

s;



cin
��

n
��

s;


in
t

o, z;


o = z = 0;


for

(
int

i = 0; in; i++) {



if

(s
[
i
]

==
'1'
) o++;



else

z++;


}



cout


n
-

2 * min(o, z)


endl;



return

0;

}







C. Арбуз

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

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

Входные данные

В первой и единственной строке входных данных записано целое число
w

(
1 ≤ 
w
 ≤ 100
)


вес
купленного ребятами арбуз
а.

Выходные данные

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

в противном случае.

Примеры

Входные данные

8

Выходные данные

YES

Примечание

Например, ребята могут поделить арбуз на две ч
асти размерами 2 и 6 килограммов соответственно
(другой вариант


две части 4 и 4 килограмма).


Решение


Чтобы арбуз мог быть разделен на две четные части, данное нам число
w

должно быть
представимо в виде 2
m

+ 2
k

(две четные части).

Таким образом
w

= 2(
m
+
k
), где
m
,
k


1
, то есть

(
w

4

и
w

-

четно)
-

необходимое и достаточное условие разделения арбуза



#include

bits/stdc++.h&#x-6b6;&#xi-6t;s-6;&#x/6s-;t-6;൬-;+6+;&#x-6.6;&#xh-60;


using

namespace

std;


int

main() {


int

n; cin �� n;



if

(n & 1 || n 4) {



cout
"NO"
;


}


else

{



cout
"YES"
;


}


ret
urn

0;

}




D. Равенство

Вам дана строка

s
s

длины

n
n
, которая содержит только первые

k
k

букв латинского алфавита.
Все буквы в строке

s
s

заглавные.

Строка называется

подпоследовательностью

строки

s
s
, если она получается удалением
из

s
s

нескольких символов б
ез изменения порядка остальных символов. Например, ©
ADE
ª и
©
BD
ª являются подпоследовательностями ©
ABCDE
ª, а ©DEAª



нет.

Подпоследовательность

s
s

называется

хорошей
, если каждая из первых

k
k

букв алфавита
встречается одинаковое число раз.

Найдите длину сам
ой длинной хорошей подпоследовательности

s
s
.

Входные данные

Первая строка входных данных содержит целые числа

n
n

(
1≤
n
≤10
5
1≤n≤105
)
и

k
k

(
1≤
k
≤26
1≤k≤26
).

Вторая строка входных данных содержит строку

s
s

длины

n
n
. Строка

s
s

содержит только
заглавные латинские б
уквы от '
A
' до

k
k
-
й буквы латинского алфавита.

Выходные данные

Выведите одно целое число



длину самой длинной хорошей подпоследовательности
строки

s
s
.

Примеры

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

9 3

ACAABCCAB

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

6

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

9 4

ABCABCABC

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

0

Пр
имечание

В первом примере, подпоследовательность ©
ACBCAB
ª (©
AC
AA
BC
C
AB
ª) является одной из
подпоследовательностей содержащей одинаковое число '
A
', '
B
' и '
C
'. Подпоследовательность
©
CAB
ª тоже содержит одинаковое число этих букв, но не является максимальной п
о длине.

Во втором примере, ни одна из подпоследовательность не может содержать '
D
', а значит
ответ равен

0
0
.










Решение



First we need to find the frequencies of the first
k

alphabets in the string. Let the minimum
frequency among these frequencies

be
m
. Then we cannot select
m+1

characters of one kind,
and we can definitely select
m

characters of each kind, hence the answer is given by
min
(frequency of first
k

characters) *
k

Overall Complexity:
O(n)


#include

bits/stdc++.h&#x-6b6;&#xi-6t;s-6;&#x/6s-;t-6;൬-;+6+;&#x-6.6;&#xh-60;

using

namespace

std;


#define

IOS

ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define

endl

"
\
n"


int

n, k;

string s;

int

f[26];


int32_t main()

{


IOS
;


cin �� n �� k �� s;


for

(
auto

&it : s)



f[it
-

'A'
]++;


int

ans = f[0];


for

(
int

i = 0; ik; i++)



ans = min(ans, f
[i]);


ans *= k;


cout ans;


return

0;

}





























E. Азартные игры

У каждого из игроков A и B есть по списку, по

n
n

целых чисел в каждом. Они оба хотят
максимизировать разность между своими очками и очками соперника.

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

В случае если в списке есть несколько од
инаковых элементов, только один из них будет
задействован в какой
-
то операции. Например, если список состоит из
элементов

{1,2,2,3}
{1,2,2,3}

и вы решили выбрать

2
2

для следующего хода, только один
экземпляр

2
2
будет удалён (и добавлен к очкам, если это треб
уется).

Игру начинает игрок А и игра заканчивается когда оба списка становятся пустыми. Найдите
разницу между очками A и B, если оба игрока играют оптимально.

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

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

Входные данные

В

первой строке входного файла записано целое число

n
n

(
1≤
n
≤100000
1≤n≤100000
)



размер списков.

Вторая строка содержит

n
n

целых чисел

a
i
ai

(
1≤
a
i
≤10
6
1≤ai≤106
), описывающих список
игрока A, который ходит первым.

Вторая строка содержит

n
n

целых чисел

b
i
bi

(
1≤
b
i
≤10
6
1≤bi≤106
), описывающих список
игрока B.

Выходные данные

Найдите разницу между очками A и B (
A

B
A−B
), если оба игрока играют оптимально.

Примеры

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

Скопировать

2

1 4

5 1

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

Скопировать

0

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

Скопировать

3

100 100 100

100 100 100

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

0

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

2

2 1

5 6

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

Скопировать

-
3

Примечание

В первом примере, игра может выглядеть так:



A удаляет

5
5

из списка B.



B удаляет

4
4

из списка A.



A прибавляет к своим очкам

1
1
, и удаляет ее из списка.



B приба
вляет к своим очкам

1
1
, и удаляет ее из списка..

Таким образом, очки A равны

1
1
, очки B равны

1
1

и разница

0
0
.

Есть также другие варианты оптимальной игры, например:



A удаляет

5
5

из списка B.



B удаляет

4
4

из списка A.



A удаляет

1
1

из списка B.



B удаляет

1
1

из списка A.

Разница между очками также

0
0
.

Во втором примере, вне зависимости от ходов, в итоге каждый участник добавит к своим
очкам одинаковое количество чисел, а значит очки у обоих игроков будут одинаковыми,
поэтому разница

0
0
.




Решение


This probl
em was greedy.

First, it is obvious that both the players will try to either take their own maximum value or
remove the opponent's maximum value. Hence, the arrays should be sorted and two pointers
should be maintained to keep track of how many elements fr
om each array have been
counted/removed already.

In every move, if the person has a choice to either take his own value
A

or remove his opponent's value
B
, then he will make the choice dependent on the values of
A

and
B

. In fact, it turns out that it is o
ptimal just to select the choice with a greater number (in case of
tie any will do).

How to prove it? One can show by induction that it does the same as the dynamic programming
of size
n
2

. However, there is a more nice way.

Let's say that initially each p
layer gets
0.5

of all numbers in his list. This way when you choose a number from your own list you add the
rest
0.5

of it to the score. And when you remove the number from opponent's list you remove
the
0.5

of it from your opponent's score. Clearly, all m
oves become symmetrical to both players now! So
each player can make a decision just based on which of the moves is greater.

If
A�B

, then he will take his number. If
AB
, he will discard the opponent's number
B
. If
A=B

, he can make either of the above m
oves, it will not make a difference.

Complexity:
O(nlogn)


#include

bits/stdc++.h&#x-6b6;&#xi-6t;s-6;&#x/6s-;t-6;൬-;+6+;&#x-6.6;&#xh-60;

using

namespace

std;


#define

IOS

ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

#define

endl

"
\
n"

#define

int

long

long


const

int

N = 1e5 + 5;


int

n;

int

a[N], b[N];


int32_t main()

{


IOS
;


cin �� n;


for

(
int

i = 1; i = n; i++)



cin �� a[i];


for

(
int

i = 1; i = n; i++)



cin �� b[i];


sort(a + 1, a + n + 1);


sort(b + 1, b + n + 1);


reverse(a + 1, a + n + 1);


reverse(b + 1, b + n + 1);


int

i = 1, j = 1, player

= 0, moves = 0, asum = 0, bsum = 0;


while

(moves2 * n)


{



moves++;



if

(!player)



{




if

(a[i] �= b[j])




{





asum += a[i];





i++;




}




else





j++;



}



else



{




if

(b[j] �= a[i])




{





bsum += b[j];





j++;




}




else





i++;



}



player ^= 1;


}


cout asum
-

bsum;


return

0;

}












































F. Биты

Рудольф отправляется в замок. Перед тем, как попасть туда, сотрудники службы
безопасности задали ему вопрос:

Задано два числа

a
a

и

b
b

в двоичной сис
теме счисления, их длина равна

n
n
. Сколько есть
различных способов поменять местами два бита в числе

a
a

(только в

a
a
, не в

b
b
) так, чтобы
побитовое ИЛИ чисел изменилось? Другими словами, пусть

c
c

равно побитовому
ИЛИ

a
a

и

b
b
, тогда вам нужно найти количест
во способов поменять местами два бита
в

a
a

так, чтобы побитовое ИЛИ не было равно

c
c
.

Обратите внимание, что числа могут содержать ведущие нули, так что длина каждого числа
равна

n
n
.

Побитовое ИЛИ



это бинарная опера
ция. Результат



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

01010
2
010102

ИЛИ

10011
2
100112

=

11011
2
110112
.

К вашему удивлению, вы не Руд
ольф, и вам не нужно помогать ему



Вы



сотрудник
службы безопасности! Пожалуйста, найдите количество способов поменять местами два бита
в

a
a

так, чтобы побитовое ИЛИ изменилось.

Входные данные

Первая строка содержит одно целое число

n
n

(
2≤
n
≤10
5
2≤n≤105
)



количество битов в
каждом числе.

Вторая строка содержит число

a
a

длиной

n
n

в двоичной системе счисления.

Третья строка содержит число

b
b

длиной

n
n

в двоичной системе счисления.

Выходные данные

Выведите количество возможных способов поменять местами два би
та в

a
a

так, чтобы
побитовое ИЛИ изменилось.

Примеры

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

Скопировать

5

01011

11001

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

4

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

6

011000

010011

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

Скопировать

6

Примечание

В первом примере вы можете поменять местами биты с такими
индексами:

(1,
4)
(1,4)
,

(2,3)
(2,3)
,

(3,4)
(3,4)

и

(3,5)
(3,5)
.

Во втором примере вы можете поменять местами биты с такими
индексами:

(1,2)
(1,2)
,

(1,3)
(1,3)
,

(2,4)
(2,4)
,

(3,4)
(3,4)
,

(3,5)
(3,5)

и

(3,6)
(3,6)
.




Решение



Let
t
xy

be the number of indexes
i

such that
a
i
=x

and
b
i
=y
.

The answer is
t
00

t
10
+t
00

t
11
+t
01

t
10

.

#include

bits/stdc++.h&#x-6b6;&#xi-6t;s-6;&#x/6s-;t-6;൬-;+6+;&#x-6.6;&#xh-60;

using

namespace

std;


long

long

ar[4];

char

c1[4] = {
'0'
,
'0'
,
'1'
,
'1'

};

char

c2[4] = {
'0'
,
'1'
,
'0'
,
'1'

};


int

main() {


int

n;


cin �� n;


string a, b;


cin �� a �� b;


for

(
in
t

i = 0; i n; i++) {



for

(
int

j = 0; j 4; j++) {




if

(c1[j] == a[i] && c2[j] == b[i]) {





ar[j]++;




}



}


}


cout ar[0] * ar[2] + ar[0] * ar[3] + ar[1] * ar[2] endl;


return

0;

}


























G. Между домами

В ряд расположено

n
n

домов. Они пронумерованы от

1
1

до

n
n

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

1
1
.

Вы хотите совершить

k
k

переходов между домами. Переходом является ходьба от текущего
дома к другому дому. Вы не можете стоять на месте (то есть во время к
аждого перехода
другой дом должен отличаться от текущего). Если вы идете от дома

x
x

до дома

y
y
,
дистанция, которую вы прошли, увеличивается на

|
x

y
|
|x−y|

единиц, где

|
a
|
|a|



абсолютная
величина (модуль числа)

a
a
. Разрешается посещать один и тот же дом нес
колько раз (но
нельзя посещать один и тот же дом два раза подряд).

Ваша задача


пройти суммарно ровно

s
s

единиц дистанции.

Если это невозможно, выведите ©
NO
ª. Иначе выведите ©
YES
ª и один из возможных способов
сделать это. Помните, что вы должны совершить
ровно

k
k

переходов.

Входные данные

Первая строка входных данных содержит три целых
числа

n
n
,

k
k
,

s
s

(
2≤
n
≤10
9
2≤n≤109
,

1≤
k
≤2

10
5
1≤k≤2

105
,

1≤
s
≤10
18
1≤s≤1018
)


количество домов, количество переходов и суммарная дистанция, которую вы должны пройти.

Выходные да
нные

Если невозможно совершить ровно

k
k

переходов с суммарной пройденной дистанцией,
равной

s
s
, выведите ©
NO
ª.

Иначе выведите ©
YES
ª в первой строке и затем выведите ровно

k
k

целых
чисел

h
i
hi

(
1≤
h
i

n
1≤hi≤n
) во второй строке, где

h
i
hi



дом, к которому вы пе
реходите на

i
i
-
м
шаге.

Для каждого

j
j

от

1
1

до

k
−1
k−1

должно выполняться следующее условие:

h
j

h
j
+1
hj≠hj+1
.
Также должно выполняться

h
1
≠1
h1≠1
.

Примеры

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

Скопировать

10 2 15

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

Скопировать

YES

10 4

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

Скопировать

10 9
45

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

Скопировать

YES

10 1 10 1 2 1 2 1 6

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

10 9 81

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

YES

10 1 10 1 10 1 10 1 10

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

10 9 82

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

NO




Решение


Решение этой задачи очень простое: если
k�s

или
k

(n−1), ответ ©NOª. Иначе да
вайте
k

раз повторим следующую операцию: пусть
dist

равно
min(n−1,s−k+1)

(мы должны
жадно уменьшать оставшуюся дистанцию, но мы также должны помнить о количестве
переходов, которое нам необходимо совершить). Перейдем к любому возможному дому,
находящемуся
на дистанции
dist

от текущего дома (также надо не забывать вычитать
dist

из
s
).

Доказательство факта, что мы всегда можем пойти к дому на дистанции
dist

, очень простое: один из возможных ответов (который получается при помощи алгоритма,
описанного выше) б
удет выглядеть как какое
-
то количество переходов дистанции
n−1
,
(возможно) один переход случайной дистанции, меньшей
n−1
, и какое
-
то количество
переходов дистанции
1
. Первая часть ответа может быть получена, если мы стоим около
самого левого или самого пра
вого дома, вторая и третья части всегда могут быть
получены, потому что расстояния, которые мы будем проходить в каждом из таких ходов,
будут меньше
n−1

Асимптотика решения
O(k)

.


if

(s�(n
-

1)*k || sk) { cout
"NO"
;
return

0; }

cout
"YES"

endl;

while

(s
-

2 * (n
-

1) �= k
-

2 && k �= 2)

{


cout n
' '

1
' '
;


k
-
= 2;


s
-
= 2 * (n
-

1);

}

ll pos = 1;

if

(k)

{


ll dist = min(s
-

k + 1, n
-

1);


pos += dist;


s
-
= dist;


k
--
;


cout pos
' '
;

}

if

(k)

{


ll dist = min(s
-

k + 1, n
-

1
);


pos
-
= dist;


s
-
= dist;


k
--
;


cout pos
' '
;

}

while

(k)

{


if

(pos == 1)


{



ll dist = 1;



pos += dist;



s
-
= dist;



k
--
;



cout pos
' '
;


}


else


{



ll dist = 1;



pos
-
= dist;



s
-
= dist;



k
--
;



cout pos
' '
;


}

}







































H. Охота за мышью

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

80%
80%

абитуриентов


девушки, и
большинство из них планируют жить в общежитии в
ближайшие

4
4

(в лучшем случае) года.

Общежитие состоит из

n
n

комнат и единственной мыши! Девушки решили установить
ловушки для мышей в некоторых комнатах, чтобы избавиться от страшного монстра.
Установка ловушки в

i
i
-
й комнате стоит

c
i
ci

бурлей. Комнаты пр
онумерованы от

1
1

до

n
n
.

Мышь не сидит все время на месте, она постоянно бегает. Если она находилась в комнате

i
i

в
секунду

t
t
, то к секунде

t
+1
t+1

она перебежит в комнату

a
i
ai
, не посещая больше никаких
других комнат (
i
=
a
i
i=ai

значит, что мышь не покинет
комнату

i
i
). История начинается с
секунды

0
0
. Если мышь находится в комнате с ловушкой, то она оказывается поймана в эту
ловушку.

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

1
1

до

n
n

в секунду

0
0
.

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

Входные данные

В первой строке записано одно ц
елое число

n
n

(
1≤
n
≤2

10
5
1≤n≤2

105
)


количество комнат
в общежитии.

Во второй строке записаны

n
n

целых чисел

c
1
,
c
2
,…,
c
n
c1,c2,…,cn

(
1≤
c
i
≤10
4
1≤ci≤104
)


c
i
ci



стоимость установки ловушки в комнату

i
i
.

В третьей строке записаны

n
n

целых чисел

a
1
,
a
2
,…,
a
n
a1,a2
,…,an

(
1≤
a
i

n
1≤ai≤n
)


a
i
ai



комната, в которую перебежит мышь к следующей секунде, из комнаты

i
i
.

Выходные данные

Выведите единственное целое число


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

Примеры

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

5

1 2 3 2 10

1 3 4 3 3

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

Скопировать

3

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

4

1 10 2 10

2 4 2 2

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

Скопировать

10

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

Скопировать

7

1 1 1 1

1 1 1

2 2 2 3 6 7 6

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

Скопировать

2

Примечание

В первом примере достаточно установить ловушку в комнаты

1
1

и

4
4
. Если мышь начнет в
комнате

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

4
4

ран
о или поздно.

Во втором примере достаточно установить ловушку в комнату

2
2
. Если мышь начнет в
комнате

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

2
2

в секунду

1
1
.

Пути мыши, начиная с каждой комнаты, для
третьего примера:



1→2→2→…
1→2→2→…
;



2→2→…
2→2→…
;



3→2→2→…
3→2→2→…
;



4→3→2→2→…
4→3→2→2→…
;



5→6→7→6→…
5→6→7→6→…
;



6→7→6→…
6→7→6→…
;



7→6→7→…
7→6→7→…
;

Поэтому достаточно установить ловушки в комнатах

2
2

и

6
6
.





Решение

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

каждый цикл.
Осталось только лишь найти самую дешевую вершину каждого цикла. Это можно сделать
простым обходом в глубину.

Асимптотика

решения
:
O(n)

#include
bits/stdc++.hk-6;&#xi6t-;s6/;&#x-6s6;&#xt-6d;&#x-6c6;&#x+-6+;.-6;&#xh600;


using

namespace

std;


#define

fore
(i, l, r)
for
(
int

i =
int
(l); i
int
(r); i++)

#
define

forn
(i, n)
fore
(i, 0, n)


#define

mp

make_pair

#define

pb

push_back


#define

sz
(a)
int
((a).size())

#define

all
(a) (a).begin(), (a).end()

#define

sqr
(a) ((a) * (a))


#define

x

first

#define

y

second


typedef

long

long

li
;

typedef

long

double

ld
;

type
def

pair
li
,
li

pt
;


template

class

A
,
class

B
� ostream&
operator

(ostream& out,
const

pair
A
,
B
� &p) {


return

out
"("

p.
x


", "

p.
y


")"
;

}

template

class

A
� ostream&
operator

(ostream& out,
const

vector
A
� &v) {


out
"["
;


forn
(i,
s
z
(v)) {



if

(i) out
", "
;



out v[i];


}


return

out
"]"
;

}


const

int

INF =
int
(1e9);

const

li

INF64 =
li
(1e18);

const

ld

EPS = 1e
-
9;


int

n;

vector
int
� a, c;


inline

bool

read() {


if

(!(cin �� n))



return

false
;


c.assign(n, 0);


a.assign(n,

0);



forn
(i, n)



assert(scanf(
"%d"
, &c[i]) == 1);


forn
(i, n) {



assert(scanf(
"%d"
, &a[i]) == 1);



a[i]
--
;


}


return

true
;

}


vector vector
int
� � cycles;


vector
char
� used;

vector
int
� path;


void

dfs(
int

v
) {


path.push_back(
v
);


used[
v
] = 1;



i
nt

to = a[
v
];


if

(used[to] != 2) {



if

(used[to] == 1) {




cycles.emplace_back();





int

id =
sz
(path)
-

1;




while

(path[id] != to)





cycles.back().push_back(path[id
--
]);




cycles.back().push_back(to);



}



else




dfs(to);


}


path.pop_back();


used[
v
] = 2;

}


inline

void

solve() {


used.assign(n, 0);



forn
(i, n) {



if

(!used[i])




dfs(i);


}



li

ans = 0;


for

(
auto

&cur : cycles) {



int

mn = c[cur[0]];



for

(
int

v : cur)




mn = min(mn, c[v]);



ans += mn;


}


cout ans endl;

}


int

m
ain() {

#ifdef

_DEBUG


freopen(
"input.txt"
,
"r"
, stdin);


int

tt = clock();

#endif


cout fixed setprecision(15);



if

(read()) {



solve();


#ifdef

_DEBUG



cerr
"TIME = "

clock()
-

tt endl;



tt = clock();

#endif


}


return

0;

}















I. Сжатие песен

У Ивана на телефоне есть

n
n

песен. Размер

i
i
-
й песни

a
i
ai

байт. У Ивана также есть флеш
-
карта, которая может хранить не более

m
m
байт информации. Изначально его флеш
-
карта
пустая.

Иван хочет записать все

n
n

песен на свою флеш
-
карту. Он мо
жет сжимать некоторые из них.
Если он сжимает

i
i
-
ю песню, размер

i
i
-
й песни уменьшается с

a
i
ai

до

b
i
bi

байт (
b
i

a
i
biai
).

Иван может сжать любое подмножество песен (возможно, пустое) и записать все песни на
флеш
-
карту, если сумма их размеров не превышает

m
m
. Он может
сжимать

любое

подмножество песен (не обязательно подряд идущих).

Иван хочет найти минимальное количество песен, которое необходимо сжать, чтобы все
песни поместились на флеш
-
карте (то есть сумма их размеров была меньше либо
равна

m
m
).

Если нево
зможно записать все песни (даже если Иван сожмет все песни, которые у него
есть), выведите ©
-
1
ª. Иначе выведите минимальное количество песен, которое Ивану
необходимо сжать.

Входные данные

Первая строка входных данных содержит два целых
числа

n
n

и

m
m

(
1≤
n

10
5
,1≤
m
≤10
9
1≤n≤105,1≤m≤109
)


количество песен на телефоне
Ивана и вместительность флеш
-
карты Ивана.

Следующие

n
n

содержат по два целых числа каждая:

i
i
-
я строка содержит два целых
числа

a
i
ai

и

b
i
bi

(
1≤
a
i
,
b
i
≤10
9
1≤ai,bi≤109
,

a
i

b
i
�aibi
)


изначальный размер

i
i
-
й песни и
размер

i
i
-
й песни после сжатия.

Выходные данные

Если невозможно сжать подмножество песен таким образом, что все песни поместятся на
флеш
-
карту, выведите ©
-
1
ª. Иначе выведите минимальное количество песен, которое
необходимо сжать.

Примеры

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

4 21

10 8

7 4

3 1

5 4

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

2

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

4 16

10 8

7 4

3 1

5 4

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

-
1

Примечание

В первом тестовом примере Иван может сжать первую и третью песни, после этого сумма
размер
ов будет равна

8+7+1+5=21≤21
8+7+1+5=21≤21
. Также Иван может сжать первую и
вторую песни, тогда сумма размеров будет равна

8+4+3+5=20≤21
8+4+3+5=20≤21
.
Заметьте, что сжатия какой
-
либо одной песни недостаточно, чтобы записать все песни на
флеш
-
карту (например
, после сжатия второй песни сумма размеров будет
равна

10+4+3+5=22�21
10+4+3+5=2�221
).

Во втором тестовом примере даже если Иван сожмет все песни, сумма размеров будет
равна

8+4+1+4=�1716
8+4+1+4=17�16
.



Решение





#include

bits/stdc++.h&#x-6b6;&#xi-6t;s-6;&#x/6s-;t-6;൬-;+6+;&#x-6.6;&#xh-60;

using

namespace

std;

int

main() {


int

n, m;


cin �� n �� m;


vectorpair
int
,
int
�� a(n);


long

long

sum = 0;


for

(
int

i = 0; i
n; ++i) {



cin �� a[i].first �� a[i].second;



sum += a[i].first;


}


sort(a.begin(), a.end(), [&](pair
int
,
int

a
, pair
int
,
int

b
) {
return

a
.first
-

a
.second �
b
.first
-

b
.second; });



for

(
int

i = 0; i n; ++i) {



if

(sum = m) {




cout i endl;




return

0;



}



sum
-
= a[i].first
-

a[i].second;


}


if

(sum = m)



cout n endl;


else



cout
-
1 endl;



return

0;

}


J. Вася и матрица

Сегодня Вася сдает экзамен по математике. Чтобы получить хорошую оценку, Вася должен
угадать загаданную учителем матрицу!

Вася знает, что в матрице

n

строк и

m

столбцов. Для каждой строки ему известен xor
(поб
итовое исключающее или) всех элементов в этой строке.
Последовательность

a
1
, 
a
2
, ..., 
a
n

задает xor элементов строки под номером

1
,

2
, ...,

n
,
соответственно. Аналогично, для каждого столбца Вася знает xor всех элементов в столбце.
Последовательность

b
1
, 
b
2
, ..., 
b
m

обозначает xor элементов в столбцах под номерами

1
,

2
,
...,

m
, соответственно.

Помогите Васе! Найдите матрицу, которая соответствует этим ограничениям, или скажите, что
такой матрицы не существует.

Входные данные

Первая строка содержит два числа

n

и

m

(2 ≤ 
n
, 
m
 ≤ 100)



размеры матрицы.

Вторая строка содержит

n

чисел

a
1
, 
a
2
, ..., 
a
n

(0 ≤ 
a
i
 ≤ 10
9
)
, где

a
i



xor всех элементов в
строке

i
.

Третья строка содержит

m

чисел

b
1
, 
b
2
, ..., 
b
m

(0 ≤ 
b
i
 ≤ 10
9
)
, где

b
i



xor всех элементов в
столбце

i
.

Выходные данные

Если не существует матрицы, удовлетворяющей заданным ограничениям, в первой строке
выведите ©NOª.

Иначе в первой строке выведите ©YESª, а затем

n

строк по

m

чисел в каждой

c
i
1
, 
c
i
2
, ...
, 
c
im

(0 ≤ 
c
ij
 ≤ 2·10
9
)



описание матрицы.

Если сущес
твует несколько подходящих матриц


разрешено вывести любую из них.

Примеры

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

2 3

2 9

5 3 13

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

YES

3 4 5

6 7 8

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

3 3

1 7 6

2 15 12

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

NO



Решение




#include

bits/stdc++.h&#x-6b6;&#xi-6t;s-6;&#x/6s-;t-6;൬-;+6+;&#x-6.6;&#xh-60;


using

namespace

std;


const

int

N = 109;


int

n, m;

int

a[N], b[N];

int

res[N][N];


int

main() {


int

cur = 0;


cin �� n �� m;


for

(
int

i = 0; i n; ++i)



cin �� a[i], cur ^= a[i];


for

(
int

i = 0; i m; ++i)



cin �� b[i], cur ^= b[i];



if

(cur != 0) {



puts(
"NO"
);



return

0;


}



puts(
"YES"
);


for

(
int

i = 1; i m; ++i)



cur ^= b[i];


cur ^= a[0];



cout cur
' '
;


for

(
int

i = 1; i m; ++i)



cout b[i]
' '
;


cout endl;


for

(
int

i = 1; i n; ++i) {



cout a[i]
' '
;



for

(
int

j = 1; j m; ++j)




cout 0
' '
;



cout endl;


}


return

0;

}

K. Вася и грибы

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

n
последовательных клеток. Про каждую клетку Вася знает число


на сколько грамм тяжелеют грибы в этой клетке за минуту. Перем
ещение в соседнюю
клетку занимает у Васи ровно одну минуту, выходить за пределы поляны Вася не может. Две
клетки считаются соседними, если у них есть общая сторона. Когда Вася приходит в клетку,
он собирает все растущие там грибы.

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

ровно по одному разу

и максимизировать при этом суммарный вес собранных
грибов. Изначально все грибы
имеют вес

0
. Обратите внимание, что Васе не обязательно
возвращаться в стартовую клетку.

Помогите Васе! Сообщите ему максимальный суммарный вес грибов, который он может
собрать.

Входные данные

Первая строка содержит число

n

(1 ≤ 
n
 ≤ 3·10
5
)



длина поляны.

Вторая строка содержит

n

чисел

a
1
, 
a
2
, ..., 
a
n

(1 ≤ 
a
i
 ≤ 10
6
)



скорость роста грибов в первом
ряду поляны.

Третья строка содержит

n

чисел

b
1
, 
b
2
, ..., 
b
n

(1 ≤ 
b
i
 ≤ 10
6
)



скорость роста грибов во втором
ряду поляны.

Выходные данные

Выведите одно число


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

ровно один раз
.

Примеры

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

3

1 2 3

6 5 4

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

70

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

3

1 1000 10000

10 100 100000

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

543210

Примечание

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


Таким образом, собраный вес грибов будет

0·1 + 1·2 + 2·3 + 3·4 + 4·5 + 5·6 = 70
.

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


Таким образом, собраный вес грибов
будет

0·1 + 1·10 + 2·100 + 3·1000 + 4·10000 + 5·100000 = 543210
.


Решение



#include

b
its/stdc++.h�


using

namespace

std;


const

int

N = 300 * 1000 + 9;


int

n;

int

a[2][N];

long

long

sum123[2][N];

long

long

sum321[2][N];

long

long

sum111[2][N];


int

main() {


//freopen("input.txt", "r", stdin);



scanf(
"%d"
, &n);


for

(
int

i = 0; i 2; ++i)



for

(
int

j = 0; j n; ++j)




scanf(
"%d"
, &a[i][j]);



for

(
int

i = 0; i 2; ++i)



for

(
int

j = n
-

1; j �= 0;
--
j) {




sum123[i][j] = sum123[i][j + 1] + (j + 1) * 1LL * a[i][j];




sum321[i][j] = sum321[i][j +
1] + (n
-

j) * 1LL * a[i][j];




sum111[i][j] = sum111[i][j + 1] + a[i][j];



}



/*

for(int i = 0; i 2; ++i)


for(int j = n
-

1; j �= 0;
--
j){


cout i ' ' j " : ";


cout sum123[i][j] " " sum321[i][j] " " sum111[i][j] endl
;


}



*/



long

long

res = 0, sum = 0;


for

(
int

i = 0, j = 0; j n; ++j, i ^= 1) {



long

long

nres = sum;



nres += sum123[i][j] + j * 1LL * sum111[i][j];



nres += sum321[i ^ 1][j] + (j + n) * 1LL * sum111[i ^ 1][j];



res = max(res, nres);




sum +=
a[i][j] * 1ll * (j + j + 1);



sum += a[i ^ 1][j] * 1ll * (j + j + 2);


}



for

(
int

j = 0; j n; ++j) res
-
= a[0][j] + a[1][j];


printf(
"%I64d
\
n"
, res);



return

0;

}


Приложенные файлы

  • pdf 9637386
    Размер файла: 2 MB Загрузок: 0

Добавить комментарий