Премини към съдържанието

Препоръчан отговор


Здравейте! Тези дни реших да реша някои от задачите, които се се паднали на националните олимпиади по програмиране. Проблемът ми е, че за повечето успявам да измисля алгоритъм, но не достатъчно оптимален. Твърде наивен. Например днес се мъча с ето тази задача, която е за 12 клас:
 

Задача A2. САМОТНА ПЕЙКА

Пейката в метрото има n места, номерирани с числата от 1 до n. В началото пейката е празна – всичките n места са свободни. Последователно, един по един, през входа на метрото влизат пътници. Всеки влязъл човек сяда в центъра на първата максимална последователност от свободни места. В случай, че максималната последователност от свободни места съдържа четен брой места, човекът сяда на мястото с по-малък номер измежду двете централни места на последователността.

Например, ако пейката има n = 6 места, първият човек сяда на място с номер 3, защото има единствена максимална последователност от свободни места – от 1 до 6, която съдържа четен брой места, и 3 е мястото с по-малък номер измежду двете централни места (3 и 4) на тази последователност. За втория човек има две последователности от свободни места – от място 1 до място 2 и от място 4 до място 6. Последователността от място 4 до място 6 е максимална, съдържаща 3 места, и вторият човек сяда в центъра  – място 5. Третият човек сяда на място с номер 1 – „централното” за последователността от свободни места от първо до второ, четвъртият човек – на място 2, петият – на място 4 и шестият – на място 6.

Напишете програма bench, която определя мястото, на което сяда определен човек, и кой човек сяда на предварително зададено място.

Вход

От стандартният вход се въвежда един ред с три цели чиста: n i p, разделени с интервал, където:

  • n е общият брой места на пейката;
  • i е номер на човек, влязъл в метрото (първият влязъл има номер 1);
  • p представлява номер на място от пейката.

 Изход

Програмата трябва да извежда на стандартния изход един ред с две цели числа q и j, разделени с интервал, за които е изпълнено, че:

  • i-тият човек, влязъл в метрото сяда на място с номер q и
  • j-тият човек, влязъл в метрото сяда на място с номер p.

Ограничения

1 ≤ i, pn ≤ 1016

В 20% от тестовете е изпълнено n ≤ 10000.

В други 30% от тестовете, n = 2k-1, където k>0 е цяло число.

Пример 1   Пример 2

Вход   Вход

6 1 5   10 2 6

Изход   Изход

3 2                                                 8 5

 

 

Накратко имам една пейка в метрото. Всеки нов пътник сяда точно в средата на най-дългото място от свободни седалки. И така докато всички седалки бъдат запълнени. Трябва да намеря мястото, на което ще седнe даден пореден пътник и кой поред пътник ще седне на дадено място.

 

Алгоритъма, който аз успях да напиша е твърде елементарен. При всяко влизане на нов пътник аз обхождам масива с n седалки и търся най-дългата свободна редица. След това маркирам средната седалка на тази редица като използвана и така се получават две отделни редици. Но този метод е твърде бавен. Както пише в условието n може да бъде до 10^16, а аз не мога да направя толкова голям масив. А и да успея ще ми трябва доста време за да го обходя.

Чуда се дали знаете за някаква техника, която да ми помогне. Може би трябва да се използва някаква формула? И също ще се радвам, ако можете да ми кажете как да започна да измислям добри алгоритми.. Ако можете да ми препоръчате някаква книга, която да развива мисленето на човека или нещо подобно? Защото няма как да стана добър програмист без да прочета нещо от някъде нали :D В книгите от които учих C++ бяха дадени само основни примери и задачи, но не и по-трудни проблеми като този. :)

