Форум программистов
 
Контакты: о проблемах с регистрацией, почтой и по другим вопросам пишите сюда - alarforum@yandex.ru, проверяйте папку спам! Обязательно пройдите активизацию e-mail.

Вернуться   Форум программистов > C++ > Общие вопросы C/C++
Регистрация

Восстановить пароль
Повторная активизация e-mail


Донат для форума - использовать для поднятия настроения себе и модераторам

А ещё здесь можно купить рекламу за 25 тыс руб в месяц! ) пишите сюда - alarforum@yandex.ru

Ответ
 
Опции темы
Старый 31.10.2012, 12:28   #1
Olzhas-KazNU
 
Регистрация: 26.10.2012
Сообщений: 4
Репутация: 10
По умолчанию Задача по программированию

Браконьер Петрович использует распространенный незаконный способ рыбалки с использованием рыболовной сети. Но проблема в том, что крупная рыба часто рвет сеть и приходится ее восстанавливать. Однажды Петрович задумался: какое максимальное количество повреждений может быть в рыболовной сети, таких, что сеть не будет разорвана на части? Вам предстоит помочь ему в вычислениях.

Сеть имеет прямоугольную форму размером M*N узлов, все смежные узлы соединены леской. Под разрывом будем понимать только единичный обрыв лески между двумя смежными узлами сети.

Например, если сеть имеет размер 2х2, то внешний вид сети будет напоминать квадрат, где допустим только один разрыв в одном из четырех возможных соединений, т.к. любые 2 разрыва приведут к разделению сети на 2 части.

Входные данные

Входной файл INPUT.TXT содержит два целых числа M и N – размеры рыболовной сети (1 <= M, N <= 10 000).

Выходные данные

В выходной файл OUTPUT.TXT выведите максимальное число разрывов заданной сети, которые не приведут к распадению рыболовной снасти Петровича.
примеры 2 2 ==>1
2 3==>3
вот прога ошибку выдает на 3 тесте
Код:
#include<iostream>
using namespace std;
main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int n,k;
cin>>n>>k;
cout<<(n*k)/2-1;
return 0;
 
       }

Последний раз редактировалось ACE Valery; 31.10.2012 в 16:49.
Olzhas-KazNU вне форума   Ответить с цитированием
Старый 31.10.2012, 12:34   #2
Helloween
Форумчанин
 
Регистрация: 24.04.2012
Сообщений: 300
Репутация: 230
По умолчанию

Т.е вы считаете что вывели формулу для расчета? Мде.
__________________
Помог? Оставляем отзыв =)
Helloween вне форума   Ответить с цитированием
Старый 31.10.2012, 13:59   #3
Mandrivnyk
Software Developer
Профессионал
 
Аватар для Mandrivnyk
 
Регистрация: 01.03.2011
Адрес: Stuttgart
Сообщений: 1,098
Репутация: 119

icq: 260063504
По умолчанию

Цитата:
Например, если сеть имеет размер 2х2, то внешний вид сети будет напоминать квадрат, где допустим только один разрыв в одном из четырех возможных соединений, т.к. любые 2 разрыва приведут к разделению сети на 2 части.
Я чего-то не понимаю?

Код:
┌─┬─┐
├─┼─┤
└─┴─┘
Вот сеть 2х2.
Делаем два разрыва:
Код:
┌─┬─┐
│ │ │
└─┴─┘
Сетка не разделяется на две части?
__________________
Болтовня ничего не стоит. Покажите мне код. (c) Linus Torvalds
Помог ответ? -- Поставьте отзыв.
Выражения особой благодарности в рублевом эквиваленте отправлять сюда --> R269634919062
Mandrivnyk вне форума   Ответить с цитированием
Старый 31.10.2012, 14:03   #4
BDA
Модератор
Заслуженный модератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Адрес: RF Moscow
Сообщений: 5,408
Репутация: 2502

icq: 438888048
По умолчанию

Mandrivnyk, сетка 2х2 - по каждой стороне 2 узла, а не 2 связи.
По-моему, формула m*n-(m+n)+1, но не нашел сайта, где можно проверить.
__________________
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )

Последний раз редактировалось BDA; 31.10.2012 в 14:11.
BDA вне форума   Ответить с цитированием
Старый 31.10.2012, 17:05   #5
Abstraction
Профессионал
 
Аватар для Abstraction
 
Регистрация: 25.10.2011
Сообщений: 3,178
Репутация: 655
По умолчанию

Минимальный связный граф - дерево. Все деревья с одним множеством вершин имеют одно и то же число рёбер, равное (числу вершин)-1. Изначально граф имеет mn вершин и (2mn-m-n) рёбер. Так что сайт для проверки не нужен.
Abstraction вне форума   Ответить с цитированием
Старый 31.10.2012, 17:13   #6
BDA
Модератор
Заслуженный модератор
 
Аватар для BDA
 
Регистрация: 09.11.2010
Адрес: RF Moscow
Сообщений: 5,408
Репутация: 2502

icq: 438888048
По умолчанию

Abstraction, я рассуждал похоже, но все же привык проверять
(а проверять нужно потому, что я не опирался на теорию графов, хотя надо было, а просто на бумажке поприкидывал)
__________________
Пишите язык программирования - это форум программистов, а не экстрасенсов. (<= это подпись )

Последний раз редактировалось BDA; 31.10.2012 в 17:16.
BDA вне форума   Ответить с цитированием
Старый 19.06.2019, 12:28   #7
Ajarus
Новичок
 
Регистрация: 19.06.2019
Сообщений: 1
Репутация: 10
По умолчанию

#include <iostream>
using namespace std;
int main()
{
int a, b;
cin >> a >> b;
cout << (a - 1) * (b - 1);
return 0;
}
Ajarus вне форума   Ответить с цитированием
Ответ

Опции темы

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

BB коды Вкл.
Смайлы Вкл.
[IMG] код Вкл.
HTML код Выкл.

Быстрый переход

Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
задача по программированию VeNdJaKe Помощь студентам 0 24.04.2012 10:45
Задача по программированию arturjoshi Паскаль 0 26.01.2012 20:59
Задача по программированию. ALex25153 Помощь студентам 0 24.11.2011 21:33
задача по динамич. программированию Morsha Помощь студентам 4 02.12.2010 23:55


08:59.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2019, Jelsoft Enterprises Ltd.