| Show all threads Hide all threads Show all messages Hide all messages |
| this is a famous problem | dingalapadum | 1203. Scientific Conference | 20 Jan 2016 09:20 | 2 |
This is a famous problem known as "interval scheduling". |
| WA on test 22. Is it a specific test? | Blademaster | 1212. Battleship | 20 Jan 2016 08:13 | 6 |
Yes. I have WA on test 22 too. Hello!
I had WA on 22 test too. But later I realized that the two numbers in the input N and M mean N - the number of boxes verticaly and M - the number of boxes horizontaly. While I read the input as if they were the opposite. So, if you are wondering why your program doesn't work check this :). Maybe all the previous tests (1-21) hare N=M i don't know. yes, me too, WA on 22. I flipped M and N and AC. I flipped M and n and AC,too!
Maybe the problem's description is wrong... |
| please give an idea | melkiy | 1726. Visits | 20 Jan 2016 01:45 | 12 |
I use the fomula to find average of n values X[i], i=1...n if I know the average of (n-1) values X[i], i=1...(n-1):
AVE(X, n) = ((n-1)AVE(X, n-1) + X[n]) / n
This doesn't help. 1.sort(X[]).
2.add (X[i+1]-X[i])*i*(n-i). Brilliant idea. I've got it.
Thanks. i've got smth similar but i don't understand how to sort it... pls help I don't have any ideea... how did you solve this problem? I've got TLE ... I use brute force.. LOL Doesn't work with 4 10 10 10 20 20 10 20 20!
1.sort(X[]).
2.add (X[i+1]-X[i])*i*(n-i).
Edited by author 07.04.2011 01:25 how do you sort it, what is min and what is max after sort... i've got WA for 3 20 20 30 30 50 10 must work!
segment[X[i],X[i+1]] is passed by all pairs from [1..i]*[i+1,..n] or i*(n-i) times
where i in[1..n-1] i still don't get it... pls send me your source at lerh_91@live.com Because for a given point i we can only go to another point vertically or horizontally and that's a great hint.
Consider an input file that contains 7 points (index from 1 to n), and now we have sorted them by x[] in ascending order.
Now let's consider the segment between point 5 and point 6, denoted by S(S=x[6]-x[5], remember that we have sorted the points by x[]). Now if we want to go from point 2 to point 6, we must pass through S, and likewise, if we want to go from point 1,2,3,4,5 to point 6,7, we have to pass through S. Inversely, from point 6,7 to point 1,2,3,4,5, we must pass through S. Actually, for a given segment x[i+1]-x[i], we have to pass through this segment i*(n-i)*2 times, for there are i points before and including the ith point and (n-i) points after the ith point, and we have to go from left to right and from right to left. This analysis is also true for the y coordinate.
By this method we can get the total distance from every point to every other point.
Finally just divide the total distance by (n*(n-1)) to get the average distance because there are n points and each point has (n-1) road to the other points.
In conclusion, the solution would be :
for(i = 1 to n-1)
{
ans += (x[i+1]-x[i]) * i * (n-i) * 2;
ans += (y[i+1]-y[i]) * i * (n-i) * 2;
// or ans += (x[i+1]-x[i] + y[i+1]-y[i]) * i * (n-1) * 2;
}
ans /= ( n*(n-1) )
Be careful about the data type of ans, int is not enough, use long long |
| I think there is something wrong | MishaRash | 2008. Swifty | 19 Jan 2016 17:34 | 4 |
I solved this problem theoretically and checked ability of a jump by counting the discriminant of square equation.
I got WA on tests 30-32 using floating point numbers and trying to find good precision (type double in C) and rewrote my program using long integer type (long long) with no precisions.
The first thing I noticed is that I got WA on test 20 when I say that jump is possible if D>=0. If I check D>0, I get WA on test 32. I'm sure it's not correct, because if D=0 exactly jump is still possible.
I thought the problem could be in overflowing. Despite long long must be enough, I rewrote the program in Python 3 to avoid overflowing for sure and nothing changed.
So I think I am right and there are wrong tests. I can show my source code if needed.
Edited by author 20.07.2015 18:27 By the way, I got AC on FreePascal using the condition that is less strict because of precisions. Approve this. Only condition D >= 0 allows test like this
0
0 1
0 0
0 2
There is additional check needed. This magic works:
L^2*g^2<=(V^2-g*(y2-y1))^2 implem. in long long(g=98/10) |
| WA 25# | wangchong756 | 1297. Palindrome | 19 Jan 2016 17:27 | 1 |
WA 25# wangchong756 19 Jan 2016 17:27 I got a wrong answer on 25 but I don't know why.
Is there someone could give me some tests? |
| wrong answer why? | kodirmullaboyev | | 19 Jan 2016 11:27 | 1 |
import java.util.Scanner;
/**
* Created by Oxygen! on 19.01.2016.
*/
public class ProstoeVirajenie2066Var3 {
// 2066. Простое выражение
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int a=sc.nextInt();
int b=sc.nextInt();
int c=sc.nextInt();
if(0<=a && a==b && a==c || a>b || a>c || b==c || a>=c && b>a || a==b && b<c && c<=100) {
System.out.print(a-b-c);
} else if(0<=a && a<b && b<c || b>c && c<=100) {
System.out.print(a-b*c);
} else {
System.out.print("error");
}
}
} |
| No subject | Sirko | 1790. Searching for the Truth | 19 Jan 2016 04:10 | 1 |
Thinking of kittens and doors rather than Dodecahedrons helped me to find O(N) solution :) |
| No subject | Felix_Mate | 1246. Tethered Dog | 18 Jan 2016 22:42 | 1 |
Edited by author 19.01.2016 11:10 |
| Used the adjacent list | zhangweilst | 1106. Two Teams | 18 Jan 2016 19:47 | 2 |
But established it with an error which makes me WA #13.
Guess cases before #13 are simple with no big number of vex. Use BFS - i get AC. Make array size as n items. Rules for filling:
0 items equals -1, if first elements have childs them set 1 and use recurce. |
| WA#3 | wodesuck | 2042. Nikita | 18 Jan 2016 16:57 | 2 |
WA#3 wodesuck 5 Jun 2015 14:08 Re: WA#3 Qantas [SESC 17] 18 Jan 2016 16:57 |
| answer c# | >OWL< | 1910. Titan Ruins: Hidden Entrance | 17 Jan 2016 15:37 | 1 |
using System;
using System.Linq;
class Program {
static void Main() {
int n = int.Parse(Console.ReadLine());
string[] a = Console.ReadLine().Split(' ');
int[] a_sum = new int[a.Length - 2];
for(int i = 0; i < a_sum.Length; i++) {
a_sum[i] = int.Parse(a[i]) + int.Parse(a[i + 1]) + int.Parse(a[i + 2]);
}
for(int i = 0; i < a_sum.Length; i++) {
if(a_sum[i] == a_sum.Max()) {
Console.WriteLine("{0} {1}", a_sum.Max(), i + 2);
}
}
}
} |
| answer c# | >OWL< | 1880. Psych Up's Eigenvalues | 17 Jan 2016 15:12 | 1 |
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);
}
} |
| answer c# | >OWL< | 1197. Lonesome Knight | 17 Jan 2016 14:35 | 1 |
using System;
class Program {
static void Main() {
int n = int.Parse(Console.ReadLine());
string[] move = new string[n];
for(int i = 0; i < n; i++) {
move[i] = Console.ReadLine();
}
for(int i = 0; i < n; i++) {
if(move[i][0] >= 'c' && move[i][0] <= 'f' &&
move[i][1] >= '3' && move[i][1] <= '6') {
Console.WriteLine(8);
}
else if(((move[i][0] == 'b' || move[i][0] == 'g') && move[i][1] >= '3' && move[i][1] <= '6') ||
((move[i][1] == '2' || move[i][1] == '7') && move[i][0] >= 'c' && move[i][0] <= 'f')) {
Console.WriteLine(6);
}
else if(move[i] == "a1" || move[i] == "a8" || move[i] == "h8" || move[i] == "h1") {
Console.WriteLine(2);
}
else if((move[i][0] == 'a' && (move[i][1] == '2' || move[i][1] == '7')) ||
(move[i][0] == 'b' && (move[i][1] == '1' || move[i][1] == '8')) ||
(move[i][0] == 'g' && (move[i][1] == '1' || move[i][1] == '8')) ||
(move[i][0] == 'h' && (move[i][1] == '2' || move[i][1] == '7'))) {
Console.WriteLine(3);
}
else
Console.WriteLine(4);
}
}
} |
| Picture gives examples of staircase | alp | 1017. Staircases | 16 Jan 2016 20:32 | 3 |
Autors! you are wrong. fix please. It's allright!
You cannot have two neighbour stair steps with horizontal difference more than 1. |
| What are Union-Find/Disjoint Set Timus Problems? | alekscooper | | 16 Jan 2016 17:37 | 1 |
Hello guys,
I've just started learning algorithms and I've read a piece from R. Sedgewick's book on Algorithms about Union Find.
I'd love to practice it. Could anyone recommend any problems here? Thanks. |
| WA8 Why? | Vincent Kotwizkiy [SESC] | 1636. Penalty Time | 15 Jan 2016 21:23 | 2 |
WA8 Why? Vincent Kotwizkiy [SESC] 31 Mar 2013 04:40 Can anybody give me test 8? Code on python2: a, b = map(int, raw_input().split(' ')) k = 0 c = map(int, raw_input().split(' ')) for x in xrange(1,10): k = k+c[x]*20 if b-k>a: print('No chance.') elif b-k<a: print('Dirty debug :(') elif b-k==a: print('No chance.') xrange(1, 10) only takes array elements 1-9. You need to use xrange(0, 10) to get elements 0-9 |
| Just use next_permutation() in C++! | GastonFontenla | 2011. Long Statement | 15 Jan 2016 17:36 | 1 |
next_permutation() generates distinct permutations of a given iterable object (vector, string, etc). Just make 6 permutations, and save each of them in a set<vector<int> >. Finally, check if the size of the set is 6, because the set only saves different elements. Pretty easy solution. |
| Follow your friends on Timus! (Chrome extension) | 🦄 Slava Shklyaev | | 15 Jan 2016 02:02 | 1 |
|
| WA#13 FreePascal | Desire | 1964. Chinese Dialects | 14 Jan 2016 04:03 | 3 |
Here is my code. What is wrong? Help, please! var m,n:int64; k,i:0..20; a:array[1..20] of int64; begin read(n,k); for i:=1 to k do read(a[i]); for i:=2 to k do if a[i]<a[i-1] then begin m:=a[i]; a[i]:=a[i-1]; a[i-1]:=m end; m:=n-(n-a[1])-(n-a[2]); if m<=0 then write(0) else write(m); end. Edited by author 02.11.2013 04:21You must only write((a1+a2+...+ak)-n)
That's all))
Good luck! no, right answer is ((a1+a2+...+ak)-n * (k-1)) |
| C++ What's wrong with my code? | zimozi | 2001. Mathematicians and Berries | 14 Jan 2016 00:40 | 4 |
#include <iostream> using namespace std; int main() { int a[3],b[3]; for (int i = 0;i<3;i++) {cin>>a[i]>>b[i]; } cout<<a[0]-a[2]<<b[0]-b[1]; return 0; } Where am I must write the space? Only in output? between ans1 << " " << ans2; |
