Common BoardI hope somebody will explain me what's wrong with my program, cause I really dont understand why i get out of memory (900KB) when my program should use only about 700KB (no more than 750KB definetly!). So pls help me smb. Now i try to explain my problem. The only memory i use, i define out of main scope and i dont use any dynamic allocations. So, the definition looks like: unsigned int length[MAXIMUMSTACKS]; unsigned int maxlength[MAXIMUMSTACKS]; unsigned int base[MAXIMUMSTACKS]; unsigned int stackPtr[MAXIMUMSTACKS]; unsigned char opbuf[OPSIZE * MAXOP]; unsigned int stack[MAXOP / 2]; where MAXIMUMSTACKS = 1000, OPSIZE = 5, MAXOP = 100000. So, let's count all memory we may use: 4*1000 + 4*1000 + 4*1000 + 4*1000 + 500000 + 4*50000 = 16*1000 + 500000 + 200000 = 716000 bytes! I is about 700KB to be honest. So, i dont inderstand, why my program get Memory Limit Error and use (as Timus says) 900KB(!). Pls, help me to fix it. Tell me what i dont understand. I give you the code of programm below. #include <stdio.h> #include <stdlib.h> #include <string.h> #define MASK(k) ((1 << k) - 1) #define OPSIZE 5 #define POPCODE 1000000001 #define MAXIMUMSTACKS 1000 #define MAXOP 100000 unsigned int N; unsigned int length[MAXIMUMSTACKS]; unsigned int maxlength[MAXIMUMSTACKS]; unsigned int base[MAXIMUMSTACKS]; unsigned int stackPtr[MAXIMUMSTACKS]; unsigned char opbuf[OPSIZE * MAXOP]; unsigned int stack[MAXOP / 2]; char op[5]; unsigned short stnum; unsigned int value; unsigned int indx; int main(int argc, char *argv[]) { // freopen("input.txt", "r", stdin); // init scanf("%u", &N); memset(opbuf, 0, N * OPSIZE); memset(length, 0, MAXIMUMSTACKS * sizeof(unsigned short)); memset(maxlength, 0, MAXIMUMSTACKS * sizeof(unsigned short)); // fill opbuf for (unsigned int i = 0; i < N; ++i) { scanf("%s%hu", op, &stnum); --stnum; indx = OPSIZE * i; opbuf[indx] = *((unsigned char*)&stnum); opbuf[indx + 1] = *((unsigned char*)&stnum + 1) & MASK(2); if (op[1] == 'U') { scanf("%u", &value); value = (value << 2); for (unsigned int j = 0; j < 4; ++j) opbuf[indx + 1 + j] += *((unsigned char*)&value + j); ++length[stnum]; if (length[stnum] > maxlength[stnum]) { maxlength[stnum] = length[stnum]; if (maxlength[stnum] > MAXOP / 2) maxlength[stnum] = MAXOP / 2; } } else { value = (POPCODE << 2); for (unsigned int j = 0; j < 4; ++j) opbuf[indx + 1 + j] += *((unsigned char*)&value + j); --length[stnum]; } } // create big memory block for stacks unsigned int prevLength = 0; unsigned int prevBase = 0; for (unsigned int i = 0; i < MAXIMUMSTACKS; ++i) { if (maxlength[i] == 0) continue; base[i] = prevBase + prevLength; stackPtr[i] = base[i]; prevBase = base[i]; prevLength = maxlength[i]; } // process through opbuf for (unsigned int i = 0; i < N; ++i) { stnum = 0; value = 0; indx = OPSIZE * i; stnum += opbuf[indx]; stnum += ((opbuf[indx + 1] & MASK(2)) << 8); for (unsigned int j = 0; j < 4; ++j) *((unsigned char*)&value + j) = opbuf[indx + 1 + j]; value = ((value >> 2) & 0x3fffffff); if (value == POPCODE) { if (stackPtr[stnum] == base[stnum]) { stackPtr[stnum] = base[stnum] + maxlength[stnum] - 1; } else { stackPtr[stnum]--; } printf("%u\n", stack[stackPtr[stnum]]); } else { stack[stackPtr[stnum]] = value; if (stackPtr[stnum] == base[stnum] + maxlength[stnum] - 1) stackPtr[stnum] = base[stnum]; else stackPtr[stnum]++; } } return 0; } Edited by author 20.08.2015 16:44 source program only uses about 300KB + 700 = MLE. So you should use about 520000 Byte = 500 KB .My advice is to use a chunk of memory that we split into pieces (for example size 8) in the first part where you keep information about previous segment of the current stack and keep the information in the stack remaining 7.Be excused my english, if you do not clear reply and will present in more detail. Allocated big buffers: commands - 5*MAXOP = 500K stack - 4*MAXOP/2 = 250K Total - 750K buffers only As empty C++ program takes about 100K you have MLE If you wont analyze save commands stack - 4*MAXOP = 500K (all pushes) + some chunks info How your program will work if input sequence is something like 33K * "PUSH 1 100" // less then MAX_OP/2 33K * "PUSH 2 100" // less then MAX_OP/2 33K * "PUSH 3 100" // less then MAX_OP/2 POP 1 POP 2 POP 3 Your program should allocate 3 stacks with total 99K size in the 50K array. Why i'm getting WA#1? #include<bits/stdc++.h> using namespace std; int capacities[2002][2002]; int flowPassed[2002][2002]; vector<int> graph[2002]; int parentsList[2002]; int currentPathCapacity[2002]; int bfs(int startNode, int endNode) { memset(parentsList, -1, sizeof(parentsList)); memset(currentPathCapacity, 0, sizeof(currentPathCapacity)); queue<int> q; q.push(startNode); parentsList[startNode] = -2; currentPathCapacity[startNode] = 999; while(!q.empty()) { int currentNode = q.front(); q.pop(); for(int i=0; i<graph[currentNode].size(); i++) { int to = graph[currentNode][i]; if(parentsList[to] == -1) { if(capacities[currentNode][to] - flowPassed[currentNode][to] > 0) { parentsList[to] = currentNode; currentPathCapacity[to] = min(currentPathCapacity[currentNode], capacities[currentNode][to] - flowPassed[currentNode][to]); if(to == endNode) { return currentPathCapacity[endNode]; } q.push(to); } } } } return 0; } int edmondsKarp(int startNode, int endNode) { int maxFlow = 0; while(true) { int flow = bfs(startNode, endNode); if (flow == 0) { break; } maxFlow += flow; int currentNode = endNode; while(currentNode != startNode) { int previousNode = parentsList[currentNode]; flowPassed[previousNode][currentNode] += flow; flowPassed[currentNode][previousNode] -= flow; currentNode = previousNode; } } return maxFlow; } int main() { long int m,n,k,x; cin>>m>>n>>k; x=m+n; for(int i=0;i<k;i++) { int a,b; cin>>a>>b; graph[a].push_back(m+b); graph[m+b].push_back(a); capacities[a][m+b]=1; } for(int i=0;i<m;i++) {graph[0].push_back(i+1);capacities[0][i+1]=1;} for(int i=0;i<n;i++) {graph[m+i+1].push_back(x+1);capacities[m+i+1][x+1]=1;} int y=edmondsKarp(0,x+1); int p=(m-y+1)/2; p=p+(n-y+1)/2; cout<<(y+p)<<endl; } import java.text.DecimalFormat; import java.util.Scanner; /** * Created by user on 06.02.2017. */ public class nytka { public static void main(String[] args) { double c = 0; Scanner sc = new Scanner(System.in); String a = sc.next(); int b = Integer.valueOf(a); String q = sc.next(); double r = Double.valueOf(q); double[] x = new double[b]; double[] y = new double[b]; if (100>b) { if (b > 0){ for (int i = 0; i <= b - 1; i++) { String x2 = sc.next(); double x1 = Double.valueOf(x2); x[i] = x1; String y2 = sc.next(); double y1 = Double.valueOf(y2); y[i] = y1; } for (int i = b - 1; i > 0; i--) { double rez = Math.sqrt(((x[i] - x[i - 1]) * (x[i] - x[i - 1])) + ((y[i] - y[i - 1]) * (y[i] - y[i - 1]))); c = c + rez; } } } double end = Math.sqrt(((x[b-1]-x[0])*(x[b-1]-x[0]))+((y[b-1]-y[0])*(y[b-1]-y[0]))); c = c + end; double rad = (Math.PI*r*r)*(b/2); double endrez = c + rad; DecimalFormat f = new DecimalFormat("#,##0.00"); System.out.print(f.format(endrez)); } } You should clarify error - WA/TLE/runtime; and show test number. b can be 100 by task description. b can be 1 by task description. Conditions like "if (b correct) then solve else do nothing" are useless. Ok, you found b==102. So what? How should you check if WA is because program mistake or because you detected invalid b? Usually if input data can be invalid then some specific program behavior is declared and required. Here - on timus - input is supposed to be always valid, no any input-error-behavior expected. You should fail program in specific way (different from regular WA) this case or remove condition at all. Edited by author 09.02.2017 19:21 using System; using System.Threading; using System.Globalization; namespace TestOfCSharp { class Program { static void Main(string[] args) { Thread.CurrentThread.CurrentCulture = CultureInfo.InvariantCulture; string[] input = Console.ReadLine().Split(' '); int N = int.Parse(input[0]); int R = int.Parse(input[1]); double sum = 0; for (int i = 0; i < N; i++) { input = Console.ReadLine().Split(' '); sum += double.Parse(input[0]) + double.Parse(input[1]); } sum += 2 * Math.PI * R; Console.WriteLine("{0:F2}", sum); } } } Edited by author 20.12.2013 05:18 (pi*r^2) Edited by author 09.02.2017 18:21 > sum += double.Parse(input[0]) + double.Parse(input[1]); How it should work? Google "points distance formula". Can somebody give me test #4? I'm getting WA 3 q 3:3.3 w 4:4:4 e 1:1.1 answer e It should be like 03:03.3 etc Don't use cin(TL1) and getc(WA1), use scanf and get AC: char s[(int)1e7]; scanf("%s", &s); length = strlen(s); in 1 test case we can't determine whether subject 3 should be earlier than 4 or 4 than 3, because there's isn't any edge that show which one should be sdutied ealrier, why answer is YES???? I think if we can't verify it answer should be NO Verify correctness = see if there's such a pair in the first list, that goes in reverse order on the second list. For test 2 it's pairs (3 5), (5 2), (4 2), for test 1 there's no such pairs. #include <iostream> #include <queue> using namespace std; int calculate (queue<int> wind) { int result = 0; for (int i = 0; i < 3; i++) { result += wind.front(); wind.pop(); } return result; } int main() { int n, sum = 0, max=0, el, position=2, middle=2; queue<int> window; cin >> n; for (int i = 0; i < 3; i++) { cin >> el; window.push(el); max += el; } for (int i = 0; i < n-3; i++) { cin >> el; window.push(el); window.pop(); sum = calculate(window); position++; if(sum > max) { max = sum; middle = position; } } cout << max << " " << middle; return 0; } import java.util.*; public class JavaApp { public static void main(String[] args) { int i=0; Scanner scan = new Scanner(System.in); int n=scan.nextInt();
if ((n>=1)&&(n<10000)){ i=n *(n + 1) / 2; System.out.print(i);} else if ((n<=1)&&(n>-10000)){ i=-((-n) *(1 -n) / 2) + 1; System.out.print(i);} }; } import java.util.Scanner; public class tests {
public static void main(String[] args) { int i=0; Scanner scan = new Scanner(System.in); try{ int n=scan.nextInt(); if ((n>=1)&&(n<=10000)){ i=n *(n + 1) / 2; System.out.print(i);} else if ((n<=1)&&(n>=-10000)){ i=-((-n) *(1 -n) / 2) + 1; System.out.print(i);} } finally { scan.close(); } } } try this: 45000270000405 answer: 9000054000081 or this: 907500003300000003 answer: 302500001100000001 Edited by author 10.10.2011 10:41 907500003300000003 right is 1 To clarify: IFullMetalLeon is not telling the truth; the correct answer to 907500003300000003 is 302500001100000001. and you could try 100102036020202601, the answer is 10010202601 I'm stuck on test 33. Please, explain, is 9000054000081 really correct answer? 9000054000081 = 3^2 + 100000600009^1. It obviously has even divisors: (2+1) * (1+1) = 6. They are 1, 3, 9, 100000600009, 300001800027, 900005400081. And 302500001100000001 is prime, thus it has 2 divisors (1 and self). Where am I wrong? 302500001100000001=550000001^2 And is has 3 uneven divisors: 1, 550000001, 302500001100000001. And every X=Y^2 has uneven number of uneven divisors. Edited by author 31.05.2012 18:57 This is the right solution Sorry for my english var ans: array[1..1000] of longint; n,m,y,q,i: longint; function BinPow(x,y: longint): longint; begin if y=1 then BinPow:=x else if y mod 2=0 then BinPow:=sqr(BinPow(x,y div 2)) mod M else BinPow:=(sqr(BinPow(x,y div 2))*x) mod M; end; begin readln(n,m,y); q:=0; for i:=0 to m-1 do begin if BinPow(i,n)=y then begin inc(q); ans[q]:=i; end; end; for i:=1 to q do write(ans[i],' '); if q=0 then writeln(-1); end. My solve in C++: #include <iostream> #include <string> #include <vector> #include <set> #include <queue> #include <map> #include <stack> #include <algorithm> #include <bitset> #include <cstring> #include <cmath> #include <cstdlib> #include <cstdio> #include <iomanip> #define F first #define S second #define ll long long #define len length() #define sqr(x) x*x #define pb push_back #define mp make_pair #define sz(x) ((int) (x).size()) #define all(x) x.begin(), x.end() #define allr(x) x.rbegin(), x.rend() #define bp(x) __builtin_popcount(x) #define INF numeric_limits<long long int>::max() #define frp freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #define forit(it, s) for(__typeof(s.begin()) it = s.begin(); it != s.end(); it++) const int maxn = (int)1e6; const int mod = (int)1e9 + 7; using namespace std; __int64 n,m,y;
int binpow(int a, int n){ if (n == 0) return 1; if (n % 2 == 1) return (binpow (a, n-1)*a)%m; else{ int b = (binpow(a, n/2)); return (b*b)%m; } }
bool ok; main(){ scanf("%I64d%I64d%I64d",&n,&m,&y); for(int i=0; i < m; i++){ if(binpow(i,n)%m==y){ cout<<i<<" "; ok=1; } } if(!ok) return cout<<"-1",0;
return 0; } What it is? else if y mod 2=0 then BinPow:=sqr(BinPow(x,y div 2)) mod M else BinPow:=(sqr(BinPow(x,y div 2))*x) mod M; #include <bits/stdc++.h> using namespace std; string a,b; string re(long long c, long long d,string x){ string y=""; for(long long i=d; i>=c; i--) y=y+x[i]; return y; } string re2(string x){ long long t=0; string res=""; for(long long i=0; i<x.size(); i++){ int q=(int)x[i]; if(q<65||(q>90&&q<97)||q>122){ res=res+re(t,i-1,x); res=res+x[i]; t=i+1; } } res=res+re(t,x.size()-1,x); return res; } int main() { while(getline(cin,a)){ istringstream iss; iss.clear(); iss.str(a); while(iss>>b) cout<<re2(b)<<" "; cout<<endl; } } In the end you write empty line. You must delete your last cout. Thanks you. But I repaired and still WA#1 Try next tests(be attentive to the newline and whitespace): 1) asdad asd sf dv answer: dadsa dsa fs vd 2)1 2 3 $ asd#!@#sad%$#%2 sdSA d!23!`123?<M@! ^^&(&*^&as asf kljdka jd1892u31ASDASD11 end. answer: 1 2 3 $ dsa#!@#das%$#%2 ASds d!23!`123?<M@! ^^&(&*^&sa fsa akdjlk dj1892u31DSADSA11 dne. 3)You must inverse word and all. But y ou could forget about the spaces and line breaks ! answer: uoY tsum esrevni drow dna lla. tuB y uo dluoc tegrof tuoba eht secaps dna enil skaerb ! Oh, I failed in test 1 and then got AC. Tks u so much ^^ Edited by author 05.02.2017 21:40 "King Hugo II wants to state the number x in his recruitment order. The king needs as many soldiers as possible for his military campaign. However, if the recruitment takes more than t days, the enemy may learn about the imminent intrusion and strike first. Help Hugo II find the maximal possible value of x." We must find "maximal possible value of x" with "if the recruitment takes more than t days, the enemy may learn about the imminent intrusion and strike first" without "The king needs as many soldiers as possible for his military campaign"!!! nvm accepted Edited by author 05.02.2017 04:33 My code: const nmax=111111; var a:array[1..nmax] of int64; n,k,p:longint; i,cnt,cntmax,max:longint; sum:int64; BEGIN readln(n,k); read(p);
for i:=1 to n-k do a[i]:=1; sum:=n-k; cnt:=n-k; cntmax:=1; max:=2;
for i:=n-k+1 to n do begin if(100*cnt<p*(i-1)) then begin inc(max); inc(cnt,cntmax-1); cntmax:=1; end else inc(cntmax);
a[i]:=max; inc(sum,max); end;
writeln(sum); for i:=1 to n do write(a[i],' '); END.
#include<stdio.h> int main() { int n,i,j,c,t,T; scanf("%d",&T); while(T--) { scanf("%d",&n); for(j=2;;j++) { c=0; t=0; for(i=2;i<=j/2;i++) { if(j%i==0) { c++; break; } } if(c==0) t++; if(t==n) { printf("%d\n",j); break; } } } return 0; } why TLE?? Edited by author 04.02.2017 11:04 Edited by author 04.02.2017 11:05 Edited by author 04.02.2017 11:08 Error here: t=0. You wanted this: #include<stdio.h> int main() { int n,i,j,c,t,T; scanf("%d",&T); while(T--) { scanf("%d",&n); t=0; for(j=2;;j++) { c=0; for(i=2;i<=j/2;i++) { if(j%i==0) { c++; break; } } if(c==0) t++; if(t==n) { printf("%d\n",j); break; } } } return 0; } But your algo will get TL on test: 15000 15000 .... 15000 (15001 times) Please, help some critical test case ps. I fix it ) Edited by author 04.02.2017 18:08 I can't understand what is wrong? Maby something with calculations and rounding??? Can anyone help me? Thanks [code deleted] Edited by moderator 22.02.2006 00:48 correst your x and y to: [code deleted] Edited by author 21.11.2005 04:45 Edited by moderator 22.02.2006 00:49 Can you tell me how to solve this problem?? Утверждение: задача эквивалентна следующей: нужно найти все комплексные q с целыми коэффициентами, удовлетворяющие |a-bq|<|b|. Если |b|=0, то решений нет Иначе |b|>0. Тогда условие эквивалентно |a/b - z|<1. Пусть a=a1+b1i, b=a2+b2i, q=q1+q2i. Тогда получим |alfa/gamma-q1+i(beta/gamma+q2)|<1 <=> ((alfa-gamma*q1)/gamma)^2+((beta+gamma*q2)/gamma)^2<1, где gamma=a2*a2+b2*b2, alfa=(a1*a2+b1*b2)/gamma, beta=i(a2*b1-a1*b2)/gamma. Теперь просто можно пройтись по всем q1 и q2 (они меняются от -1+alfa/gamma до 1+alfa/gamma и от -1-beta/gamma до 1-beta/gamma) и проверить условие. Hi. I've also got AC with O(m*2^n), but it seems that it's a bit more fast. Here's an idea. Each set of taps or a combination of sets has corresponding bit mask. We have an array int minPrice[2^N]. Obviously, index is a mask, element — min price for buying such combination of taps. Initially the only !=0 elements are those each corresponding to one of predefined M sets. Then the DP comes. We go from 0-th element to the last (11...1 target). If i-th element !=0, we process it: a) if i corresponds to one of M predefined sets, we try to OR "i" with all younger mask with !=0 price. b) if i doesn't correspond to any predefined set, thus, it's a combination of some predefined sets, then we OR this "i" with younger predefined masks ONLY (not all younger "j" !=0). However, there's still a question to those guys who got AC in less than 0.1 second. Especially to those who did it in ~200 KB. Edited by author 01.02.2017 17:12 |
|