Общий форум#include <iostream> using namespace std; int sumDigit(int n) { int sum = 0; while (n) { sum += n % 10; n /= 10; } return sum; } int main() { int n; cin >> n; if (n % 2 == 1) { cout << 0; } else { // We need to choose at most 4 digits, so the largest digit sum is 9*4 int count[9*4 + 1] = {0}; int halfN = n / 2; int maxNum = 9; for (int i = 1; i < halfN; ++i) { maxNum *= 10; maxNum += 9; } // Count the ways to create a particular sum for (int i = 0; i <= maxNum; ++i) ++count[sumDigit(i)]; // Now, for each number i whose digit sum are s, there are // count[s] numbers (including i itself) have the sum s. // So we have count[s] ways to choose the second half. int result = 0; for (int i = 0; i <= maxNum; ++i) result += count[sumDigit(i)]; cout << result; } return 0; } thanks a lot.It was really helpful Reading the entire input char by char can be done quickly this way: while ((input = (char)getchar())) { if (input == EOF) { break; } The canonical way is: while ((input = std::getc()) != EOF) { ... } /* ALGORITHM: In any substring that is encountered the most, at least one letter of that substring should be encountered the same time as the substring. So, we just need to find the most encountered symbol in the string. */ using System; using System.Linq; class Program { static void Main() { Console.WriteLine((from u in Console.ReadLine().ToArray() group u by u into gg orderby gg.Count() descending select gg.Key).ToList()[0]); } } Power of Python :) from collections import Counter print(Counter(input().strip()).most_common(1)[0][0]) Power of C/C++ int main() { //shitcode_fiveloops } // AC :) #include <The Power of me!> int main() { ThePowerOfMe.makeItAC(); } ...AC!:) Edited by author 25.04.2014 16:46 I think that one line could be enough. Console.WriteLine(input.GroupBy(c => c).OrderByDescending(g => g.Count()).First().Key); // the power of C++ :) #include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; int main() { string s; cin >> s;
vector<int> v(30, 0); for (int i=0; i<s.size(); ++i) { ++v[s[i]-'a']; } auto c = distance(v.begin(), max_element(v.begin(), v.end())); cout << (char)('a'+c); return 0; } Slightly shorter C++ version of Raphael: #include <algorithm> #include <cstdio> int main() { size_t v[26]{}; char c; while ((c = std::getc(stdin)) != EOF) ++v[c - 'a']; std::putc(static_cast<char>('a' + std::distance(v, std::max_element(v, v + 26))), stdin); return 0; } Edited by author 01.06.2024 21:37 The authors should've mentioned these in the question. Like if q is 0 then you should print 10 but if it is any number between 1 to 9 then you should print that number only, i.e. 2 for 2, 4 for 4 not 14 for 4. Thanks, that saved me a lot of time. I was printing 0 for 0. Which makes sense in my opinion. thanks to you .It was really helpful 13 0 0 0 0 0 0 0 0 0 0 0 0 0 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ans: 31.513956103964 WA on test 7. I've used uint64_t in array and sum, and int64_t in result. Corner case of sum = 0 is taken care of. Regards, So Sui Ming even signed long long should work fine. try to find error in your solution what is wrong with my program? I used Python code below: n = input() list = n.split() n = int(list[0]) k = len(list[1]) if (n < k): p = k else: p = n
i=2 num = n - k if (n>=1 and n<=10) and (k>=1 and k<=20) and (num > 0): if((n%k) == 0): while(num>k): p = p*num num = n-i*k i=i+1 p = p*k else: while(num>(n%k)): p = p*num num = n-i*k i=i+1 p = p*(n%k) print(p) Edited by author 17.06.2022 20:39 Don't confuse it, (n mod k) or k are not the final factors!! skip these lines p = p*k and p = p*(n%k) binsearch + dijkstra works but with naive dijkstra my solution is the following: start with least common multiple = 1 make char array of 1000 000 to track forbidden divisors let div be the divisor and ans the answer if ans == 1 make new lcm of the previous lcm and current divisor. if it is over 10^12 - fail. find all the divisors of div, check that they are not forbidden in the forbidden array if ans == 0 - check if lcm is divisible by the divisor and fail if it is.
complexitiy O(n * sqrt(1000000)) (sqrt from the "find all divisors) my solution gets 0.5 sec (using cin,cout with tie(null)) what is the solution that gets less than 0.1 sec? Is there any hint? no need to find all divisors. u can just use lcm and mod operations. i can send you easy solution if u r still interested It would be interesting to solve such a problem on an arbitrary graph (not a tree) or to say that there is no solution for such a graph. it is well known problem. but its hard to implement. You should find a clique of size 5 or complete bipartite subgraph with size (3, 3). There is no solution if and only if there exist such subgraph or topologicaly equal to that(other vertex can adjust 2 dif. vertexes of such subgraph). I took lectures about that a long time ago. Can't find source now. Edited by author 26.05.2024 21:22 Edited by author 26.05.2024 06:13 These are some of the things I had to overcome: 1)Testing on something like: 6 5 5 1 1 2 2 and 6 5 5 1 1 1 2 2)There cant be 2 out of place pairs in the ascending/descending order 3)Swapping elements across all pairs Hope this helps someone. #include <iostream> #include <iomanip> #include <cmath> using namespace std; int main() { int x1, y1, x2, y2, x0, y0, l; cin >> x1 >> y1 >> x2 >> y2; cin >> x0 >> y0 >> l; cout << fixed << setprecision(2); // <|ENG: Set 2 symbols after dot |> <|RUS: stavim 2 simvola dlia tochki |> //<|ENG: get all sides |> //<|RUS: poluchaem vse storonui |> double firstEdge = sqrt(pow(x1 - x0, 2) + pow(y1 - y0, 2)); double secondEdge = sqrt(pow(x2 - x0, 2) + pow(y2 - y0, 2)); double field = sqrt(pow(x2 - x1, 2) + pow(y2 - y1, 2)); double ans2 = max(firstEdge, secondEdge) - l; // <|ENG: Second answer - max length |> <|RUS: Vtoroi otvet = prosto maximum do krainih tochek |> double ans1; //<|ENG: get the squares of the sides|> //<|RUS: Vosvodim v kvadrat storonui |> double a = firstEdge * firstEdge; double b = secondEdge * secondEdge; double c = field * field; //<|ENG: checking if there are obtuse angles on the side that is the pineapple field |> //<|RUS: Proverka est li typie ygli vosle toi storoni kotoraiy iavliaetsia polem c ananasami |> if (a+c < b || b+c < a) { ans1 = min(firstEdge, secondEdge) - l; } else { //<|ENG: get half the perimeter of triangle|> //<|RUS: poluchaem poly perimetr treygolnika |> double p = (firstEdge + secondEdge + field) / 2; //<|ENG: get square of triangle|> //<|RUS: poluchaem ploshad treygolnika |> double S = sqrt(p * (p - firstEdge) * (p - secondEdge) * (p - field)); //<|ENG: If the area is zero and the field with pineapples does not exist (test: 2 2 2 2 3 3 1)|> //<|RUS: Esli ploshad ravna 0 i polia c ananasami kak bu net (test: 2 2 2 2 3 3 1)|> if (S == 0 && field == 0) { ans1 = min(firstEdge, secondEdge) - l; } //<|ENG: If the area is zero and more than one side is not zero (test: -5 0 5 0 1 0 1)|> //<|RUS: Esli ploshad ravna 0 i ni odna storona ne ravna 0 (test: -5 0 5 0 1 0 1)|> else if (S == 0 && firstEdge != 0 && secondEdge != 0 && field != 0) { ans1 = 0; } else { //<|ENG: Default. We just look for the height using the formula|> //<|RUS: Obichni slychai. Prosto po formule S = a*h/2 (test: -5 0 5 0 1 0 1)|> double d = 2 * S / field; ans1 = d - l; } } //<|ENG: If, after subtracting the rope, the length becomes negative, then do 0|> //<|RUS: Esli sle vichetania verevki otvet stal menihe nylia to delayem 0|> ans1 = ans1 < 0 ? 0 : ans1; ans2 = ans2 < 0 ? 0 : ans2; //<|ENG: Next just cout "round(ans1 * 100) / 100" and "round(ans2 * 100) / 100"|> //<|RUS: Teper prosto vivedi "round(ans1 * 100) / 100" i "round(ans2 * 100) / 100"|> //!!!!!!!!!!!!!!!!!!! //cout << round(ans1 * 100) / 100 << endl; //cout << round(ans2 * 100) / 100; return 0; //<|ENG: Thanks a lot for your time here!|> //<|RUS: Spasibo chto pochitali i uia vam pomog (navernoe)|> // :) } #include <iostream> #include <cmath> using namespace std; int main(){ double x1 = 0, y1 = 0, x2 = 0, y2 = 0; double px = 0, py = 0; double length; double A = 0; double B = -1; double C = 0; double slope = 0; cin>>x1>>y1>>x2>>y2>>px>>py>>length; // get the equation of pineapple line in the form Ax + By + c = 0
if((x2 - x1) != 0){ slope = (y2 - y1) / (x2 - x1); A = slope; C = y2 - slope * x2; } if((x2 - x1) == 0){ A = 1; B = 0; C = -x1; } // now since we have Ax + By + C = 0 // we can find the shortest distance between the point and the line double short_dist = fabs(A*px + B*py + C) / sqrt(pow(A, 2) + pow(B, 2)); double dist_x1y1 = fabs(sqrt(pow(px-x1, 2) + pow(py-y1, 2))); double dist_x2y2 = fabs(sqrt(pow(px-x2, 2) + pow(py-y2, 2))); // once we have calculated the shorted distance, we need to // find out the point lying on that pineapple line which is // closest to the peg double slope_new = 0; double B_new = 0; double C_new = 0; double A_new = 0; bool status = true; if((x2 - x1) == 0){ slope_new = 0; // the other line has slope of inifinity, so this is parallel B_new = 1; A_new = 0; C_new = -py; status = false; } if((y2 - y1) == 0){ B_new = 0; A_new = 1; C_new = -px; status = false; } if(status){ slope_new = -1.0/slope; C_new = py - slope_new*px; A_new = slope_new; B_new = -1; } // calculating the point of intersection double inter_X = (-C*B_new - B*(-C_new)) / (A*B_new - B*A_new); double inter_Y = (A*(-C_new) - (-C*A_new))/(A*B_new - B*A_new); // now check whether this point lies between the given points or not ? // to do that we need to check whether both of the above calculated // coordinates lie between the range of x1, y1 and x2, y2 double min_x_coor = min(x1, x2); double min_y_coor = min(y1, y2); double max_x_coor = max(x1, x2); double max_y_coor = max(y1, y2); if(inter_X >= min_x_coor && inter_X <= max_x_coor && inter_Y >= min_y_coor && inter_Y <= max_y_coor){ // this means, the point lies on the line double one_pineapple_distance = short_dist - length; if(one_pineapple_distance <= 0){ cout<<"0.00"<<endl; } else printf("%.2f\n", one_pineapple_distance); // now to eat all the pineapples double larger_distance = max(dist_x1y1, dist_x2y2); if(larger_distance - length <= 0){ cout<<"0.00"<<endl; } else printf("%.2f\n", larger_distance - length); } // or else the perpendicuar point does not lies on the line else{ // first shorter one double shorter_distance = min(dist_x1y1, dist_x2y2); double larger_distance = max(dist_x1y1, dist_x2y2); double pineapple_1 = shorter_distance - length; if(pineapple_1 <= 0){ cout<<"0.00"<<endl; } else printf("%.2f\n", pineapple_1); double pineapple_all = larger_distance - length; if(pineapple_all <= 0){ cout<<"0.00"<<endl; } else printf("%.2f\n", pineapple_all); } return 0; } вай, как много кода) с помощью численных методов решение в 30 строк AC) С помощью точной формулы решение в 25 строк. I used DSU algorithm and AC 0.046. test: 10 4 5 3 6 9 10 8 7 2 1 answer: Not a proof. good test tho I used stack & queue and got AC I used DSU algorithm and AC 0.046. test: 10 4 5 3 6 9 10 8 7 2 1 answer: Not a proof. Thanks for the test case... Helped a lot to find bug in my algo. I am wondering how to use DSU here... Would you please mail me your idea? ealham86@gmail.com Thanks again. The hint was great. Stack + queue can get you AC in 0.031 Admins, please increase Memory Limit in this task. It is wrong that solutions with O(Q*log2(10^9)) memory - segment tree on hash table - has not got any chance to pass Memory Limit without additional input queries coordinates compression (because 100000 * 30 * (3*double + char) is obviously > 64 Mb). This data structure is quite complex even without input queries coordinates compression, why not to AC such solutions? Nowadays commonly used ML is 256 Mb, not 64. Edited by author 19.05.2024 12:37 Edited by author 19.05.2024 12:39 There is only one eligible lowered numbered ball at any round. Keeping track of this should result in O(n) solution |
|