Problem A. Count Squares ≡

Author:B. Vasilyev, A. Klenin
Input file: input.txt   Time limit:3 sec
Output file: output.txt   Memory limit:64 Mb

Statement

Given a set of points with integer coordinates xi, yi, i = 1… N, your program must find all the squares having each of four vertices in one of these points.

Input file format

Input file contains integer N followed by N pairs of integers xi yi.

Output file format

Output file must contain a single integer — number of squares found.

Constraints

−104 ≤ xi, yi ≤ 104, 1 ≤ N ≤ 2000. All points in the input are different.

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
4 0 0 4 3 -3 4 1 7
 
1
2 
9
1 1  1 2  1 3  
2 1  2 2  2 3  
3 1  3 2  3 3
 
6

Задача B. Длинный текст и много слов ≡

Автор:A. Klenin
Входной файл: input.txt   Ограничение времени:5 сек
Выходной файл: output.txt   Ограничение памяти:200 Мб

Условие

Имеется текст и N слов. Длина текста составляет L символов, длина каждого слова — от 1 до 255 символов. Требуется для каждого слова определить, входит ли оно в текст. Все слова и текст состоят из латинских букв. Заглавные и строчные буквы считаются различными. Обратите внимание, данная задача отличается от задачи B только ограничениями.

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

В первой строке входного файла содержится текст, во второй — число N, в следующих N строках — слова.

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

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

Ограничения

1 ≤ L ≤ 20000, 1 ≤ N ≤ 10000.

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

№ Входной файл (input.txt) Выходной файл (output.txt)
1 
Longlongstring
2
short
string
 
0 1

Problem C. Enormous spiral ≡

Author:A. Klenin
Input file: input.txt   Time limit:3 sec
Output file: output.txt   Memory limit:64 Mb

Statement

Consider an infinite plane divided into square cells with the side of 1. The spiral starts at cell (0, 0) and consists of N straight segments. First segment runs from the starting cell in the direction of x axis, each following segment takes a 90° turn to the right. Segment number i contains exactly ai cells.

Segments do not overlap except at joint cells, which are treated as belonging to both adjacent segments.

A square window on the plane consists of S × S cells and is defined by coordinates of top left cell (x, y) (y axis is directed upwards).

Your program will be given coordinates of K square windows, and must determine, for each window, the number of cells inside it belonging to the spiral.

For example, a spiral below is defined by input of sample test 3. Cells marked with 'x' are inside the first window from the same test.

xxx
xxx
xxx

Input file format

Input file contains numbers N K S followed by N integers ai, and then by K coordinates xi yi.

Output file format

Output file must contain K numbers — cell counts for each window.

Constraints

2 ≤ ai ≤ 109, ai−1 < ai+1, 1 ≤ N ≤ 106, −109 ≤ xi, yi ≤ 109, 1 ≤ K ≤ 10000, 1 ≤ S ≤ 100

Sample tests

No. Input file (input.txt) Output file (output.txt)
1 
1 1 10
100
0 0
 
10
2 
2 1 10
100 1000
1 -1
 
0
3 
4 3 3
4 3 6 4
-1 0
0 0
1 0
 
5 6 7
0.033s 0.005s 11