Каким алгоритмом лучше решать задачи на макс. поток?
Например, при ограничениях V<=500, E<=10000
26 2010-08-29 11:08:06
Тема: MaxFlow (3 ответов, оставленных в Algo)
27 2010-08-28 11:18:00
Re: ЛКШ 2010 (9 ответов, оставленных в OlympNews)
в DepositFiles.com или Letitbit.net
28 2010-08-27 16:42:16
Re: ЛКШ 2010 (9 ответов, оставленных в OlympNews)
Если есть, только параллели A и B(только задачи с тестами)!
29 2010-08-27 11:28:44
Тема: ЛКШ 2010 (9 ответов, оставленных в OlympNews)
У кого есть архив ЛКШ 2010 (июль или август)?
30 2010-08-15 19:39:46
Тема: IOI 2010 (0 ответов, оставленных в OlympNews)
Кто знает, будет ли онлайн раунд IOI 2010?
31 2010-08-08 00:55:43
Тема: Hash (3 ответов, оставленных в Algo)
Кто может посоветовать задачи на хэш?
и вообще хэш часто используют на олимпиадах?
кстати, на с++ - map это и есть hash?
32 2010-06-28 11:10:57
Re: triangles (4 ответов, оставленных в Problems)
А как за logN отвечать на запрос: лежит ли точка внутри многоугольника
33 2010-06-27 19:18:11
Тема: triangles (4 ответов, оставленных в Problems)
Даны K точек с положительными целыми координатами. Также даны M треугольников, координаты одной из вершин которых лежат на координате 0, 0 (начала координат), координаты остальных двух вершин являются целыми положительными числами. Определите для каждого треугольника, находится ли хотя бы одна из K точек внутри нее (никакая точка не является вершиной треугольника).
1<=k,m<=10^5
1<=x,y<=10^9
34 2010-06-23 13:24:21
Re: timus 1761 (3 ответов, оставленных в Algo)
nichego ne ponyal
vrode bi
2 2 -> 1
3 3 -> 2
4 5 -> 4
6 15 -> 5
16 33 -> 7
34 47 -> 9
48 69 -> 10
70 87 -> 11
88 174 -> 13
175 175 -> 14
176 374 -> 16
375 375 -> 17
376 830 -> 19
831 831 -> 20
832 1862 -> 22
1863 1863 -> 23
// a b -> c
// in interval a..b max palindrome's length is c
// sequence 0110111001011101111000..................................
35 2010-06-21 19:30:07
Тема: timus 1761 (3 ответов, оставленных в Algo)
Let an integer n be given. Write the integers from 1 to n in binary notation successively from left to right. In the resulting string consisting of zeros and ones, choose a palindrome substring of maximal length. It is required to find the length of this substring.
Input
The only input line contains the integer n in binary notation (1 ? n ? 2^1 000 000).
Output
Output one line containing the required length.
Samples
input output
101 5
10100 11
Hint
In the first sample, the string 11011100101 will be written (a variant of the longest palindrome is underlined).
Nereal'naya zadacha na vid, esli chto http://acm.timus.ru/problem.aspx?space=1&num=1761
36 2010-05-29 08:10:25
Тема: Произведение цифр (3 ответов, оставленных в Problems)
Требуется найти наименьшее натуральное число Q такое, что произведение его цифр равно заданному числу N.
Входные данные
В единственной строке входного файла INPUT.TXT записано одно целое число N (0 ? N ? 10^9).
Выходные данные
В выходной файл OUTPUT.TXT нужно вывести искомое число Q. В том случае, если такого числа не существует, следует вывести -1.
Примеры
№ INPUT.TXT OUTPUT.TXT
1 10 25
2 13 -1
3 90 259
who can solve this problem?
37 2010-05-28 15:22:49
Re: far manager (2 ответов, оставленных в Feedback)
a kak na far kompilirovat' faili c++, naprimer, na pascale fpc aaa.pas, a kak na c++?
38 2010-05-27 19:24:23
Тема: obyom (0 ответов, оставленных в Problems)
Определить объем прямоугольного параллелепипеда, диагональ которого равна K составляет с одной гранью угол 30?, а с другой 45?.
Найти объем, например, K^3/8
39 2010-05-16 18:56:37
Тема: Who are you, Mister Graph? (2 ответов, оставленных в Problems)
Given degrees of a graph vertices, determine whether they conform to any undirected graph.
If so - output it. It is guaranteed that in the case when the graph exists, the number of edges does not exceed 500000. The graph should not contain loops and multiple edges.
*loop = петля
----------------------------
The first line of the input file contains an integer N - the number of vertices in the graph (1 < N <= 10000).
N numbers are written in the next line: d1, d2, ..., dn - the degrees of vertices (0 <= di <= 10000). Numbers in the line are separated by spaces.
-----------------------------
Write "YES" or "NO" - depending on the existence of a graph.
If yes, the first line should contain M - the number of edges in the resulting graph, and the following M lines must contain the description of each edge - numbers of vertices, that are the ends of the corresponding edge. Vertices are numbered starting from one in the order they are given in the input file.
If there are multiple graphs satisfying the condition, output any.
----------------------------
например:
input
4
2 1 2 3
output
YES
4
4 3
4 1
4 2
3 1
40 2010-05-11 18:50:26
Re: problem div to mul (3 ответов, оставленных в Problems)
1<=l,r<=10^9
|l-r|<=10^5
41 2010-05-11 15:45:42
Тема: problem div to mul (3 ответов, оставленных в Problems)
Найдите количество чисел из отрезка [l,r] , которые делятся на произведение своих цифр.
42 2010-04-25 12:06:08
Тема: сложная задача (3 ответов, оставленных в Problems)
Fourth Great and Bountiful Human Empire is developing a transconduit tunnel
network connecting all it's planets. The Empire consists of N planets,
represented as points in the 3D space. The cost of forming a transconduit
tunnel between planets A and B is:
TunnelCost[A,B]=min{|xa-xb|, |ya-yb|, |za-zb|}
where (xa, ya, za) are 3D coordinates of planet A, and (xb, yb, zb) are
coordinates of planet B. The Empire needs to build exactly N - 1 tunnels in
order to fully connect all planets, either by direct links or by chain of links.
You need to come up with the lowest possible cost of successfully completing
this project.
INPUT
The first line of input contains one integer N (1 ? N ? 100 000), number of
planets.
Next N lines contain exactly 3 integers each. All integers are between -10^9 and 10^9 inclusive. Each line contains the x, y, and z coordinate of one planet (in order).
No two planets will occupy the exact same point in space.
OUTPUT
The first and only line of output should contain the minimal cost of forming
the network of tunnels.
SAMPLE TEST CASES
input
5
11 -15 -15
14 -5 -15
-1 -1 -5
10 -4 -1
19 -4 19
output
4
43 2010-04-21 18:57:32
Тема: задача на дерево отрезков (10 ответов, оставленных в Problems)
Манхэттенское расстояние
На плоскости дано N различных точек. Расстоянием между точками (x1, y1) и (x2, y2) будем
считать |x1 - x2| + |y1 - y2|. Для каждой точки требуется найти одну из ближайших к ней точек.
Формат входных данных
Первая строка входного файла содержит целое число N (1 < N <= 100000). Следующие N строк
содержат по два числа — координаты точек. Координаты — целые числа, по модулю не
превышающие 10000. Числа в строках разделены пробелами.
Формат выходных данных
Выходной файл должен содержать N целых чисел, разделенных пробелом: i-е число есть номер
одной из точек, ближайших к i-й. Точки нумеруются в том порядке, в котором они даны во
входном файле, начиная с единицы.
44 2010-04-21 16:41:31
Тема: far manager (2 ответов, оставленных в Feedback)
4to nado sdelat' na FAR 4tobi, kogda otkrivaesh' *pas, ili *.cpp, takiye slova kak "#include" ili "if then else" bili raznih cvetov?
45 2010-04-20 20:04:47
Тема: Dijkstra with Set (8 ответов, оставленных в Algo)
Кто может реализовать дейкстру с set-ом на с++?
А, если, кто знает как реализовывается с Фенвиком? (просто алгоритм)
46 2010-04-14 07:38:53
Тема: Longest Path (5 ответов, оставленных в Problems)
you are given directed graph without cycles. How to find the longest path in this graph?
47 2010-04-14 07:37:11
Тема: Диаметр графа (13 ответов, оставленных в Algo)
Как находить диаметр взвешенного графа?
48 2010-03-27 19:18:02
Тема: Точка сочл. (1 ответов, оставленных в Feedback)
...
...
.
.
void dfs (int v, int p = -1) {
used[v] = true;
tin[v] = fup[v] = timer++;
int children = 0;
for (size_t i=0; i<g[v].size(); ++i) {
int to = g[v][i];
if (to == p) continue; // эту строку можно удалить
.
..
...строка
int to = g[v][i]; кажется неправильна
49 2010-03-14 19:03:37
Тема: Импульсные сигналы (3 ответов, оставленных в Problems)
F Импульсные сигналы
Некоторая сеть связи содержит N генераторов импульсных сигналов, в составе которых имеется
внутренний счетчик. Линии связи двунаправленные и между двумя генераторами может быть
только одна линия связи. Изначально все генераторы выключены и их счетчики установлены в ноль.
Во включенном состоянии каждый генератор отправляет сигнал с интервалом в одну секунду всем
соседним генераторам в сети, если таковые имеются. Если к генератору приходит сигнал по линии
связи, то его внутренний счетчик увеличивается на единицу. Если генератор был выключен при
получении сигнала, то он включается и увеличивает свой счетчик на единицу, и через 1 секунду
рассылает свой первый сигнал. В момент времени 0 включается и отправляет свой первый сигнал
генератор номер 1. От вас требуется определить состояние счетчиков всех генераторов в момент
времени T (через T полных секунд, т.е. сигнал, прошедший на секунде T, считается обработанным).
Формат входных данных
Первая строка входного файла содержит целые числа N и M (1 ? N ? 100, 1 ? M ? 10000) – число
генераторов и число линий связи в сети. Следующие M строк содержат по два различных числа –
номера генераторов соединенных между собой в сети. Генераторы нумеруются от 1 до N. Далее
следует целое число T (1 ? T ? 1000000000). Числа в строках разделены пробелами.
Формат выходных данных
Выходной файл должен содержать N разделенных пробелами чисел – показания счетчиков через T
полных секунд для всех генераторов, приведенные последовательно от 1-го до N-го генератора.
например:
input.txt
2 1
1 2
10
output.txt
10 11
50 2010-03-14 18:59:14
Тема: Текстовый редактор (2 ответов, оставленных в Problems)
При поиске строки в тексте текстовый редактор выделяет все найденные вхождения строки в
тексте. Например, для текста "hello world" при поиске строки "o" будут выделены обе буквы "o".
Следует заметить, что вхождения строки в текст могут перекрываться между собой. Для
заданного текста и строки требуется посчитать количество выделенных букв.
Формат входных данных
Первая строка входного файла содержит текст, длиной не меньше 1 и не больше 500000 симво-
лов. Вторая строка содержит строку поиска длиной не меньше 1 и не больше 500000 символов.
Текст и строка поиска состоят из строчных букв английского алфавита и пробелов.
Формат выходных данных
Выходной файл должен содержать одно целое неотрицательное число - количество выделенных
букв.
например:
input.txt
ababa
aba
output.txt
5