| Show all threads Hide all threads Show all messages Hide all messages |
| What is the easiest way to solve this problem?(I have already got AC) | Ярославцев Григорий | 1066. Garland | 24 Jun 2013 14:19 | 9 |
My solution uses binary search to find such height for second lamp that garland is never under the floor and this height is the lowest possible. For checking that garland is never under the floor I use simple O(N). I have used a simulation method, first I have built that garland thinking that second lamp is at the same height as first, then Ive calculated then minimum of i*H[i] and lowered the garland by the result, and the resulted height of Nth lamp was the answer. Overall O(n) I think. I like the idea of binary search, but I check that garland is never under the floor in O(1).
It easily can be proved, that the garland has an equation x*x+p*x+A. p is a parameter of binary search. Also it's known, that such a parabola(defined in integer points only) has minimum in floor(0.5-p/2). So the checking is very easy.
Edited by author 27.07.2004 14:40 Knowing that the form of the garland is parabola and knowing exact solution for h[i], it is very easy to check minimal B:
n--;
for(i=1;i<n;i++)
if((tmp=(n-i)*(n*i-a)/i) >b) b = tmp;
That's all! b is answer! It is short. But while you will think about a garland's form, I will have written a solution, based on binary search. In real competition it is better. Actually,we can get the formula by mathematical induction very easily.We can see:
h1=h1,
h2=h2,
Since hn+1=2hn-h(n-1)+2,
so we can find:
h3=2h2-h1+2,
h4=3h2-2h1+6,
h5=4h2-3h1+12,
and by mathematical induction,not difficult to prove:
hn=(n-1)h2-(n-2)h1+n(n+1).
Thus we can trace every hi>0 and get the minimum for h2 and then we can find hn. Guys why this cleverness. Binary search - is solution that author recognized I think. But about parabolf thinking is good idea - you're clever boys ;) I have change h2 to h, h1 to A and n to x. Then i have get something like x^2+bx+c. hn>0 if that formula ax^2+bx+c>=0. Its possible only if D<=0. I have found and get the othe formula but now with h like h^2+bh+c.
After that i have found h1 and h2, and choose the smallest bigger than 0. And that result i have written in the first formula, and have found B. But the problem that my result is different from the real, but not very much.
its my code:
#include <stdio.h>
#include <math.h>
int main()
{
int N,i;
double h1,h2,A,B,min;
scanf("%d%lf",&N,&A);
h1=A+1.0+2*sqrt(A);
h2=A+1.0-2*sqrt(A);;
if(h2<h1&&h2>0) min=h2;
else min=h1;
B=(N-1)*min-(N-2)*A+(N-1)*(N-2);
printf("%0.2lf",B);
return 0;
}
PS sorry for my English
Edited by author 27.06.2008 02:38 a2=(1/2)a1 + (1/2)a3 -1
a3=(1/3)a1 + (2/3)a4 -2
a4=(1/4)a1 + (3/4)a5 -3
...
an=(1/n)a1 + ((n-1)/n) a(n+1) - (n-1)
Just by putting a2 into a3's initial formula a3=(1/2)(a2+a4) -1 and so on, you can get the relationship of an and a(n+1), then you can guess An, and calculate the whole sequence. As long as ai>=0, An can be lower, in this way you'll get the answer. |
| only use one change | Huang Chen | 1007. Code Words | 24 Jun 2013 08:56 | 1 |
1 Any (but only one) symbol 0 is replaced by 1.
2 Any (but only one) symbol is removed.
3 A symbol (0 or 1) is inserted at any position.
a word is changed only once through 1 or 2 or 3. so it needn't think about a word is changed by both or three. |
| Easy problem! | Adhambek | 1873. GOV Chronicles | 23 Jun 2013 20:12 | 1 |
answer of output :
Миша — 5
Вадик — 20
Лёша — 12
Саша — 2
Ваня Б. — 1
Никита — 4
Федя — 6
Ваня К. — 1
Ден — 4
Егор — 4
Сяохун — 1
Виталий — 0 |
| How can I improve this program? | thefourtheye | 1017. Staircases | 23 Jun 2013 16:06 | 2 |
Num = int(raw_input())
Array = [0] * (Num + 1)
def Rec (Sum, Start):
global Array
if Start == Num + 1 or Sum + Start > Num: return
if Sum + Start <= Num and Sum != 0: Array[Sum + Start] += 1
Rec (Sum + Start, Start + 1)
Rec (Sum, Start + 1)
Rec (0, 1)
print Array[Num]
It produces following output (first column input, second column output)
0 0
1 0
2 0
3 1
4 1
5 2
6 3
7 4
8 5
9 7
10 9
11 11
12 14
13 17
14 21
15 26
16 31
17 37
18 45
19 53
20 63
But it exceeds 1 sec limit when the input is 88.
Edited by author 23.06.2013 10:28
Edited by author 23.06.2013 10:28 Num = int(raw_input())
Array = [0] * (Num + 1)
def Rec (Sum, Start):
global Array
if Start == Num + 1 or Sum + Start > Num: return
if Sum + Start <= Num and Sum != 0: Array[Sum + Start] += 1
Rec (Sum + Start, Start + 1)
Rec (Sum, Start + 1)
Rec (0, 1)
print Array[Num]
It produces following output (first column input, second column output)
0 0
1 0
2 0
3 1
4 1
5 2
6 3
7 4
8 5
9 7
10 9
11 11
12 14
13 17
14 21
15 26
16 31
17 37
18 45
19 53
20 63
But it exceeds 1 sec limit when the input is 88.
Never mind. Memoization did the trick. |
| WA #4 | igloo | 1100. Final Standings | 23 Jun 2013 14:41 | 1 |
WA #4 igloo 23 Jun 2013 14:41 i get WA when i use for M unsigned char. i replace to unsigned short and get AC. Used merge sort. |
| how to solve this ?????????????? | Dulat_KBTU | 1017. Staircases | 22 Jun 2013 21:49 | 3 |
|
| Open Ural FU Personal Contest 2013 | lacbs | | 22 Jun 2013 19:50 | 1 |
When will it be available on archive to submit? |
| Unable to understand question | annonynous | 1209. 1, 10, 100, 1000... | 22 Jun 2013 18:20 | 4 |
for the given 5 sample how 4 values 0 0 1 0 are coming. please explain anybody 1101001000 1 0 0 0 0
k: 1234567891011
example:
k = 2 ==> 1
k = 3 ==> 0
k = 7 ==> 1 You must know how to generate the sequence first! And then the input gives the position for the given 5 sample how 4 values 0 0 1 0 are coming. please explain anybody |
| wtf? | sfersox | 1961. Cantonese Dialect | 22 Jun 2013 18:06 | 4 |
wtf? sfersox 22 Jun 2013 15:29 Re: wtf? Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 22 Jun 2013 17:54 Statement is more than clear. Solution is not that trivial. I can not understand this string "Help Vova to find such M, which maximizes the probability that exactly m out of n random passers-by speak Cantonese." What does it mean? Re: wtf? Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 22 Jun 2013 18:06 This means exactly what is written - for any possible M there is some probability that, when taken n people out of N, exactly m of them will speak Cantonese. You want to estimate M in a way to maximize that probability. This is called maximum likelihood approach in statistics. |
| WA#13 | kxurshid | 1402. Cocktails | 22 Jun 2013 17:14 | 6 |
WA#13 kxurshid 19 Sep 2009 01:43 My code:
#include <iostream>
using namespace std;
double fac(int n)
{
double l = 1.0;
for(int i = 1; i <= n; i++)
l *=i;
return l;
}
double A(int m, int n)
{
return fac(m)/fac(m-n);
}
void main()
{
int n;
double soni = 0;
cin >> n;
for(int i = 2; i<=n; i++)
{
soni += A(n,i);
}
cout.precision(0);
cout << fixed << soni;
}
WA#13
Where is my mistake? pls help me i have met the same problem with u Precision
Edited by author 28.01.2012 00:07
Edited by author 28.01.2012 00:07 primer
21=138879579704209680000
19=330665665962403980
20=6613313319248079980 0-1
2-2
3-12
4-60
5-320
6-1950
7-13692
8-109592
9-986400
10-9864090
11-108505100
12-1302061332
13-16926797472
14-236975164790
15-3554627472060
16-56874039553200
17-966858672404672
18-17403456103284402
19-330665665962403980
20-6613313319248079980
21-138879579704209680000 |
| Test 19 | aaa | 1402. Cocktails | 22 Jun 2013 17:11 | 3 |
What is the right answer in test 19 ? |
| Может ли Вова разворачиваться возле статуй? | Uran | 1966. Cycling Roads | 22 Jun 2013 15:25 | 2 |
Edited by author 22.06.2013 15:11 |
| easy for the Java coders | Konstantin Yovkov | 1243. Divorce of the Seven Dwarfs | 22 Jun 2013 14:47 | 2 |
If you use BigInteger the program is e-a-s-y :) Got AC from the first try :) Not only Java, but Python and Ruby as well. |
| B (when i>m)is not required according to a fixed position to sit? | hnust_liuwenjing | 1962. In Chinese Restaurant | 22 Jun 2013 14:03 | 1 |
Edited by author 22.06.2013 14:08 |
| Don't understand the problem | Prime | 1287. Mars Canals | 22 Jun 2013 09:22 | 3 |
can someone please explain the problem, specially the part "(parallel to the north-south or east-west directions or at the angle 45° to them)" and the first sample input-output. At last I have understood the problem (thanks to Fahim and Sadia). You have to consider either north-south, or east-west or diagonal straight lines; consider which yields highest amount of crop of a kind instead of all of them together.
More clearly, for first test,
SsS
sSs
SsS
my confusion was
_s_
s_s
_s_
we can get a ring of 4 's' ... so the ans should be
s
4
but later my friends explained consider only one straight line,which ever produces most as
S__
_S_
__S
or
_s_
s__
___
or
___
__s
_s_
Hope my problem helps other. |
| Runtime error (access violation) and I don't know why? | kaa..........ai | 1086. Cryptography | 21 Jun 2013 21:39 | 2 |
Here's my code:
#include<iostream>
using namespace std;
int pri[20000],pr[4040000];
void p()
{
memset(pr,0,sizeof(pr));
int i,j;
for(i=2;i<=1500;i++)
for(j=i*i;j<4000000;j+=i)pr[j]=1;
int kk=1;
for(i=2;i<=4000000;i++)
if(pr[i]==0)pri[kk++]=i;
}
int main()
{
int n,t;
p();
while(scanf("%d",&n)!=-1)
{
while(n--)
{
scanf("%d",&t);
printf("%d\n",pri[t]);
}
}
return 0;
}
What's wrong with it?Who can help me?
Edited by author 21.06.2013 21:02 Cheer up!
Solved!
Here's my code:(一个合适的范围是看来是很必要的啊！）
#include<iostream>
using namespace std;
int pri[20000];
int pr[204000];
void p()
{
int i,j;
for(i=0;i<=200000;i++)pr[i]=1;
for(i=2;i<=447;i++)
for(j=i*i;j<200000;j+=i)pr[j]=0;
int kk=1;
for(i=2;i<=200000&&kk<=15010;i++)
if(pr[i])pri[kk++]=i;
}
int main()
{
int n,t;
p();
while(scanf("%d",&n)!=-1)
{
while(n--)
{
scanf("%d",&t);
printf("%d\n",pri[t]);
}
}
return 0;
} |
| If you have WA 4 | Alexey Dergunov [Samara SAU] | 1959. GOV-internship 3 | 21 Jun 2013 21:26 | 1 |
There are no zeroes in this test. |
| You use BigIntegers or strings | Adhambek | 1206. Sum of Digits of the Sum of Numbers | 21 Jun 2013 21:05 | 1 |
because ,
input:
n = 50
Length of output is 87 digits
output :
682455418022864824778975492858747729001539122984270520078098343219608068466186523437500
Edited by author 21.06.2013 21:07 |
| WA #5 | igloo | 1891. Language Ocean | 21 Jun 2013 02:08 | 1 |
WA #5 igloo 21 Jun 2013 02:08 In one line more then one error.
1
ReadInt2() : int
ReadInt(int) : int
2
int x = ReadInt2()
int x = ReadInt(y) |
| To admins : two possible answers | sylap | 1303. Minimal Coverage | 21 Jun 2013 00:56 | 1 |
For Input :
10
-5 1
1 14
-5 2
2 3
3 19
0 0
Output1 :
2
-5 1
1 14
Output2 :
2
-5 2
1 14
Are both output1 and output2 considered as correct ?
EDIT At least output2 is considered as CORRECT. (Finally solved :D)
Edited by author 21.08.2013 18:18 |
