Time limit. Where is my mistake? cnt1 = int(input()) lst1 = input() lst1 = lst1.split() cnt2 = int(input()) lst2 = input() lst2 = lst2.split() cnt3 = int(input()) lst3 = input() lst3 = lst3.split() cnt = 0 for i in range(cnt1): for j in range(cnt2): if lst1[i] == lst2[j]: for k in range(cnt3): if lst1[i] == lst3[k]: cnt += 1 else: continue print(cnt) Edited by author 31.10.2017 14:42 Your code has O(cnt1 * cnt2 * cn3). If cnt1 is 4000, cnt2 is 4000, cnt3 is 4000, Your code will work (4000*4000*4000)/10^8 seconds. 640 seconds. 640 > 0.5 I agree 640>0.5 Edited by author 15.07.2018 02:43 Edited by author 15.07.2018 02:43 a = input() A = list(map(int , input().split())) a = input() B = list(map(int , input().split())) a = input() C = list(map(int , input().split())) print(len(set(A) & set(B) & set(C))) a=input() a1=list(map(int,input().split())) b=input() b1=list(map(int,input().split())) c=input() c1=list(map(int,input().split())) cnt=0 for i in a1: if i in b1: if i in c1: cnt+=1 print(cnt) cnt = 0 a = int(input()) a1 = list(map(int, input().split())) b = int(input()) b1 = list(map(int, input().split())) c = int(input()) c1 = list(map(int, input().split())) for i in a1 : if i in b1 and c1 and a1 : cnt += 1 print(cnt) what is wrong? tells "wrong answer" m=[] m2=[] for tik in range(3): n=int(input()) m1=input().split() for i in m1: if i not in m: m.append(i) elif i in m: if i not in m2: m2.append(i) print(len(m)-len(m2)) I don't know why this program doesn't work. Edited by author 03.05.2021 00:22 import java.util.*; public class Main { public static void main(String[] args) { ArrayList<Integer> mas = new ArrayList<>(); Scanner input = new Scanner(System.in); int n,bin,delta = 0; n = input.nextInt(); for (int i = 0; i <n;i++){ bin = input.nextInt(); mas.add(bin); } n = input.nextInt(); for (int i = 0; i <n;i++){ bin = input.nextInt(); mas.add(bin); } n = input.nextInt(); for (int i = 0; i <n;i++){ bin = input.nextInt(); mas.add(bin); } Collections.sort(mas); delta = mas.size(); for (int i = 0;i<mas.size()-1;i++){ bin = mas.get(i); delta = delta - (mas.lastIndexOf(bin)-mas.indexOf(bin)+1); } delta = -1*delta-mas.size(); System.out.print(delta); } } this is my code a=int(input()) b = [int(a) for a in input().split()] c=int(input()) d = [int(c) for c in input().split()] e=int(input()) f=[int(e) for e in input().split()] spisok=b+d+f spisok.sort() kolich=0 for i in range(0, len(spisok)-1): if spisok[i-1]==spisok[i] and spisok[i]==spisok[i+1]: kolich+=1 print(kolich) i dont know why but it writes wrong answer on test №37 please could you text me what is on this test #include <iostream> using namespace std; int v[4001],w[4001],q[4001]; int se_gaseste (int val , int inceput , int sfarsit,int v[4001]) { int mijloc=(inceput+sfarsit)/2; if (v[mijloc]==val) return 1; if (inceput >= sfarsit) return 0; if (val>v[mijloc]) se_gaseste(val,mijloc+1,sfarsit,v); else se_gaseste(val,inceput,mijloc-1,v); } int main() { int n,m,t,nr=0; cin>>n; for (int i=1;i<=n;i++) cin>>v[i]; cin>>m; for (int i=1;i<=m;i++) cin>>w[i]; cin>>t; for (int i=1;i<=t;i++) cin>>q[i]; for (int i=1;i<=n;i++) { if ( se_gaseste(v[i],1,m,w) && se_gaseste(v[i],1,t,q)) nr++; } cout<<nr; return 0; } i tested this algorithm on many exemples and all works how i can't pass the first test, please help , thx. A little explication : i take every number from first vector and i check if exist in last both vectors . i use binary search Edited by author 22.05.2020 16:12 #include <iostream> #include <stack> using namespace std; int main() { unsigned short n1, n2, n3; int a, n=0; stack<int> group1; cin >> n1; for (int i = 0; i <n1; i++) { scanf_s("%d", &a); group1.push(a); } stack<int> group2; cin >> n2; for (int i = 0; i < n2; i++) { scanf_s("%d", &a); group2.push(a); } stack<int> group3; cin >> n3; for (int i = 0; i < n3; i++) { scanf_s("%d", &a); group3.push(a); } while (!group1.empty()) { if (group1.top() == group2.top()) { if (group1.top() == group3.top()) { n++; group1.pop(); group2.pop(); group3.pop(); if ((group1.empty()) || group2.empty() || group3.empty()) break; } else if (group1.top() > group3.top()) { group1.pop(); group2.pop(); if (group1.empty() || group2.empty()) break; } else group3.pop(); } if (group1.top() > group2.top())group1.pop(); if (group1.empty()) break; if (group1.top() < group2.top())group2.pop(); if (group2.empty()) break; } cout << n;
} what's wrong? after else group3.pop(); if (group3.empty()) break; accapte #include <iostream> #include <string> using namespace std; int main(int argc, char* argv[]) { int co1=0,co2=0,co3=0,c=0; //init //1 cin >> co1; int *nm1 = new int[co1]; for (int i = 0; i < co1; i++) { cin >> nm1[i]; } //2 cin >> co2; int *nm2 = new int[co2]; for (int i = 0; i < co2; i++) { cin >> nm2[i]; } //3 cin >> co3; int *nm3 = new int[co3]; for (int i = 0; i < co3; i++) { cin >> nm3[i]; } for(int i=0;i<co1;i++) { for(int k=0;k<co2;k++) { if(nm1[i]==nm2[k]) { for(int j=0;j<co3;j++) { if(nm2[k]==nm3[j]) { c++; break; } } break; } } } cout << c; system("pause"); return 0; } def bin_Search(arr, val): low = 0 high = len(arr)-1 while low <= high: mid = (low + high) // 2 if val < arr[mid]: high = mid - 1 elif val > arr[mid]: low = mid + 1 else: return True else: return False aa = int(input()) aArr = list(map(int, input().split())) b = int(input()) bArr = list(map(int, input().split())) c = int(input()) cArr = list(map(int, input().split())) aArr.sort() bArr.sort() cArr.sort() cnt = 0 for i in aArr: s = bin_Search(bArr, i) if s == True: s1 = bin_Search(cArr, i) if s1 == True: cnt += 1 print(cnt) Here i use binary search Edited by author 30.07.2019 19:29 u have 3 arrays, so. try to compare arr1 and arr2 and if u found matched numbers, then compare the second and the third arrays, if u got matched again - count var +1 in the end just writeline (count) Edited by author 23.11.2018 18:22 program m; var a:array[1..4000] of integer; p:array[1..4000] of integer; x:array[1..4000] of integer; n,s,i,j,k,f,m:integer; begin read(n); for i:=1 to n do read(a[i]); read(s); for j:=1 to s do read(p[j]); read(k); for f:=1 to k do read(x[f]);m:=0; for i:=1 to n do for j:=1 to s do for f:=1 to k do begin if (a[i]=p[j]) and (p[j]=x[f]) and (x[f]=a[i]) then m:=m+1; end; write(m); end. Your algo has complexity O(n1*n2*n3) id est 4000*4000*4000= 6.4*10^10. It's too much operations for one half a second. Try to use other algo instead of linear search twice. var i,j,n,n#,n2,a,m:integer; l:array[#..400#,#..2] of longint; begin read(n); for i:=# to n do read(l[i,#]); read(n1); for i:=# to n# do begin read(a); for j:=# to 400# do if l[j,#]=a then l[j,2]+=#; end; read(n2); for i:=# to n2 do begin read(a); for j:=# to 400# do if l[j,#]=a then l[j,2]+=#; end; for i:=# to 400# do if l[i,2]=2 then m:=m+#; writeln(m); end. Where is # change it with 1 The main method I followed was to first compare two of the arrays and extract the similar values in another array. I then compared that array with the third array, and updated the counter each time there was a match in eigenvalues. This method avoids comparing all the arrays together, and hence takes up less time. So in essence number of operations reduces to O(2*N^2) instead of O(N^3). However, more sophisticated algorithms like binary search are more effective. But still I include this method for people like myself, who are new to algorithms. Hope it helps someone. Thank you! Did as you said and get Accepted)) 0.046 seconds (FreePascal) var A:array[1..4000] of integer; B:array[1..4000] of integer; C:array[1..4000] of integer; q,w,e,r,t,y,i,o,p,s:integer; begin read(q); for r:=1 to q do read(A[r]); read(w); for t:=1 to w do read(B[t]); read(e); for y:=1 to e do read(C[y]); for i:=1 to q do begin for o:=1 to w do for p:=1 to e do if (A[i]=B[o]) and (A[i]=C[p]) then inc(s); end; write(s); end. You should make variables like i1 ,i2, i3 but not q,w,e.r,t,y you know? So your program isn't clear. And about your timelimi.... : put here for o:=1 to w do >>> for p:=1 to e do if (A[i]=B[o]) and (A[i]=C[p]) then inc(s); this: if A[i]=B[o] then begin for p:=1 to e do if (A[i]=B[o]) and (A[i]=C[p]) then inc(s);end; and...think about what you can delete from this: if (A[i]=B[o]) and (A[i]=C[p]) then inc(s);end; using System; class Program { static void Main() { int[] n = new int[3]; string[][] val = new string[3][]; int count = 0; for(int i = 0; i < 3; i++) { n[i] = int.Parse(Console.ReadLine()); val[i] = Console.ReadLine().Split(' '); } for(int i = 0; i < n[0]; i++) { for(int k = 0; k < n[1]; k++) { if(val[0][i] == val[1][k]) { for(int j = 0; j < n[2]; j++) { if(val[0][i] == val[2][j]) { count++; break; } } } } } Console.WriteLine(count); } } It`s wrong on 32 test. I can`t understand the problem. I used bin search. const n0=10000; type u = array[1..n0] of integer; var a:u; b:u; c:u; n,i,k,l,m,j,q,t:integer; function bin_search(s,n:integer; var mas:u):integer; var ib,im,i1:integer; begin i1:=1; ib:=n; while i1<=ib do begin im:=i1+(ib-i1) div 2; if mas[im] = s then begin bin_search:=s; break; end else if mas[im] < s then i1:=im+1 else ib:=im-1; end; if i1>ib then bin_search:=-1; end; begin readln(n); for i:=1 to n do read(a[i]); readln(k); for l:=1 to k do read(b[l]); readln(m); for j:=1 to m do read(c[j]);
for t:=1 to m do begin if bin_search(c[t],m,b)<>-1 then if bin_search(c[t],m,a)<>-1 then q:=q+1; end; writeln(q); end. Edited by author 25.11.2015 10:20 What is "Wrong answer - test 2", and how can i fix it? Edited by author 17.10.2015 11:58 Edited by author 17.10.2015 11:58 |
|