Общий форум| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения | | Accepted | TARASHI {Kutaisi SU3} (Georgia) | 1409. Два бандита | 16 фев 2017 17:46 | 7 | Accepted TARASHI {Kutaisi SU3} (Georgia) 5 июл 2008 18:48 [code deleted] Edited by moderator 19.11.2019 23:54 Could you tell me why? Thanks in advance!! Edited by author 29.07.2008 17:35 Actually,it is a "check"... lol, your algo works as much as 0.031 seconds. but mine works 0.015: [code deleted] Edited by moderator 19.11.2019 23:55 [code deleted] //c language. 0.001 sec Edited by moderator 19.11.2019 23:55 but mine works 0.001 LOOOOL You must use smaller type: BYTE | | WA9 ! what's wrong with my code !?! my code here | Far Qf | 1120. Сумма последовательных чисел | 15 фев 2017 18:05 | 3 | #include<iostream> #include<math.h> using namespace std; int main() { int n; int p; double a; int i; cin>>n; int flag; for(p=sqrt(n*2);p>0;p--) { a=(double)n/p-(double)(p-1)/2; if(a==(int)a && a>0) { cout<<a<<" "<<p; return 0; }
} cout<<n<<" "<<1; return 0; } Edited by author 09.10.2008 14:39 cout << (int)a << " " << p; :) | | "runtime error (access violation)" | philimonix | 1001. Обратный корень | 15 фев 2017 12:40 | 5 | #include <stdio.h> #include <math.h> #include <stdlib.h> #define SIZE 1024 int main(void) { unsigned long long int *buffer = \ (unsigned long long int *) malloc(sizeof(unsigned long long int) * SIZE); int i = 0;
while (scanf("%llu", &buffer[i]) > 0) i++;
for(i -= 1; i >= 0; i--) printf("%.4f\n", sqrt(buffer[i]));
return 0; } У меня всё работает, на тестовых данных выдаёт правильный результат. В чём косяк? Edited by author 14.02.2017 15:27 > #define SIZE 1024 Number is wrong. Max input size is much bigger. Пробовал и большие числа туда вписывать. Всё равно не работает. Точнее, оно работает, но у меня на компе.. а вот на сайте проверку не проходит > и большие числа Which one? How did you estimate max input size? By task, max input size is 256K bytes . Assuming 2 bytes per number - "1 " - max input size is 128K numbers. Btw, why raw C? Why not C++ with stl containers? Edited by author 15.02.2017 12:38 > Btw, why raw C? Why not C++ with std containers? Не интересует С++ с его чрезмерной сложностью и нагромождением какой-то невероятной кучи всякого-разного :) Мне как-то больше по душе чистый и простой С. А задачу, кстати, всё-таки решил. Действительно, нужно было просто сильно увеличить размер массива. Я сделал #define SIZE 10241024. Большое спасибо за помощь! Edited by author 15.02.2017 12:42 | | anyone give some hints?? | Shen Yang | 1693. Задача Лойда | 13 фев 2017 14:16 | 1 | | | WA#6, help me plz!!! | quangduytr | 1011. Кондукторы | 13 фев 2017 12:43 | 1 | #include <bits/stdc++.h> using namespace std; float p,q,t1,t2,t3,l1,l2; int main() { cin>>p>>q; for(int i=1; i<=1000000; i++){ t1=(p*(float)i)/(float)100; t2=(q*(float)i)/(float)100; l1=(int)t1; l2=(int)t2; if(l1==t1||l2==t2||l1!=l2){ if(l1!=t1) l1=l1+1; for(int j=l1; j<=l2; j++){ t3=((float)j/(float)i)*(float)100; if(p-0.000001<t3&&t3<q+0.000001){ cout<<i; return 0; } } } } } | | how does sample works? | Shen Yang | 1649. Абстракционизм в массы | 13 фев 2017 11:50 | 2 | I can only get 2 3 1 3 4 3 2 3 2 according to the sample output... understand now... four populated adjcent cells | | O(n) | wefgef | 1069. Код Прюфера | 12 фев 2017 15:50 | 8 | O(n) wefgef 4 июн 2006 18:45 has anyone done it in O(n)? But this solution is O(n^2) becouse of ... 7 for each value i in a 8 for each node j in T ... maybe I don't understand whi it is O(n) so I ask you tell me why please. Sorry for bad English. Никто с форума не знает решение O(N), т.к. в рейтинге решений у всех время 0.015, которое соответствует N*logN (я сам так решил). Идея задачи проста-на очередном шаге находить ещё не использованные вершинки (а также отсутствующие в оставшемся списке),и среди всех таких вершины с минимальным номером. Это как раз и будут "очередные" в "оставшемся" дереве висячие вершины. Стандартное решение с использованием кучи работает O(N*logN). Если кто-нибудь ДЕЙСТВИТЕЛЬНО знает решение за O(N), то напишите на общем форуме. Edited by author 28.08.2015 00:24 I'm implemented O(N) algo, and got 0.001s AC!. You can easily do it in O(N) with counting sort. | | For whom, who get WA 4 | Gleb Kazantaev (NNSTU) | 1084. Пусти козла в огород | 12 фев 2017 14:06 | 2 | if(a/2. >= r) { printf("%.3lf", pi*r*r); return 0; } This is 4th test, use only "%.3lf" ! Yeah, thanks a lot. There are terrible tests | | WA3 | 💻Evgeny Nemtsev [UrFU FT-17] | 1371. Грузоперевозки | 11 фев 2017 17:09 | 1 | WA3 💻Evgeny Nemtsev [UrFU FT-17] 11 фев 2017 17:09 Don't forget about cargo delivery time: 4 1 2 1 2 3 10 2 4 1 ------ 6 Edited by author 11.02.2017 17:10 | | Memory Limit. Dont know why. Pls help me to understand where i am wrong. | intueor | 1220. Stacks | 10 фев 2017 14:56 | 3 | I 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. | | WA1 ? | Nibir338 | 1109. Конференция | 10 фев 2017 14:44 | 1 | WA1 ? Nibir338 10 фев 2017 14:44 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; } | | что не так? | Kovalyshyn Artur | 1020. Ниточка | 9 фев 2017 19:16 | 2 | 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 | | What is wrong? / Что не так? | bulka94 | 1020. Ниточка | 9 фев 2017 19:07 | 3 | 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". | | What is test #4? | panLevan | 1821. Биатлон | 9 фев 2017 17:46 | 3 | 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 | | for C++ programmers | 💻Evgeny Nemtsev [UrFU FT-17] | 1102. Странный диалог | 9 фев 2017 17:38 | 1 | Don't use cin(TL1) and getc(WA1), use scanf and get AC: char s[(int)1e7]; scanf("%s", &s); length = strlen(s); | | Can anyone explain 1# test case? | Just_do_it | 1280. Topological Sorting | 8 фев 2017 13:01 | 2 | 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. | | C++ sliding window, queue | babaka | 1910. Руины титанов: сокрытый вход | 8 фев 2017 11:46 | 1 | #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; } | | wa9. | Andrew | 1068. Сумма | 6 фев 2017 17:28 | 2 | wa9. Andrew 27 ноя 2016 17:21 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(); } } } | | What is 33 Test? | ProeBos | 1854. Переговоры с Парфией | 6 фев 2017 05:24 | 7 | 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 | Aliaksei Vistiazh [netman] | 1110. Степень | 6 фев 2017 02:07 | 3 | 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; |
|
|