Отправляет email-рассылки с помощью сервиса Sendsay

Олимпиадные задачи и алгоритмы на C++

Рассылка закрыта

При закрытии подписчики были переданы в рассылку "Обзор инструментов SEO-оптимизатора и методов продвижения" на которую и рекомендуем вам подписаться.

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

←   Май 2004   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Автор
Виктор Журавлев

Статистика

1.725 подписчиков
-1 за неделю
←   Все выпуски   →

Олимпиадные задачи и алгоритмы на C++


Информационный Канал Subscribe.Ru

Олимпиадные задачи и алгоритмы на C++

    Здравствуйте, уважаемые подписчики.

Решение задачи №7 "Манхеттен" (5 баллов).

     Очевидно, что задачу минимизации заданной суммы можно свести к двум подзадачам: для 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_bodaaccepted
aleksandrraccepted
artiaccepted
Berdanaccepted
DEathkNIghtSaccepted
SadKo_Sobakatime limit exceeded on test #7
VOLANDaccepted

Решение задачи №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_bodawrong answer on test #2
aleksandrraccepted
artiwrong answer on test #4
Berdanaccepted
DEathkNIghtSaccepted
SadKo_Sobakawrong answer on test #9
VOLANDwrong answer on test #17

    Условия задач, тесты и решения вы всегда можете найти на сайте accepted.narod.ru.

Ведущий рассылкой: Виктор Журавлев
Вопросы, пожелания, предложения пишите на мой e-mail.

http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу

В избранное