Ĺadny brzuch
Wzorem lat ubiegłych (06, 07) temat musi być :D
13 maja rusza największy polski otwarty konkurs programistyczny. Rejestracja i sesja próbna trwa pod adresem: http://konkurs.adb.pl/ - do wygrania 256 koszulek i parę laptopów.
Kto bierze udział i na co się nastawiacie? Ja w ubiegłym roku obiecałem sobie, że w tym zgarnę koszulkę - i jeśli tylko wystarczy czasu, to tak też zrobię. :D
@down - fernandez, wiedziałem, że będziesz pierwszym, który odpowie :P
Użytkownik bryn edytował ten post 05 maj 2008, 20:59
biore udzial, ale nie oczekuje zbyt wiele - mam za duzo projektow na glowie na uczelni :/
zycze powodzenia wszystkim :)
btw - bryn, wiedzialem ze predzej czy pozniej zalozysz ten temat :P
Użytkownik fernandez edytował ten post 05 maj 2008, 20:51
no te próbne jest banalne :)
w czym można pisać te programy?
pascal, c, c++, java
pascal, c/c++, java - w regulaminie masz to napisane ;)
Tak, to próbne było banalne nawet dla mnie ^^
Zobaczymy ile pkt. dostanę po testach ;]
ja oczywiście też biorę udział, i też koszulka by się przydała(choćby na w-f:P) no a próbne to rzeczywiście banalne, zresztą jak co roku, chociaż poprzednie próbne(o samolocie) było chyba łatwiejsze
A wszystkie zadania można zrobić w programowania strukturalnym ?
@down
chodziło mi raczej czy wszystkie zadnia dałoby się zrobić strukturalnie
Użytkownik webmasterscool edytował ten post 06 maj 2008, 17:51
tak, mozna - czasem jest to wrecz wskazane..
akurat w czasie matury z matmy i fizy :/
@down - fernandez, wiedziałem, że będziesz pierwszym, który odpowie tongue.gif
btw - bryn, wiedzialem ze predzej czy pozniej zalozysz ten temat tongue.gif
A ja gdybym się nad tym zastanawiał, to wiedziałbym to i to.
Sartuję po raz pierwszy (a jestem już w II LO), ale nie oczekuję zbyt wiele.
poniewaz runda sie zakonczyla to chialbym jak sobie pordzialiscie z zadaniem ?? :)
tzn. po prostu wklejcie kod ;)
moj wyglada tak :]
1: #include <iostream> 2: main() { 3: std::ios::sync_with_stdio( 0 ); 4: std::string str; 5: std::getline( std::cin, str ); 6: for( int i=0; i<str.size(); i++ ) { 7: switch( str[i] ) { 8: case'`': case'1': case'2': case'3': case'4': case'5': case'6': case'7': case '8': case'9': case'0': case'-': case'=': std::cout << "1"; break; 9: case'Q': case'W': case'E': case'R': case'T': case'Y': case'U': case'I': case 'O': case'P': case'[': case']': case'\\': std::cout << "2"; break; 10: case'A': case'S': case'D': case'F': case'G': case'H': case'J': case'K': case 'L': case';': case'\'': std::cout << "3"; break; 11: case'Z': case'X': case'C': case'V': case'B': case'N': case'M': case',': case '.': case'/': std::cout << "4"; break; 12: case' ': std::cout << "5"; break; 13: default: return 0; 14: } 15: } 16: } 17:
jak sie pojawia czasy to tez byscie mogli zamiescic ;)
moje czasy:
0 OK 0.00s/1.00s 0/0 1 OK 0.00s/1.00s 1/1 2 OK 0.00s/1.00s 1/1 3 OK 0.00s/1.00s 1/1 4 OK 0.00s/1.00s 1/1 5 OK 0.00s/1.00s 1/1 6 OK 0.01s/1.00s 1/1 7 OK 0.01s/1.00s 1/1 8 OK 0.02s/1.00s 1/1 9 OK 0.07s/2.00s 1/1 10 OK 0.07s/2.00s 1/1
edit@down:
potem sobie napisalem program "znak po znaku" (dalej z iostream) i niestety bylo wolniej, minimalnie ale wolniej :P
Użytkownik fernandez edytował ten post 11 maj 2008, 09:20
moj kod bardzo podobny, tylko że na stdio, i "znak-po-znaku":
#include <cstdio> int main() { char c; for(;;) { scanf("%c",&c); switch Ĺ { case '`': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': case '0': case '-': case '=': printf("1"); break; case 'Q': case 'W': case 'E': case 'R': case 'T': case 'Y': case 'U': case 'I': case 'O': case 'P': case '[': case ']': case '\\': printf("2"); break; case 'A': case 'S': case 'D': case 'F': case 'G': case 'H': case 'J': case 'K': case 'L': case ';': case '\'': printf("3"); break; case 'Z': case 'X': case 'C': case 'V': case 'B': case 'N': case 'M': case ',': case '.': case '/': printf("4"); break; case ' ': printf("5"); break; case '\n': return 0; } } return 0; }
edit:
0 OK 0.00s/1.00s 0/0 1 OK 0.00s/1.00s 1/1 2 OK 0.00s/1.00s 1/1 3 OK 0.00s/1.00s 1/1 4 OK 0.00s/1.00s 1/1 5 OK 0.01s/1.00s 1/1 6 OK 0.00s/1.00s 1/1 7 OK 0.00s/1.00s 1/1 8 OK 0.01s/1.00s 1/1 9 OK 0.05s/2.00s 1/1 10 OK 0.06s/2.00s 1/1
Użytkownik bryn edytował ten post 11 maj 2008, 09:52
nie znam się za bardzo na c++, ale czy uwzględniliście wciśnięcie SHIFTa?
przeczytaj tresc zadania.. :>
A ja, nie przejmując się zbytnio optymalizacją, wpisałem kolejne rzędy liter do 4 tablic i w pętlach for dla każdego znaku uprzednio zapisanego getline() w stringu sprawdzałem, do której tablicy dany znak należy. ;]
Potem stwierdziłem, że dużo szybciej byłoby napisać to jak Wy - switch'em sprawdzać kolejne znaki, ale już mi się nie chciało, bo to i tak tylko próbne zadanie.
Też biorę udział w tym konkursie. Btw to pierwszy konkurs programistyczny w ktorym biorę udział, więc nie liczę na za wiele, ale koszulke to bym mimo wszystko chciał zgarnąć :D Btw ile mniej wiecej trza miec zrobionych programów kategorii B by sie zalapac (tj. jak to było w poprzednich latach?).
A oto moje koty:
#include<cstdio> #include<iostream> using namespace std; string a, litery[] = {"QWERTYUIOP[]", "ASDFGHJKL;\'", "ZXCVBNM,./"}; main() { getline(cin, a); for(int i = 0; i < a.size(); i++) { if(isdigit(a[i]) || a[i] == '~' || a[i] == '-' || a[i] == '=') printf("%d", 1); else if(isspace(a[i])) printf("%d", 5); else if(litery[0].find(a[i]) != -1) printf("%d", 2); else if(litery[1].find(a[i]) != -1) printf("%d", 3); else if(litery[2].find(a[i]) != -1) printf("%d", 4); } printf("\n"); return 0; }
Btw ile mniej wiecej trza miec zrobionych programów kategorii B by sie zalapac (tj. jak to było w poprzednich latach?).
W ub. roku trzeba było mieć 50pkt (równowartość 5 pełnych zadań) żeby dostać koszulkę (no i nie być wśród ostatnich 4 osób które mając 50pkt zajęły miejsca 257-260 ;))
Czasy moich kotów w poprzednim poście.
Użytkownik bryn edytował ten post 11 maj 2008, 10:47
0.06s w teście 10., a wy jak?
podalismy w postach wraz z kodami..
0,07 - u mnie..
widac przewage <stdio> nad <iostream> - mala bo mala, ale jest ;)
z reszta to wszystko miesci sie w granicach bledu pomiarowego i zaokraglen ;)
Użytkownik fernandez edytował ten post 11 maj 2008, 10:46
Heh cały ja... zapomniałem o znaku \ przez co mam 3/10 pkt :P
nie startuje w potyczkach bo nie lubie algorytmiki, ale t o zadanie można zrobić też tworząc tablice 256 elementową i przypisując każdemu elementowi odpowiedni numer od 1 do 5, a potem wypisywaniu na out wartosci elementu o indexie będącym kodem ascii znaku. to chyba nawet było by szybsze niż switch...
0.06s w teście 10., a wy jak?
0.02s
zadanie można zrobić też tworząc tablice 256 elementową i przypisując każdemu elementowi odpowiedni numer od 1 do 5, a potem wypisywaniu na out wartosci elementu o indexie będącym kodem ascii znaku. to chyba nawet było by szybsze niż switch...
No nie bardzo ;)
A jak ja zrobiłem?
int c; while(c = getchar()) { if(c == EOF || c == '\n') break; switch(c) // ... putchar('1') ...
Użytkownik Coldpeer edytował ten post 12 maj 2008, 08:56
No nie bardzo wink2.gif
Chyba jednak
char znaki[256]; char c; for ( c=wartosc_najnizszego_mozliwego_znaku; c<wartosc_najwyzszego_mozliwego_znaku; c++) { //tutaj klasyczny switch dla znaków tylko out dajemy na znaki[c]; w postaci '1', '2', ... lub '5' }; // tutaj posłuze sie twoją petlą tylko zmienoną: while (c=getchar()) { if(c == EOF || c == '\n') break; putchar(znaki[c]); };
I mamy tylko max 256 switchy, a nie tyle co znaków... Chyba ze o cos innego chodzi w zadaniu...
3 zadanka już są. Jak idzie?
Wczorajsze Papryczki raczej proste, ale nie banalne. Dzisiaj na Spinacze mam już pomysł, którego jestem chyba nawet bardziej pewien niż wczorajszych Papryczek. ;) Postaram się udowodnić poprawność i pewnie na wieczór zostanie Bug. :D
Natomiast nie podoba mi się to co się wyprawia na forum Potyczek. Regularna dyskusja nad rozwiązaniami... <_<
Użytkownik bryn edytował ten post 14 maj 2008, 15:07
hehe tylko mogę Wam pozazdrościć ;)
ja dzisiaj musiałem maturę pisać i jutro tak samo :/
Z bugami już sobie poradziłem, spinaczów niestety kompletnie nie rozumiem.
PAP - daje do myslenia zadanie..
SPI - nie mam zbyt bujnej wyobrazni do takich rzeczy ale jesli moje przypuszczenia sprawdza sie to bedzie mila niespodzianka ;)
BUG - jestesm w trakcie realizowania mojego algorytmu ;)
Użytkownik fernandez edytował ten post 14 maj 2008, 22:17
Tak jak myślałem: papryczki logarytmiczne banalne, potwierdza wynik 10pkt i czas - we wszystkich przypadkach 0.00s xD oraz ilość osób, które otrzymała maksa. Coś wydaje mi się, że zadanie dzisiejsze z grupy B jest równie proste.
Nad zadaniem z grupy A wciąż myślę - póki co mam pomysł, ale strasznie czasochłonny - szukam innego ;)
Użytkownik PcSA edytował ten post 15 maj 2008, 00:07
tak jest - PAP 10/10 w czasach 0.00s, okazalo sie trywialne, ale mysle ze jakis pseudo-brut powinien tez dac rade ;)
kodu chyba nie musze zmieszczac ;)
BUGa chyba jutro rano skoncze :P te 8s jednoczesnie zacheca i niepokoi :P
Użytkownik fernandez edytował ten post 15 maj 2008, 00:17
Papryczki - 10/10
Przekątne - zadanie proste więc będę miał jeszcze czas, żeby zastanowić się nad spinaczami
Studia - na razie przeczytałem tylko treść i myślę, że da się zrobić :-)
Prosze o drobna wskazowke do spinaczy :D Trzeba prowadzic symulacje tych odpiec czy jest jakis inny sposob(oczywiscie jesli jest to o niego pytam, pytam tylko czy takowy jest)? Pytam tylko dlatego, ze nie chce zeby sie okazalo ze sie namecze z pisaniem symulacji, a sie okaze ze nie tedy droga.
Użytkownik Kamil Wajda edytował ten post 15 maj 2008, 17:54
Prosze o drobna wskazowke do spinaczy :D Trzeba prowadzic symulacje tych odpiec czy jest jakis inny sposob(oczywiscie jesli jest to o niego pytam, pytam tylko czy takowy jest)? Pytam tylko dlatego, ze nie chce zeby sie okazalo ze sie namecze z pisaniem symulacji, a sie okaze ze nie tedy droga.
Nie dostaniesz nawet takiej wskazówki :) Zastanów się jaka złożoność będzie wystarczająca dla tych limitów a poznasz odopowiedź na swoje pytanie :)
Papryczki na dychę, spinaczy jestem pewien, przekątne chyba mam, ale implementacja idzie mi jak krew z nosa...
Użytkownik bryn edytował ten post 15 maj 2008, 18:07
z tym BUGiem to nie mo ge dojsc do jakis konkretnych wnioskow, zaden algorytm mi tutaj nie pasuje :/
z PRZekatnymi to sobie niezle polecialem "po bandzie" :P narazie wyslalem wersje bardzo wolna, poki nic nowego nie wymysle to tak zostanie :P
Użytkownik fernandez edytował ten post 15 maj 2008, 18:14
Przekątne - zadanie proste więc będę miał jeszcze czas, żeby zastanowić się nad spinaczami
A zaklepałeś już te przekątne? Bo ja stwierdziłem że mój pierwszy pomysł był do kitu ;) I nie byłbym taki pewien że proste (chyba że już masz napisane). :P
jednak moje kontrowersyjne SPInacze nie przeszyl wsyzstkich testow 6/10 :P zabraklo dokladnie 4-ech poprawnych opdowiedzi (pech chcial ze kazda z nich byla w innej grupie testowej)
z BUGiem niestety sobie nie poradzilem :(
edit@down:
taaa, 1M x 1M to jedank trwa troche :P
Użytkownik fernandez edytował ten post 16 maj 2008, 12:45
A zaklepałeś już te przekątne? Bo ja stwierdziłem że mój pierwszy pomysł był do kitu wink2.gif I nie byłbym taki pewien że proste (chyba że już masz napisane). tongue.gif
W momencie, gdy to pisałem, to myślałem, że algorytm O(n^2) starczy :P
Spinacze w czasie stałym, nie licząc wczytytania wejścia - można podać odpowiedź spoglądając tylko na początek i koniec łańcucha + na liczbę spinaczy:
#include <cstdio> int n; char s[10000010]; int main() { scanf("%d\n",&n); scanf("%s",&s); int a = 0; int b = 2*n-2; if(!(n%2)) { if(( (((s[a]=='A')&&(s[a+2]=='B'))|| ((s[a]=='A')&&(s[a+2]=='D'))|| ((s[a]=='C')&&(s[a+2]=='B'))|| ((s[a]=='C')&&(s[a+2]=='D')))&& (((s[b-2]=='A')&&(s[b]=='B'))|| ((s[b-2]=='A')&&(s[b]=='D'))|| ((s[b-2]=='C')&&(s[b]=='B'))|| ((s[b-2]=='C')&&(s[b]=='D'))) )) printf("%d\n",n); else printf("%d\n",n-1); } else printf("%d\n",n-1); return 0; }10/10 ;) Biorę się ostro za przekątne ;)
Spinacze w czasie stałym, nie licząc wczytytania wejścia - można podać odpowiedź spoglądając tylko na początek i koniec łańcucha + na liczbę spinaczy:
tak i ja zrobilem, ale zuplenie nie pomsyalalem ze jest roznica gdy liczba spinaczy jest parzysta czy nieparzysta :P
Co do przekątnych, to udało mi się już coś lepszego niż O(n^2)
Mi w zasadzie też. 8 pkt za toporną O((n+m)log m) i jestem w miarę zadowolony. Jak u was?
6 pkt za cos majacego zlozonosc miedzy n log n a n^2 (n^2 w testach typu ze pierwszu wierzcholek laczy sie z przedostatnim, drugi z przedprzed ostatnim itd).
EDIT: No to teraz juz 7 (sprawdzili to zad jeszcze raz zwiekszajac limity do 8 sek w niektorych testach xD)
Użytkownik Kamil Wajda edytował ten post 17 maj 2008, 17:57
normalnie chlopaki odpadam :(
z potyczek na potyczki coraz gorzej :/
za PRZekatne dostalem az 1 pkt, juz pomijam ze predkosc jego nie byla zbyt mocna strona, ale bylem pewien ze wyala poprawne wyniki, jednak rzeczywistosc sprowadzila mnie na ziemie :/ znowu o czyms zapomnialem albo cos niedopatrzylem jak w ostatniej chiwli chcialem przyspieszyc algorytm :/
dzisiejsze zadania przeczytalem i nie wiem czy cokolwiek rusze, bo zaczyna mi sie ciezki okres na uczleni + praca (wlasnie w ADB ;) )
zycze wszystkim powodzenia, jestescie dobrzy "w te klocki" ;)
Użytkownik fernandez edytował ten post 18 maj 2008, 10:41
Ja wczoraj poległem ;/ Tylko "ulepszony brut" na mozaikę. Nie liczę na więcej niż 4pkt...
edit: no dobra, dostałem 5 :P
Użytkownik bryn edytował ten post 18 maj 2008, 08:53
moj az 3pkt :/
Użytkownik fernandez edytował ten post 18 maj 2008, 10:37
Mój 6 pkt. Btw ktore miejsca macie na liscie B?
A w obecnej rundzie chyba polegne... o ile szachy moze jakos zrobie, to juz z podroza bedzie tragedia... bo przy takich danych to z brutem daleko nie zajde.
A tak btw: czemu nie da sie zadeklarowac bardzo duzej tablicy np. o 1000000000 elementach? A moze sie da jakos specialnym sposobem?
EDIT: Heh niedopatrzenie xD Trzeba bedzie zmienić podejscie do szachow :P
Użytkownik Kamil Wajda edytował ten post 18 maj 2008, 11:47
ale elemntach jakich??
bo jak INT to policz 4*109/220 czy tyle masz wolnego miejsca w RAMie (w MB oczywiscie)
btw, tez sie przymierzam do SZAchownicy - tworzenie takich tablic tutaj nie wchodzi w gre :/
miejsce daaaaaalekie - 789
Użytkownik fernandez edytował ten post 18 maj 2008, 11:46
211 miejsce
szachy mam, a przynajmniej tak mi się wydaje :>
Ja gram już trzeci raz, ale chyba teraz jest najgorzej, pozycja 527 w dywizji B. Zadań z grupy A już na wstępie postanowiłem nie czytać, za mało czasu na wszystko. Przekątne wysłałem za 15 północ, to też na teście wstępnym się zakończyło, a dalej nic, zero punktów. Mozaika też mnie rozczarowała, wydawało się, że jest w miarę sprawna, a tymczasem tylko 3 punkty, na resztę za mało czasu. Teraz wysłałem szachy, a na podróż w ogóle nie mam pomysłu. Pewnie dlatego, że nie mam pojęcia o grafach, jeszcze tego w szkole nie braliśmy :)
Biorac pod uwage rozmiar danych w PODrozy, to wydaje mi sie (choc moge sie mylic) ze tu bardziej wiedza z kombinatoryki sie przyda a z grafow to w duzo mniejszym stopniu...
Ktoś z forum jest może wsród tych 350 osób które walczą do końca? :) Ja jeszcze jestem w strefie koszuklowej... ale po dzisiejszej (ostatnie) serii czarno to widzę - pomysłów brak :|
Ja sie poddalem (tzn. jak mi cos do glowy przyjdzie w co watpie, to sobie zaklepe). A uważam że jak na pierwszy raz skonczyc na ok 500 miejscu na liscie B to nie jest az tak zle :P
Dobrze że nie startowałem w tym konkursie :P od samych treści zadań aż głowa boli... algorytmy matematyczne i krótkie programiki cud-robiące to nie moja dziedzina :) Ale wiem, że wielu fascynuje pisanie programów, których widzialne działanie sprowadza się do wypisania na ekranie cyferek :P
Użytkownik Herion edytował ten post 20 maj 2008, 21:16
51 pkt i koniec imprezy ;) koszulki prawdopodobnie nie będzie, bo poddałem się w ostatniej rundzie (5/20) z powodu baaaaardzo złego samopoczucia... mimo to jestem w miarę zadowolony z całości ;) polecam wszystkim na przyszły rok wyjąć sobie tydzień z życiorysu i trochę się pobawić :D
edit: jednak koszulka wpadła :D
Użytkownik bryn edytował ten post 21 maj 2008, 19:13
51 pkt i koniec imprezy ;) koszulki prawdopodobnie nie będzie, bo poddałem się w ostatniej rundzie (5/20) z powodu baaaaardzo złego samopoczucia... mimo to jestem w miarę zadowolony z całości ;) polecam wszystkim na przyszły rok wyjąć sobie tydzień z życiorysu i trochę się pobawić :D
Tak, w przyszlym roku juz nie zrobie tego bledu co w tym i sobie wezme zwolnienie z lekcji na caly tydzien :D
Ja zakończyłem na 3 rundzie. Razem 25 pkt :-)
Podziwiam tych, którzy wytrwali do końca.
Użytkownik Capellini edytował ten post 22 maj 2008, 19:31
gratulacje wszystkim bioracym udzial :)
u mnie razem 20 pkt ;)
edit@down:
farciarz :thumbsup:
Użytkownik fernandez edytował ten post 25 maj 2008, 22:59
Gratulacje tym co przeszli dalej! Za rok znowu trzeba będę spróbować :)
U mnie 23 pkt + koszulka :D
zanotowane.pl doc.pisz.pl pdf.pisz.pl zsf.htw.pl
13 maja rusza największy polski otwarty konkurs programistyczny. Rejestracja i sesja próbna trwa pod adresem: http://konkurs.adb.pl/ - do wygrania 256 koszulek i parę laptopów.
Kto bierze udział i na co się nastawiacie? Ja w ubiegłym roku obiecałem sobie, że w tym zgarnę koszulkę - i jeśli tylko wystarczy czasu, to tak też zrobię. :D
@down - fernandez, wiedziałem, że będziesz pierwszym, który odpowie :P
Użytkownik bryn edytował ten post 05 maj 2008, 20:59
biore udzial, ale nie oczekuje zbyt wiele - mam za duzo projektow na glowie na uczelni :/
zycze powodzenia wszystkim :)
btw - bryn, wiedzialem ze predzej czy pozniej zalozysz ten temat :P
Użytkownik fernandez edytował ten post 05 maj 2008, 20:51
no te próbne jest banalne :)
w czym można pisać te programy?
pascal, c, c++, java
pascal, c/c++, java - w regulaminie masz to napisane ;)
Tak, to próbne było banalne nawet dla mnie ^^
Zobaczymy ile pkt. dostanę po testach ;]
ja oczywiście też biorę udział, i też koszulka by się przydała(choćby na w-f:P) no a próbne to rzeczywiście banalne, zresztą jak co roku, chociaż poprzednie próbne(o samolocie) było chyba łatwiejsze
A wszystkie zadania można zrobić w programowania strukturalnym ?
@down
chodziło mi raczej czy wszystkie zadnia dałoby się zrobić strukturalnie
Użytkownik webmasterscool edytował ten post 06 maj 2008, 17:51
tak, mozna - czasem jest to wrecz wskazane..
akurat w czasie matury z matmy i fizy :/
@down - fernandez, wiedziałem, że będziesz pierwszym, który odpowie tongue.gif
btw - bryn, wiedzialem ze predzej czy pozniej zalozysz ten temat tongue.gif
A ja gdybym się nad tym zastanawiał, to wiedziałbym to i to.
Sartuję po raz pierwszy (a jestem już w II LO), ale nie oczekuję zbyt wiele.
poniewaz runda sie zakonczyla to chialbym jak sobie pordzialiscie z zadaniem ?? :)
tzn. po prostu wklejcie kod ;)
moj wyglada tak :]
1: #include <iostream> 2: main() { 3: std::ios::sync_with_stdio( 0 ); 4: std::string str; 5: std::getline( std::cin, str ); 6: for( int i=0; i<str.size(); i++ ) { 7: switch( str[i] ) { 8: case'`': case'1': case'2': case'3': case'4': case'5': case'6': case'7': case '8': case'9': case'0': case'-': case'=': std::cout << "1"; break; 9: case'Q': case'W': case'E': case'R': case'T': case'Y': case'U': case'I': case 'O': case'P': case'[': case']': case'\\': std::cout << "2"; break; 10: case'A': case'S': case'D': case'F': case'G': case'H': case'J': case'K': case 'L': case';': case'\'': std::cout << "3"; break; 11: case'Z': case'X': case'C': case'V': case'B': case'N': case'M': case',': case '.': case'/': std::cout << "4"; break; 12: case' ': std::cout << "5"; break; 13: default: return 0; 14: } 15: } 16: } 17:
jak sie pojawia czasy to tez byscie mogli zamiescic ;)
moje czasy:
0 OK 0.00s/1.00s 0/0 1 OK 0.00s/1.00s 1/1 2 OK 0.00s/1.00s 1/1 3 OK 0.00s/1.00s 1/1 4 OK 0.00s/1.00s 1/1 5 OK 0.00s/1.00s 1/1 6 OK 0.01s/1.00s 1/1 7 OK 0.01s/1.00s 1/1 8 OK 0.02s/1.00s 1/1 9 OK 0.07s/2.00s 1/1 10 OK 0.07s/2.00s 1/1
edit@down:
potem sobie napisalem program "znak po znaku" (dalej z iostream) i niestety bylo wolniej, minimalnie ale wolniej :P
Użytkownik fernandez edytował ten post 11 maj 2008, 09:20
moj kod bardzo podobny, tylko że na stdio, i "znak-po-znaku":
#include <cstdio> int main() { char c; for(;;) { scanf("%c",&c); switch Ĺ { case '`': case '1': case '2': case '3': case '4': case '5': case '6': case '7': case '8': case '9': case '0': case '-': case '=': printf("1"); break; case 'Q': case 'W': case 'E': case 'R': case 'T': case 'Y': case 'U': case 'I': case 'O': case 'P': case '[': case ']': case '\\': printf("2"); break; case 'A': case 'S': case 'D': case 'F': case 'G': case 'H': case 'J': case 'K': case 'L': case ';': case '\'': printf("3"); break; case 'Z': case 'X': case 'C': case 'V': case 'B': case 'N': case 'M': case ',': case '.': case '/': printf("4"); break; case ' ': printf("5"); break; case '\n': return 0; } } return 0; }
edit:
0 OK 0.00s/1.00s 0/0 1 OK 0.00s/1.00s 1/1 2 OK 0.00s/1.00s 1/1 3 OK 0.00s/1.00s 1/1 4 OK 0.00s/1.00s 1/1 5 OK 0.01s/1.00s 1/1 6 OK 0.00s/1.00s 1/1 7 OK 0.00s/1.00s 1/1 8 OK 0.01s/1.00s 1/1 9 OK 0.05s/2.00s 1/1 10 OK 0.06s/2.00s 1/1
Użytkownik bryn edytował ten post 11 maj 2008, 09:52
nie znam się za bardzo na c++, ale czy uwzględniliście wciśnięcie SHIFTa?
przeczytaj tresc zadania.. :>
A ja, nie przejmując się zbytnio optymalizacją, wpisałem kolejne rzędy liter do 4 tablic i w pętlach for dla każdego znaku uprzednio zapisanego getline() w stringu sprawdzałem, do której tablicy dany znak należy. ;]
Potem stwierdziłem, że dużo szybciej byłoby napisać to jak Wy - switch'em sprawdzać kolejne znaki, ale już mi się nie chciało, bo to i tak tylko próbne zadanie.
Też biorę udział w tym konkursie. Btw to pierwszy konkurs programistyczny w ktorym biorę udział, więc nie liczę na za wiele, ale koszulke to bym mimo wszystko chciał zgarnąć :D Btw ile mniej wiecej trza miec zrobionych programów kategorii B by sie zalapac (tj. jak to było w poprzednich latach?).
A oto moje koty:
#include<cstdio> #include<iostream> using namespace std; string a, litery[] = {"QWERTYUIOP[]", "ASDFGHJKL;\'", "ZXCVBNM,./"}; main() { getline(cin, a); for(int i = 0; i < a.size(); i++) { if(isdigit(a[i]) || a[i] == '~' || a[i] == '-' || a[i] == '=') printf("%d", 1); else if(isspace(a[i])) printf("%d", 5); else if(litery[0].find(a[i]) != -1) printf("%d", 2); else if(litery[1].find(a[i]) != -1) printf("%d", 3); else if(litery[2].find(a[i]) != -1) printf("%d", 4); } printf("\n"); return 0; }
Btw ile mniej wiecej trza miec zrobionych programów kategorii B by sie zalapac (tj. jak to było w poprzednich latach?).
W ub. roku trzeba było mieć 50pkt (równowartość 5 pełnych zadań) żeby dostać koszulkę (no i nie być wśród ostatnich 4 osób które mając 50pkt zajęły miejsca 257-260 ;))
Czasy moich kotów w poprzednim poście.
Użytkownik bryn edytował ten post 11 maj 2008, 10:47
0.06s w teście 10., a wy jak?
podalismy w postach wraz z kodami..
0,07 - u mnie..
widac przewage <stdio> nad <iostream> - mala bo mala, ale jest ;)
z reszta to wszystko miesci sie w granicach bledu pomiarowego i zaokraglen ;)
Użytkownik fernandez edytował ten post 11 maj 2008, 10:46
Heh cały ja... zapomniałem o znaku \ przez co mam 3/10 pkt :P
nie startuje w potyczkach bo nie lubie algorytmiki, ale t o zadanie można zrobić też tworząc tablice 256 elementową i przypisując każdemu elementowi odpowiedni numer od 1 do 5, a potem wypisywaniu na out wartosci elementu o indexie będącym kodem ascii znaku. to chyba nawet było by szybsze niż switch...
0.06s w teście 10., a wy jak?
0.02s
zadanie można zrobić też tworząc tablice 256 elementową i przypisując każdemu elementowi odpowiedni numer od 1 do 5, a potem wypisywaniu na out wartosci elementu o indexie będącym kodem ascii znaku. to chyba nawet było by szybsze niż switch...
No nie bardzo ;)
A jak ja zrobiłem?
int c; while(c = getchar()) { if(c == EOF || c == '\n') break; switch(c) // ... putchar('1') ...
Użytkownik Coldpeer edytował ten post 12 maj 2008, 08:56
No nie bardzo wink2.gif
Chyba jednak
char znaki[256]; char c; for ( c=wartosc_najnizszego_mozliwego_znaku; c<wartosc_najwyzszego_mozliwego_znaku; c++) { //tutaj klasyczny switch dla znaków tylko out dajemy na znaki[c]; w postaci '1', '2', ... lub '5' }; // tutaj posłuze sie twoją petlą tylko zmienoną: while (c=getchar()) { if(c == EOF || c == '\n') break; putchar(znaki[c]); };
I mamy tylko max 256 switchy, a nie tyle co znaków... Chyba ze o cos innego chodzi w zadaniu...
3 zadanka już są. Jak idzie?
Wczorajsze Papryczki raczej proste, ale nie banalne. Dzisiaj na Spinacze mam już pomysł, którego jestem chyba nawet bardziej pewien niż wczorajszych Papryczek. ;) Postaram się udowodnić poprawność i pewnie na wieczór zostanie Bug. :D
Natomiast nie podoba mi się to co się wyprawia na forum Potyczek. Regularna dyskusja nad rozwiązaniami... <_<
Użytkownik bryn edytował ten post 14 maj 2008, 15:07
hehe tylko mogę Wam pozazdrościć ;)
ja dzisiaj musiałem maturę pisać i jutro tak samo :/
Z bugami już sobie poradziłem, spinaczów niestety kompletnie nie rozumiem.
PAP - daje do myslenia zadanie..
SPI - nie mam zbyt bujnej wyobrazni do takich rzeczy ale jesli moje przypuszczenia sprawdza sie to bedzie mila niespodzianka ;)
BUG - jestesm w trakcie realizowania mojego algorytmu ;)
Użytkownik fernandez edytował ten post 14 maj 2008, 22:17
Tak jak myślałem: papryczki logarytmiczne banalne, potwierdza wynik 10pkt i czas - we wszystkich przypadkach 0.00s xD oraz ilość osób, które otrzymała maksa. Coś wydaje mi się, że zadanie dzisiejsze z grupy B jest równie proste.
Nad zadaniem z grupy A wciąż myślę - póki co mam pomysł, ale strasznie czasochłonny - szukam innego ;)
Użytkownik PcSA edytował ten post 15 maj 2008, 00:07
tak jest - PAP 10/10 w czasach 0.00s, okazalo sie trywialne, ale mysle ze jakis pseudo-brut powinien tez dac rade ;)
kodu chyba nie musze zmieszczac ;)
BUGa chyba jutro rano skoncze :P te 8s jednoczesnie zacheca i niepokoi :P
Użytkownik fernandez edytował ten post 15 maj 2008, 00:17
Papryczki - 10/10
Przekątne - zadanie proste więc będę miał jeszcze czas, żeby zastanowić się nad spinaczami
Studia - na razie przeczytałem tylko treść i myślę, że da się zrobić :-)
Prosze o drobna wskazowke do spinaczy :D Trzeba prowadzic symulacje tych odpiec czy jest jakis inny sposob(oczywiscie jesli jest to o niego pytam, pytam tylko czy takowy jest)? Pytam tylko dlatego, ze nie chce zeby sie okazalo ze sie namecze z pisaniem symulacji, a sie okaze ze nie tedy droga.
Użytkownik Kamil Wajda edytował ten post 15 maj 2008, 17:54
Prosze o drobna wskazowke do spinaczy :D Trzeba prowadzic symulacje tych odpiec czy jest jakis inny sposob(oczywiscie jesli jest to o niego pytam, pytam tylko czy takowy jest)? Pytam tylko dlatego, ze nie chce zeby sie okazalo ze sie namecze z pisaniem symulacji, a sie okaze ze nie tedy droga.
Nie dostaniesz nawet takiej wskazówki :) Zastanów się jaka złożoność będzie wystarczająca dla tych limitów a poznasz odopowiedź na swoje pytanie :)
Papryczki na dychę, spinaczy jestem pewien, przekątne chyba mam, ale implementacja idzie mi jak krew z nosa...
Użytkownik bryn edytował ten post 15 maj 2008, 18:07
z tym BUGiem to nie mo ge dojsc do jakis konkretnych wnioskow, zaden algorytm mi tutaj nie pasuje :/
z PRZekatnymi to sobie niezle polecialem "po bandzie" :P narazie wyslalem wersje bardzo wolna, poki nic nowego nie wymysle to tak zostanie :P
Użytkownik fernandez edytował ten post 15 maj 2008, 18:14
Przekątne - zadanie proste więc będę miał jeszcze czas, żeby zastanowić się nad spinaczami
A zaklepałeś już te przekątne? Bo ja stwierdziłem że mój pierwszy pomysł był do kitu ;) I nie byłbym taki pewien że proste (chyba że już masz napisane). :P
jednak moje kontrowersyjne SPInacze nie przeszyl wsyzstkich testow 6/10 :P zabraklo dokladnie 4-ech poprawnych opdowiedzi (pech chcial ze kazda z nich byla w innej grupie testowej)
z BUGiem niestety sobie nie poradzilem :(
edit@down:
taaa, 1M x 1M to jedank trwa troche :P
Użytkownik fernandez edytował ten post 16 maj 2008, 12:45
A zaklepałeś już te przekątne? Bo ja stwierdziłem że mój pierwszy pomysł był do kitu wink2.gif I nie byłbym taki pewien że proste (chyba że już masz napisane). tongue.gif
W momencie, gdy to pisałem, to myślałem, że algorytm O(n^2) starczy :P
Spinacze w czasie stałym, nie licząc wczytytania wejścia - można podać odpowiedź spoglądając tylko na początek i koniec łańcucha + na liczbę spinaczy:
#include <cstdio> int n; char s[10000010]; int main() { scanf("%d\n",&n); scanf("%s",&s); int a = 0; int b = 2*n-2; if(!(n%2)) { if(( (((s[a]=='A')&&(s[a+2]=='B'))|| ((s[a]=='A')&&(s[a+2]=='D'))|| ((s[a]=='C')&&(s[a+2]=='B'))|| ((s[a]=='C')&&(s[a+2]=='D')))&& (((s[b-2]=='A')&&(s[b]=='B'))|| ((s[b-2]=='A')&&(s[b]=='D'))|| ((s[b-2]=='C')&&(s[b]=='B'))|| ((s[b-2]=='C')&&(s[b]=='D'))) )) printf("%d\n",n); else printf("%d\n",n-1); } else printf("%d\n",n-1); return 0; }10/10 ;) Biorę się ostro za przekątne ;)
Spinacze w czasie stałym, nie licząc wczytytania wejścia - można podać odpowiedź spoglądając tylko na początek i koniec łańcucha + na liczbę spinaczy:
tak i ja zrobilem, ale zuplenie nie pomsyalalem ze jest roznica gdy liczba spinaczy jest parzysta czy nieparzysta :P
Co do przekątnych, to udało mi się już coś lepszego niż O(n^2)
Mi w zasadzie też. 8 pkt za toporną O((n+m)log m) i jestem w miarę zadowolony. Jak u was?
6 pkt za cos majacego zlozonosc miedzy n log n a n^2 (n^2 w testach typu ze pierwszu wierzcholek laczy sie z przedostatnim, drugi z przedprzed ostatnim itd).
EDIT: No to teraz juz 7 (sprawdzili to zad jeszcze raz zwiekszajac limity do 8 sek w niektorych testach xD)
Użytkownik Kamil Wajda edytował ten post 17 maj 2008, 17:57
normalnie chlopaki odpadam :(
z potyczek na potyczki coraz gorzej :/
za PRZekatne dostalem az 1 pkt, juz pomijam ze predkosc jego nie byla zbyt mocna strona, ale bylem pewien ze wyala poprawne wyniki, jednak rzeczywistosc sprowadzila mnie na ziemie :/ znowu o czyms zapomnialem albo cos niedopatrzylem jak w ostatniej chiwli chcialem przyspieszyc algorytm :/
dzisiejsze zadania przeczytalem i nie wiem czy cokolwiek rusze, bo zaczyna mi sie ciezki okres na uczleni + praca (wlasnie w ADB ;) )
zycze wszystkim powodzenia, jestescie dobrzy "w te klocki" ;)
Użytkownik fernandez edytował ten post 18 maj 2008, 10:41
Ja wczoraj poległem ;/ Tylko "ulepszony brut" na mozaikę. Nie liczę na więcej niż 4pkt...
edit: no dobra, dostałem 5 :P
Użytkownik bryn edytował ten post 18 maj 2008, 08:53
moj az 3pkt :/
Użytkownik fernandez edytował ten post 18 maj 2008, 10:37
Mój 6 pkt. Btw ktore miejsca macie na liscie B?
A w obecnej rundzie chyba polegne... o ile szachy moze jakos zrobie, to juz z podroza bedzie tragedia... bo przy takich danych to z brutem daleko nie zajde.
A tak btw: czemu nie da sie zadeklarowac bardzo duzej tablicy np. o 1000000000 elementach? A moze sie da jakos specialnym sposobem?
EDIT: Heh niedopatrzenie xD Trzeba bedzie zmienić podejscie do szachow :P
Użytkownik Kamil Wajda edytował ten post 18 maj 2008, 11:47
ale elemntach jakich??
bo jak INT to policz 4*109/220 czy tyle masz wolnego miejsca w RAMie (w MB oczywiscie)
btw, tez sie przymierzam do SZAchownicy - tworzenie takich tablic tutaj nie wchodzi w gre :/
miejsce daaaaaalekie - 789
Użytkownik fernandez edytował ten post 18 maj 2008, 11:46
211 miejsce
szachy mam, a przynajmniej tak mi się wydaje :>
Ja gram już trzeci raz, ale chyba teraz jest najgorzej, pozycja 527 w dywizji B. Zadań z grupy A już na wstępie postanowiłem nie czytać, za mało czasu na wszystko. Przekątne wysłałem za 15 północ, to też na teście wstępnym się zakończyło, a dalej nic, zero punktów. Mozaika też mnie rozczarowała, wydawało się, że jest w miarę sprawna, a tymczasem tylko 3 punkty, na resztę za mało czasu. Teraz wysłałem szachy, a na podróż w ogóle nie mam pomysłu. Pewnie dlatego, że nie mam pojęcia o grafach, jeszcze tego w szkole nie braliśmy :)
Biorac pod uwage rozmiar danych w PODrozy, to wydaje mi sie (choc moge sie mylic) ze tu bardziej wiedza z kombinatoryki sie przyda a z grafow to w duzo mniejszym stopniu...
Ktoś z forum jest może wsród tych 350 osób które walczą do końca? :) Ja jeszcze jestem w strefie koszuklowej... ale po dzisiejszej (ostatnie) serii czarno to widzę - pomysłów brak :|
Ja sie poddalem (tzn. jak mi cos do glowy przyjdzie w co watpie, to sobie zaklepe). A uważam że jak na pierwszy raz skonczyc na ok 500 miejscu na liscie B to nie jest az tak zle :P
Dobrze że nie startowałem w tym konkursie :P od samych treści zadań aż głowa boli... algorytmy matematyczne i krótkie programiki cud-robiące to nie moja dziedzina :) Ale wiem, że wielu fascynuje pisanie programów, których widzialne działanie sprowadza się do wypisania na ekranie cyferek :P
Użytkownik Herion edytował ten post 20 maj 2008, 21:16
51 pkt i koniec imprezy ;) koszulki prawdopodobnie nie będzie, bo poddałem się w ostatniej rundzie (5/20) z powodu baaaaardzo złego samopoczucia... mimo to jestem w miarę zadowolony z całości ;) polecam wszystkim na przyszły rok wyjąć sobie tydzień z życiorysu i trochę się pobawić :D
edit: jednak koszulka wpadła :D
Użytkownik bryn edytował ten post 21 maj 2008, 19:13
51 pkt i koniec imprezy ;) koszulki prawdopodobnie nie będzie, bo poddałem się w ostatniej rundzie (5/20) z powodu baaaaardzo złego samopoczucia... mimo to jestem w miarę zadowolony z całości ;) polecam wszystkim na przyszły rok wyjąć sobie tydzień z życiorysu i trochę się pobawić :D
Tak, w przyszlym roku juz nie zrobie tego bledu co w tym i sobie wezme zwolnienie z lekcji na caly tydzien :D
Ja zakończyłem na 3 rundzie. Razem 25 pkt :-)
Podziwiam tych, którzy wytrwali do końca.
Użytkownik Capellini edytował ten post 22 maj 2008, 19:31
gratulacje wszystkim bioracym udzial :)
u mnie razem 20 pkt ;)
edit@down:
farciarz :thumbsup:
Użytkownik fernandez edytował ten post 25 maj 2008, 22:59
Gratulacje tym co przeszli dalej! Za rok znowu trzeba będę spróbować :)
U mnie 23 pkt + koszulka :D