Олимпиадные задачи

21.05.04

"Манхеттен" (5 баллов).

Входной файл: input.txt
Выходной файл: output.txt
Ограничение по времени: 1 сек. на тест
Ограничение по памяти: 1 Mb

Условие

На плоскости задано n точек. Расстояние между точками (x₁, y₁) и (x₂, y₂) будет вычислять как сумму модулей разностей их координат: r = |x₁ - x₂| + |y₁ - y₂|. Найти точку, сумма расстояний от которой до заданных n точек минимальна.

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

В первой строке задано одно целое число n, 1 <= n <= 1000. Далее идут n строк, в каждой из которых записаны два числа, разделенные пробелом, - координаты точек. Координаты - целые числа, по модулю меньше 10000.

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

Вывести одну строку, содержащую два вещественных числа, разделенные пробелом. Числа выводить с 5 знаками после десятичной точки. Если существует

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

Пример входного файла (input.txt)

Пример выходного файла (output.txt)


2.00000 3.14159

Решение:

 Очевидно, что задачу минимизации заданной суммы можно свести к двум подзадачам: для x и для y. Рассмотрим одномерную задачу для x. По заданным x1,

 x2, ..., xn найти x, такое что s(x) = |x - x1| + |x - x2| + ... + |x - xn| минимально. Пусть x - точка, в которой s(x) достигает минимума. Пусть

слева от нее k1 точек, а справа k2 точек. Если k1 < k2, то, сдвинувшись на небольшое расстояние вправо, мы уменьшим s(x), поэтому k1 >= k2.

Аналогично k1 <= k2. В результате получаем, что k1 = k2. Таким образом, искомая точка - это точка, слева и справа от которой одинаковое количество

точек из заданного набора. В случае когда n нечетно x = x(n+1)/2, а когда n четно в качестве x можно взять любую точку из отрезка [xn/2, xn/2+1]. 
Текст программы: 

#include <stdio.h>
#include <algorithm>
#include <vector>

using namespace std;

int main()
{
int n, x1, y1, i;
vector<int> x, y; 

freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);

scanf("%d", &n);
for (i = 0; i < n; i++)
{
scanf("%d%d", &x1, &y1);
x.push_back(x1);
y.push_back(y1);
}
sort(x.begin(), x.end());
sort(y.begin(), y.end());
printf("%d.0000 %d.0000\n", x[(n-1) / 2], y[(n-1) / 2]);

fclose(stdout);
return 0;
}
Результаты по задаче №7 "Манхеттен" (5 баллов).
Ник
Результат 
ak13_boda
accepted 
aleksandrr
accepted 
arti
accepted 
Berdan
accepted 
DEathkNIghtS
accepted 
SadKo_Sobaka
time limit exceeded on test #7 
VOLAND
accepted 
********************************************************************

"Морской бой" (10 баллов).

Условие

В игру "Морской бой" играют два человека. В начале игры каждый чертит на клеточном листе бумаги свое поле - квадрат с длиной стороны 10 клеток. Строки квадрата обозначаются латинскими буквами от a до j сверху вниз, столбцы - цифрами от 0 до 9 слева направо. Затем игрок расставляет на своем поле корабли: один 4-палубный, два 3-палубных, три 2-палубных и четыре 1-палубных. Корабль - это группа соседних клеток, образующих горизонтальную или вертикальную полоску. Количество палуб корабля - это количество клеток, из которых он состоит. Корабли могут соприкасаться со сторонами поля, но не могут касаться друг друга. Игроки не показывают друг другу свои поля. Примеры полей с расставленными кораблями ('.' - пусто, '#' - палуба):

     №1               №2               №3               №4

  0123456789       0123456789       0123456789       0123456789
a .......###     a ....##....     a .#.....###     a ..........
b ..####....     b ..........     b #.........     b ..........
c #.........     c .##...#...     c ..#.###...     c .####.....
d #.#..##...     d ......#...     d ..........     d ..........
e #.#.......     e .#.#......     e ####......     e ##....##..
f ..........     f ...#...#..     f ..........     f ....#.....
g ......#...     g ...#......     g .#....#...     g .#..#.....
h ##.......#     h #..#...#.#     h .#....#...     h .#..#..#..
i ....#.....     i #.........     i ..........     i ..........
j .......#..     j #......###     j .#....##..     j ..#.#.#...

В примерах №1 и №2 корабли расставлены правильно. В примере №3 корабли расставлены неверно, потому что два однопалубных корабля (a1 и b0) касаются друг друга. В примере №4 не хватает одного 3-палубного корабля.

