| ENG RUS | Timus Online Judge |
Common BoardKOTMAKRUS TL 11, help please // Problem 1998. The old Padawan 14 Feb 2014 00:44 Edited by author 14.02.2014 01:31 Edited by author 14.02.2014 01:31 Sa Lang Hae How to solve this problem(1158)? It's too hard.... [9] // Problem 1158. Censored! 23 Feb 2005 07:51 I have been working on it for a week.... Dmitry 'Diman_YES' Kovalioff DP of extreme difficulty. Can not be easily explained (-) [8] // Problem 1158. Censored! 23 Feb 2005 10:53 Vladimir Yakovlev (USU) Re: DP of extreme difficulty. Can not be easily explained (-) [7] // Problem 1158. Censored! 23 Feb 2005 15:05 Why extreme difficulty? My DP is about 30 lines. Idea is very simple. But it's hard to discover as well :) Dmitry 'Diman_YES' Kovalioff For instance, Ural-1342 is 8-lines DP... (+) // Problem 1158. Censored! 23 Feb 2005 15:17 I mean no true DP solution is really large, but this very DP is rather difficult to find and understand. Sa Lang Hae Re: DP of extreme difficulty. Can not be easily explained (-) [5] // Problem 1158. Censored! 23 Feb 2005 18:01 would you please tell me your method? I think only a big-number code will use more than 30 lines... Ilya Rasenstein (9 class) Re: DP of extreme difficulty. Can not be easily explained (-) [4] // Problem 1158. Censored! 6 Mar 2005 14:53 I think Aho-Korasick+DP Jiang Xu This seems pretty interesting.. Could you give me a link where I can read more about this algo? [3] // Problem 1158. Censored! 16 Aug 2005 17:10 Jiang Xu I solved it with a dfa + dp, but my source is very big (180 lines).. How to do it in 30 lines? [2] // Problem 1158. Censored! 16 Aug 2005 17:12 Denis Koshman Re: I solved it with a dfa + dp, but my source is very big (180 lines).. How to do it in 30 lines? [1] // Problem 1158. Censored! 5 Aug 2008 04:24 ALGO IS HERE: 1. Remove all words which contain some other word as a substring. They do not affect anything, but make further things more difficult. 2. Build characters tree from forbidden words. E.g. for set "aabc, abd, bcd" it will be like that: root(a(a(b(c)),b(d)),b(c(d))) positions in this tree will represent history (recent placed letters) and its size will be <= 100 (total amount of letters in all forbidden words) A path from root to node is safe if it does not end in a leaf (otherwise you're in jail for 10 years). Any sub-paths of a safe path are also safe because we removed all words which could lead to such paths. So, we have a good test for path safety - it shouldn't be a leaf, and that's enough. While we place letters, we are allowed to make only safe steps - we can't step into a leaf. If we attempt to perform a step outside of the tree, we should apply 1st postfix of history to that tree to find where will we get after forgetting that least recent placed letter. For example, if the string 'aabce' falls out from the tree after 'aab' (i.e. there is no forbidden word starting with 'aabc'), then we will search for 'abce' (1st postfix of 'aabce') in the same manner, recursively. All this information can be precalculated (which state leads where after adding some particular letter). It's like prebuilding automaton for multi-substring search and then calculate number of programs which do not lead to terminal states. This gave me AC in 0.031 sec and final understanding of KMP which I used blindly before :) Edited by author 05.08.2008 04:24 NotImplemented Re: I solved it with a dfa + dp, but my source is very big (180 lines).. How to do it in 30 lines? // Problem 1158. Censored! 14 Feb 2014 00:35 The limits are not very strict. I did not perform precalculation and did not build automata. Sinigami17 хотя бы шесть различных слов длины n // Problem 2011. Long Statement 13 Feb 2014 20:28 Ребята будьте внимательный когда читаете условия. Я потратил пол часа пока понял что нужно составить не менее 6 а не не менее n слов... Evgeniy++ WA8. What the f??k :) [7] // Problem 1795. Husband in a Shop 20 Oct 2010 20:02 Hello gentlemen! Who can explain why I get WA8? Are there any test data available to anyone? ostr91 Re: WA8. What the f??k :) [4] // Problem 1795. Husband in a Shop 24 Oct 2010 04:02 1 10 of anawa 2 10 of anawa 1 of anawa answer = 2 not 3 Edited by author 24.10.2010 04:07 alp Re: WA8. What the f??k :) // Problem 1795. Husband in a Shop 13 Mar 2011 00:11 2 Pavel Pisligin [IATE] Re: WA8. What the f??k :) [2] // Problem 1795. Husband in a Shop 22 Jul 2012 20:07 I've got this answer, but WA8 too. Andrew Sboev Re: WA8. What the f??k :) [1] // Problem 1795. Husband in a Shop 22 Jul 2012 20:13 Try this test 1 2 of vodka 1 3 of vodka answer 1 Pavel Pisligin [IATE] Re: WA8. What the f??k :) // Problem 1795. Husband in a Shop 22 Jul 2012 20:25 Yes, it is ;) Edited by author 22.07.2012 20:26 Edited by author 22.07.2012 20:26 Edited by author 22.07.2012 20:31 Vassenbaher [IU7.BMSTU] Re: WA8. What the f??k :) [1] // Problem 1795. Husband in a Shop 10 Jul 2013 18:11 2 100 of vodka 1 of matryoshka 3 100 of vodka 1 of vodka 1 of matryoshka †‡ S † i † r † i † u † S ‡† Re: WA8. What the f??k :) // Problem 1795. Husband in a Shop 13 Feb 2014 18:49 I think answer is 3. Anam What is the test 2? // Problem 1880. Psych Up's Eigenvalues 13 Feb 2014 17:05 wrong answer, but I do't know why! help, please #include<iostream> using std::cout; using std::cin; using std:: endl; int main(){ int res = 0; int n1, n2, n3; cin >> n1; unsigned *arr1 = new unsigned[n1]; unsigned temp[100]; for(int i = 0; i < n1; ++i){ cin >> arr1[i]; } cin >> n2; unsigned *arr2 = new unsigned[n2]; for(int i = 0; i < n2; ++i){ cin >> arr2[i]; } cin >> n3; unsigned *arr3 = new unsigned[n3]; for(int i = 0; i < n3; ++i){ cin >> arr3[i]; } int sum = 0; for(int i = 0; i < n1; i++){ for(int j = 0; j < n2; ++j){ if(arr2[j] == arr1[i]) temp[i]= arr2[j]; sum++; } } int sum1 = 0; for(int i = 0; i < sum; i++){ for(int j = 0; j < n3; ++j){ if(arr3[j] == temp[i]) sum1++; } } cout << sum1 << endl; delete[]arr1; delete[]arr2; delete[]arr3; system("PAUSE"); return 0; } Delyan Something is wrong with Check Program [8] // Problem 1625. Hankel Matrix 8 Oct 2008 06:26 I make matrices from the sequence of Catalan numbers 1,2,5,14,42,132,429,1430,4862,... Such matrices satisfy all criterion: 1)All numbers are positive integers 2) Determinants of all matrices are equal to 1 But I get WA2 svr Re: Something is wrong with Check Program // Problem 1625. Hankel Matrix 23 Oct 2008 10:06 I got AC using your method with first submission. Hanzbrow (TNU) KCC Re: Something is wrong with Check Program [3] // Problem 1625. Hankel Matrix 10 Aug 2009 15:27 Edited by author 10.08.2009 18:08 KALO Re: Something is wrong with Check Program [2] // Problem 1625. Hankel Matrix 28 Aug 2009 04:54 Use big numbers... Crash_access_violation Re: Something is wrong with Check Program [1] // Problem 1625. Hankel Matrix 11 Nov 2009 21:43 I use your method, but I got wa6. :( please help me. Edited by author 11.11.2009 21:43 Crash_access_violation Admins please check the problem // Problem 1625. Hankel Matrix 23 Nov 2009 03:29 Artem Khizha Re: Something is wrong with Check Program [1] // Problem 1625. Hankel Matrix 25 Apr 2010 03:00 Wow, its great, but how did you get to Catalan's numbers? Crash_access_violation Re: Something is wrong with Check Program // Problem 1625. Hankel Matrix 5 Jul 2010 21:42 please said me, what answer when n=20? thanks Vit Demidenko Re: Something is wrong with Check Program // Problem 1625. Hankel Matrix 13 Feb 2014 16:45 burn in hell with you spoiler Maxim O(NlogN) C++ soluton // Problem 1021. Sacrament of the Sum 13 Feb 2014 03:02 /* * File: main.cpp * Author: Maxim Cherchuk <maxim.cherchuk@gmail.com> * * Created on 12 Февраль 2014 г., 23:36 */ #include <iostream> #include <algorithm> using namespace std; /* * */ const int MAXN = 50000, MAX = 10000; int a[MAXN], b[MAXN]; int n, k, m; int main(int argc, char** argv) { ios_base::sync_with_stdio(0); cin >> n; for(int i = 0; i < n; ++i) { cin >> a[i]; } cin >> k; for(int i = 0; i < k; ++i) { cin >> b[i]; } sort(a, a+n); sort(b, b+k); for(int i = 0; i < n; ++i) { const int cur = a[i]; int l = 0; int r = k; while(r-l > 1) { // binary search m = (l+r)>>1; if(cur+b[m] > MAX) r = m; else l = m; } if(cur + b[l] == MAX) { cout << "YES"; return 0; } } cout << "NO"; } qazwsxmn WA#19HELP // Problem 1297. Palindrome 12 Feb 2014 19:31 anonymous Runtime error #1 Java [1] // Problem 1083. Factorials!!! 23 Nov 2013 22:42 What is test #1?? lichtgestalt2710 Re: Runtime error #1 Java // Problem 1083. Factorials!!! 12 Feb 2014 04:45 maybe you divide a number by zero to get that runtime error ace Accepted [2] // Problem 1259. How to Become Star? 20 Oct 2012 11:51 #include<iostream> using namespace std; int GCD( int a, int b ) { a = abs( a ); b = abs( b ); while ( b ) { int tmp = a % b; a = b; b = tmp; } return ( a ); } int main() { int s=0,n,i; cin>>n; for(i=1;i<=n/2;i++) if(GCD(n,i)%n==1) s++; cout<<s; system("pause"); return 0; } Ade Re: Accepted // Problem 1259. How to Become Star? 20 Oct 2012 19:01 can't believe somebody used system("pause"); Spatarel Dan Constantin Re: Accepted // Problem 1259. How to Become Star? 12 Feb 2014 02:34 Should'nt this code be deleted by the admins? Edited by author 12.02.2014 02:34 b108 WA#7 // Problem 1345. HTML 11 Feb 2014 00:28 If you have WA#7 check that your program works correct with strings with symbols "{" and "//" Samoylov Test #6 What's wrong? // Problem 1910. Titan Ruins: Hidden Entrance 10 Feb 2014 12:30 #include <iostream> using namespace std; int main() { int k,a[1001],i(0),s(0),maxs(0),j(0); cin >> k; while(i<k) { cin >> a[i]; i++; } for (i=0; i<k; i++){ if (a[i]==a[i+1] && a[i]==a[i+2]) { s = a[i]*3; j = i+2; } if (s > maxs) { maxs = s; s = 0; } } cout<<maxs<<"\n"<<j<<endl; } Edited by author 10.02.2014 22:44 [USU]And_IV[КБ-101] Crash(acsses violation) on 3test [1] // Problem 1220. Stacks 4 Dec 2008 14:54 why??? #include <iostream> //#include <stdlib.h> //#include <stdio.h> #include <string.h> using namespace std; int i,o,tp,nm; struct Tpart { int val [24]; int k; Tpart *lst; }; char com[100]; Tpart stk[1024]; int Pop(Tpart *p) { if(p->k>0) return p->val[--(p->k)]; else { Tpart *e=p; p=p->lst; delete e; return p->val[--(p->k)]; }}; void Push(Tpart *p, int val) { if((p->k)<24) (p->val)[(p->k)++]=val; else { Tpart *uk= new Tpart; uk->lst=p; p=uk; p->k=0; (p->val)[(p->k)++]=val; } return; } int main() { int n; cin>>n; for(int j=0;j<n;j++) { cin>>com; if (strcmp(com,"PUSH")==0) { cin>>nm>>tp; Push(&stk[nm-1],tp); } if (strcmp(com,"POP")==0) { cin>>nm; cout<<Pop(&stk[nm-1])<<endl;} } return 0; } †‡ S † i † r † i † u † S ‡† Re: Crash(acsses violation) on 3test // Problem 1220. Stacks 9 Feb 2014 22:41 I've this problem too(( intueor WA #15... I just don't understand what is wrong with my program.... Help me pls! // Problem 1495. One-two, One-two 2 9 Feb 2014 18:06 Just give me some hint pls: intueor19@gmail.com I really don't understand what is wrong... It passes all tests on that forum but still has WA15 #include <iostream> #include <vector> using namespace std; vector < int > pm (30, 0); vector < vector < char > > d (31, vector < char > (1000000, 0)); int n; void printAnswer (int, int); int main () { cin >> n; pm[0] = 1 % n; for (int i = 1; i < 30; ++i) pm[i] = (pm[i - 1] * (10 % n)) % n; d[0][0] = 1; char found = 0; for (int i = 1; i <= 30; ++i) { int m1 = pm[i - 1]; int m2 = ((2 % n) * pm[i - 1]) % n; if (d[i - 1][(n - m1) % n] != 0) { printAnswer (1, i); found = 1; break; } if (d[i - 1][(n - m2) % n] != 0) { printAnswer (2, i); found = 1; break; } for (int j = 0; j < n; ++j) { if (d[i - 1][j] == 0) continue; d[i][(j + m2) % n] = 2; d[i][(j + m1) % n] = 1; } } if (!found) cout << "Impossible"; return 0; } void printAnswer (int digit, int lvl) { int k = 0; int x, j; while (lvl != 0) { cout << (int)digit; j = ((digit % n) * pm[lvl - 1]) % n; x = (k >= j) ? (k - j) : (n - j + k); digit = d[lvl - 1][x]; k = x; --lvl; } return; } I got AC with other code but I still don't understand what's wrong with this one. Help me PLS!!! Edited by author 09.02.2014 19:37 Mamuka Sakhelashvili [Freeuni] WA 6 // Problem 1930. Ivan's Car 9 Feb 2014 04:05 Could you tell me some useful test, if you had the same problem?! Thanks ^_^ frufru WA test 35 // Problem 1299. Psylonians 9 Feb 2014 00:39 can you tell me test 35? i have WA BORODA hint for WA 10 // Problem 1201. Which Day Is It? 8 Feb 2014 19:24 The answer for "30 1 2012": mon........2....9...16...23..[30] tue........3...10...17...24...31 wed........4...11...18...25..... thu........5...12...19...26..... fri........6...13...20...27..... sat........7...14...21...28..... sun...1....8...15...22...29..... between first and second column there are exactly 4(!) '.'; Baz Tests are inconsistent // Problem 1151. Radiobeacons 8 Feb 2014 17:19 Considering my submissions, I concluded that in the 15-th test there is a radiobeacon for which its coordinates can't be integers between 1 and 200. If for such radiobeacons output "UNKNOWN", the solution gets AC. This does not fit with the statement. intueor WA#1 Who can find an error in my prog? =) // Problem 1513. Lemon Tale 7 Feb 2014 18:47 I didn't use any long arithmethic but i think it should passes the first test. But judge says WA !!! Help please if you can #include <iostream> using namespace std; long long d[10001][2]; int main () { int n, k; cin >> n >> k; d[0][0] = 1; d[0][1] = 0; int i, j; for (i = 1; i <= n; ++i) { d[i][1] = 0; for (j = 1; j <= k; ++j) { if (n - j < 0) continue; d[i][1] += d[i - j][0]; } d[i][0] = d[i - 1][0] + d[i - 1][1]; } cout << d[n][0] + d[n][1]; return 0; } Noob Proof [3] // Problem 1206. Sum of Digits of the Sum of Numbers 12 May 2012 03:16 I've solved it using bruteforce for small K and then guessing the formula. But I still don't know the proof. Can anybody write it? balandini Re: Proof [2] // Problem 1206. Sum of Digits of the Sum of Numbers 7 Jun 2012 18:20 S(A + B) = S(A) + S(B) is equal to that that for every pair of corresponding digits of A and B their sum is lower then 10 (1). For example: 12 and 13 :1+1<10;2+3<10 it means S(A + B) = S(A) + S(B) 18 and 19: 8+9>10 it means S(A + B) = S(A) + S(B) is wrong here. Then for every pair of digits from A and B you just count how many varints of pair suits (1) and multiply these quantities for all pairs. Dmitri Belous Re: Proof [1] // Problem 1206. Sum of Digits of the Sum of Numbers 2 Sep 2012 15:22 thanks Kuros Re: Proof // Problem 1206. Sum of Digits of the Sum of Numbers 7 Feb 2014 01:51 Another way to go at it is to think of the number (A+B) as a bunch of stacked blocks, each stack representing a digit. Here is 43 for example: _ |_| _ |_||_| |_||_| |_||_| Now, to find all the A's and B's that can form S(A+B) = S(43), for example 12+31 or 22+21, etc, we can represent this as chopping each stack into two parts, for example in the case of 12+31: _ |_| _ _ |_| |_||_| |_| _ |_||_| Now, if we take the general case of having two digits, if the first digit is 1, we can't split the first digit in two since the first digit of A or B can't be 0. However, if the first digit is 2, we can split it in one way (in the middle), and then we can split the second digit depending on what digit it is. If it is 2, we can split it in 3 different ways ( (0,2),(1,1),(2,0) ). If it is 3, we can split it in 4 different ways, etc. So, if the first digit of the two-digit number is 2, we can split the whole number in 1*(1+2+3+4+5+6+7+8+9+10)=1+(10*11/2) different ways. If the first digit is 3, we can split the whole number in 2*(1+2+3+4+5+6+7+8+9+10)=2*(10*11/2) different ways, etc. If we sum everything we get (8*9)/2*(10*11)/2 ways to split a two digit number. For an n digit number continuing the same way we get (8*9)/2*((10*11)/2)^(n-1).
|