Въпроси
от Съзтезателно програмиране
Ето една задача от usaco-то която не можах да измисля как да реша.
Това е първа задача за bronze devision на последното състезние.Въвежда се N и след него N подмножества на буквите {A,B,C,...,Y,Z}.Валидна пермутация <math>a_1,a_2,...,a_N</math> е такава последователност от букви че <math>a_i \in</math> i-тото подмножество и <math>a_i \ne a_j </math> за <math>i \ne j</math>. Като вход се дават две числа:1<=start<=end<=22 000 000 ,start-end<=2000.И от нас се иска да изведем валидните пермутации с лексикографски номера между start и end.
Все още не съм измислил решение със сложност по-малка от линейна,а за съжаление линейна е твърде бавно.
Ето условието на една на пръв поглед тривиална задача, която обаче все още не мога да реша, вече я мъчихме доста хора без успех. http://acm.timus.ru/problem.aspx?space=1&num=1220
Отговор: доколкото разбирам, проблема е големината на използваната памет? Ето го моето решение. Правиш си масив int a[100000], в които записваш самите стойности, които се вкарват в стековете. В масив c[1000] си записваш, за всеки стек, къде в масива a[] се намира последния вкаран елемент. Имаш още int24 b[100000], който е от 24-битови числа (изглежда, например така: struct int24 { char data[3]; } - сиреч 3 байта на число). В b[] си записваш един вид история: за всеки елемент a[i], който принадлежи на някой стек, пазиш индекса предходния елемент в стека (той се намира на a[b[i]]). Т.е. push операцията ти изглежда така:
push(st, val) {
static int i;
a[i] = val;
b[i] = c[st];
c[st] = i;
i++;
}
а pop():
pop (st) {
retval = a[c[st]];
c[st] = b[c[st]];
}
Паметта е, съответно 400к за a[], 300 за b[] и 4 за c[]. --Anrieff 23:28, 4 дек 2006 (EET)
Искам да попитам за една задача от OpenCup, става въпрос за задача D5 Segments, решението, което написах дава Run Time Error, но на компилатора, на който пиша - DevCpp 4.9.9.2 върви без проблеми. Освен това под VS2005 същата задача дава някаква грешка при оператора '<', ето го и сорса ми:
#include <fstream>
#include <set>
using namespace std;
ofstream fout("segments.out",ios::out);
ifstream fin("segments.in", ios::in);
struct segment
{
long x, y;
};
class Comp
{
public:
bool operator()(const segment a, const segment b) const
{ return a.x <= b.x && a.y >= b.y; }
};
typedef multiset<segment,Comp> Data;
bool cmp ( segment a, segment b )
{
return a.x <= b.x && a.y >= b.y;
}
int main()
{
Data data;
multiset <segment,Comp>::iterator it;
char ch;
segment t;
long br=0;
while ( true )
{
if ( ! (fin>>ch) ) break;
fin>>t.x>>t.y;
if ( ch=='+')
{
br=0;
for ( it=data.begin() ; it!=data.end(); it++ )
if ( cmp(t, *it ) ) br++;
fout<<br<<endl;
data.insert(t);
}
else
{
it = data.find ( t );
data.erase ( it );
}
}
fout.close();
return 0;
}
като имам още няколко аналогични на този варианти, които стигат до Run Time Error.
Грешката при компилация най-вероятно е от недодефинирани оператори.
bool operator()(const segment a, const segment b) е по-добре да стане bool operator()(const segment& a, const segment& b)
аналог за cmp.
Също така cmp и operator() не сортират по два критерия. например ако искаш да сортираш първо по x и ако са равни - по y, функцията за сравнение е различна от използваната при теб. В същност функцията за сравнение е сериозно сгрешена.. тя не трябва да връща true при равни елементи. Вярна е нещо от типа на:
if (a.x == b.x) return a.y < b.y; return a.x < b.x;
Vesu 11:50, 24 фев 2007 (EET)
Значи проблема при мен не е с компилацията, а е с Run Time Error, освен това аз не сортирам по x, а проверявам дали една отсечка е вътрешна за друга. Кода, който съм написал върви под DevCpp, а под VS след стариране дава Run Time Error, имам вариант с предефениран оператор '<', но при него проблема е същия.
Проблема,който имаш е на логическо ниво-както си дефинирал оператора две отсечки от типа абаб и от типа аабб са равни.Първото решение което написах самия аз беше подобно но възникваше проблем с това че е възможно едновременно а<б и б<а.Ако си спомням правилно vc2005 трябва да throw-ва incorrect operator < или нещо подобно.Дебъгни програмата и ще видиш кога се появява проблема...Аз лично смятам че не е възможно решение с такъв оператор за сравнение.
infomathic 12:55, 24 фев 2007 (EET)
Ами аз вече видях, че проблема е там, просто ми е интересно защо на VS, съответно и в системата се получава този проблем, докато на DevCPP, горепосочения код върви без грешка. Иначе мисля, че си прав, че затова не може да се подкара задачата. --Tabledott 13:06, 24 фев 2007 (EET)
Задачата тръгна, но трябва да се напише с vector. --Tabledott 14:11, 24 фев 2007 (EET)
Здравейте, искам да попитам за задачата от Open Cup H5 Weed ( от Гран При на Карелия) , условието изглежда лесно, но я мъчим доста време без успех, ето и основната част от кода ми:
for(i=0;i<n;i++)
for(j=0;j<m;j++)
{
br=0;
if(isInside(i-1,j) && a[i-1][j]=='X') br++;
if(isInside(i+1,j) && a[i+1][j]=='X') br++;
if(isInside(i,j-1) && a[i][j-1]=='X') br++;
if(isInside(i,j+1) && a[i][j+1]=='X') br++;
if(br>=2) a[i][j]='X';
}
for(i=n-1;i>=0;i--)
for(j=m-1;j>=0;j--)
{
br=0;
if(isInside(i-1,j) && a[i-1][j]=='X') br++;
if(isInside(i+1,j) && a[i+1][j]=='X') br++;
if(isInside(i,j-1) && a[i][j-1]=='X') br++;
if(isInside(i,j+1) && a[i][j+1]=='X') br++;
if(br>=2) a[i][j]='X';
}
for(i=0;i<n;i++)
for(j=m-1;j>=0;j--)
{
br=0;
if(isInside(i-1,j) && a[i-1][j]=='X') br++;
if(isInside(i+1,j) && a[i+1][j]=='X') br++;
if(isInside(i,j-1) && a[i][j-1]=='X') br++;
if(isInside(i,j+1) && a[i][j+1]=='X') br++;
if(br>=2) a[i][j]='X';
}
for(i=n-1;i>=0;i--)
for(j=0;j<m;j++)
{
br=0;
if(isInside(i-1,j) && a[i-1][j]=='X') br++;
if(isInside(i+1,j) && a[i+1][j]=='X') br++;
if(isInside(i,j-1) && a[i][j-1]=='X') br++;
if(isInside(i,j+1) && a[i][j+1]=='X') br++;
if(br>=2) a[i][j]='X';
}
Засега сме до WA12 --Tabledott 11:38, 25 фев 2007 (EET)
Една задача не ми дава мира от доста време и ще съм благодарен ако дадете идея как се решава: Дадени са N(N<=50) големи дъски и дължните на M(M<=1023)малки дъски.Всяка голяма дъска може да бъде разрязана на части и целта ни е след като разрежем големите дъски да получим дължините на максимален брой малки дъски.Дължините на малките дъски са не непременно различни и са до 128.Трябва да се изведе само намереният максимален брой,но не и разрязването.--infomathic 13:34, 25 май 2007 (EEST)
Гореописаната задача много ми напомня на една от USACO (абе да си го кажем, че е едно към едно). Решението е brute force с много оптимизации. Едно от нещата, които силно ускоряват решението, е как подреждаш дъските - с кои почваш, кои от кои режеш и тн. Цялостното оптимизиране няма да го коментирам тук (или евентуално по-късно), предимно защото така задачата ще си изгуби смисъла (да мислиш оптимизации), и най-вече защото не го помня =) Като гледам кога е писан въпроса, май много отдавна си я решил, но все пак... --espr1t 12:32, 24. септември 2007 (ЕЕТ)
