Форум программистов
 

Восстановите пароль или Зарегистрируйтесь на форуме, о проблемах и с заказом рекламы пишите сюда - alarforum@yandex.ru, проверяйте папку спам!

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

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

Купить рекламу на форуме - 42 тыс руб за месяц

Ответ
 
Опции темы Поиск в этой теме
Старый 20.03.2014, 16:59   #1
kostan3
- Дорогой, а ты ку
Форумчанин
 
Регистрация: 06.10.2012
Сообщений: 184
По умолчанию ЗАДАЧА №307 Атлеты

есть задача ЗАДАЧА 307
написал довольно длинный и тупой(но рабочий код)
Код:
#include <vector>
#include <fstream>
#include <cassert>
using namespace std;
int main() {

ifstream is("input.txt");
ofstream os("output.txt");
int N, M, P; is >> N >> M >> P;
vector<vector<bool> > m(N, vector<bool>(M));
for (int i = 0; i < P; ++i) {
int r, c; is >> r >> c;
m[r - 1][c - 1] = true;
}
vector<vector<int> > dp(N, vector<int>(M));
int ans = 0;
for (int i = N - 1; i >= 0; --i) {
for (int j = 0; j < M; ++j) {
if (i < N - 1 && j > 0 && m[i][j])
ans += dp[i + 1][j - 1];
int v = 0;
if (m[i][j])
v += 1;
if (i < N - 1)
v += dp[i + 1][j];
if (j > 0)
v += dp[i][j - 1];
if (i < N - 1 && j > 0)
v -= dp[i + 1][j - 1];
dp[i][j] = v;
}
}
assert(dp[0][M - 1] == P);
os << ans;
}
Размер кода: 517
у кого нибуть есть идеи насчёт более короткого и понятного кода?
kostan3 вне форума Ответить с цитированием
Старый 21.03.2014, 14:11   #2
Somebody
Участник клуба
 
Регистрация: 08.10.2007
Сообщений: 1,185
По умолчанию

Цитата:
Сообщение от kostan3 Посмотреть сообщение
написал довольно длинный и тупой(но рабочий код)
Глядя на assert и твои предыдущие темы, сильно сомневаюсь, что этот код написал ты.
Цитата:
Сообщение от kostan3 Посмотреть сообщение
у кого нибуть есть идеи насчёт более короткого и понятного кода?
Насчёт более понятного есть:
Код:
#include <fstream>

using namespace std;

template<class R, class T>
R Sum2D(T a, size_t yb, size_t ye, size_t xb, size_t xe)
{
	R result = R();
	for (size_t y = yb; y < ye; y++)
		for (size_t x = xb; x < xe; x++)
			result += a[y][x];
	return result;
}

int main()
{
	ifstream fin("input.txt");
	unsigned n, m, p;
	fin >> n >> m >> p;

	static bool a[251][251];
	unsigned nSurprises = 0;
	for (unsigned i = 0; i < p; i++)
	{
		unsigned lvlS, lvlE;
		fin >> lvlS >> lvlE;
		nSurprises +=
			Sum2D<unsigned>(a, 1, lvlS, lvlE + 1, m + 1) +
			Sum2D<unsigned>(a, lvlS + 1, n + 1, 1, lvlE);
		a[lvlS][lvlE] = true;
	}

	ofstream fout("output.txt");
	fout << nSurprises;
}
Насчёт более короткого - тоже есть; но тебе вместо этого лучше прочитать, например, про дерево Фенвика...
Somebody вне форума Ответить с цитированием
Старый 21.03.2014, 20:22   #3
kostan3
- Дорогой, а ты ку
Форумчанин
 
Регистрация: 06.10.2012
Сообщений: 184
По умолчанию

Цитата:
Сообщение от Somebody Посмотреть сообщение
Глядя на assert и твои предыдущие темы, сильно сомневаюсь, что этот код написал ты.

Насчёт более понятного есть:
Код:
#include <fstream>

using namespace std;

template<class R, class T>
R Sum2D(T a, size_t yb, size_t ye, size_t xb, size_t xe)
{
	R result = R();
	for (size_t y = yb; y < ye; y++)
		for (size_t x = xb; x < xe; x++)
			result += a[y][x];
	return result;
}

