| Показать все ветки Спрятать все ветки Показать все сообщения Спрятать все сообщения |
| Test case 5 | Arinjay Patni | 1725. Аншлаг, аншлаг! | 15 янв 2015 03:05 | 1 |
Please help me .this code failed at test case 5
#include <stdio.h>
int main() {
int n,k;
scanf ("%d\n%d" ,&n,&k);
int l, pos;
l = n % 2 ;
if ( l != 0 || n < 1 || k < 1 || k > n || n > 50 )
{
printf("invalid input");
}
else
{
if (n != 2 )
{
if ( k <= n/2 )
{
pos = n/2 - k ;
printf("%d", pos);
}
else
{
pos = k - ((n/2) + 1 );
printf("%d", pos);
}
}
}
if ( n == 2 )
{
pos = 0;
printf("%d", pos);
}
return 0;
}
|
| Time limit exceeded | Lincoln | 1247. Проверка последовательности | 14 янв 2015 23:00 | 3 |
used:
...
for(i=1;i<=S;i++)
for(j=i;j<=S;j++)
...
But the result is 'Time limit exceeded'. Please help, why 'Time limit exceeded'? don't use brute force... O(n^2) n=30000 ===>>> time limit)
hint: you can don't use N in your solution brute force (with some optimizations) works fine |
| Test case 11 | aybek | 1018. Двоичная яблоня | 14 янв 2015 19:46 | 2 |
Hi, guys!
Can't move throw #11 test. Need help.
I just have build tree, and in every step removing smallest leaf.
At last, I count sum of left leaf's weight and print it.
But, algorithm don't pass at #11 test.
Thanks 7 3
1 2 12
1 3 1
2 4 30
2 5 30
3 6 30
3 7 30
Correct answer is 72, your answer 61 |
| test 3 and answer | Aleqsandre Skhirtladze | 1068. Сумма | 14 янв 2015 14:25 | 1 |
what is test #3; 3 or what?
don't you think that when n>0 answer is (n*(n+1))/2?
when n<0 answer is (-((n*(n-1))/2-1))?
when n=0 or n=1 answer is 1 ?
Edited by author 14.01.2015 14:52 |
| a confusing statement | yongwhan | 2024. Время приключений | 14 янв 2015 05:20 | 1 |
please change the wording of the statement:
"there should be at most k Rocks of pairwise different colors among the Rocks taken from the Cave" would be much better read if it is changed to "there should be at most k Rocks of different colors among the Rocks taken from the Cave."
in other words, the word 'pairwise' should be removed to make the statement clear.
Edited by author 14.01.2015 05:20
Edited by author 14.01.2015 05:21 |
| Ideas | Artem Khizha [DNU] | 1824. Ифрит-бомбардировки | 13 янв 2015 19:10 | 10 |
Ideas Artem Khizha [DNU] 19 мар 2011 18:26 I tried greedy approach during the contest, but got failed.
Idea was in bombing the city (even if it has been already destroyed) with the most number of remained cities in a radius. But WA#14.
Please, would you share any AC idea? My bruteforce dies with TL :( There should be some optimizations.
Edited by author 22.03.2011 12:31 Finally AC. Yes brootforce rules here. But it's a little BIT tricky brootforce.
Edited by author 22.03.2011 12:39 Idea:
Graph,
Minimal inner stable subset,
algo of Bron - Kerboach(effective brute force)
oh..(my God!?)
Idea:
Graph,
Minimal dominating set of vertices,
problem of set covering,
simplest brute force stack searching with table of covering reducing,
easy AC
By the way! To admin!.
It is interesting to make competiton
on one problem only(which is NP): minimal covering collection of sets.
This algo is very helpfull in practice.
Edited by author 25.03.2011 11:10 Could you explain the meaning of this "table of covering reducing"& I've never heard about it. My BF gives TL 10 :(
By the way, isn't the problem #1739 - Faryuks based on minimal covering collection of sets algo, as you want? "table of covering reducing"- my term(auto trans. is used)
Classical algo for minimal covering had good success in this problem
and under emotion I wrote that helping.
Again: we have NP problem but can to speed up.
So, in stack data we add matrix of covering for example as
1 0 1 0
0 1 1 1
0 1 1 1
This means that 4 points(columns) are covered by 3 sets(rows). First point is covered by only 1-th row and we must use Set-1 as obligatory.
Thus, the search tree hasn't branching in this-time vertex and we create
only one child vertex with reduced matrix:
1 1
1 1
because 1,3 points are covered by obligated row 1.
Finally: when we make choice for some set in search tree we transfer in child
vertex reduced matrix.
P.S. I had expirience in this algo from boolean design(all practice problem are NP). Re: Ideas Fetisov Alex [Psych Up club] 28 фев 2012 13:46 I did really stupid brute with simple speed up, like bit mask for graph and degree sorting for each connected component. AC with 0.3 seconds. to: svr
could you send me your solution of this problem, please? :D
my mail: night10101@yahoo.com
Edited by author 30.10.2012 22:29 SVR, please, can you tell me, how can you use idea of Bron - Kerboach algorithm and inner stable subset into this problem? It's really interesting and surprising for me.
How to use Bron - Kerboach for finding Minimal Dominating Set? Or how to reinterpret problem for searching inner stable subset? |
| file handling. | bright | 1414. Астрономическая база данных | 13 янв 2015 11:57 | 1 |
is file handling is necessary in this problem or not?.. |
| I have WA#1 | Dembel {AESC USU} | 1468. Дробь | 12 янв 2015 22:27 | 12 |
for input "10000 9999 10" my prog gives "1.(0001)".
But I have WA#1.
help me!
Edited by author 25.12.2006 11:40 And what about 1000 9999 10 ?
Good luck! Fixed. Dembel {AESC USU} 25 дек 2006 21:56 Correct answer is 0.1(0001),isn't it?
Thank you. but I have WA#1.
Please give me some test or hint
Edited by author 25.12.2006 22:02 Input
9800 9999 10
0 0
output
0.98(0098)
or
0.9(8009) input
4 4095 4
1 9999 10
10 9999 10
100 9999 10
1000 9999 10
10000 9999 10
9800 9999 10
3 2 8
0 0
output
0.00001(000001)
0.(0001)
0.001(0001)
0.01(0001)
0.1(0001)
1.(0001)
0.9(8009)
1.4
this output is correct,isn't it? Re: is it true? C-- AESC USU {Kurpilyanskij Gein Parfenenkov} 25 дек 2006 23:38 Correct output
0.(000010)
0.(0001)
0.(0010)
0.(0100)
0.(1000)
1.(0001)
0.(9800)
1.4 I have checked all the anwers in this post all are working fine and sample input is working fine still I got WA1??
Any idea for test1...
please provide some rigourous test Thank you!AC now!
Edited by author 12.01.2015 23:19 Correct answer for "1000 9999 10" is 0.(1000), not 0.1(0001). In another example 0.(9800) is correct, not 0.98(0098). Re: What answer C-- AESC USU {Kurpilyanskij Gein Parfenenkov} 25 дек 2006 23:34
Edited by author 25.12.2006 23:41 why?
'The output must not contain insignificant zeros.'
0.(1000) contain 3 zeroes on the end, don't it?
sorry bad English.
Edited by author 25.12.2006 23:42 |
| Explain example test case | rohit | 1468. Дробь | 12 янв 2015 22:26 | 2 |
For the case,
2794 6083 23
2794/6083, I get
0.4593128390596745027124 (in decimal)
But when I convert 0.ACM from base 23, I get
0.459275088353744 (in decimal)
Where is the mistake ? 2794 6083 23
reason：The correct result:0.ACMACMACMACM...........ACM....... (loop) |
| c++ AC | amirshir | 1581. Работа в команде | 11 янв 2015 23:19 | 1 |
c++ AC amirshir 11 янв 2015 23:19 #include <iostream>
using namespace std;
int main()
{
int n ;
cin>>n ;
int f,s,l ;
for(int i=0;i<n;i++)
{
cin>>s ;
if(i==0)
{
l=s ;
f=1 ;
}
else if(l!=s)
{
cout<<f<<" "<<l<<" " ;
f=1 ;
l=s ;
}
else
f++ ;
}
cout<<f<<" "<<l ;
} |
| Some hint about this problem. | Y.Y.M. | 1045. Забавная игра | 11 янв 2015 11:03 | 2 |
1. If we regard the start airport as the root,it is clear that the graph is a tree.
2. If start from all the leaf airport that from one airport could win, start from this airport suerly will lose. Otherwise,he could win.
3. We use a flag to record start from one airport will win or not.Just DFS to obtain all flag.
In this way,you could get AC in O(e).
Is there any better way to solve this problem?
I think the answer is yes.
So,could you write down your thought? I didn't want to create new thread, so I will just revive this thread.
My idead was to use simple minimax algorithm:
boolean firstWins(node v)
for every neighbour u of node v check secondWins(u)
return true if for some u second loses
return false
boolean secondWins(node v)
for every neighbour u of node v check firstWins(u)
return true if for some u first loses
return false
Hope it will be helpful to someone.
Edited by author 11.01.2015 11:04 |
| Help!! WA test 9 | tinrodriguez | 1837. Число Исенбаева | 11 янв 2015 05:21 | 1 |
|
| prim's algorithm | Adhambek | 1982. План электрификации | 10 янв 2015 17:19 | 1 |
|
| ACC on Java 8 :) | Сергей | 1001. Обратный корень | 10 янв 2015 00:04 | 1 |
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class Main {
static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
public static void main(String... args) throws Exception {
StringTokenizer tokenizer;
Stack<Double> stack = new Stack<Double>();
String line;
while ( (line = reader.readLine()) != null ) {
tokenizer = new StringTokenizer(line);
while (tokenizer.hasMoreTokens()) {
stack.add(Math.sqrt(Double.parseDouble(tokenizer.nextToken())));
}
}
while (!stack.empty()) {
System.out.println(stack.pop());
}
}
} |
| Admins! Java and TL... | HonoraryCoder | 1222. Chernobyl’ Eagles | 9 янв 2015 20:31 | 2 |
Please do something with TL on java applications. My usual programs gets TL too often. For example, normal solution in 1222 using DP and BigInteger has failed because of this problem. I had to use precalculations, but it's not so clear a normal solutions. I solved it with Python and 4 SLOC in 0.14 |
| If WA #6 | DKarev | 1796. Парк аттракционов | 9 янв 2015 19:55 | 2 |
First make the sum to determinate MIN and MAX money the teacher wanted to give. Then divide it by the price of one ticket. Do it in this order. Hope I helped! :) |
| What is wrong??? | Mosca Felice | 1360. Философский спор | 9 янв 2015 18:43 | 1 |
read(x,y);
readln(e);
t:=0;
if ((abs (x-sin(sqrt(t)))<=e) and (abs(y-cos(t))<=e))
then begin write('0') ; exit; end;
f1:=true;
f2:=true;
repeat
t:=t+e
until (abs(sin(sqrt(t))-x)<=e) and (abs(cos(t)-y)<=e) or (t>10e12) ;
if t>10e12 then write ('FAIL') else write(t:0:1); |
| A good problem for real philosophers. | Yaroslavtsev Grigory (SpbSPU) | 1360. Философский спор | 9 янв 2015 18:35 | 7 |
Nothing special to get AC, just think a little and write about 20 strings of code. Look what happens when T becomes large. !!!!!!!!!!!!!!!!!!!!!!!!!
What interval at you for T?
And what step of increase?
?????????????????????????? search(+)
little hint
repeat
t:=t+0.001;
until cos(t)-y<0.00001; Where is mistake?
read(x,y);
readln(e);
t:=0;
if ((abs (x-sin(sqrt(t)))<=e) and (abs(y-cos(t))<=e))
then begin write('0') ; exit; end;
repeat
t:=t+e
until (abs(sin(sqrt(t))-x)<=e) and (abs(cos(t)-y)<=e) or (t>10e12) ;
if t>10e12 then write ('FAIL') else write(t:0:1); |
| WA 10 some ideas>? | Roman Samokhin | 2010. Юный гроссмейстер Саша | 9 янв 2015 06:02 | 1 |
|
| WA #32 Who can give me test 32? Please! | Mosca Felice | 1880. Собственные числа Psych Up | 9 янв 2015 00:13 | 1 |
program ex; type z=array [1..4002] of longint; var n,n1,n2,i,t,k,s,j,l:longint; a,a1,a2,r:z; begin readln(n); for i:=1 to n do read(a[i]); readln(n1); for i:=1 to n1 do read(a1[i]); readln(n2); for i:=1 to n2 do read(a2[i]); j:=1; i:=1; k:=0; repeat if a1[j]>a[i] then i:=i+1; if a1[j]<a[i] then j:=j+1; if a1[j]=a[i] then begin k:=k+1; r[k]:=a1[j]; j:=j+1; end; until (i>=n) or (j>=n2) ; i:=1; j:=1; s:=0; repeat if r[j]>a2[i] then i:=i+1; if r[j]<a2[i] then j:=j+1; if r[j]=a2[i] then begin s:=s+1; j:=j+1; end; until (i>=n2) or (j>=k) ; write(s); end. |
