Общий форум| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | WA#2 please help! | [KhAI] Smusenok Sergey | 1706. Шифровка 2 | 17 сен 2009 23:06 | 2 | Did you find what was the test? I have Wa2 too! Please s.o. help | | if agents are missing | re.nikonoff (ONPU) | 1524. Men in Black | 17 сен 2009 19:45 | 2 | If I have such situation that current quest cannot be performed because of all agents are tired or existing agents not able to perform current quest. I skip all incoming quest(s) until new agent(s) are come in organization (or existing agents up their experience to able to perform skipped quest(s)). Then I try to assign new agent(s) to perform skipped quest(s). Question: can I face with such situation or it is guaranteed that all quests can be performed in the same order they are appear in input (maybe with some lag of course)? P.S. And what about if new agent(s) not come in organization but quests still pending at end of input? (maybe this situation is not present in tests) | | WA14 | Freezing Sun | 1366. Подарки | 17 сен 2009 19:04 | 1 | WA14 Freezing Sun 17 сен 2009 19:04 Could someone give me a few tests. I get WA14. I use the formula f(n) = n*f(n-1) + (-1)^n where f(1)=0 and f(2)=1. If someone could take a look at my code, post an email to send it to. | | statement suggestion | re.nikonoff (ONPU) | 1524. Men in Black | 17 сен 2009 14:03 | 1 | Statement: But, if agent finished quest <<possible with other agent>> and started other quest <<possible with other agent>> simultaneously, you are to write first message about finishing, and second about starting. e.g. 0001:01:01 Agent A finished quest 1. 0001:01:01 Agent A and agent B started quest 2. or 0001:01:01 Agent A and agent B finished quest 1. 0001:01:01 Agent A started quest 2. or 0001:01:01 Agent A and agent B finished quest 1. 0001:01:01 Agent B and agent C started quest 2. | | What is answer to "один глаз, один рог, но не носорог"? | silveracm3 | 1685. Орфография | 17 сен 2009 13:27 | 2 | What is "г рковоаззи- аул лаывгвдяыеат"? I have no desire to suffer with Russian letters in the console. Answer: "корова из-за угла выглядывает". Translated by Google: "cow from behind a corner peeps". Sorry for my bad English :) | | Please, give me a test. WA 19 (-) | Orfest (Novosibirsk SU) | 1508. Японский кроссворд | 16 сен 2009 23:51 | 1 | | | WA3 xelp | Freeuni: GioSag | 1016. Кубик на прогулке | 16 сен 2009 21:49 | 1 | WA3 xelp Freeuni: GioSag 16 сен 2009 21:49 please give me test case, where my prog files, I've tested it on my friend's AC code and did not find mistake thanks. #include <iostream> #include <string> #include <vector> #include <algorithm> #include <map> #include <set> #define VI vector<int> using namespace std; map< VI , int > mp[10][10]; int p[4][6] = { {2 , 4 , 1 , 3 , 0 , 5}, // forw {4 , 2 , 0 , 3 , 1 , 5},//backw {0 , 1 , 5 , 2 , 3 , 4}, // left {0 , 1 , 3 , 4 , 5 , 2} // right }; int t[4][2] = {{0,1},{0,-1},{-1,0},{1 , 0}}; string s1 , s2; int xst , yst , xfin , yfin , i , j , n , m , a[10] , st , fin , x , y , ans = 1000000000 , nom , xx , yy; struct str { int x , y; vector<int> v; str(){ x = y = 0; } str(int _x , int _y , vector<int> _v) { x = _x; y = _y; v = _v; } }; bool operator < (str a , str b) { return a.x < b.x || a.x == b.x && a.y < b.y || a.x == b.x && a.y == b.y && a.v < b.v; } bool operator == (str a , str b) { return a.x == b.x && a.y == b.y && a.v == b.v; } set<pair<int , str> > stt; map<str , str> par; void findans(str n) { if (n.x == xst && n.y == yst && mp[n.x][n.y][n.v] == a[4]); else findans(par[n]); cout<<char(n.x + 'a' - 1)<<char(n.y + '0')<<" "; } int main() { cin>>s1>>s2; xst = s1[0] - 'a' + 1; yst = s1[1] - '0'; xfin = s2[0] - 'a' + 1; yfin = s2[1] - '0'; for (i = 0; i < 6; i++) cin>>a[i]; if (s1 == s2) { cout<<a[4]<<" "<<s1; return 0; } vector<int> v(a , a + 6);
vector<int> sle = v; sort(sle.begin() , sle.end()); do { for (i = 1; i <= 8; i++) for (j = 1; j <= 8; j++) { mp[i][j][sle] = 110000000; stt.insert(make_pair(110000000 , str(i,j,sle))); } } while (next_permutation(sle.begin() , sle.end())); mp[xst][yst][v] = a[4]; stt.erase( stt.find(make_pair(110000000 , str(xst,yst,v))) ); stt.insert(make_pair(a[4] , str(xst,yst,v))); str stans; while (1) { str w = stt.begin()->second; int dis = stt.begin()->first; if (dis == 110000000) break; x = w.x; y = w.y; VI b = w.v , c(6);
for (i = 0; i < 4; i++) { xx = x + t[i][0]; yy = y + t[i][1]; if (xx >= 1 && xx <= 8 && yy >= 1 && yy <= 8); else continue; for (j = 0; j < 6 ; j++) { c[p[i][j]] = b[j]; } if (mp[xx][yy][c] > dis + c[4]) { mp[xx][yy][c] = dis + c[4]; par[str(xx , yy , c)] = w; stt.insert(make_pair(dis + c[4] , str(xx , yy , c))); if (xx == xfin && yy == yfin && mp[xx][yy][c] < ans) { ans = dis + c[4]; stans = str(xx ,yy , c); } } }
stt.erase(stt.find(make_pair(dis , w)));
} cout<<ans<<" "; findans(stans); return 0; } | | TO ADMINS | Vedernikoff 'Goryinyich' Sergey (HSE: АОП) | | 16 сен 2009 20:06 | 1 | TO ADMINS Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 16 сен 2009 20:06 Please check timus_support@acm.timus.ru | | Too easy | sevenkplus | 1280. Topological Sorting | 16 сен 2009 19:22 | 1 | | | how to determine the end of the console's input with Java | robinpjl(Peking University) | 1007. Кодовые слова | 16 сен 2009 15:45 | 4 | Scanner in; while (in.hasNext()){...} (for String) or while (in.hasNextType()){...} (for Type = Int, Double, Byte, ...) BufferedReader in; int c; while ((c=in.read()) != -1) {...} StreamTokenizer in; in.nextToken(); while (in.ttype != StreamTokenizer.TT_EOF){ ... in.nextToken(); } Edited by author 16.09.2009 00:17 i think ,second method(use -1 to end input) can't ac this problem with JAVA, and i try to use first Scanner method to solve it,failed ,and TT_EOF is -1 in nature. | | Weak tests! | Scalar | 1590. Шифр Бэкона | 15 сен 2009 18:36 | 1 | Not yet. If i'm compile with Microsoft Visual Studio, my program got stack owerflow. But if I'm compile with Intel C++ compiler, I got AC :) Edited by author 21.09.2009 17:22 | | WA12. | MaxE_PSPI(Pskov) | 1531. Zones on a Plane | 15 сен 2009 01:40 | 1 | WA12. MaxE_PSPI(Pskov) 15 сен 2009 01:40 #include<stdio.h> int a[2001][330]; int main() { int n; for(int i=0; i<2001; i++) { for(int j=0; j<330; j++) { a[i][j]=0; } } scanf("%d", &n);
a[1][329]=1; a[2][329]=4; a[3][329]=8; for(int i=4; i<2001; i++) { for(int j=329; j>0; j--) { if((i%2)==0) { a[i][j]=a[i][j]+(2*a[i-1][j])%10-a[i-2][j]; if(a[i][j]<0) { a[i][j]=a[i][j]+10; a[i][j-1]=a[i][j-1]-1; } if(a[i][j]>10) { a[i][j]=a[i][j]%10; a[i][j-1]=a[i][j-1]+a[i][j]/10; } if(2*a[i-1][j]>9) { a[i][j-1]=a[i][j-1]+(2*a[i-1][j])/10; } } else { a[i][j]=a[i][j]+(3*a[i-1][j])%10-(2*a[i-2][j])%10; if(a[i][j]<0) { a[i][j]=a[i][j]+10; a[i][j-1]=a[i][j-1]-1; } if(a[i][j]>10) { a[i][j]=a[i][j]%10; a[i][j-1]=aa[i][j-1]+[i][j]/10; } if(3*a[i-1][j]>9) { a[i][j-1]=a[i][j-1]+(3*a[i-1][j])/10; } if(2*a[i-2][j]>9) { a[i][j-1]=a[i][j-1]-(2*a[i-2][j])/10; } } } } for(int i=0; i<330; i++) { if(a[n][i]!=0) { for(int j=i; j<330; j++) { printf("%d", a[n][j]); } printf("\n"); goto A; } } A: return 0; } All tests are right, but I can't understand why WA12? | | use same memory in all test but MLE test 10, WHY? | Alexander J. Villalba G. | 1220. Stacks | 14 сен 2009 19:48 | 3 | OK Denis Koshman, I did (thanks) but MLE test 10 why? the program in all test use same memory and no use dinamic memory BUT MLE test 10 WHY? is unbelive !!! #include <iostream> #include <string> using namespace std; unsigned int a[100000]; unsigned short b[100000]; int f[1000]; int nn=0; inline int get_value(unsigned x) { return a[x] & 0x7FFFFFFF; } inline void set_value(unsigned x, unsigned v) { (a[x] &= 0x80000000) |= v; } inline int get_next(unsigned x) { return b[x] | ((a[x]>>31)<<16); } inline int set_next(unsigned x, unsigned v) { b[x] = v, (a[x] &= 0x7FFFFFFF) |= (v>>16)<<31; } void push (int pila, int v) { int x = nn++; // 'nn' is global ever-growing variable set_value(x, v); set_next(x, f[pila]); f[pila] = x; } void pop(int pila) { cout << get_value(f[pila]) << endl; f[pila] = get_next(f[pila]); } int main (void) { int n; int pila, v; cin >> n; string s; unsigned int a,b,ss=0; for(int i=0; i<n; i++) { cin >> s; if(s=="PUSH") { cin >> pila; cin >> v; push(pila, v); } if(s=="POP") { cin >> pila; pop (pila); } } return 0; } 1. remove #include <iostream> #include <string> using namespace std; ...cin... ...cout... 2. but use #include <cstdio> ...scanf ()... ...printf ()... 3. You'll get AC because <iostream> use some extra memory more than <stdio.h> 4. about MLE Timus Judge counts only real used memory for current test while executable running. e.g. static int vector [4*1024*1024]; ... for (int i = 0; i < 1024*1024; ++i) { ...vector [i]... } this code gives you only 4MB used (not 16MB as expected) this fact checked experimentally... | | how to solve this F!@#$%G problem? | - | 1220. Stacks | 14 сен 2009 18:46 | 12 | MLE#10 #include <iostream> #include <string> using namespace std; struct aaa { unsigned int a :30; }pop[1001],data[100001][2]; int main() { int n; cin >> n; string s; unsigned int a,b,ss=0; for(int i=0; i<n; i++) { cin >> s; if(s=="PUSH") { cin >> a >> b; data[ss][0].a=b; data[ss][1].a=pop[a].a; pop[a].a=ss; ss++; } if(s=="POP") { cin >> a; cout << data[pop[a].a][0].a << endl; data[pop[a].a][0].a=0; pop[a].a=data[pop[a].a][1].a; } } } Edited by author 26.08.2008 15:33 i rewrote it without using strings and "namespace std" but MLE10 again( may be it is unreal problem? i think it can't be solved without array for 10^5 elements.... wrong cheker? I keep two big arrays: dword a[100000] word nx[100000] int f[1000] bits 0..30 of 'a' - value bits 0..15 of 'nx' together with 31th bit of 'a' - index of next item in the same stack 'f' - index of the top for corresponding stack >together with 31th bit of 'a' how can i write it? i have ML(( #include <iostream.h> struct aaa { unsigned a :30; unsigned n :14; }data[100001]; struct bbb { unsigned a :14; }pop[1001]; int main() { int n; cin >> n; char c; unsigned int a,b,ss=0; for(int i=0; i<n; i++) { cin >> c; cin >> c; if(c=='U') { cin >> c; cin >> c; cin >> a >> b; data[ss].a=b; data[ss].n=pop[a].a; pop[a].a=ss; ss++; }else { cin >> c; cin >> a; cout << data[pop[a].a].a << endl; data[pop[a].a].a=0; pop[a].a=data[pop[a].a].n; } } return 0; } unsigned int a[100000]; unsigned short b[100000]; inline int get_value(unsigned x) { return a[x] & 0x7FFFFFFF; } inline void set_value(unsigned x, unsigned v) { (a[x] &= 0x80000000) |= v; } inline int get_next(unsigned x) { return b[x] | ((a[x]>>31)<<16); } inline int set_next(unsigned x, unsigned v) { b[x] = v, (a[x] &= 0x7FFFFFFF) |= (v>>16)<<31; } When you push item 'v' to stack 'i', you perform: int x = nn++; // 'nn' is global ever-growing variable set_value(x, v) set_next(x, f[i]); f[i] = x; when you pop item from stasck 'i', you perform: cout << get_value(f[i]); f[i] = get_next(f[i]); Another approach does not use bit manipulationson, but relies on fact that every output value requires two commands in the input (push and pop). i just use dynamic arrays and nothing more :) int* a[1001]; int len[1001]; void add(int ind,int data) { len[ind]++; a[ind]=(int*)realloc(a[ind],len[ind]*4); a[ind][len[ind]-1]=data; } int del(int ind) { --len[ind]; int res=a[ind][len[ind]]; a[ind]=(int*)realloc(a[ind],len[ind]*4); return res; } it accepts with large time but with extra small memory Strange, Oracle, that shouldn't work on hard test cases. Not only because of time, but because of memory too. I've used short s[100000], long a[100000], long top[1000]. Time - 0.234 Memory - 721 KB Edited by author 25.01.2009 03:19 Edited by author 25.01.2009 03:19 ID 2260315 Oracle[Lviv NU] 1220 C++ Accepted 0.765 529 KB OK Denis Koshman, I did (thanks) but MLE test 10 why? the program in all test use same memory and no use dinamic memory BUT MLE test WHY? is unbelive !!! #include <iostream> #include <string> using namespace std; unsigned int a[100000]; unsigned short b[100000]; int f[1000]; int nn=0; inline int get_value(unsigned x) { return a[x] & 0x7FFFFFFF; } inline void set_value(unsigned x, unsigned v) { (a[x] &= 0x80000000) |= v; } inline int get_next(unsigned x) { return b[x] | ((a[x]>>31)<<16); } inline int set_next(unsigned x, unsigned v) { b[x] = v, (a[x] &= 0x7FFFFFFF) |= (v>>16)<<31; } void push (int pila, int v) {
int x = nn++; // 'nn' is global ever-growing variable set_value(x, v); set_next(x, f[pila]); f[pila] = x; } void pop(int pila) { cout << get_value(f[pila]) << endl; f[pila] = get_next(f[pila]); } int main (void) { int n; int pila, v; cin >> n; string s; unsigned int a,b,ss=0;
for(int i=0; i<n; i++) { cin >> s; if(s=="PUSH") { cin >> pila; cin >> v; push(pila, v); }
if(s=="POP") {
cin >> pila; pop (pila); } } return 0; } Edited by author 14.09.2009 18:47 I read input several times and get AC in C++. | | Maybe there are weak tests!? | Lomir | 1028. Звёзды | 14 сен 2009 07:46 | 6 | My solution with O(n*x) get AC in 0.171. However for max test it would have 15000*32000=480 000 000 iterations. On my not so fast PC(ADM 1800+) it works 1 - 1.3 sec, so i think it wouldn't pass TL of 0.25sec. The test is: 15000 32000 1 32000 2 32000 3 .......... 32000 15000 Very good information. Admins should pay attention on it. This question about real effectivness of our algorithms. Edited by author 01.07.2007 10:41 Edited by author 01.07.2007 10:41 Nevertheless some other algo with complexivity O(n^2) works well... ... which is quite sad for the ones that spent all eternity, which means about 10 minutes, to write the most straight-forward index tree and produce an N*logN algorithm... 10 minutes are not forever eternity are days, months, years, centuries, millennia ... | | to Admins: your tests | Klyuchnikov Nikita | 1097. Квадратная страна 2 | 13 сен 2009 22:54 | 2 | my AC program failed on many tests If you have good tests (for example, if your AC solution gives wrong answer on them), please, send them to timus_support@acm.timus.ru. | | Problem with testcase | Svyatoslav [Vologda Multiple-Discipline Lyceum] | 1587. Летающая свинья | 13 сен 2009 22:11 | 2 | My old program get AC, but on the test 15 2 -2 3 -1 0 2 1 -1 1 3 -2 -1 -3 -2 3 My old answer on this test is 36, but right answer is 108. I noticed it only when I wrote the solution again. | | Brain-damaged compiler! (2 all who has WA29 or WA30) | ftc | 1274. Fractional Arithmetic | 13 сен 2009 20:05 | 1 | In this compiler built-in abs() function casts its argument to int, so if you will pass long long there, it will not work. Take care of it and pass tests #29 and 30. | | Advice | Anatoly | 1234. Bricks | 13 сен 2009 15:39 | 1 | Advice Anatoly 13 сен 2009 15:39 I had good formula but couldn't get AC because of precision problems. So, I multiplied input by 10, put it to integers, and transformed formula to avoid "sqrt" and "/". If every variable is integer => there are no precision problems and there is AC. | | Broken tests/checker | Fyodor Menshikov | 1025. Демократия в опасности | 13 сен 2009 12:38 | 2 | Solutions that earlier got AC now get wa3. I think that 3rd test was modified according to the problem statement (recently 10001 was changed to 9999), but answer was left old. |
|
|