int main()
{
	ifstream fin("input.txt");
	unsigned n, m, p;
	fin >> n >> m >> p;

	static bool a[251][251];
	unsigned nSurprises = 0;
	for (unsigned i = 0; i < p; i++)
	{
		unsigned lvlS, lvlE;
		fin >> lvlS >> lvlE;
		nSurprises +=
			Sum2D<unsigned>(a, 1, lvlS, lvlE + 1, m + 1) +
			Sum2D<unsigned>(a, lvlS + 1, n + 1, 1, lvlE);
		a[lvlS][lvlE] = true;
	}

	ofstream fout("output.txt");
	fout << nSurprises;
}
Насчёт более короткого - тоже есть; но тебе вместо этого лучше прочитать, например, про дерево Фенвика...
Хм... очередные 86 символов не мног почесал голову и пришло в голову что всё таки это пример того когда программа подстраивается под тесты
этим обьясняется всё. (ннужно обращятся к админисратору)
kostan3 вне форума Ответить с цитированием
Старый 21.03.2014, 23:43   #4
kostan3
- Дорогой, а ты ку
Форумчанин
 
Регистрация: 06.10.2012
Сообщений: 184
По умолчанию

Код:
#include <fstream>
template<class R, class T>
R D(T a, size_t yb, size_t ye, size_t xb, size_t xe)
{
	R r = R();
	for (size_t y = yb; y < ye; y++)
		for (size_t x = xb; x < xe; x++)
			r += a[y][x];
	return r;
}
main(){
	std::fstream f("input.txt"),o("output.txt",2);
	__int64 n, m, p;
	f >> n >> m >> p;

	static bool a[251][251];
	__int64 S = 0,i;
	for (i = 0; i < p; i++)
	{
		__int64 l, lv;
		f>> l >> lv;
		S +=D<unsigned>(a, 1, l, lv+ 1, m + 1) +D<unsigned>(a, l + 1, n + 1, 1, lv);
		a[l][lv] = true;
	}
	o<< S;
}
412
/////////////////////////////////////////////////////////////////////////////////////
Код:
#include <fstream>
template<class R, class T>
R D(T a, size_t yb, size_t ye, size_t xb, size_t xe)
{
	R r = R();
	for (size_t y = yb; y < ye; y++)
		for (size_t x = xb; x < xe; x++)
			r += a[y][x];
	return r;
}
main(){
	std::fstream f("input.txt"),o("output.txt",2);
	__int64 n, m, p;
	f >> n >> m >> p;

	static bool a[251][251];
	__int64 S = 0,i;
	for (i = 0; i < p; i++)
	{
		__int64 l, lv;
		f>> l >> lv;
		S +=D<__int64>(a, 1, l, lv+ 1, m + 1) +D<__int64>(a, l + 1, n + 1, 1, lv);
		a[l][lv] = true;
	}
	o<< S;
}
410
//////////////////////////////////////////////////////////////////
Код:
#include <fstream>
template<class R, class T>
R D(T a, size_t yb, size_t ye, size_t xb, size_t xe)
{
	R r = R();
	for (size_t y = yb; y < ye; y++)
		for (size_t x = xb; x < xe; x++)
			r += a[y][x];
	return r;
}
main(){
	std::fstream f("input.txt"),o("output.txt",2);
	__int64 n, m, p,S=0,i,l,lv;
	f >> n >> m >> p;
	static bool a[251][251];
	for (i = 0; i < p; i++){
		f>> l >> lv;
		S +=D<__int64>(a, 1, l, lv+ 1, m + 1) +D<__int64>(a, l + 1, n + 1, 1, lv);
		a[l][lv] = true;
	}
	o<< S;
}
392

Последний раз редактировалось kostan3; 21.03.2014 в 23:51.
kostan3 вне форума Ответить с цитированием
Старый 21.03.2014, 23:52   #5
kostan3
- Дорогой, а ты ку
Форумчанин
 
Регистрация: 06.10.2012
Сообщений: 184
По умолчанию

на сегодня хватит кто ещё ужмет заранее спасибо
kostan3 вне форума Ответить с цитированием
Старый 21.03.2014, 23:56   #6
kostan3
- Дорогой, а ты ку
Форумчанин
 
Регистрация: 06.10.2012
Сообщений: 184
По умолчанию

Насчёт более короткого - тоже есть; но тебе вместо этого лучше прочитать, например, про дерево Фенвика...



Ну прочитал но в этом смысла не вижу код сам по себе не сократиться
kostan3 вне форума Ответить с цитированием
Ответ


Купить рекламу на форуме - 42 тыс руб за месяц

Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
задача на зачёт. проблема Задача на нобелевскую премию! Sabotage5 Паскаль, Turbo Pascal, PascalABC.NET 2 18.03.2013 15:18
Задача по подсчёту статистики использования букв. Другая задача - по длинной арифметике Pascal ABC kimberly Паскаль, Turbo Pascal, PascalABC.NET 3 24.12.2012 17:03
Задача на оптимальный расчет маршрута (задача в презентации) в табличном процессоре Excel Toofed Помощь студентам 0 30.11.2011 01:12
Задача минимизации дисбаланса на линии сборки (задача минимакса) LenZab Microsoft Office Excel 13 13.03.2011 22:51