Задача A. Arithmetic pairs ≡

Условие

Требуется подсчитать общее количество пар целых чисел (p, n) таких, что p ≥ 1, n > 1 и A ≤ pⁿ ≤ B.

Формат входного файла

Входной файл содержит два натуральных числа: A и B.

Формат выходного файла

Выходной файл должен содержать единственное целое число — количество пар.

Ограничения

2 ≤ A ≤ B < 2⁶³

Примеры тестов

10 100

13

37 48

0

Problem B. Biota ≡

Statement

Young marine biologist Masha spent her summer in Primorye, diving and taking notes of what she saw on the seafloor. Later she found her records for one of the bays where she has been. These records were:

• A % of the seafloor is inhabited by starfish.
• B % of the seafloor is inhabited by sea urchins.
• C % of the seafloor is inhabited by shellfish.

Help Masha to figure the minimum possible percentage of the seafloor inhabited by all three species simultaneously.

In the first example, shellfish live everywhere. Starfish and sea urchins each take 3/4 of the seafloor, which means that at least half of the seafloor is inhabited by shellfish, starfish and sea urchins simultaneously.

In the second example, there are areas where 2 out of 3 species live. But it's possible that there are no areas where all 3 species live.

Input file format

Input file contains integers A, B and C.

Output file format

Output file must contain a single integer from 0 to 100 — the answer, in percents.

Constraints

0 ≤ A, B, C ≤ 100

Sample tests

75 75 100

50

30 45 40

0

70 80 90

40

Problem C. Easy patrol ≡

Statement

Young programmer Vasya tinkered with robots, and decided to create a new startup Easy Patrol with the goal of producing robot guardian to replace human guards.

As a first step, he considered a single wall of N meters in length and two patrolling robots moving back and forth along it.

First robot starts patrolling at the point located x meters from the left edge of the wall, moving to the right. Second robot starts patrolling at the point located y meters from the left edge of the wall, moving to the left.

Each second, events happen in the following order:

1. if robots are about to collide (that is, are facing each other at the distance 0 or 1 meters), both reverse direction.
2. each robot checks whether it has reached the edge and reverses direction if it is so.
3. both robots move simultaneously, each for exactly 1 meter in its current direction.

Your program must determine maximum possible distance between two robots.

Input file format

Input file contains integers N, x, y.

Output file format

Output file must contain a single integer — maximum distance between robots in meters.

Constraints

4 ≤ N ≤ 10⁶

0 ≤ x, y ≤ N

Sample tests

5 1 3

4

8 3 1

4

Problem D. Great triangle ≡

Statement

Consider a set of n points on a plane, described by their coordinates: M = {(x_i, y_i): i = 0, 1, …, n − 1}.

Your program must, given two points A and B, find a point C from set M, such that triangle {A, B, C} contains maximum possible number of points from M. Points both inside and on the edges of the triangle are counted.

Input file format

Input file contains integer n, followed by n pairs of integers — point coordinates (x_i, y_i). Next, four integers follow — coordinates of points A and B.

Output file format

Output file must contain a single integer — index of point C. Indexes start from zero. If there are several solutions, output any of them.

Constraints

Points A and B are different.

 − 10⁴ ≤ (x_i, y_i) ≤ 10⁴, 0 < n ≤ 10⁵

Sample tests

10
-7683 -1465
 1000  6970
-1096 -1613
 7052  3877
-8237  2965
 5089  6152
-7697  5970
 1340 -7370
 2068  1467
 4499 -3269

 1990 -5786
-6140 -5000

5

10
-4036  1190
 4691 -1023
 7809 -1023
 7021 -6507
 4691 -1023
-1000 -5000
 3096 -1023
 1570 -4210
 7809 -1023
 7809 -1023

-7500 -5103
-1059 -1023

9

Задача E. Highway cycle ≡

Условие

Улицы города, в котором живет юный программист Вася, могут быть представлены в виде дерева. Каждая вершина дерева соответствует перекрестку, а каждое ребро — улице. Таким образом, улиц в городе на 1 меньше, чем перекрестков. Из каждого перекрестка по улицам можно добраться до любого другого.

Улицы в городе бывают двух типов — жилые или офисные.

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

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

Формат входного файла

Входной файл содержит целое число N — количество перекрестков в городе, за которым следует N − 1 троек целых чисел u, v, c — номера перекрестков, соединенных улицей (u, v) и тип улицы. c = 0 — жилая улица, c = 1 — офисная улица.

Формат выходного файла

Выходной файл должен содержать единственное целое число — количество способов.

Ограничения

3 ≤ N ≤ 3000

0 ≤ u, v < N

Примеры тестов

4
0 1 0
1 2 1
2 3 1

1

5
0 1 0
1 2 1
2 3 1
3 4 0

2

Задача F. Interactive increment ≡

Условие

Данная задача является интерактивной.

Жюри загадало секретное целое число X, состоящее из ровно N бит. Известно, что в этом числе есть K единичных бит (и N − K нулевых бит). Ваша программа может делать запросы вида "+ Y", которые к текущему значению числа X будет прибавляют целое число Y. При этом биты старше N-о отбрасываются, то есть выполняется операция вида X = (X + Y) mod 2^N.

На каждый запрос программа жюри отвечает количеством единичных бит в текущем значении X. Требуется определить текущее значение числа X, сделав не более ⌊ N2⌋ запросов.

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

В первой строке входных данных записано два целых числа N и K — общее количество бит в числе и количество единичных бит в начальном значении соответственно.

Протокол взаимодействия

Чтобы сделать запрос, ваша программа должна вывести "+ Y", где Y — целое число, которое нужно прибавить к X. На каждый запрос программа жюри ответит целым числом — количеством единичных бит в числе X после выполнения запроса.

Когда ваша программа определит текущее значение X, она должна вывести "! X" и завершиться.

Если ваша программа сделает недопустимый запрос, то она получит вердикт "Presentation error". Если ваша программа превысит допустимое количество запросов, то она получит вердикт "Wrong answer".

Каждый запрос и вывод окончательного результата должен быть одиночной строкой заканчивающейся одиночным переводом строки (\n). Буфер вывода необходимо сбрасывать после каждой строки:

Ограничения

1 ≤ N ≤ 60

0 ≤ K ≤ N

0 ≤ X, Y < 2^N

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

В первом примере было загадано число 13 (1101 в двоичной системе счисления). После выполнения первого запроса получилось (13 + 9) mod 16 = 6 (0110₂). После выполнения второго запроса получилось (6 + 9) mod 16 = 15 (1111₂).

Примеры тестов

4 3 

2

4

+ 9

+ 9

! 15

2 2

! 3

Problem G. Jigsaw separation ≡

Statement

Rectangular jigsaw puzzle consists of two pieces. Each piece is a 4-connected set of square cells, each cell represented by character 'X' or 'O'.

Your program must determine whether it is possible to separate puzzle pieces by moving either of them in vertical or horizontal direction.

In the first sample it is possible to separate pieces by moving 'X' piece up and/or 'O' piece down.

Input file format

First line of input contains two integers W H. Following H lines contain W characters each — puzzle representation.

Output file format

Output must contain a single string YES or NO.

Constraints

1 ≤ W, H ≤ 100. Each piece contains at least one cell.

Sample tests

4 3
XXXX
XOXO
OOOO

YES

3 3
XXX
XOX
XXX

NO