Как доказать что там период ? при этом длина периода маленькая.
2 2010-08-22 06:13:00
Тема: acm.sgu.ru 124 (1 ответов, оставленных в Problems)
помогите найти ошибку в коде !!! WA 6 test
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <fstream>
#include <vector>
using namespace std;
int x1[20000],w1[20000],x2[200000],y2[200000],n,x,y;
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d",&n);
for (int i = 0; i < n; i++) {
scanf("%d%d%d%d",&x1[i],&w1[i],&x2[i],&y2[i]);
}
scanf("%d%d",&x,&y);
long double ans = 0;
for (int i = 0 ; i < n; i++) {
if (x1[i] == x2[i] && x == x1[i]) {
if (w1[i] <= y && y <= y2[i] ) {
puts("BORDER");
return 0;
}
if (y2[i] <= y && y <= w1[i]) {
puts("BORDER");
return 0;
}
}
if (w1[i] == y2[i] && y == w1[i]) {
if (x1[i] <= x && x <= x2[i] ) {
puts("BORDER");
return 0;
}
if (x2[i] <= x && x <= x1[i]) {
puts("BORDER");
return 0;
}
}
long double vect = (x1[i]-x)*(y2[i]-y) - (w1[i]-y)*(x2[i]-x);
long double scal = (x1[i]-x)*(x2[i]-x)+(w1[i]-y)*(y2[i]-y);
ans+=atan2(vect,scal);
}
if (fabs(ans) < 1e-3 ) puts("OUTSIDE"); else
puts("INSIDE");
return 0;
}3 2010-08-22 06:10:32
Тема: acm.sgu.ru 144 (2 ответов, оставленных в Problems)
Не могу понять!!!! почему тупое решение не проходит ?
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
int x,y;
double z;
cin>>x>>y>>z;
double cnt = 0 ,win = 0;
for (int i = 0; i <= 60*(y-x); i++)
for (int j = i; j <= 60*(y-x); j++)
{
cnt++;
if (abs(j-i) <= z) win++;
}
printf("%.7lf",win/cnt);
return 0;
}4 2010-05-27 12:12:34
Re: Задача Кактусы (2 ответов, оставленных в Problems)
Код непонятый. Объясните плз, в чем идеа!!!! вот Код:
import java.util.*;
import java.io.*;
import java.math.BigInteger;
public class cacti_as implements Runnable {
final long MOD = 1000000007;
final long INV2 = BigInteger.valueOf(2).modInverse(BigInteger.valueOf(MOD)).longValue();
public void solve() throws IOException {
Scanner in = new Scanner(new File("cacti.in"));
PrintWriter out = new PrintWriter("cacti.out");
int n = in.nextInt();
long[] fact = new long[n + 1];
fact[0] = 1;
for (int i = 1; i <= n; i++) {
fact[i] = (fact[i - 1]) * i % MOD;
}
long[][] c = new long[n + 1][n + 1];
c[0][0] = 1;
for (int i = 1; i <= n; i++) {
c[i][0] = 1;
for (int j = 1; j <= n; j++) {
c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % MOD;
}
}
long[] a = new long[n + 1];
long[] ah = new long[n + 1];
a[0] = ah[0] = 1;
a[1] = ah[1] = 1;
for (int i = 2; i <= n; i++) {
for (int k = 1; k <= i - 1; k++) {
ah[i] = (ah[i] + (k * c[i - 2][k - 1] % MOD * a[k] % MOD * ah[i - k]) % MOD) % MOD;
}
for (int l = 3; l <= i; l++) {
long[][] d = new long[l][i - l + 1];
for (int k = 0; k <= i - l; k++) {
d[0][k] = (c[i - 1][k] * ah[k + 1]) % MOD;
}
for (int j = 1; j < l; j++) {
for (int k = 0; k <= i - l; k++) {
for (int t = 0; t <= k; t++) {
d[j][k] = (d[j][k] + d[j - 1][k - t] * c[i - j - k + t][t + 1] % MOD * ah[t + 1] % MOD * (t + 1) % MOD) % MOD;
}
}
}
a[i] = (a[i] + d[l - 1][i - l] * INV2) % MOD;
}
a[i] = (a[i] + ah[i]) % MOD;
// System.out.println(a[i]);
}
out.println(a[n]);
long[] b = new long[n + 1];
long[] bh = new long[n + 1];
b[0] = bh[0] = 1;
b[1] = bh[1] = 1;
for (int i = 2; i <= n; i++) {
for (int k = 1; k <= i - 1; k++) {
bh[i] = (bh[i] + (k * c[i - 2][k - 1] % MOD * b[k] % MOD * b[i - k]) % MOD) % MOD;
}
for (int l = 3; l <= i; l++) {
long[][] d = new long[l][i - l + 1];
for (int k = 0; k <= i - l; k++) {
d[0][k] = (c[i - 2][k] * b[k + 1]) % MOD;
}
for (int j = 1; j < l; j++) {
for (int k = 0; k <= i - l; k++) {
for (int t = 0; t <= k; t++) {
d[j][k] = (d[j][k] + d[j - 1][k - t] * c[i - j - k + t][t + 1] % MOD * b[t + 1] % MOD * (t + 1) % MOD) % MOD;
}
}
}
b[i] = (b[i] + d[l - 1][i - l] * INV2) % MOD;
}
b[i] = (b[i] + bh[i]) % MOD;
System.out.println(b[i]);
}
out.println(b[n]);
in.close();
out.close();
}
public void run() {
try {
solve();
} catch (IOException e) {
}
}
public static void main(String[] arg) {
new Thread(new cacti_as()).start();
}
}5 2010-05-21 21:26:41
Тема: Задача Кактусы (2 ответов, оставленных в Problems)
Как можно решить такую задачу ?
http://algoprog.kz/ej/contests/5/statements/kaktusi/
Заранее спасибо!!!
6 2010-05-21 19:48:02
Re: Задача (6 ответов, оставленных в Problems)
Ура ошибку нашел.
d[to] = min(d[to],Calc(d[pos]+w*k,to));
здесь должно быть
d[to] = min(d[to],Calc(d[pos]+w/k,to));
7 2010-05-21 19:48:01
Re: Задача (6 ответов, оставленных в Problems)
Ура ошибку нашел.
d[to] = min(d[to],Calc(d[pos]+w*k,to));
здесь должно быть
d[to] = min(d[to],Calc(d[pos]+w/k,to));
8 2010-05-18 06:43:23
Re: Задача (6 ответов, оставленных в Problems)
Ну , я так же решил . Но не выходит 
9 2010-05-13 19:42:22
Re: Обратная функция tan() (1 ответов, оставленных в Problems)
#include <cmath>
atan(alpha)
10 2010-05-13 17:09:18
Тема: Задача (6 ответов, оставленных в Problems)
Помогите плз . Вроде задача легкая , но немогу найти ошибку в коде.
http://algoprog.kz/ej/contests/5/statements/svetofori
#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
using namespace std;
#define f first
#define s second
#define mp make_pair
int n,m,st,fn;
double k,d[100000],xx[100000],yy[100000];
bool u[100000];
vector<pair<int,double> > a[100000];
double Calc(double T,int v)
{
if (v == fn) return T;
double W = xx[v] + yy[v];
long long x = (long long)floor(T/W);
while (x*W < T) x++;
x--;
if (x*W + xx[v] >= T) return T;
return x*W + W;
}
int main()
{
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
scanf("%d%d%lf",&n,&m,&k);
for (int i = 0; i < m; i++) {
int l,r;
double w;
scanf("%d%d%lf",&l,&r,&w);
a[l].push_back(mp(r,w));
a[r].push_back(mp(l,w));
}
for (int i = 1; i <= n; i++) scanf("%lf%lf",&xx[i],&yy[i]);
scanf("%d%d",&st,&fn);
double inf = (1ll<<59);
for (int i = 1; i <= n; i++) d[i] = inf;
d[st] = 0;
while (true) {
int pos = -1;
for (int i = 1; i <= n; i++)
if (!u[i] && (pos == -1 || d[pos] > d[i])) pos = i;
if (pos == -1 || d[pos] == inf) break;
u[pos] = true;
for (int i = 0; i < a[pos].size(); i++) {
int to = a[pos][i].f;
double w = a[pos][i].s;
d[to] = min(d[to],Calc(d[pos]+w*k,to));
}
}
if (d[fn] == inf) puts("-1"); else
printf("%.4lf",d[fn]);
return 0;
}11 2009-06-23 12:03:44
Re: zadachka s acm.mipt.ru (145. Antiplagiat II) (4 ответов, оставленных в Problems)
Thanks !!!!
12 2009-06-23 09:22:52
Re: zadachka s acm.mipt.ru (145. Antiplagiat II) (4 ответов, оставленных в Problems)
net ya pisal Суффиксное Дерево . A kak reshat s pomochu suffix massiva?
Mojezh skinut kod(Madiyar_TKTL@mail.ru)
13 2009-06-13 19:24:42
Тема: zadachka s acm.mipt.ru (145. Antiplagiat II) (4 ответов, оставленных в Problems)
Ya reshil etu zadachu tolko za o(n*logn*logn).
No snachala ya reshal za O(n) (Suffix Tree Ukkonean) (ne poluchilsya) Time Limit 6 test
Ya vstroel suffix Tree dlya stroki S#T$ , potom proshol rekursivno.
Pomogite naiti oshibku v kode.
#include <iostream>
#include <string>
using namespace std;
const int maxn = 100000;
struct ST {
int l,r,p,suf,fl,len;
int a[28];
} a[maxn*2];
int s[maxn],nb,cur,flag,inf,ans,ver,p[maxn];
string s1,s2,ss;
int FindSuff(int cur,int k)
{
int l=k;
while (cur!=1 && !a[cur].suf) {
l-=(a[cur].r-a[cur].l+1);
cur=a[cur].p;
}
if (cur==1) l++; else cur=a[cur].suf;
if (l>k) return 0;
while (l<k) {
cur=a[cur].a[s[l]];
l+=(a[cur].r-a[cur].l+1);
}
if (l!=k) {
nb++;
int par = a[cur].p;
l-=(a[cur].r-a[cur].l+1);
a[nb].l=a[cur].l;
a[nb].r=a[nb].l+k-l-1;
a[cur].l = a[nb].r+1;
a[nb].p = par;
a[cur].p = nb;
a[par].a[s[ a[nb].l ]] = nb;
a[nb]. a[s[ a[cur].l ]] = cur;
a[nb].fl = 0;
a[nb].len = a[a[nb].p].len+ a[nb].r-a[nb].l+1;
return nb;
}
return cur;
}
void Add(int k)
{
while (true) {
if (!a[cur].a[s[k]]) {
a[cur].a[s[k]] = ++nb;
a[nb].p = cur;
a[nb].l = k;
a[nb].r = inf;
a[nb].fl = flag;
a[nb].len = a[a[nb].p].len+ a[nb].r-a[nb].l+1;
if (cur==1) return;
a[cur].suf = FindSuff(cur,k);
cur = a[cur].suf;
continue;
}
a[cur].suf = FindSuff(cur,k);
cur= a[cur].a[s[k]];
if (a[cur].r!=a[cur].l) {
nb++;
int par = a[cur].p;
a[nb].l=a[nb].r=a[cur].l;
a[cur].l = a[nb].r+1;
a[nb].p = par;
a[cur].p = nb;
a[par].a[s[ a[nb].l ]] = nb;
a[nb]. a[s[ a[cur].l ]] = cur;
a[nb].fl = 0;
a[nb].len = a[a[nb].p].len+ a[nb].r-a[nb].l+1;
cur=nb;
}
return;
}
}
int Dfs(int cur)
{
if (a[cur].fl) return a[cur].fl;
bool u[4];
u[0]=u[1]=u[2]=u[3]=false;
for (int i=0;i<28;i++)
if (a[cur].a[i]) u[Dfs(a[cur].a[i])] = true;
u[3]=(u[3]||(u[1] && u[2]));
if (u[3]) {
if (ans < a[cur].len) ans=a[cur].len,ver=cur;
return 3;
}
if (u[1]) return 1;
if (u[2]) return 2;
return 0;
}
void WriteS(int cur)
{
if (cur==1) return;
WriteS(a[cur].p);
for (int i=a[cur].l;i<=a[cur].r;i++) ss+=char(s[i]+'a');
}
int main()
{
cin>>s1;
cin>>s2;
s1+=char('a'+26);
s2+=char('a'+27);
nb=1;
cur=1;
int n=0;
flag=1;
inf=s1.length()+s2.length();
for (int i=0;i<s1.length();i++) {
s[++n] = tolower(s1[i])-'a';
Add(n);
}
flag=2;
for (int i=0;i<s2.length();i++) {
s[++n] = tolower(s2[i])-'a';
Add(n);
}
Dfs(1);
// cout<<ans;
WriteS(ver);
// cout<<ss<<endl;
p[0]=-1;
int k=-1;
for (int i=1;i<ss.length();i++)
{
while (k>-1 && ss[k+1]!=ss[i]) k=p[k];
if (ss[k+1] == ss[i]) k++;
p[i]=k;
}
int i1,i2;
k=-1;
for (int i=0;i<s1.length();i++)
{
while (k>-1 && ss[k+1]!= s1[i]) k=p[k];
if (ss[k+1] == s1[i]) k++;
if (k==ss.length()-1) {i1 = i;break;}
}
k=-1;
for (int i=0;i<s2.length();i++)
{
while (k>-1 && ss[k+1]!= s2[i]) k=p[k];
if (ss[k+1] == s2[i]) k++;
if (k==ss.length()-1) {i2 = i;break;}
}
cout<<ans<<" "<<i1+1-ss.length()<< " "<<i2-ss.length()+1;
}