Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
quite a tricky ques | luffy | 1930. Машина инженера Ивана | 11 фев 2020 23:40 | 1 |
Easy concept, just to think for a while. AC in one go! |
easy problem | bhaskar bhardwaj | 1930. Машина инженера Ивана | 10 фев 2020 23:55 | 1 |
just use bfs as a modified version of dijkstra and you will be done |
Is it true or not | ura | 1091. Тмутараканские экзамены | 10 фев 2020 12:13 | 1 |
K= 11 S= 125 OTVET= 511435086865 K= 11 S= 126 OTVET= 620074954696 K= 11 S= 127 OTVET= 620074954696 K= 11 S= 128 OTVET= 747880479697 K= 11 S= 129 OTVET= 749351922670 K= 11 S= 130 OTVET= 900828406180 K= 11 S= 131 OTVET= 900828406180 K= 11 S= 132 OTVET= 1081759187586 K= 11 S= 133 OTVET= 1081759231344 K= 11 S= 134 OTVET= 1292739780552 K= 11 S= 135 OTVET= 1295226349065 |
Please tell me how to solve it.... | Asyamov Igor | 1635. Мнемоника и палиндромы | 10 фев 2020 00:19 | 3 |
I have got WA 23, but I know that my algo will have TLE... What is the right algo??? Accepted!!!! BFS - very good thing!!!! #include <iostream> #include <algorithm> #include <string> unsigned counter = 0; void printPalindroms(unsigned short *splitIndex, unsigned short i, const std::string& str){ if(splitIndex[i] == 0){ std::cout<<str.substr(0, i+1)<<" "; }else{ printPalindroms(splitIndex, splitIndex[i]-1, str); std::cout<<str.substr(splitIndex[i], i + 1 - splitIndex[i])<<" "; } } int main() { std::string strr; std::cin>>strr; const char* str = strr.data(); unsigned length = strr.size(); unsigned arrSize = (length*length + length)/2; bool *pArrData = new bool[arrSize]; bool **pArr = new bool*[length]; unsigned short *splitWeights = new unsigned short [length]; unsigned short *splitIndex = new unsigned short[length]; std::fill(pArrData, pArrData + arrSize, false); std::fill(splitWeights, splitWeights + length, length +2); std::fill(splitIndex, splitIndex + length, 0);
unsigned offset = 0; for(unsigned i = 0; i<length; ++i){ pArr[i] = pArrData + offset; offset += length - i; } // init the first row std::fill(pArr[0], pArr[0] + length, true); //init the second row for(unsigned i = 0; i<length - 1; ++i){ if(str[i] == str[i+1]){ pArr[1][i] = true; } } for(unsigned i = 2; i < length; ++i){ for(unsigned j = 0; j< length - i; ++j){ if(pArr[i-2][j+1] && str[j] == str[j+i]){ pArr[i][j] = true; } } } for(unsigned i = 0; i < length; ++i){ if(pArr[i][0] == true){ splitWeights[i] = 0; splitIndex[i] = 0; }else{ for(unsigned j = 1; j <= i; ++j){ if(pArr[i-j][j]){ unsigned short temp = splitWeights[j-1] + 1; if(temp < splitWeights[i]){ splitWeights[i] = temp; splitIndex[i] = j; } } } } } std::cout<<splitWeights[length -1] + 1<<std::endl; printPalindroms(splitIndex, length - 1, strr); delete[] splitIndex; delete[] splitWeights; delete[] pArr; delete[] pArrData;
return 0; } |
If you have WA 3 | Toshpulatov (MSU Tashkent) | 1294. Марсианские спутники | 9 фев 2020 20:11 | 1 |
use cout.precision(0) and cout << sqrt(ans) * 1000.0 << endl; Edited by author 09.02.2020 20:13 |
How to solve this problem in o(n^2)? | lnxdx | 1017. Лестницы | 9 фев 2020 17:08 | 2 |
How to solve this problem in o(n^2)? Let's start from the beginning: Let R(n) will be the function that returns count of unique staircases. Now let's introduce function G(n,j) that returns count of unique staircases each first step of which has more than j bricks. Then R(n) = G(n,0) - 1 . We have to subtract one because it is the case when all bricks are spent on the first step. G(n,j) = (n>j ? 1 : 0) + (G(n-j-1, j+1) + G(n-j-2, j+2) + ... +G(0,n)) G(n,j-1) - G(n,j) = (n == j ? 1 : 0) + G(n-j, j) => G(n,j) = G(n,j-1) - G(n-j,j) - (n == j ? 1 : 0) We know that in the case when n<=j G(n,j) = 0, so we can solve upper equation only for cases when j<n, in such cases upper formula will transform to G(n,j) = G(n,j-1) - G(n-j,j). But we still have to solve the cases when j == 0 and i > j as G(n, 0) = 1 + G(n-1, 1) + G(n-2, 2) + ... + G(0,n) //Alloc and init matrix g with zeroes //Calculat g matrix for(i = 2; i<=N; ++i){ g[i][0] = 1; for(j=1; j<i;++j){ g[i][0] += g[i-j, j]; } for(j=1; j<i;++j){ g[i][j] = g[i][j-1] - g[i-j,j]; } } cout<<g[N][0]-1; Edited by author 09.02.2020 17:14 |
This may help if WA 7 | MishaRash | 1430. Преступление и наказание | 9 фев 2020 14:56 | 3 |
I have WA 7 and I found the problem on test '20 30 13456'. It's a nice case to fix program but still it doesn't fix WA7. Edited by author 09.02.2020 15:46 |
What is wrong in my solution (WA 16) | Paul | 1215. Точность попадания снаряда | 9 фев 2020 03:12 | 3 |
Edited by author 26.03.2009 23:03 Edited by author 26.03.2009 23:03 |
If you are having trouble | urmat | 1303. Минимальное покрытие | 9 фев 2020 01:50 | 1 |
There is full solution!!! Try thinking yourself or using hints before watching it and use visual c++ 2017 . . . . . . . . . . . . . . . . . . . //#include <bits/stdc++.h> #include <iostream> #include <vector> #include <algorithm> #define int long long #define pb push_back using namespace std; const int N = 50000; pair<int, int> dp[N], right_end[N]; vector<pair<int, int> > v; vector<int> ans; unsigned main() { for(int i = 0; i < N; i++) { right_end[i].first = -50001; right_end[i].second = -50001; } int m; cin >> m; int l, r; int k = 0; while(true) { cin >> l >> r; if(l > m || r < 0) continue; if(l == 0 && r == 0) break;
v.pb({l, r});
if(r > right_end[l].first) { right_end[l].first = r; right_end[l].second = k; } k++; }
int i = 0; for(auto it: v) { if(it.first <= 0 && it.second > 0) { if(it.second > dp[0].first) { dp[0].first = it.second; dp[0].second = i; } } i++; } for(int i = 1; i <= m; i++) { if(dp[i - 1].first >= right_end[i].first) { dp[i].first = dp[i - 1].first; dp[i].second = dp[i - 1].second; } else { dp[i].first = right_end[i].first; dp[i].second = right_end[i].second; } } for(int i = 0; i <= m; i++) { if(dp[i].first < i) { cout << "No solution" << endl; return 0; } } int pos = 0; while(pos < m) { ans.pb(dp[pos].second); if(dp[pos].first == pos) { cout << "No solution" << endl; return 0; } pos = dp[pos].first; } cout << ans.size() << endl; for(auto it: ans) { cout << v[(int)it].first << " " << v[(int)it].second << endl; } } Edited by author 09.02.2020 01:50 |
Whats wrong with this code? Please help | Naman Sharma | 1001. Обратный корень | 7 фев 2020 13:12 | 2 |
#include<iostream> using namespace std; float sqrt(long long2 n,int p) { int start = 0; int end = n; float ans; int mid; while(start <= end) { mid = (start+end)/2; if(mid*mid < n) start = mid + 1; else if(mid*mid > n) end = mid - 1; else { ans = mid; break; } } float increment = 0.1; for(int i = 0; i < p;i++) { while(ans * ans <= n) { ans += increment; } ans -= increment; increment /= 10; } return ans; } int main() { long long int n; while(cin >> n) { cout << sqrt(n,4) << endl; } } 1) Please read task, especially "from the last one till the first" carefully. Look at the example. 2) Your sqrt function lies. https://ideone.com/wcJVz0 |
What is the test #46? | ura | 2070. Интересные числа | 6 фев 2020 19:45 | 2 |
L=p^(q-1),p and q prima numbers. |
Test #9 | bsu.mmf.team | 1812. Остров Невезения 2 | 5 фев 2020 22:58 | 7 |
Test #9 bsu.mmf.team 4 фев 2011 02:56 Please, help with this test. I am always getting WA on it. I did 2 assumptions: 1. If after any iteration the radius becomes irrational - then the answer will be irrational too. 2. The numerator and denominator of resulting fraction both don't exceed 2^64. Are these assumptions wrong? If so, please, give me some useful tests. The one interesting test I found is: 1 1 30 34785346 3131185849/1170753394542713625 But it doesn't help me much... Edited by author 04.02.2011 02:56 Re: Test #9 Alipov Vyacheslav [Tomsk PU] 4 фев 2011 22:50 The 1st assumption is right. The 2nd one seems to be wrong. I can't say exactly if the result always fits in int64, but temporary (or itermediate) calculations exceed 2^64 for sure. Answer to your test is wrong. In this test the denominators of intermediate fractions (before reduction) exceed 2^64. My AC program answer: 1/6265197409 Oh, thanks, now I understood why it gets WA. Now my program gives correct answer to this test (I optimized it a little bit), but I found several tests with the same problem. It is interesting for me to solve it without BigInteger, I guess, there exists such solution for this problem. After a lot of tries I gave up :( AC now, but with big numbers. Edited by author 07.02.2011 23:02 Re: Test #9 Toshpulatov (MSU Tashkent) 5 фев 2020 22:58 Что бы не было переполнения вы могли сделать следующие : Представить r1 и r2 таким образом r1 = A / B ^ 2 r2 = A / C ^ 2 Где А = r1 * r2 / gcd(r1, r2); Отсюда найдете B и C. Теперь в чем прелесть такого представления: Вы наверное вывели формулу r3 = (r1 * r2 ) / (r1 + r2 + 2 * sqrt(r1, r2) ); Так вот если будете подставлять то получите r3 = A / ( B + C) ^ 2 т.е числитель не меняется а вот знаменатель будет меняться но не быстро ! I got Wa22(ac 1-21) under positions: r1*r2!=k*k-"irrational";(BUT IF i>min and i<MAX ONLY!) else 1/sqrt(r)=a/sqrt(r1)+b/sqrt(r2); a,b- recursion f(n,2i)=f(n-1,i),f(n,2i+1)=f(n-1,i)+f(n-1,i+1) All- __int64 AC now: a,b<=30- by induction. int- is enought, nor __int64, nor BigInteger Edited by author 27.02.2011 12:18 My mistake was: __int64 needed. a+b<=2^30 |
WA 9 | FaddeyKr | 2149. Принцип Дирихле | 4 фев 2020 03:10 | 2 |
WA 9 FaddeyKr 23 ноя 2019 18:28 I have WA in the 9th test, please tell me this test. We have 4 case of perfect position of birds. I found the amount of flips for all cases. I used min_element() from algorithm.h to find the result, but it gave me WA 9. Then i replaced min_element() and found minimal by myself and my code finally accepted. Hope it will help you, good luck! |
Test cases 6 and 12 | Gilles Deleuze | 2088. Вечер ностальгии | 3 фев 2020 14:52 | 1 |
Test case #6: 9 40 10 10 10 10 10 10 10 10 10 10 0 5 6 1 0 0 0 0 0 0 12 20 Answer: 158882255 Test case #12: 10 20 52 4 2 3 6 7 6 3 6 5 6 6 0 0 0 0 1 0 0 0 0 1 10 50 Answer: 978217740 |
PyCharm execution is much faster than here | roman velichkin | 1698. Квадратная страна 5 | 1 фев 2020 20:13 | 1 |
PyCharm calculates n=2000 in 0.55 sec while here I got exceed time limit with 2.020 sec. I don't get it. |
WA test 3. But it answers correctly on my machine... | jedianmb | 1044. Счастливые билеты. Easy! | 31 янв 2020 17:11 | 2 |
Can't find the error, because it gives the same answers as those stupid precalc solutions: #include <bits/stdc++.h> using namespace std; using ll = long long; int soma[40] = {0}; int main() { ios::sync_with_stdio(0); cin.tie(0); int n, i, lim; ll ans = 0; cin >> n; lim = pow(10, n/2); for(i=0; i<lim; ++i){ soma[i%10 + (i/10)%10 + (i/100)%10 + (i/1000)%10]++; } for(i=0; i<=n*9; ++i){ ans += soma[i]*soma[i]; } cout << ans << '\n'; return 0; } for(i=0; i<=n*9; ++i){ ans += soma[i]*soma[i]; } i is out of soma range. |
Help!WA#11 | miao22 | 1671. Паутина Ананси | 30 янв 2020 18:15 | 3 |
#include<bits/stdc++.h> using namespace std; int n,m,q,a[100003],b[100003],c[100003]; vector<pair<int,int> >v; vector<int>g[100003]; bool vis[100003]; int qq[100003]; map<int,int>mp; void dfs(int x,int cc){ vis[x]=1; for(int i=0;i<g[x].size();i++) if(!vis[g[x][i]]) dfs(g[x][i],cc); qq[x]=cc; } int main(){ cin>>n>>m; for(int i=0;i<m;i++) cin>>a[i]>>b[i], a[i]--, b[i]--; cin>>q; for(int i=0;i<q;i++)cin>>c[i],c[i]--,v.push_back(make_pair(a[c[i]],b[c[i]])),a[c[i]]=b[c[i]]=-1; reverse(c,c+n);reverse(v.begin(),v.end()); for(int i=0;i<m;i++) if(a[i]!=-1) g[a[i]].push_back(b[i]), g[b[i]].push_back(a[i]); int cnt=0; for(int i=0;i<n;i++) if(!vis[i]) mp[cnt]=cnt, dfs(i,cnt++); vector<int>ans; for(int i=0;i<q;i++){ ans.push_back(cnt); if(mp[qq[v[i].first]]!=mp[qq[v[i].second]]) mp[qq[v[i].first]]=mp[qq[v[i].second]], qq[v[i].first]=qq[v[i].second], cnt--; } reverse(ans.begin(),ans.end()); for(int i=0;i<ans.size();i++) cout<<ans[i]<<' '; } 5 8 2 3 1 2 2 5 1 4 1 5 3 4 3 4 4 4 8 7 6 8 2 3 4 5 1 |
JavaEntryPointWrapper.java:10: error: cannot access Oppa | Kairat | 1000. A+B Problem | 28 янв 2020 18:35 | 3 |
JavaEntryPointWrapper.java:10: error: cannot access Oppa Oppa.main(args); ^ bad source file: .\Oppa.java file does not contain class Oppa Please remove or make sure it appears in the correct subdirectory of the sourcepath. 1 error Выходит такая ошибка, почему? У меня аналогичная ошибка. В том, что файл содержит один публичный класс, совпадающий с именем файла уверен на 100%. Причем проверил на файлах, которые отправлял ранее и удачно решенные, тоже самое. Даже решение из руководства не проходит... |
WA 22!!! HELP!!! i have already 20 attempt | Lifanov | 1299. Псилонцы | 28 янв 2020 01:41 | 3 |
Please give this test! lifanov@mail.ru Oh, I has mixed too, but now it works, thank you :) |
Delete account | lareon | | 27 янв 2020 11:24 | 1 |
Please, delete my account. I don't need it anymore. |