Common BoardCould someone provide tests for me? Thank you Try this test: 4 3 #### #..# #### Answer is 1 :) It is something unique I have had WA20, WA23, TLE32, MLE56 But never WA42 #include <bits/stdc++.h> using namespace std; int main() {int x; vector <string> myvector (2001); fill (myvector.begin(),myvector.begin()+5,"few"); fill (myvector.begin()+6,myvector.begin()+10,"several"); fill (myvector.begin()+11,myvector.begin()+20,"pack"); fill (myvector.begin()+21,myvector.begin()+50,"lots"); fill (myvector.begin()+51,myvector.begin()+100,"horde"); fill (myvector.begin()+101,myvector.begin()+250,"throng"); fill (myvector.begin()+251,myvector.begin()+500,"swarm"); fill (myvector.begin()+501,myvector.begin()+1000,"zounds"); fill (myvector.begin()+1001,myvector.end(),"legion"); cin>>x; cout<<myvector[x]; return 0; } correct solution: #include <bits/stdc++.h> using namespace std; int main() {int x; vector <string> myvector (2001); fill (myvector.begin(),myvector.begin()+5,"few"); fill (myvector.begin()+5,myvector.begin()+10,"several"); fill (myvector.begin()+10,myvector.begin()+20,"pack"); fill (myvector.begin()+20,myvector.begin()+50,"lots"); fill (myvector.begin()+50,myvector.begin()+100,"horde"); fill (myvector.begin()+100,myvector.begin()+250,"throng"); fill (myvector.begin()+250,myvector.begin()+500,"swarm"); fill (myvector.begin()+500,myvector.begin()+1000,"zounds"); fill (myvector.begin()+1000,myvector.end(),"legion"); cin>>x; cout<<myvector[x]<<endl;; return 0; } Edited by author 30.09.2017 07:20 I want to know how to approach this question in what direction to think so that i can solve it on my own. Thank you. Problem is tagged with dynamic programming First, think about each possible configuration of the current state when you add next song Second, think about techniques of DP - compression well let x[n] be the number of sequences that finish with 1 and y[n] be the number of sequences that finish with 2 of the length n, x[0] = y[0] = 1, x[1] = y[1] = 1, the recurent formula for this is x[n] = y[n - 1] + y[n - 2] + y[n - 3] + .. + y[n - b] and y[n] = x[n - 1] + x[n - 2] + x[n - 3] + .. + x[n - a], basicly for a sequance of n + 1 you must think of the number of ways that the sequance will finish with 1 or with 2 Edited by author 11.08.2017 04:09 I am sorry but I still didn't understand, why x is dependent on y. Won't Y[] include cases having consecutive A times 1 and moreover won't Y[] Include duplicate cases ? I am sorry but I am new to this so that's why I am asking. well let's approuch one case where your array is finishing with 1 but no more than "a" times in a row, because the 1 array is dependent from array of 2 and array 2 is alwais finishing with 2 it will look like this 12.... that is y[n] = x[n - 1], than 112... that is y[n] = x[n - 1] + x[n - 2], than 111...112.... which is y[n] = x[n] + x[n - 1] + x[n - 2] + ... + x[n - a] and is the same in the second case Маяки могут находится в 1 точке. P.S. Если считать, что маяки не могут быть в одной точке, то тогда нужно решать паросочетанием (как я в начале и решал), что гораздо сложнее по реализации I tried different tasks and always got the right answer. My code is very messy I can't understand it after getting AC some months ago So probably if your code is clean and easy to read your approach is fundamentally wrong I mean, maybe there are some corner cases What's wrong in my code? < #include <stdio.h> #include <string.h> int main() { int i,h,w,n,tmp; int curLen = 0, curNumStr = 0; char s[105]; scanf("%d%d%d\n",&h,&w,&n); for(i = 0; i < n; i ++) { gets(s); //scanf("%s",s); tmp = strlen(s); if(curLen) curLen += 1 + tmp; else curLen += tmp; if(curLen / w){ curNumStr += curLen / w; if(curLen % w) curLen = tmp; else curLen = 0; } } if(curLen) curNumStr ++;
tmp = curNumStr / h; if(curNumStr % h) tmp ++; printf("%d",tmp); return 0; } > What's wrong with my code too? h,w,n=map(int,input().split()) a=[] for i in range(n): a.append(input()) lines=0 pag=0 while len(a)>0: if len(a)!=1: length=-1 while length<w: length+=len(a[0])+1 b=a[0] a.remove(a[0]) if length>w: a.reverse() a.append(b) a.reverse() lines+=1 else: lines+=1 a.remove(a[0])
if lines%h==0: pag=lines//h else: pag=lines//h+1 print(pag)
Edited by author 27.09.2017 21:28 Do you mean, why RE#12? I understand, thanks Edited by author 27.09.2017 22:28 You are removing a[0], not element with index 0 So if there are several elements having the same value as a[0] they would be removed together with a[0] So they would be not processed Also I strongly recommend you not to store the entire input but process data just in time I got WA at test 18. Any tests for me? Got it fixed just, was using wrong indexing -> for rows used N, however, I had to use M. Hello, I didn't understand the problem statement correctly. Do cities having power stations need to be connected to each other? The solution can be also having more than 1 connected components( Graphs ), right? Edited by author 21.09.2017 09:28 Edited by author 21.09.2017 09:32 Questions you are asking are not about the statement Questions you are asking are about the solution Oh sorry, my bad! However can you please help me ? I will change the topic of the comment. The first question is maybe OK. It is about the statement. So there is "k cities have stations, the other cities need to be connected..." So we need to connect the other n-k cities Oh, got it ! Thanks a lot :) And second question is really about the solution To understand it pay your attention to fact That there is NO INFORMATION ABOUT ANY GRAPHS in the statement No information about Graphs, you mean that whether it's directed or undirected? Statement doesn't contain the word "graph" So the graph is just a mathematical model used for solving such kind of problems not something from statement Also remember that it is ACM ICPC tradition to write informal statements Statements which need to be formalized Thanks a lot for helping me ! :) Hello, I am not that strong in DP but I have been trying hard to understand the problem. I tried coming up with a solution however got WA. I cannot completely understand the hints given before, PLEASE HELP !!! There are two dp-approaches already described on the webboard So I have accepted with dp I have two dp Stirling numbers of the second kind and factorial Then precalculate answer array I have seen the 2 DP solutions however I still don't understand how do they arrive at the relation? Can you describe in detail if possible, Please ! There are X groups consisting of equal numbers. X=1,2,..n. What does it mean, to put some '<' and '>' signs between them? It is just to define some order relation. Just assign one group as the greatest, another group as the second greatest etc. So we find number of ways to make groups and multiply it by number of ways to make ordering https://ideone.com/00UUdfMy solution is very ugly Maybe yours is beautiful How nice is your solution? How ugly can it be? Just need to use three functions: convert board to 2-byte value, unconvert, modify board by making a move at (x, y). And with those, we just do usual BFS, until 0 or 65535 is reached. Unless of course you're not doing brute force but some smart solution. What? Why? You can't be serious. I'll try to scribble the concept in pascal... type TBoard = array[0..3, 0..3] of shortint; //the board TMod = array[0..2, 0..2] of shortint; //the modifier var md: TMod; ... procedure ModifyBoard(x, y: shortint; var board: TBoard); //x, y are coordinates of our move's center //board links to the board array we're modifying var i, j: shortint; begin for i:=-1 to +1 do for j:=-1 to +1 do if (x + i >= 0) and (x + i <= 3) and (y + j >= 0) and (y + j <= 3) then begin //out of bounds check if md[i + 1, j + 1] > 0 then board[x + i, y + j]:=1 - board[x + i, y + j]; //flipping if spot is marked for that end; end; I guess not more effecient than your bit operations, but definitely easier to read. You can, like, just convert 2-byte state into a full board and convert it back with separate functions if needed. Why? Because I have solved a very similar task Flip game I don't like to solve the same task with the same method twice I see, you weren't serious. Sorry. const maxH=500; var N,K,q,w,e:longint; H:array[1..maxH] of longint; z:array[1..2,1..maxH,0..2] of longint; x:array[0..1] of longint; begin readln(N,K); for q:=1 to N do readln(h[q]); for q:=1 to K do begin z[2,q,0]:=0; z[2,q,1]:=0; z[2,q,2]:=0; end; z[2,1,h[1]]:=1; for q:=2 to N do begin z[1]:=z[2]; for e:=1 to K do begin z[2,e,0]:=0; z[2,e,1]:=0; z[2,e,2]:=0; end; z[2,1]:=z[1,1]; z[2,1,h[q]]:=z[2,1,h[q]]+1; e:=K; if q<K then e:=q; for w:=2 to e do begin x[0]:=z[1,w,0]; x[1]:=z[1,w,1]; x[h[q]]:=x[h[q]]+1; z[2,w,h[q]]:=1; z[2,w,2]:=z[1,w-1,0]*z[1,w-1,1]+z[1,w-1,2]; if z[2,w,2]>z[1,w,2]+x[0]*x[1] then begin z[2,w,0]:=x[0]; z[2,w,1]:=x[1]; z[2,w,2]:=z[1,w,2]; end; end; end; writeln(z[2,K,0]*z[2,K,1]+z[2,K,2]); end. Could you give me a test on which my solution gives wrong answer? 7 2 1 1 0 0 1 1 1 Isn't the correct answer 4? 7 2 1 1 0 0 1 1 1 ответьте на вопрос: допустим есть цилиндр с размеромами: 1 на 1000 и отверсие в стене размером 2 на 4, можно ли нарезать мелкими лоскутками цилиндр на размеры 1 на 2, таких отрезков понадобиться 4 штуки, подобный ход удовлетворяеет поставленной задаче ? The sample input shows that 234 3456 is "too small" to cover 314 x 314. а в чём тогда моя ошибка ? Никак не могу пройти тест 4. В отсутствии пространственного воображения. Вы хоть намекните в чем смысл правильного решения, а то мне эта задача спать не даёт, хотя бы вышлите мне тест 4 по возможности as i understand u can rotate cylinder почти правильно сказал предыдущий автор. нужно поворачивать боковую поверхность вокруг центроида, и если её площадь "захлёстывает" прямоугольное отверстие, тогда "Block the hole" Edited by author 22.09.2017 16:36 Dear anyone, show me the 11th test case please! import java.util.Scanner; public class JavaApplication12 {
public static void main(String[] args) {
double x,k; int a; double y =Math.pow(10,18);
System.out.println("Сколько хотите ввести чисел ? "); Scanner sc = new Scanner(System.in); a = sc.nextInt(); int arr[] = new int[a]; for(int j=0;j<a;j++) { do { arr[j] =(int) sc.nextLong(); } while (arr[j]<0 || arr[j]>y);
} for(int i=a-1;i>=0;i--) { k = Math.sqrt(arr[i]); System.out.println(k); }
} } >Сколько хотите ввести чисел? ))))) where do you fill your dp? is it in dfs? I did that but it has a problem:( Edited by author 20.09.2017 15:25 Edited by author 20.09.2017 15:25 Help! I dont understand that problem. test: 3 0 1 0 0 can you explain which one is right ? 2 1 3 or 3 2 1 In addition I get WA6 and this is my code : /* #include <stdio.h> #define maxn 105 int vp[maxn], pv[maxn]; int main() {
int n, x, y; scanf("%d", &n); for(int i = 1; i <= n; i ++) { vp[i] = i; pv[i] = i; } for (int i = 1; i <= n; i ++) { int min = vp[i]; while(1) { scanf("%d", &x); if(x == 0) break; if(vp[x] < min) min = vp[x]; } for (int j = i - 1; j >= min; j --) { pv[j + 1] = pv[j]; vp[pv[j + 1]] = j + 1; } pv[min] = i; vp[i] = min; } for (int i = 1; i <= n; i ++) { printf("%d ", pv[i]); } return 0; } */ I don't understand what your code does. Probably intended solution uses an algorithm calling "topological sorting". (My solution uses it too). By definition, topological sorting solves the task 1022. Edited by author 14.07.2017 12:44 Yeah you are right. It is not an algorithm. It is just an idea but i think this idea should accept! Yes, I made a mistake. Correct would be something like. Intended solution is a program that calculates topological sort of vertices of a graph built from input data using some well-known algorithm for calculating topological sorting In topological sorting, you are doing depth first search and memorize vertices when you leave them. When all the vertices are considered, you have memorized vertices in reversed topological sorted order. Edited by author 14.07.2017 12:45 void dfs(int nd) { for(int to : adj[nd]) if(!used[to]) dfs(to); used[nd] = true; //switch the node into visited ans.push_back(nd); //put the node to array } Edited by author 19.09.2017 16:03 My AC program gives "3 2 1". So, probably "3 2 1" is the right answer. If several sequences satisfy the conditions of the problem, you are to write to the standard output any of them!!! ;) ;/ You should all do just DFS!(How? Just enter any node and check its adjacents were visited. So that enter node which was not visited before. Finally, put this node to array after checking and reverse the answer array)! Edited by author 19.09.2017 16:04 |
|