Первый игрок делает первый ход. Ход заключается в том, что игрок называет позицию на поле противника. Это клетка, в которую стреляет игрок. Причем по правилам он не может выстрелить в одну и ту же клетку дважды. Если эта клетка пуста, то противник говорит "мимо" и ход переходит к нему. В противном случае палуба корабля, расположенная в данной клетке, считается уничтоженной, и возможны два варианта. 1) Если все остальные палубы данного корабля были уничтожены раньше (или это 1-палубный корабль), то противник говорит "убит". 2) Если у корабля сохранилась хотя бы одна палуба, то противник говорит "ранен". В обоих случаях ход снова делает тот же игрок (т.е. он стреляет, пока не промахнется). Задача каждого игрока - уничтожить все корабли противника. Выигрывает тот, кто сделает это раньше.

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

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

Первые десять строк входного файла содержат по десять символов каждая. В них задано описание поля первого игрока. В строках содержатся символы '.' (пустая клетка) и '#' (палуба корабля). Затем идет пустая строка. В следующих десяти строках аналогично задается поле второго игрока. Затем идет пустая строка. Следующая (23-я по счету) строка содержит одно целое число n, 0 <= n <= 1000 - количество сделанных ходов. Следующие n строк задают описание ходов в том порядке, в котором их делали игроки. Описание хода имеет формат "номер_игрока позиция ответ_противника". "номер_игрока" - один из символов '1' или '2'. "позиция" - два символа, первый - буква от 'a' до 'j', второй - цифра от '0' до '9'. "ответ_противника" - слово 'past' (мимо), 'killed' (убит) или 'wounded' (ранен).

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

В выходной файл вы должны выдать одно из следующих сообщений.

"Error: first player's field is incorrect"
Первый игрок неверно расставил свои корабли.
"Error: second player's field is incorrect"
Второй игрок неверно расставил свои корабли.
"Error in move #k: the game is already finished"
(Здесь и далее k нужно заменить на номер хода (нумерация с 1).) Игра уже завершена, но игрок делает ход. Напомню, что игра завершается, когда у одного из игроков уничтожены все корабли.
"Error in move #k: this move must be made by another player"
Ходить должен другой игрок.
"Error in move #k: two shots in one place"
Игрок выстрелил в клетку, в которую уже стрелял.
"Error in move #k: wrong enemy's answer"
Противник дал неправильный ответ.
"OK: first player is winner"
Первый игрок победил.
"OK: second player is winner"
Второй игрок победил.
"OK: the game isn't finished yet"
Игра еще не завершена.

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

Пример входного файла (input.txt)


 .......###
 ..####....
#.........
#.#..##...
#.#.......
 ..........
 ......#...
##.......#
 ....#.....
 .......#..

 ....##....
 ..........
 .##...#...
 ......#...
 .#.#......
 ...#...#..
 ...#......
#..#...#.#
#.........
#......###

8
1 a4 wounded
1 a3 past
2 j9 past
1 b4 past
2 b1 past
1 a5 killed
1 h1 past
2 b2 wounded

Пример выходного файла (output.txt)


OK: the game isn't finished yet

Пример входного файла (input.txt)


 .......###
 ..####....
#.........
#.#..##...
#.#.......
 ..........
 ......#...
##.......#
 ....#.....
 .......#..

 ....##....
 ..........
 .##...#...
 ......#...
 .#.#......
 ...#...#..
 ...#......
#..#...#.#
#.........
#......###

8
2 a0 killed
1 a3 past
2 j9 past
1 b4 past
2 b1 past
1 a5 killed
1 h1 past
2 b2 wounded

Пример выходного файла (output.txt)


Error in move #1: this move must be made by another player

Пример входного файла (input.txt)


#........#
 .########.
 ..#....#..
####..####
 .#..##..#.
##..##..##
 .#.#..#.#.
###....###
 .########.
#........#

 ..........
 ..#####...
 .#....##..
 .#...#.#..
 .#..#..#..
 .#..#..#..
 .#.#...#..
 .##....#..
 ..#####...
 ..........

8
2 a0 killed
1 a3 past
2 j9 past
1 b4 past
2 b1 past
1 a5 killed
1 h1 past
2 b2 wounded

Пример выходного файла (output.txt)


Error: first player's field is incorrect

Решение:

Решение задачи №8 "Морской бой" (10 баллов).
Данная задача скорее не алгоритмическая, а задача на аккуратную реализацию. Поэтому просто помещаю текст решения.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define max(a, b) (((a) > (b)) ? (a) : (b))

typedef char tfield[10][11];
typedef int tshot[10][10];

void show_mes(char *mes)
{
printf("%s\n", mes);
exit(0);
}

void input_field(tfield &f)
{
for (int i = 0; i < 10; i++)
scanf("%s", f[i]);
}

