Предлагаю делать отдельные ветки обсуждений для каждой тренировки...
Problems of September 28, 2011 Contest.
Team standings of today's contest.
Personal standings of today's contest.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
7 | cnnfls_csy | 3569 |
9 | ecnerwala | 3494 |
10 | Um_nik | 3396 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 160 |
3 | -is-this-fft- | 159 |
4 | atcoder_official | 158 |
4 | awoo | 158 |
4 | cry | 158 |
7 | adamant | 155 |
8 | nor | 154 |
9 | TheScrasse | 152 |
10 | maroonrk | 151 |
Предлагаю делать отдельные ветки обсуждений для каждой тренировки...
Название |
---|
Хотя, на самом деле, все простые пути из S в E проходят через одни и те же точки сочленения... странно. Может, лишние посчитал (те, у которых с обеих сторон путь в одной компоненте)?
1 2
2 3
3 4
4 5
2 6
6 5
6 7
Находим путь из 1 в 5. В итоге пройдем лишнюю точку - 6. Для графа она точка сочленения, а для нашего пути никакой роли не играет.
Я под конец пытался сдать такое решение:
Сначала идем по диагоналям, пока не сравняемся по улицам или авеню. А дальше увеличиваем/уменьшаем оставшуюся координату. Там 2 случая, либо 600 футов проходим, либо 200 в зависимости от четности суммы координат. Но WA. В чем ошибка?
не совсем верно в конце.
там или 2 * k * 200 футов или (2 * k +/- 1) * 200 футов в зависимости от четности, где k - сколько кварталов нужно пройти по прямой до финиша.
Можно использовать половину очереди....т.е. зациклить по модулю 5000^2 / 2. Тогда возможно хватит памяти и вроде такого количества вершин должно хватать....но тогда нужно пользоваться или 10 или 12 байтным типом для хранения вершин в очереди.
Там можно вывести простую формулу для ответа - а идея, как уже упоминалась выше, это сначала по диагонали подойти к финишу, чтоб первая или вторая координаты сравнялись, а потом дойти по прямой подобием зиг-зага.