Общий форум| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | (java) memory limit even using PQ<Integer> with capacity = 125'000 | Ozzy | 1306. Медиана последовательности | 15 апр 2013 00:43 | 1 | hi I found some hint about this task (PQ usage with size = n/2+1) and applied it. My class have only PQ<Integer> object and three int variables + StreamTokenizer + System.out. Unfortunately, I've got MLE (1096 Kb). So I think that java needs more than 1 Mb to store 125'001 elements on PQ<Integer> - is it right ? If yes than which way this task can be solved using java ? TIA. | | O(n^2) is the best way or not? | hoan | 1403. Курьер | 14 апр 2013 23:04 | 5 | No. I solved in in O(nlogn) Can you explain me your algo? thanks in advance. I think you have to use binary tree to implement something. Binary tree? Are you kidding? just quick sorting of array and little thinking. Edited by author 14.04.2013 23:05 | | 3 тест | Doshirak | 1843. Разрезание параллелепипеда | 14 апр 2013 10:54 | 1 | 3 тест Doshirak 14 апр 2013 10:54 Подскажите пожалуйста пример третьего теста | | Problem with the first test | Drotaverin | 1843. Разрезание параллелепипеда | 13 апр 2013 23:46 | 11 | As i have read, the first test is like in example. And i have tried to use a kind of cheat: Console.WriteLine("F D 0 0 0" + Environment.NewLine + "R F 1 0 0"); But i have got "Wrong answer". What have i done wrong? There's no guarantee that the first test is exactly the same as the example. У кого есть предположение, какой пример в первом тесте? В первых двух тестах исходный параллелепипед не имеет разрезов, его только нужно повернуть правильным образом. Числа друг от друга (координаты) разделяются одним пробелом? Пример параллелепипеда без разрезов 1 1 1 ROYGBV 1 1 1 1 GYBVOR R B 0 0 0 Ввод и вывод все так должно быть, ничего не перепутал? Это нормально, я сам эти методы использую. Можешь написать на akaviri93@gmail.com, прислать код, помогу разобраться с ошибкой. Edited by author 13.04.2013 23:50 | | [AC] | Karpov Alexandr | 1709. Пингвин-Авиа | 13 апр 2013 08:46 | 2 | [AC] Karpov Alexandr 9 янв 2013 17:57 I had a stupid bug and found better to post it here rather than trying to look on my code. Looked, found. Edited by author 09.01.2013 18:03 | | WA 6. Give me some tests, please | Nafania | 1700. Пробуждение | 12 апр 2013 20:40 | 1 | On my data program works fine, but got WA. Help me, please :( I can't understand where is trouble in my code | | WA №4 | daria | 1131. Копирование | 12 апр 2013 18:29 | 1 | WA №4 daria 12 апр 2013 18:29 Pleaze, give me some tests that I will be able to find my error. | | Контрпример | Александр | 1843. Разрезание параллелепипеда | 12 апр 2013 12:33 | 7 | Подскажите контрпример 7 теста. Prompt a counterexample of the 7th dough. Edited by author 05.04.2013 17:38 Re: Контрпример Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 6 апр 2013 02:57 MGIMO finished? A-a-ask! =) Тест - test in English Dough == тесто (булочки выпекать) =))) +1 Sergey trolling detected XD Присоединяюсь =) очень хочется увидеть тест 7... 7 тест это три куска, разрезы сделаны параллельно одной из граней. Важно правильно определять ориентацию в случае, когда "внутренних" граней у куска больше чем одна. Edited by author 09.04.2013 11:41 А будет ли важно, как я поставлю эти две грани. Допустим, в описании идёт сначала куб x, затем куб у. Если я поставлю сначала у, затем х, это будет ошибкой? по идее не должно... вариантов то много может быть... в условии же сказано об этом. | | Please look here if you WA on this problem | true1023 | 1106. Две команды | 12 апр 2013 12:33 | 2 | First my code maxn=100 then WA on 8 Second my code maxn=105 then WA on 11 Third my code maxn=200 then WA on 20 Fourth my code maxn=1000 then ......AC Thanks man, i'm very pleased for your help. | | shortest solution contest | pohmelie | 1607. Такси | 11 апр 2013 23:57 | 2 | //c++ #include <iostream> void main() { int ps,pu,ts,td,dif; std::cin>>ps>>pu>>ts>>td; dif=((ts=ps>ts?ps:ts)-ps)/(pu+td); std::cout<<(((ps+=(dif+1)*pu)<(ts-=dif*td))?ps:ts); } // Ruby a,b,c,d=gets.split.map { |x| x.to_i } e=((c=[a,c].max)-a)/(b+d) puts ((a+=(e+1)*b)<(c-=e*d)) ? a : c Edited by author 11.04.2013 23:58 | | WA 8 | Squire [Lviv NU] | 1119. Метро | 11 апр 2013 16:55 | 1 | WA 8 Squire [Lviv NU] 11 апр 2013 16:55 Guys, what is 8-th test? I have a lot of WA on it and i can't find out why. | | I really don't know that what's wrong with it. Give the fresh a hand .thank you.CE error. | ever_cc | 1001. Обратный корень | 11 апр 2013 10:15 | 1 | #include <stdio.h> #include<math.h> void main() { float a[1024]; int i=0,count=0;
do{ scanf("%f",&a[i]); i++; count=i-1; }while((a[count]>=0)&&(a[count]<=pow(float(10),18))); getchar(); for (i=count-1;i>=0;i--) printf("%.4f\n",sqrt((float)a[i])); } | | Why don't workng !!?!?!??!? | Daniel | 1902. Нео-Венеция | 11 апр 2013 03:24 | 3 | #include<iostream> #include<cmath> #include<iomanip> using namespace std; int main() { double *a,*d; int n,t,s,i; float temp; cin>>n; if(n>=1 && n<=100) { cin>>t; if(t>=1 && t<=100) { cin>>s; if(s>= 360 && s<=1200) { a = new double[n]; d = new double[n]; for(i=0;i<n;i++) { cin>>a[i]; if(i==1) { if(a[i] <= a[i-1]) { return 0; } }
}
for(i=0;i<n;i++) { temp = t/n; if(s == a[i]) { d[i] = a[i]+temp; } else if(s < a[i]) { temp = temp/n; d[i] = a[i]+temp; }
} cout.setf(ios::showpoint); for(i=0;i<n;i++) { cout<<d[i]<<0<<0<<0<<endl; } } else { return 0; } return 0;} return 0;}
return 0; } First of all, you don't have to check if the input is correct, so the following lines are useless: if(n>=1 && n<=100) if(t>=1 && t<=100) if(s>= 360 && s<=1200) if(i==1) //this is wrong - I think the that the condition is i>=1 { if(a[i] <= a[i-1]){ return 0; } } Then, n has nothing to do with t. So temp=t/n is not ok. (try: 3 60 600 600 630 631 to see why). Imagine that you have 4 points: A,B,C,D. The distance (in time) between them is as it follows: B-A=s ,C-B=t, D-C=sn. So two gondolas that have the same speed, would meet in the point (A+D)/2. Also, you may want to check http://www.cplusplus.com/reference/ios/ios_base/precision/ to see how you can set the floating-point precision. That is (s+t+sn)/2. | | Sick Problem | Varun Sharma | 1607. Такси | 10 апр 2013 17:56 | 2 | When I first saw this problem, I thought I would be done in 5 minutes but ended up spending 1 and 1/2 hours. Few test cases, so that you don't blow your head up ! Input: 4000 100 200 100 Output: 4000 Input: 150 400 1000 200 Output: 800 petr taxi 150 1000 550 800** 950 600 so in the example the answer is 800,not 950; but ** in test case no 1: petr taxi 150 1000 200 900 250 800 300 700 350 600 400 500 450** 400 the same set of sequence(rather similar)of event occurs with different answers... plz help with this mess..... Edited by author 10.04.2013 17:58 | | WA 5 | Meteora | 1900. Машина счастья | 10 апр 2013 10:24 | 1 | WA 5 Meteora 10 апр 2013 10:24 I am using DP O(n^2) time and getting WA 5. I have tried all the test cases listed here and my program outputs correct answer for all of them. If anyone has any examples, please respond, thank you. | | Correct Java Code | Rostam | 1020. Ниточка | 10 апр 2013 08:43 | 2 | import java.text.DecimalFormat; import java.util.Scanner; public class P1020 { private static double pi = 3.14159; private static double totalDist;
public static void main(String args[]) {
DecimalFormat df = new DecimalFormat("#.##"); Scanner in = new Scanner(System.in); int nRopes = in.nextInt(); double radius = in.nextDouble(); double[][] nodes = new double[nRopes][2];
for (int i=0; i<nRopes; i++) { nodes[i][0] = in.nextDouble(); nodes[i][1] = in.nextDouble(); }
totalDist = distance(nodes[0], nodes[nRopes-1])+pi*radius*2; for (int i=0; i < nRopes-1; i++) { totalDist += distance(nodes[i], nodes[i+1]); }
System.out.println(df.format(totalDist)); }
static double distance (double arr1[], double arr2[]) { double distance = Math.sqrt((Math.pow((arr1[0]-arr2[0]), 2)+Math.pow((arr1[1]-arr2[1]), 2))); return distance; } } Can you say different between code? I have WA#4 import java.io.PrintWriter; import java.util.Scanner; public class p1020 { /** * @param args */ static double line(double xy, double xy2,double xy3,double xy4){ return (Math.sqrt(Math.pow(xy-xy3,2)+Math.pow(xy2-xy4,2))); }
public static void main(String[] args) { // TODO Auto-generated method stub Scanner in = new Scanner(System.in); PrintWriter out = new PrintWriter(System.out); int n = in.nextInt(); double r = in.nextDouble(); double pi = 3.14159; if (n==1) { out.println(Math.round(pi*r*200)/100.00); out.flush(); return; } float[][] c = new float[n][2]; for (int i =0; i < n; i++ ){ c[i][0]=in.nextFloat(); c[i][1]=in.nextFloat(); }
double res = pi *2 *r; for (int i =0; i < n-1; i++ ){ res+=line(c[i][0],c[i+1][0],c[i][1],c[i+1][1]); }
res+=line(c[0][0],c[n-1][0],c[0][1],c[n-1][1]); out.println(Math.round(res*100)/100.00); out.flush(); } } | | Почему моя программа выдаёт неправельный ответ на 6 вопрос? | Criss009 | 1248. Сумма последовательности | 9 апр 2013 17:42 | 3 | Почему моя программа выдаёт неправельный ответ на 6 вопрос? Looks like there is some bug in it =))) program p1; type tabel=array[-100..100] of byte; var r,eror,s,a,c,i,num,b:integer; n,pr:string; x:tabel; procedure insertare(var t:tabel; f:string; p:integer); var q,e,i:integer; begin for i:=1 to length(f) do begin s:=0; val(f[length(f)-i+1],q,e); if t[i+p-1]+q+s<=9 then begin t[i+p-1]:=t[-1+i+p]+q+s; s:=0; end else begin t[i+p-1]:=t[i+p-1]+q+s-10; s:=1; end; end; while s<>0 do begin inc(i); if t[i+p-1]+s<=9 then begin t[i+p-1]:=t[i+p-1]+s; s:=0; end else begin t[i+p-1]:=t[i+p-1]+s-10; s:=1; end; end; end; begin s:=0; for i:=-100 to 100 do x[i]:=0; readln(num); for i:=1 to num do begin readln(n); a:=pos('e',n); val(copy(n,pos('e',n)+1,length(n)),b,eror); if pos('.',n)<>0 then begin pr:=copy(n,1,pos('.',n)-1); insertare(x,pr,b); pr:=copy(n,pos('.',n)+1,a-pos('.',n)-1); insertare(x,pr,b-(a-pos('.',n)-1)); end else begin pr:=copy(n,1,pos('e',n)-1); insertare(x,pr,b); end; end; for i:=100 downto -100 do if x[i]<>0 then if x[i-20]>5 then insertare(x,'1',i-19); for i:=100 downto -100 do if x[i]<>0 then begin write(x[i],'.'); for c:=i-1 downto i-19 do write(x[c]); write('e'); if i<>0 then write(i); break; end; readln; end. Why, test please and tell me why it don't work | | What's the magic in #18 | Ade | 1766. Шалтай-Болтай | 9 апр 2013 14:18 | 3 | Always WA at #18 I gave it everything I have. Resolve the formula group. Iterate to 1e-15. Still WA. Any hints? Thanks Edited by author 05.04.2013 23:37 Iterative schemes are unstable (small deviations from equilibrium in neighbor nodes lead to large error in final solution), so stupid iteration is hard to get AC here. Better reduce the problem to linear system and solve it honestly, or reduce it to matrix multiplications (even in this case you need some streetmagic to beat accuracy!) Thanks, Vedernikoff I resolved the linear formulations, but WA#18. Then I add some iterations afterward to 1e-14. Still failing. I'm now planning to pure iterations. The initial state doesn't matter, I think. So I'm gonna start from 1/64 in every cell. | | Java the best | TUITUF_Bahrom | 1219. Symbolic Sequence | 8 апр 2013 18:32 | 1 | public class T_1219_Symbolic_Sequence { public static void main(String[] args) { PrintWriter pw= new PrintWriter(new OutputStreamWriter(System.out)); Random r= new Random(); char a[]=new char[30]; int k = 0 ; for (char j ='a'; j <='z'; j++) a[++k]=j; for (int i = 1; i <=1000000; i++) pw.print(a[r.nextInt(26)+1]); pw.close(); } } | | got AC in 0.31 but i still did n^2 is there anyhting better? | marius dumitran | 1078. Отрезки | 8 апр 2013 16:38 | 7 | i used a df after i made an oriented graf(it's much easier to do than other solutions) if u did it better than O(N*N) please email me at dmarius1@yahoo.com Thanks Edited by author 15.04.2004 19:05 My decision not worse at all... At last! AC 0.001 and 394 KB I use dp O(n).ac in 0.0001s first,sort; second dp: answer=max{f(1)..f(n)}; f(i) means the best sum from the i one If you use sorting, it must be at least O(n*logn) I used sorting and then found the LIS in O(nlogn) time, 0.031 seconds |
|
|