int test_field(tfield &f)
{
int i, j;
int m[10][10], c[6];
for (i = 0; i < 9; i++)
for (j = 0; j < 9; j++)
{
if (f[i][j] == '#' && f[i+1][j+1] == '#') return 0;
if (f[i][j+1] == '#' && f[i+1][j] == '#') return 0;
}
m[0][0] = (f[0][0] == '#') ? 1 : 0;
for (i = 1; i < 10; i++)
{
if (f[0][i] == '.') m[0][i] = 0;
else m[0][i] = 1 + m[0][i - 1];
if (f[i][0] == '.') m[i][0] = 0;
else m[i][0] = 1 + m[i - 1][0];
}
for (i = 1; i < 10; i++)
for (j = 1; j < 10; j++)
if (f[i][j] == '.') m[i][j] = 0;
else m[i][j] = 1 + max(m[i - 1][j], m[i][j - 1]);
c[5] = 0;
for (i = 4; i > 0; i--) c[i] = (5 - i) + c[i + 1];
for (i = 0; i < 10; i++)
for (j = 0; j < 10; j++)
if (m[i][j] > 4) return 0;
else if (m[i][j] > 0) c[m[i][j]]--;
for (i = 1; i <= 4; i++)
if (c[i]) return 0;
return 1;
}

void recur(int &killed, tfield &f, tshot &s, int r, int c, int dr, int dc)
{
if (r < 0 || r >= 10 || c < 0 || c >= 10) return;
if (f[r][c] != '#') return;
if (!s[r][c]) killed = 0;
else recur(killed, f, s, r + dr, c + dc, dr, dc);
}

void main()
{
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);

tfield f1, f2;
int n, i, curpl, ships1, ships2;
char str[200];
tshot shot1, shot2;

input_field(f1);
if (!test_field(f1))
show_mes("Error: first player's field is incorrect");
input_field(f2);
if (!test_field(f2))
show_mes("Error: second player's field is incorrect");

curpl = 1;
ships1 = ships2 = 10;
scanf("%d", &n);
memset(shot1, 0, sizeof(shot1));
memset(shot2, 0, sizeof(shot2));
for (i = 0; i < n; i++)
{
if (ships1 == 0 || ships2 == 0)
{
sprintf(str, "Error in move #%d: the game is already finished", i + 1);
show_mes(str);
}
int pl, r, c;
char pos[3], ans[10];
scanf("%d%s%s", &pl, pos, ans);
if (pl != curpl)
{
sprintf(str, "Error in move #%d: this move must be made by another player", i + 1);
show_mes(str);
}
r = pos[0] - 'a';
c = pos[1] - '0';
if (pl == 1)
{
if (shot1[r][c])
{
sprintf(str, "Error in move #%d: two shots in one place", i + 1);
show_mes(str);
}
shot1[r][c] = 1;
int killed = 0;
if (f2[r][c] == '#')
{
killed = 1;
recur(killed, f2, shot1, r - 1, c, -1, 0);
recur(killed, f2, shot1, r + 1, c, +1, 0);
recur(killed, f2, shot1, r, c - 1, 0, -1);
recur(killed, f2, shot1, r, c + 1, 0, +1);
}
if (f2[r][c] == '.' && strcmp(ans, "past") ||
f2[r][c] == '#' && !killed && strcmp(ans, "wounded") ||
f2[r][c] == '#' && killed && strcmp(ans, "killed"))
{
sprintf(str, "Error in move #%d: wrong enemy's answer", i + 1);
show_mes(str);
}
if (killed) ships2--;
if (f2[r][c] == '.') curpl = 2;
}
else
{
if (shot2[r][c])
{
sprintf(str, "Error in move #%d: two shots in one place", i + 1);
show_mes(str);
}
shot2[r][c] = 1;
int killed = 0;
if (f1[r][c] == '#')
{
killed = 1;
recur(killed, f1, shot2, r - 1, c, -1, 0);
recur(killed, f1, shot2, r + 1, c, +1, 0);
recur(killed, f1, shot2, r, c - 1, 0, -1);
recur(killed, f1, shot2, r, c + 1, 0, +1);
}
if (f1[r][c] == '.' && strcmp(ans, "past") ||
f1[r][c] == '#' && !killed && strcmp(ans, "wounded") ||
f1[r][c] == '#' && killed && strcmp(ans, "killed"))
{
sprintf(str, "Error in move #%d: wrong enemy's answer", i + 1);
show_mes(str);
}
if (killed) ships1--;
if (f1[r][c] == '.') curpl = 1;
}
}
if (!ships2)
show_mes("OK: first player is winner");
else if (!ships1)
show_mes("OK: second player is winner");
else
show_mes("OK: the game isn't finished yet");
}
Результаты по задаче №8 "Морской бой" (10 баллов).
Ник
Результат
ak13_boda
wrong answer on test #2
aleksandrr
accepted
arti
wrong answer on test #4
Berdan
accepted
DEathkNIghtS
accepted
SadKo_Sobaka
wrong answer on test #9
VOLAND
wrong answer on test #17

Домой | Мои программы | Олимпиадные задачи

Дата последнего изменения этого узла 21.05.2004