Поздрави!

 

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Чуда се дали знаете за някаква техника, която да ми помогне. Може би трябва да се използва някаква формула? И също ще се радвам, ако можете да ми кажете как да започна да измислям добри алгоритми.. Ако можете да ми препоръчате някаква книга, която да развива мисленето на човека или нещо подобно? Защото няма как да стана добър програмист без да прочета нещо от някъде нали :D В книгите от които учих C++ бяха дадени само основни примери и задачи, но не и по-трудни проблеми като този. :)

Мога да добавя още едно нещо към препоръките на soundtracker, които са много добри. И това е, че добър, във каквото и да е, се става със знания и опит. Ако целта са ти алгоритми и задачи, освен четенето на теория, бих ти препоръчал да си намериш решени задачи и много хубаво да ги разбереш, да осмислиш мотивите за избор на решението и самата му реализация. Да го кажа по такъв начин: ако знаеш решенията на 50 различни проблема, като дойде 51ият, в най-лошия случай ще знаеш 50 възможни начина, които директно да отхвърлиш. Но по-вероятно е, поне нещо от тях да те насочи към решението.

Относно задачата.

Мисля, че и двамата имате една и съща солидна грешка в подхода. При положение, че имате директно и еднозначно дефинирана редица и то само от 2 числа - големината на пейката и номера на човека или съответно седалката, вие реално знаете, къде е той. Няма нужда да го търсите, независимо с колко сложен или ефективен метод. Е, може би не е толкова очевидно, но... Не мисля да решавам задачата, само ще продължа подсказката от условието.

вземаме 30те % в които n = 2k -1,  Това не е случайна стойност. Всъщност това е best-case на задачата. Тоест:

  • проверката дали число е от вида 2k -1 е елементарна
  • първият седнал ще раздели пейката на две равни половини и то забележете как:
  • всяка половина ще е (2k -1 - 1) / 2 = (2k - 2) / 2 = 2k-1 - 1 - т.е число от същия вид.
  • тоест първият човек ще я раздели на 2, първите 3ма на 4, първите 7 на 8 и т.н равни части. Не е ли прекрасно?
  • намираме колко е броят на хората, които ще разделят пейката по такъв начин преди да седне нашия човек: това е най-голямата стойност 2m -1 < i, Може с побитови операции или логаритъм с основа 2 - избирате си.
  • към момента след сядане на 2m -1вия човек, на пейката има 2m празни места, всяко от по (n - 2m -1) / 2m седалки.
  • Е те са еднакви, значи просто всеки следващ ще сяда в средата на първата свободна, по ред.
  • значи нашия човек ще седне в средата на (i - 2m -1) % 2m -тото празно място (% -  остатък от деленето).
  • Това дотук се разписва в формула на 1 ред.

От мен толкова. :)

  • Харесва ми 4

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

За да продължа обаче по-нататък с помощта, трябва да ми отговорите на следните въпроси:

1) Знаете ли какво са Binary Tree и Heap ? Можете ли да боравите с тях и знаете ли как ?

2) Знаете ли какво е Balanced Tree и каква е идеята, заложено в него ?

3) Знаете ли какво е B-Tree - какво представлява и с какво се различава от горното ?

4) Знаете ли какво представлява алгоритъма Alpha-Beta Pruning ? Той ще е необходим за оптимизирането на работата на алгоритъма Ви.

Мерси за предложените алгоритми. 1) и 2) знам какво представляват, но за 3) и 4) не мога да кажа същото. Ще ги разгледам по-подробно :)

 

 

Други, които мога да дам като пример са тези две:

Основи на алгоритмите

Алгоритми на С

За съжаление втората книга не мога да я намеря в наличност. Първата съм я разглеждал и аз, но ми се стори, че по-голямата част от кода е на Pascal и може би малко по-трудно ще осмисля съдържанието. Може би някоя книга, която използва C/C++, C# или Java ще е по-добър избор :)

 

 

@flare, мерси много за предложената формула. Ще се опитам да я реализирам. А откъде мога да намеря решени задачи? Може би можете да ми препоръчате някоя книга или сайт?  :)

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Коментар-допълнение в телеграфен стил:

 

