Задачи
от Съзтезателно програмиране
Съдържание |
OpenCup задачи
Няколко мои решения на задачи от OpenCup-а.
OpenCup_23.12.2006_задача_B_Матрица
OpenCup_23.12.2006_задача_F_Парад
OpenCup_23.12.2006_задача_К_Тенис
-- Владимир Недев
OpenCup_26.05.2007_задача_А_Футбол,Визи и TopCoder
-- Ивайло Странджев
Fmi internal contest 2007-04-01 Problem I
Ето линк към условието: http://milo0.no-ip.org/spoj0/contests.pl?contest_id=8
Идеята на решението е следната. Имаме, че <math>(t^a-1)/(t^b-1)</math> е цяло, тогава и само тогава когато b дели a. След което прилагаме стандартната идея за намиране на броя цифри на степен на голямо число, използвайки десетичен логаритъм. Следва сорс:
import java.util.*;
import java.math.*;
//author: Todor Tsonkov
public class Main
{
static BigInteger pow( BigInteger a, int n )
{
if ( n == 0 ) return BigInteger.ONE;
if ( n% 2== 1 ) return pow(a, n-1).multiply(a);
return pow(a, n/2).multiply(pow(a,n/2));
}
public static void main(String args[])
{
Scanner in = new Scanner (System.in);
int t, a, b;
while ( in.hasNextInt() )
{
t = in.nextInt();
a= in.nextInt();
b = in.nextInt();
if ( a%b != 0 )
{
System.out.println("bad!");
continue;
}
double f = Math.log10(a)- Math.log10(b);
if ( f > 100.0 )
{
System.out.println("bad!");
continue;
}
BigInteger first = BigInteger.valueOf(t), second = BigInteger.valueOf(t);
first = pow(first, a);
second = pow(second,b);
first = first.subtract(BigInteger.ONE);
second = second.subtract(BigInteger.ONE);
System.out.println( first.divide(second) );
}
}
}
OpenCup Gran Pri Peterburg 2007 Problem C
За решението на задачата използваме Flow като добавяме фиктивни източник и консуматор, а ребрата между тях получаваме като определяме ребрата по това дали имаме еднакви букви от двата низа след местенето на букви в първия на разстояние най-много k. Ще имаме решение тогава когато по време на Flow-a след всяко пускане на BFS достигаме до консуматора.
Прилагам AC сорс:
// author Kiril Kalchev
#include <sstream>
#include <cstring>
#include <string>
#include <vector>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <cstdio>
#include <stack>
#include <queue>
using namespace std;
#define np next_permutation
#define pb push_back
#define ALL(a) a.begin(),a.end()
#define sz size
typedef vector<int> vi;
typedef vector< vi > vvi;
typedef vector<string> vs;
int f[500][500];
int v[500],pred[500];
ifstream cin ("dhopper.in");
ofstream cout( "dhopper.out");
string a,b;
int k;
int c;
void inp(void)
{
cin>>k;
cin>>a;
cin>>b;
if (a.length()!=b.length())
{ cout << "NO\n";
exit(0);
}
}
void init(void)
{ int i,j;
memset(f,0,sizeof(f));
for (i=0;i<a.length();i++)
{
for (j=0;j<=k;j++)
{ if (a[i]==b[(i+j)%b.length()]) f[i+1][a.length()+(i+j)%b.length()+1]=1;
if (a[i]==b[(b.length()+i-j)%b.length()]) f[i+1][a.length()+(b.length()+i-j)%b.length()+1]=1;
}
f[0][i+1]=1;
f[a.length()+i+1][2*a.length()+1]=1;
}
}
bool bfs(int s)
{ queue<int> a;
int u,i;
a.push(s);
while (!a.empty())
{ u=a.front();
a.pop();
for (i=2*b.length()+1;i>=0;i--) if (!v[i] && f[u][i])
{ if (i==2*b.length()+1) { pred[i]=u; return true;}
pred[i]=u;
v[i]=1;
a.push(i);
}
}
return false;
}
bool dfs(int s)
{ int i;
if (s==2*a.length()+1) return true;
for (i=0;i<=2*a.length()+1;i++)
if (f[s][i] && !v[i])
{ v[i]=1;
if (dfs(i))
{ f[s][i]=0;
f[i][s]=1;
return true;
}
v[i]=0;
}
return false;
}
void reverse(void)
{ int i=2*b.length()+1;
while (pred[i]!=-1)
{ f[pred[i]][i]=0;
f[i][pred[i]]=1;
i=pred[i];
}
}
void flow(void)
{ memset(v,0,sizeof(v));
v[0]=1;
pred[0]=-1;
while (bfs(0)){ reverse(); memset(v,0,sizeof(v)); c++; v[0]=1; pred[0]=-1;}
}
int main()
{
inp();
init();
c=0;
flow();
if (c<a.length()) cout<<"NO\n";
else cout<<"YES\n";
return 0;
}
OpenCup Gran Pri Ponor 2006/2007 Problem H
В условието на задачата се изисква да се намери лицето на общата част на два триъгълника. Решението, което прилагам използва най-очевидния алгоритъм за решаване - намиране на всички пресечни и вътрешни точки и намира изпъкналата им обвивка, както и лицето. В сорса прилагам редица функции за работа с някои 2D обекти, които могат да бъдат използвани при редица задачи.
// Author: Deyan Doychev
#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <deque>
#include <list>
#include <set>
#include <map>
#include <string>
#include <queue>
#include <stack>
#include <iomanip>
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
#define all(i,n) for(i=0;i<n;i++)
#define rep(i,a,b) for(int i=(int)(a);i<=(int)(b);++i)
#define eps 1e-6
#define inf 100000
#define ulong unsigned long long
ofstream fout("dispute.out",ios::out);
ifstream fin("dispute.in", ios::in);
typedef double datatype;
const int maxn=10000;
struct point
{
datatype x,y;
bool operator <(const point & a) const
{ if (x<a.x || (x==a.x && y<a.y)) return 1;
return 0;
}
bool operator ==(const point & a) const
{
return a.x == this->x || a.y == this->y ;
}
bool operator <=(const point & a) const
{ return ((*this<a)|| (*this==a));
}
};
double dist(point a,point b)
{
return sqrt ( (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y) );
}
bool ravni(datatype a,datatype b)
{
return fabs(a-b)<eps;
}
struct prava
{
datatype a,b,c;
};
prava make(point a, point b)
{
prava t;
t.a=b.y-a.y;
t.b=a.x-b.x;
t.c=b.x*a.y-a.x*b.y;
return t;
}
bool vytre(point a, point b, point c)
{
return ravni( dist(a,b)+ dist(b,c), dist(a,c) );
}
point pres(prava p,prava q)
{ point t;
if (ravni(q.a*p.b, q.b*p.a))
{ t.x=inf;
t.y=inf;
return t;
}
if (p.a==0.0)
{ t.y=-p.c/p.b;
t.x=(-q.c-q.b*t.y)/q.a;
return t;
}
t.y=(-q.c*p.a+q.a*p.c)/(- p.b*q.a + p.a*q.b);
t.x=(-p.c-p.b*t.y)/p.a;
return t;
}
typedef pair<point, point> pp;
point a[maxn];
point b[maxn];
int m,n=3;
double det(point a, point b)
{
return a.x*b.y-a.y*b.x;
}
void input()
{
short i;
//fin>>n;
all(i,n)
fin>>a[i].x>>a[i].y;
all(i,n)
fin>>b[i].x>>b[i].y;
}
vector<point> final;
double S(point a,point b,point c)
{ return a.x*b.y+a.y*c.x+b.x*c.y-c.x*b.y-c.y*a.x-b.x*a.y;
}
long double area( point a, point b, point c)
{
return fabs(S(a,b,c))/2.0;
}
int main()
{
input ();
int i;
prava t11,t12,t13;
prava t21,t22,t23;
t11=make(a[0],a[1]);
t12=make(a[2],a[1]);
t13=make(a[0],a[2]);
t21=make(b[0],b[1]);
t22=make(b[2],b[1]);
t23=make(b[0],b[2]);
point tt;
set < point > data;
//cout<<t11.a<<" "<<t11.b<<" "<<t11.c<<endl;
tt=pres(t11, t21);
//cout<<tt.x<<" "<<tt.y<<endl;
if ( vytre(a[0], tt, a[1]) && vytre(b[0],tt,b[1]) )
data.insert(tt);
tt=pres(t11, t22);
//cout<<tt.x<<" "<<tt.y<<endl;
if ( vytre(a[0],tt,a[1]) && vytre(b[2],tt,b[1]) )
data.insert(tt);
tt=pres(t11, t23);
//cout<<tt.x<<" "<<tt.y<<endl;
if ( vytre(a[0],tt,a[1]) && vytre(b[0],tt,b[2]) )
data.insert(tt);
tt=pres(t12, t21);
//cout<<tt.x<<" "<<tt.y<<endl;
if ( vytre(a[2],tt,a[1]) && vytre(b[0],tt,b[1]) )
data.insert(tt);
tt=pres(t12, t22);
//cout<<tt.x<<" "<<tt.y<<endl;
if ( vytre(a[2],tt,a[1]) && vytre(b[2],tt,b[1]) )
data.insert(tt);
tt=pres(t12, t23);
//cout<<tt.x<<" "<<tt.y<<endl;
if ( vytre(a[2],tt,a[1]) && vytre(b[0],tt,b[2]) )
data.insert(tt);
tt=pres(t13, t21);
//cout<<tt.x<<" "<<tt.y<<endl;
if ( vytre(a[2],tt,a[0]) && vytre(b[0],tt,b[1]) )
data.insert(tt);
tt=pres(t13, t22);
//cout<<tt.x<<" "<<tt.y<<endl;
if ( vytre(a[2],tt,a[0]) && vytre(b[1],tt,b[2]) )
data.insert(tt);
tt=pres(t13, t23);
//cout<<tt.x<<" "<<tt.y<<endl;
if ( vytre(a[2],tt,a[0]) && vytre(b[2],tt,b[0]) )
data.insert(tt);
double s=area( a[0], a[1], a[2] );
double s1=area( b[0], b[1], b[2] ) ;
double s2;
for (i=0;i<=2;i++)
{
s2=area( a[0], b[i], a[1]) + area( a[2], b[i], a[1]) + area( a[0], b[i], a[2]) ;
if ( ravni(s,s2) ) data.insert( b[i] ) ;
}
for (i=0;i<=2;i++)
{
s2=area( b[0], a[i], b[1]) + area( b[2], a[i], b[1]) + area( b[0], a[i], b[2]) ;
if ( ravni(s1,s2) ) data.insert(a[i]) ;
}
set < point > :: iterator it ;
for ( it = data.begin(); it!= data.end(); it++ )
final.push_back ( *it );
//cout<<final.size()<<endl;
if (final.size()<3)
{ fout<<0.0<<endl;
fout.close();
return 0;
}
sort ( final.begin(), final.end() );
vector <point> up,down;
down.push_back(final[0]);
for (i=1;i<final.size()-1;i++)
{ if (S(final[0],final[final.size()-1],final[i])<0.0) down.push_back(final[i]);
else up.push_back(final[i]);
}
up.push_back(final[final.size()-1]);
reverse(up.begin(),up.end());
//final.erase( unique( final.begin(), final.end () ) , final.end() ) ;
final.clear();
for (i=0;i<down.size();i++) final.push_back(down[i]);
for (i=0;i<up.size();i++) final.push_back(up[i]);
fout.setf(ios::fixed);
fout<<setprecision( 7 );
double lice1=0.000;
i=0;
point uuuu;
uuuu.x=0;
uuuu.y=0;
while( i+1 < final.size() )
{
lice1+=(S(uuuu,final[i],final[i+1]));
i++;
}
lice1+=(S(uuuu,final[i],final[0]));
fout<<lice1/2.0<<endl;
fout.close();
return 0;
}
