Common Boardjust the rule of multiplication in combinatorics... just one problem - the sequence of colors, but many 'if's will save the World! Use set data structure Add each color from input to a set Check the set for red, blue and yellow Formula: ceil(log2(min(n, k))) + ceil((double)(n - (1 << (int)(ceil(log2(min(n, k))))))/ k) Edited by author 29.07.2018 13:01 Edited by author 09.09.2018 17:50 This test helped me to get ac after wa16: 5 1 2 1 3 2 5 3 4 Edited by author 28.07.2018 15:42 sol.push_back(ceil((double)n/2)) (sol is vector in c++) If you solved it using such code, please explain why it works. Basically, it's a greedy algorithm: the maximum length you can fold is CURRENT_LENGTH / 2. So, you just fold it in half until it's of length 1. Проверяйте пограничные ситуации, когда номер билета на входе 000000 или 999999 номера 000000 и 999999 проверять не надо,потому что сумма первых трёх цифр не отличается на единицу от суммы последних трёх цифр(по условию). double check lazy calculations Edited by author 25.10.2012 03:55 Had a problem here as well. In my code I do the following void apply_push(int64 postponed) { sum += (r - l) * postponed; lazy += postponed; } The following function is called when node range is contained within update range. And at first I had the following code that caused WA3 which caused same update to be performed several times. void apply_push(int64 postponed) { lazy += postponed; sum += (r - l) * lazy; } Edited by author 26.07.2018 18:46 deleted Edited by author 26.10.2021 22:50 Сделай так, запиши все элементы в массив, а затем выводи их с условием: if (massiv[i] == 3) a++(ну или a = a+1), я просто не знаю, на каком языке ты работал. Далее, если а больше 0, значит нет стипендии, ибо есть тройка. Потом также с 5 и 4. Если больше 4 так то так то, если 5 аналогично, а если нет троек и кол - во 4 равно кол - во 5, то так то так то I think my idea completely right What's wrong?????? import java.util.Scanner; public class Main { public static void main(String [] args) { Scanner in = new Scanner(System.in); int n; n = in.nextInt(); String s[][] = new String[n][3]; for(int i=0;i<n;i++){ for(int j=0;j<3;j++){ s[i][j] = in.next(); } } boolean all[][] = new boolean[n][3]; String ss[][] = new String[3*n][3*n]; ss[0][0] = "Isenbaev"; int []index = new int[3*n]; for(int i=0;i<n;i++){ index[i] = 0; } index[0] = 1; int d = 1; for(int i=0;i<n;i++){ for(int j=0;j<3;j++){ if(s[i][j].equalsIgnoreCase("Isenbaev"))all[i][j] = true; } } boolean BOR = false; for(int i=0;i<n;i++){ for(int j=0;j<3;j++){ if(s[i][j].equalsIgnoreCase("Isenbaev"))BOR = true; } } for(int q=0;q<3*n;q++){ boolean bormi = false; for(int i=0;i<n;i++){ boolean bor = false; for(int j=0;j<3;j++){ for(int t=0;t<index[d-1];t++){ if(ss[d-1][t].equalsIgnoreCase(s[i][j])){ bor = true; break; } }if(bor)break; } if(bor){ for(int j=0;j<3;j++){ if(!all[i][j]){ ss[d][index[d]++] = s[i][j]; all[i][j] = true; bormi = true; for(int g=0;g<n;g++){ for(int h=0;h<3;h++){ if(s[g][h].equalsIgnoreCase(s[i][j]))all[g][h] = true; } } } } } } if(bormi)d++; } String []sss = new String[3*n]; int []son = new int[3*n]; for(int i=0;i<3*n;i++){ son[i] = -1; } int koef = 0; for(int i=0;i<d;i++){ if(i==0){ if(BOR){ BOR = false; }else i++; } for(int j=0;j<index[i];j++){ sss[koef] = ss[i][j]; son[koef++] = i; } } for(int i=0;i<n;i++){ for(int j=0;j<3;j++){ if(!all[i][j]){ boolean top = true; for(int p=0;p<koef;p++){ if(sss[p].equalsIgnoreCase(ss[i][j]))top = false; } if(top)sss[koef++] = s[i][j]; } } } n = koef; for(int i=0;i<n-1;i++){ if(sss[i].compareTo(sss[i+1])>0){ String S = sss[i]; sss[i] = sss[i+1]; sss[i+1] = S; int SS = son[i]; son[i] = son[i+1]; son[i+1] = SS; i=-1; } } for(int i=0;i<koef;i++){ if(son[i]!=-1)System.out.println(sss[i] + " " + son[i]); else System.out.println(sss[i] + " undefined" ); } } } Edited by author 25.07.2018 00:30 Edited by author 27.07.2018 23:09 You can make this problem even harder by setting TL to 1s. My current solution runs in 0.96s and there are two optimizations that aren't too hard to come up with that can speed up program significantly (probably sub 0.1s). Firstly, for any complete graph on N vertices the answer is 2^N. Secondly, if you program has TL issues look up 3-regular graphs, they are the worst case of my algorithm. My solution uses no random, there is a nice deterministic solution, i.e. no hashes or shuffling. The following tests should be enough to get rid of all WAs Tests: 3 001 000 100 Answer: 5 6 000001 001001 010000 000001 000000 110100 Answer: 11 6 010010 101010 010100 001011 110100 000100 Answer: 15 4 0011 0000 1001 1010 Answer: 9 4 0110 1011 1101 0110 Answer: 12 4 0001 0000 0000 1000 Answer: 6 10 0001111111 0011111111 0101111111 1110111101 1111011110 1111100111 1111100111 1111111000 1110111001 1111011010 Answer: 195 7 0111101 1011110 1100111 1100111 1111000 0111001 1011010 Answer: 39 Edited by author 24.07.2018 19:09 > I use the segment tree,but I can't find anything wrong... > Could you please give me some tests so that I can find out my program's problem? > Thank you. But now I got WA #5,and I have considered the following tests: 6 + 9 - 3 - 3 + 3 + 3 + 3 And I think the answer is: 9 9 9 9 9 3 But I still WA #5,Could someone can give me some hints or some tests? Edited by author 20.06.2013 10:52 Edited by author 20.06.2013 10:52 6 + 9 - 3 - 3 + 3 + 3 + 3 It`s impossible. Read the task again. Edited by author 15.08.2013 13:41 May be you don't use Long long #include <iostream> using namespace std; int main(){ int n(0),m(0),last(0),temp_f(0),temp_s(0),end_(0); cin >> n >> m; for(int i = 0;i<n;++i){ cin >> temp_f >> temp_s; last += temp_f-2-temp_s; } end_ = last + (m - 2); if(end_ < 0)cout << "Big Bang!"; else cout << end_; return 0; } can I import the numpy library type a = array[1..50000] of integer; b = array[1..50000] of integer;
Var c,d,i,k,g: integer; Var n: a; Var p: b;
begin d:= 0; read(c); for i:= 1 to c do read(n[i]); read(k); for i:= 1 to k do read(p[i]);
for i:=1 to c do for g:=1 to k do begin if (n[i] + p[g] = 10000) then begin writeln('YES'); exit; end else if (i = c) and (g = k) and (n[i] + p[g] <> 10000) then begin writeln('NO'); exit; end; end; end. Also pay attention to the fact that according to the example - segment is (a;b]. I used this approach and got accepted. (O (N*N) btw :) ) Yes. Compressing coordinates and painting segments straightforwardly is enough. think the four edges as four mirror...... :) really good hint) thanx Just compute total chanhe in X and Y and then output hypotenuse. It can be shown pretty intuitively by reflecting triangles, thanks for the hint. I think this is very interesting and hard problem so who can tell me the solution of this problem what is the author's solution I will tell you the solution because this problem should have time limit of around 3-5 seconds. I struggled for almost two days making that algo suffice all tests, and still I had to precompute an empty 12x12 grid, and my AC solution ran for exactly 1 second :)) Go row-by-row with state representing connected components above. These will be something like 11022, 12021, 10220133, etc... Where 0 stands for no exit from above and 1..n stand for connected component number. Actually, every connected component will have exactly two exits downwards, and they will be placed in stack order. Cases like 1212 are impossible because it would mean that paths 1..1 and 2..2 intersect somewhere above. So, this gives us a way to effectively enumerate all of components using at most 2^2 * 3^10 states. Digit 0 means skip. Digit 1 means start new component. Digit 2 means close last open component (remeber their stack order). First digit can't be 2 and last digit can't be 1. This is enough to keep values about previous and next row with cache of next_x[12] - a matching of exits for each column. Also, don't forget to keep array of indices with non-zero values for previous and the next row, this optimizes things a little as you will run only through reachable states. Once you complete current row, paint everything to find resulting components matching with exits from the row just painted. It can be done via BFS, but I couldn't meet TL with that, so I had to optimize it - all paths are chains, so just walk straight. For the last row a path should be a chain loop covering of all upper exits. Internal transfers should keep all components alive, that is - there must be no loops. This also allows to optimize recursive steps for building current row by remembering last connected upper component connected by "rhhhh..." - so just don't allow closing it towards itself, unless it is the last row. Also, do not forget to skip first and last rows full of **********. Is tracing row-by-row quicker than element-by-element??? Can be solved in less than 0.1s using broken profile dynamic programming. I've used Ford-Fulkerson algo and got TL on test 22.(in java) I took in internet one of the best Ford-Falkerson with BFS, based on priority queue and got Ac immidiately(but time is not very good) Could you give me the link to this site please Could you give me the link to this site please TLE? It's really strange. Try to find bug in your code. I accepted this problem using usual Ford-Fulkerson at 0.031 May be the reason of TLE is realization of algo. Or possibly you build graph in some strange manner. Don't use adjacency matrix. Just use list of edges for each vertices. Build bipartite graph. Left part is mages (100 vertices). Right part - is time at which mages would be possibly shave (2000 vertices). Connect i-th mage with ti...ti+si-1 times (1-capacity). Connect source vertex with each mage (2-capacity). Connect each time (0..2000) with target vertex (k-capacity). I'd built the graph as you said. I didn't use adjacency matrix instead I used adjacency list for each vertex. I don't know what to do else. i saw that you had WA on 39. test... i have same problem... if you could say to me what have you done to get AC? there are some anti-bfs tests, try to cheat somehow :) Edited by author 08.04.2011 18:48 My simple BFS implementation of F-F also TLed, but Dinic's modification got AC ford-fulkerson based on simple dfs gives ac in 0.031 let us calc complexity, O(E * F), where E is edge's count, F is flow in huge test E is ~ 2000 * 100 + 2000 + 100 F is ~ 200 so we have ~ 40*10^6 operations multiplied by some constant if use own vectors (not stl-one), based on simple arrays, you'll be ok this problem does not need bfs-flow, 'cause there are 1-weighted edges on the way every time Edited by author 20.08.2011 04:55 Edited by author 12.07.2012 19:25 If you FF algorithm runs slow you can add scaling, either bit-scaling or simple capacity scaling, this alone should be enough to deal with all possible anti-FF networks. |
|