Първата книга е много добра и не отстъпва на чуждестранните такива. Третата я има на английски, ако ви устройва -- Algorithms in C. Акцентира повече върху имплементацията, отколкото върху теорията и анализа. Introduction to Algorithms  е класическа.

 

Освен това, курсовете на Масачузетския институт може да са от полза: http://ocw.mit.edu

Редактирано от arcane (преглед на промените)

  • Харесва ми 1

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

@flare, мерси много за предложената формула. Ще се опитам да я реализирам.

Че тя е реализирана. По скоро помисли, как да я разшириш за случаите, когато n != 2k -1...

 

А откъде мога да намеря решени задачи?

Google. Редактирано от flare (преглед на промените)

Сподели този отговор


Линк към този отговор
Сподели в други сайтове

Регистрирайте се или влезете в профила си за да коментирате

Трябва да имате регистрация за да може да коментирате това

Регистрирайте се

Създайте нова регистрация в нашия форум. Лесно е!

Нова регистрация

Вход

Имате регистрация? Влезте от тук.

Вход

  • Горещи теми в момента

  • Подобни теми

    • от eXXcal
      #include <iostream> #include <fstream> #include <map> #include <ctime> #include <string> #include <stdio.h> #include <stdlib.h> #include <vector> #include <list> #include <iterator> #include <algorithm> #include <utility> #include <time.h> using namespace std; class CPerson { private: string name; string EGN; public: CPerson() { name=" "; EGN=" "; } CPerson(const string n, const string e) { name=n; EGN=e; } string getname()const { return name; } string getEGN()const { return EGN; } void setname(const string n) { name=n; } void setEGN(const string e) { EGN=e; } virtual void print() = 0; //1.1 int getAge() const //1.2 { int age; time_t currentTime; struct tm * ltm; time( &currentTime ); ltm= localtime( &currentTime ); int year = atoi(getEGN().substr(0, 2).c_str()); int month = atoi(getEGN().substr(2, 2).c_str()); int day = atoi(getEGN().substr(4, 2).c_str()); int cyear = 1900 + ltm->tm_year; int cmonth = 1 + ltm->tm_mon; int cday = 1 + ltm->tm_mday; age = cyear - (year + 1900); if (cmonth < month) age--; if (cmonth == month && cday < day) age--; return age; } }; class CStudent: public CPerson { private: string FN; map<int, int> st_tests; public: CStudent() { FN=" "; } CStudent(const string n) { FN=n; } CStudent(const string o, const string p, const string n):CPerson(o,p) { FN=n; } void setFN(const string n) { FN=n; } void setst_tests(map<int, int> m) { st_tests=m; } string getFN() const { return FN; } bool operator () (CStudent a, CStudent b) const { return a.average() < b.average(); } map<int, int> getst_tests() { return st_tests; } void print() { cout<<"Ime: "<<getname()<<endl; cout<<"EGN: "<<getEGN()<<endl; cout<<"FN: "<<getFN()<<endl; map<int, int>::iterator it=st_tests.begin(); while(it!=st_tests.end()) { cout<<it->first<<" "<<it->second<<endl; it++; } } void add_st_tests(int a, int b) { map<int, int>::iterator it=st_tests.begin(); while(it!=st_tests.end()) { st_tests.insert(pair<int,int>(a,b)); } } double average() //2.1 { double sum=0; map<int, int>::iterator it=st_tests.begin(); for (it=st_tests.begin();it!=st_tests.end();it++) sum+=it->second; if(st_tests.size()!=0) return sum/st_tests.size(); return -1; } int search(const int a) //2.2 { return st_tests.find(a)->second; } }; class CGroup { private: string spec; int kurs; int grupa; vector<CStudent> students; public: string getspec() const { return spec; } int getkurs() const { return kurs; } int getgrupa() const { return grupa; } vector<CStudent> getstudents() { return students; } void setstudents(vector<CStudent> a) { students=a; } void setspec(const string n) { spec=n; } void setkurs(const int n) { kurs=n; } void setgrupa(const int n) { grupa=n; } CGroup(const string s, const int k, const int g) { spec=s; kurs=k; grupa=g; } void addstudent(CStudent &a) { students.push_back(a); } /* int ReadFile() //3.1 { ifstream st; st.open("students.txt",ios::in); if(!st) { cout<<"Cannot open students.txt or file does not exist."<<endl; return 0; } string a, b, c; int d, e, i=0; if (st.is_open()) { do { st >> a >> b >> c; students[i].setname(a); students[i].setEGN(b); students[i].setFN(c); do { st >> d >> e; students[i].add_st_tests(d,e); }while(st.peek() != '\n' || st.peek() != '\r'); i++; }while(!st.eof()); } st.close(); }*/ double averagetest(int a) //3.2 { double sum=0; int br=0; vector<CStudent>::iterator itt; for (itt=students.begin();itt!=students.end();itt++) { map<int, int>::iterator it=(*itt).getst_tests().find(a); while(itt!=students.end()) sum+=it->second; br++; } cout<<sum/br; return sum/br; } list<CStudent> averageparam(const int a, const int b) //3.3 { list<CStudent> l; int i=0; vector<CStudent>::iterator itt=students.begin(); for (itt=students.begin();itt!=students.end();itt++) { if((*itt).average() >= a && (*itt).average() <= b) l.push_back(*itt); i++; } cout<<"List ot studenti sus sreden broi tochki mejdu "<<a<<" - "<<b<<endl; list<CStudent>::iterator it=l.begin(); for (it=l.begin();it!=l.end();it++) (*it).print(); return l; } int averageabove(const int a) //3.4 { int br=0; vector<CStudent>::iterator itt=students.begin(); for (itt=students.begin();itt!=students.end();itt++) if((*itt).average() > a) br++; cout<<"Broi studenti sus sreden broi tochki nad "<<a<<": "<<br<<endl; return br; } void averageage(const int a) //3.5 { cout<<"Sreden uspeh na "<<a<<" godishni studenti."<<endl; vector<CStudent>::iterator itt=students.begin(); for (itt=students.begin();itt!=students.end();itt++) { int b=(*itt).getAge(); if(a == b) cout<<(*itt).getname()<<" "<<(*itt).average()<<endl; } } void beststudent() //3.6 { cout<<"Student s nai-visoka uspevaemost."<<endl; CStudent temp; vector<CStudent>::iterator itt=students.begin(); for (itt=students.begin();itt!=students.end();itt++) if ((*itt).average() > temp.average()) temp = (*itt); temp.print(); } void sortaverage() //3.7 { sort(students.begin(),students.end(),CStudent()); } void sortasc() //3.8 { } void averageage() //3.9 { } }; int main() { CStudent p1("Ivan","9711156070","61360140"); CStudent p2("Petar","9703041020","61360127"); CStudent p3("Mihail","9708032540","61360134"); p1.add_st_tests(1,55); p1.add_st_tests(2,80); p1.add_st_tests(3,69); p2.add_st_tests(1,98); p2.add_st_tests(2,25); p2.add_st_tests(3,56); p3.add_st_tests(1,32); p3.add_st_tests(2,87); p3.add_st_tests(3,57); CGroup g1 ("SIT",1,1); g1.addstudent(p1); g1.addstudent(p2); g1.addstudent(p3); g1.averagetest(2); }  
      Имам малък проблем с програмата .Успешно се  Build -ва , не изкарва грешки .А като се Run - не ми изписва map set iterator not dereferencable  също така и standard c++ libraries out of range && 0 .  Може ли някой да помогне ? Благодаря предварително
       
       Ето го и условието :
       
      1. Да се дефинира абстрактен клас CPerson, с член данни име и ЕГН, освен необходимите методи, да се напишат и следните:
      абстрактен метод за печат
       
      метод, който връща възрастта на човека на база на ЕГН-то
       
      2. Да се дефинира клас CStudent наследник на CPerson, съхраняващ информацията за факултетен номер на студента и контейнер съхраняващ резултатите на студента от различни тестове (код на теста и получения брой точки, напр. (map<unsigned, unsigned> st_tests). Освен необходимите конструктори, методи и оператори (сред които е функцията за печат) да се добавят:
       
      метод, който връща средния брой точки получени от студента
       
      метод, който връща брой точки по код на тест, подаден като параметър
       
      3. Да се дефинира клас група студенти CGroup, съхраняващ информацията за специалност, курс, група и контейнер от студентите в нея (напр. vector<CStudent>). Освен необходимите методи, да се реализират и следните член функции:
       
      да се дефинира конструктор с параметър име на файл, съдържащ необходимата информация за запълване на контейнера
       
      изчислява и връща средния брой точки за тест, подаден като параметър
       
      връща списък от студенти (list<CStudent*>) със среден брой точки принадлежащи на интервал [a;b] (a,b - параметри)
       
      изчислява и връща броя на студентите със среден брой точки, по-голям от числото подадено като параметър
       
      изчислява и връща средния брой точки на студентите на възраст, подадена като параметър
       
      намира студента с най-висока успеваемост на тестовете
       
      сортира студентите по среден брой точки
       
      сортира тестовете в низходящ ред по среден брой точки, получени от студентите в групата
       
      изчислява средната възраст на студентите от групата
       
      4. Да се създадат няколко обекта от класа CGroup и се демонстрира работоспособността на методите му като се направят различни справки и съпоставки между тях (напр. коя специалност има по-висока средна успеваемост на тестовете, коя по-висока средна възраст, коя повече студенти получили точки над зададена стойност). Да има обработка на изключения на необходимите места.
    • от barry
      Здравейте,
      имам един масив от цели числа
      int a[] = {1, 2, 3, 4, 5, 6}; а израза
      (1 + 3)[a] - a[0] + (a + 1)[2] е равен на 8. По принцип i-тия елемент на масива е
      a[i] или *(a+i) но не разбирам другите две конструкции. Може ли някой да обясни как се изчисляват те?
      Благодаря предварително.
    • от martin stoqnov
      Здравейте!от скоро се занимавам с онлайн симулатор на ардуино "Tinkercad" ,но имам някой проблеми с логическото изпълнение на кодовете.
      ето и част от първият 
       if (digitalRead(Zaqvka2) == HIGH)
      {
      switch (i){
      case 0:
      digitalWrite(Up,HIGH);
      digitalWrite(Fast,HIGH);}
      }                                                     тук проблема идва от това, че без да е изпълнено условието за If (zaqvka da e HIGH)   се изпълнява оператора switch ?!?
      друг проблем който срещнах е  ,че когато не е изпълнено условие за if  не се изпълнява else частта. 
      Ще се радвам ако някой сподели дали е имал проблем с средата и да каже този код дали върви нормално в реални условия с контролер и др-те физически елементи.
      Започвам да си мисля, че средата е боза ?!?
       

    • от Pepi Litkov
      Здравейте колеги ! Спешно ми трябва една задача написана на C++ за понеделник . Много ми е труден този език и не мога да измисля никакъв код ..Ако е възможно погледнете условието : Да се напише програма,която за дадено естествено число N да намира такава тройка числа a,b,c (естествени и c<N), за която a2+b2=c2 (двойките са степен).. Благодаря ви много предварително ! 
  • Разглеждащи в момента   0 потребители

    Няма регистрирани потребители разглеждащи тази страница.

  • Дарение

×

Информация

Поставихме бисквитки на устройството ви за най-добро потребителско изживяване. Можете да промените настройките си за бисквитки, или в противен случай приемаме, че сте съгласни с нашите условия за ползване.