Commits

Anonymous committed 2af1f3d

OpenCup, Siberia GP

  • Participants
  • Parent commits 6b77d01

Comments (0)

Files changed (7)

File 2010-10-27/i_andrey.cpp

+/* University of Latvia, team 3: KVV, room 507, PC 2 */
+#define PROB "injurious"
+/*************************************************************************/
+#if !defined(LOCAL_PC) && !defined(NDEBUG)
+#define NDEBUG
+#endif
+#include <algorithm>
+#include <bitset>
+#include <cassert>
+#include <cctype>
+#include <cmath>
+#include <cstdlib>
+#include <deque>
+#include <iomanip>
+#include <iostream>
+#include <fstream>
+#include <limits>
+#include <list>
+#include <map>
+#include <queue>
+#include <set>
+#include <cstdlib>
+#include <sstream>
+#include <stack>
+#include <string>
+#include <utility>
+#include <valarray>
+#include <vector>
+using namespace std;
+struct _{ios_base::Init i;_(){cin.sync_with_stdio(false);cin.tie(NULL);}
+#if defined(LOCAL_PC)
+~_(){system("pause");}
+#endif
+}_; typedef long long LL; typedef unsigned long long ULL;
+#ifndef LOCAL_PC
+struct __{filebuf a,b;__(){cin.rdbuf(a.open(PROB".in",ios::in));cout.rdbuf
+(b.open(PROB".out",ios::out));}~__(){cin.rdbuf(NULL);cout.rdbuf(NULL);}}__;
+#endif
+#ifndef NDEBUG
+#define LOG(x) static_cast<void>(cerr<<setw(10)<<__FUNCTION__<<":"<<setw(3)<<__LINE__<<": "<<#x<<" = "<<setw(6)<<left<<(x)<<right)
+#else
+#define LOG(x) static_cast<void>(0)
+#endif
+/*************************************************************************/
+
+struct indices { long i, j; };
+
+int main ()
+{
+	int n;
+	vector<long> arr;
+
+	cin >> n;
+	arr.resize(n + 1);
+	for (int i = 1; i <= n; i++)
+		cin >> arr[i];
+	
+	const long size = 2 * 1313131 - 1;
+	indices *lookup = reinterpret_cast<indices *>(calloc(size + 1, sizeof(indices)));
+	for (int i = 1; i <= n - 2; i++)
+	{
+		for (int j = i + 1; j <= n - 1; j++)
+		{
+			if (2*arr[j] - arr[i] >= 1)
+			{
+				indices& p = lookup[2*arr[j] - arr[i]];
+				if (p.j == 0 || p.j > j)
+				{
+					p.i = i; p.j = j;
+				}
+			}
+		}
+	}
+
+	for (int k = 3; k <= n; k++)
+	{
+		indices& p = lookup[arr[k]];
+		if (p.j != 0 && p.j < k)
+		{
+			cout << "Yes\n" << p.i << " " << p.j << " " << k << "\n";
+			return 0;
+		}
+	}
+
+	cout << "No\n";
+}

File 2010-11-07/2.cpp

+/*****************************************************************************
+ * University of Latvia, team KVV                                            *
+ *****************************************************************************/
+
+#define PROB "test"        /* Comment out to use standard I/O everywhere     */
+//#define STDIO            /* Uncomment to use standard I/O on our PC        */
+
+/*****************************************************************************/
+#if !defined(LOCAL_PC) && !defined(NDEBUG)
+#define NDEBUG
+#endif
+#include <algorithm>
+#include <bitset>
+#include <cassert>
+#include <cctype>
+#include <cmath>
+#include <cstdlib>
+#include <deque>
+#include <iomanip>
+#include <iostream>
+#include <fstream>
+#include <limits>
+#include <list>
+#include <map>
+#include <queue>
+#include <set>
+#include <sstream>
+#include <stack>
+#include <string>
+#include <utility>
+#include <valarray>
+#include <vector>
+using namespace std;
+struct _{ios_base::Init i;_(){cin.sync_with_stdio(false);cin.tie(NULL);}
+#if defined(_WIN32) && defined(LOCAL_PC)
+~_(){system("pause");}
+#endif
+}_; typedef long long LL; typedef unsigned long long ULL;
+#if defined(PROB) && (!defined(LOCAL_PC) || !defined(STDIO))
+struct __{filebuf a,b;__(){cin.rdbuf(a.open("input.txt",ios::in));cout.rdbuf
+(b.open("output.txt",ios::out));}~__(){cin.rdbuf(NULL);cout.rdbuf(NULL);}}__;
+#endif
+#define FOR(i, a, b) for (long i = (a); i <= (b); ++i)
+#ifndef NDEBUG
+#define DOLOG cerr<< setw(10)<< __FUNCTION__<< ":"<< setw(3)<< __LINE__<< ": "
+#define DOVAR(x) << #x << " = " << setw(6) << left << (x) << right
+#define ENDLOG << "\n"
+#else
+#define DOLOG 0
+#define DOVAR(x)
+#define ENDLOG
+#endif
+#define LOG(x) static_cast<void>(DOLOG DOVAR(x) ENDLOG)
+#define LOG2(x,y) static_cast<void>(DOLOG DOVAR(x) DOVAR(y) ENDLOG)
+#define LOG3(x,y,z) static_cast<void>(DOLOG DOVAR(x) DOVAR(y) DOVAR(z) ENDLOG)
+/*****************************************************************************/
+
+int main ()
+{
+	while (1) {
+		int n, m, s, t;
+		cin >> n >> m >> s >> t;
+		if (n == 0) break;
+
+		vector<vector<char> > grafs(n, vector<char>(n));
+		
+		FOR(i, 0, m-1) {
+			int a, b;
+			cin >> a >> b;
+			grafs[a-1][b-1] = 1;
+			grafs[b-1][a-1] = 1;
+		}
+
+		vector<vector<char> > poss(1<<n, vector<char>(n));
+		FOR(v, 0, n-1) {
+			if (grafs[s-1][v]) poss[1<<v][v] = s;
+		}
+
+		FOR(k, 1, (1<<n) - 1) {
+			if (!(k & (k-1))) continue; // ��das kopas jau apskat�j�m agr�k
+			FOR(v, 0, n-1) {
+				if (!(k & (1<<v))) continue;
+				char rez = 0;
+				FOR(u, 0, n-1) {
+					if (!(k && (1<<u))) continue;
+					if (grafs[u][v] && poss[k & ~(1<<v)][u])
+					{
+						rez = u+1;
+						break;
+					}
+				}
+				poss[k][v] = rez;
+			}
+		}
+
+		stack<int> result;
+		FOR(k, 0, (1<<n)-1) {
+			if (!(k & (1<<(t-1)))) continue;
+			if (k & (1<<(s-1))) continue;
+			
+			int bitsum = 0;
+			int j = k; while (j > 0) { bitsum += j%2; j/=2; }
+			if (bitsum % 2 == 1) continue;
+
+			if (poss[k][t-1]) {
+				stack<int> newresult;
+				newresult.push(t);
+				int ss = k, v = t-1;
+				while (poss[ss][v])
+				{
+					newresult.push(poss[ss][v]);
+					int newv = poss[ss][v]-1;
+					ss = ss & ~(1<<v);
+					v = newv;
+				}
+				if (result.empty() || newresult.size() < result.size()) {
+					result = newresult;
+				}
+			}
+		}
+
+		if (result.empty()) {
+			cout << "No path\n";
+		} else {
+			string s = "";
+			while (!result.empty()) {
+				cout << s << result.top();
+				result.pop();
+				s = " ";
+			}
+			cout << endl;
+		}
+	}
+}

File 2010-11-07/6.cpp

+/*****************************************************************************
+ * University of Latvia, team KVV                                            *
+ *****************************************************************************/
+
+#define PROB "test"        /* Comment out to use standard I/O everywhere     */
+//#define STDIO            /* Uncomment to use standard I/O on our PC        */
+
+/*****************************************************************************/
+#if !defined(LOCAL_PC) && !defined(NDEBUG)
+#define NDEBUG
+#endif
+#include <algorithm>
+#include <bitset>
+#include <cassert>
+#include <cctype>
+#include <cmath>
+#include <cstdlib>
+#include <deque>
+#include <iomanip>
+#include <iostream>
+#include <fstream>
+#include <limits>
+#include <list>
+#include <map>
+#include <queue>
+#include <set>
+#include <sstream>
+#include <stack>
+#include <string>
+#include <utility>
+#include <valarray>
+#include <vector>
+using namespace std;
+struct _{ios_base::Init i;_(){cin.sync_with_stdio(false);cin.tie(NULL);}
+#if defined(_WIN32) && defined(LOCAL_PC)
+~_(){system("pause");}
+#endif
+}_; typedef long long LL; typedef unsigned long long ULL;
+#if defined(PROB) && (!defined(LOCAL_PC) || !defined(STDIO))
+struct __{filebuf a,b;__(){cin.rdbuf(a.open("input.txt",ios::in));cout.rdbuf
+(b.open("output.txt",ios::out));}~__(){cin.rdbuf(NULL);cout.rdbuf(NULL);}}__;
+#endif
+#define FOR(i, a, b) for (long i = (a); i <= (b); ++i)
+#ifndef NDEBUG
+#define DOLOG cerr<< setw(10)<< __FUNCTION__<< ":"<< setw(3)<< __LINE__<< ": "
+#define DOVAR(x) << #x << " = " << setw(6) << left << (x) << right
+#define ENDLOG << "\n"
+#else
+#define DOLOG 0
+#define DOVAR(x)
+#define ENDLOG
+#endif
+#define LOG(x) static_cast<void>(DOLOG DOVAR(x) ENDLOG)
+#define LOG2(x,y) static_cast<void>(DOLOG DOVAR(x) DOVAR(y) ENDLOG)
+#define LOG3(x,y,z) static_cast<void>(DOLOG DOVAR(x) DOVAR(y) DOVAR(z) ENDLOG)
+/*****************************************************************************/
+
+LL x, y;
+
+int best = 1000;
+void recurse(LL xx, int steps) {
+	if (steps >= best) return;
+	if (xx > y) return;
+	if (y % xx != 0) return;
+	if (xx == y) best = steps;
+	for (int i = xx; i >= 2; --i) {
+		recurse(i*xx, steps+1);
+	}
+}
+
+int main ()
+{
+	cin >> x >> y;
+	recurse(x, 0);
+	if (best == 1000) {
+		cout << "Impossible\n";
+	}
+	else
+	{
+		cout << best << endl;
+	}
+}

File 2010-11-07/8.cpp

+/*****************************************************************************
+ * University of Latvia, team KVV                                            *
+ *****************************************************************************/
+
+#define PROB "test"        /* Comment out to use standard I/O everywhere     */
+//#define STDIO            /* Uncomment to use standard I/O on our PC        */
+
+/*****************************************************************************/
+#if !defined(LOCAL_PC) && !defined(NDEBUG)
+#define NDEBUG
+#endif
+#include <algorithm>
+#include <bitset>
+#include <cassert>
+#include <cctype>
+#include <cmath>
+#include <cstdlib>
+#include <deque>
+#include <iomanip>
+#include <iostream>
+#include <fstream>
+#include <limits>
+#include <list>
+#include <map>
+#include <queue>
+#include <set>
+#include <sstream>
+#include <stack>
+#include <string>
+#include <utility>
+#include <valarray>
+#include <vector>
+using namespace std;
+struct _{ios_base::Init i;_(){cin.sync_with_stdio(false);cin.tie(NULL);}
+#if defined(_WIN32) && defined(LOCAL_PC)
+~_(){system("pause");}
+#endif
+}_; typedef long long LL; typedef unsigned long long ULL;
+#if defined(PROB) && (!defined(LOCAL_PC) || !defined(STDIO))
+struct __{filebuf a,b;__(){cin.rdbuf(a.open("input.txt",ios::in));cout.rdbuf
+(b.open("output.txt",ios::out));}~__(){cin.rdbuf(NULL);cout.rdbuf(NULL);}}__;
+#endif
+#define FOR(i, a, b) for (long i = (a); i <= (b); ++i)
+#ifndef NDEBUG
+#define DOLOG cerr<< setw(10)<< __FUNCTION__<< ":"<< setw(3)<< __LINE__<< ": "
+#define DOVAR(x) << #x << " = " << setw(6) << left << (x) << right
+#define ENDLOG << "\n"
+#else
+#define DOLOG 0
+#define DOVAR(x)
+#define ENDLOG
+#endif
+#define LOG(x) static_cast<void>(DOLOG DOVAR(x) ENDLOG)
+#define LOG2(x,y) static_cast<void>(DOLOG DOVAR(x) DOVAR(y) ENDLOG)
+#define LOG3(x,y,z) static_cast<void>(DOLOG DOVAR(x) DOVAR(y) DOVAR(z) ENDLOG)
+/*****************************************************************************/
+
+int main ()
+{
+	double a, b;
+	cin >> a >> b;
+	double pi = 4.0*atan(1.0);
+
+	double x = max(a,b), y = min(a,b);
+
+	double res = pi*y + 2*sqrt((x-y)*(x-y)+y*y);
+	cout << fixed << setprecision(2) << res << endl;
+}

File 2010-11-07/9.cpp

+/*****************************************************************************
+ * University of Latvia, team KVV                                            *
+ *****************************************************************************/
+
+#define PROB "test"        /* Comment out to use standard I/O everywhere     */
+//#define STDIO            /* Uncomment to use standard I/O on our PC        */
+
+/*****************************************************************************/
+#if !defined(LOCAL_PC) && !defined(NDEBUG)
+#define NDEBUG
+#endif
+#include <algorithm>
+#include <bitset>
+#include <cassert>
+#include <cctype>
+#include <cmath>
+#include <cstdlib>
+#include <deque>
+#include <iomanip>
+#include <iostream>
+#include <fstream>
+#include <limits>
+#include <list>
+#include <map>
+#include <queue>
+#include <set>
+#include <sstream>
+#include <stack>
+#include <string>
+#include <utility>
+#include <valarray>
+#include <vector>
+using namespace std;
+struct _{ios_base::Init i;_(){cin.sync_with_stdio(false);cin.tie(NULL);}
+#if defined(_WIN32) && defined(LOCAL_PC)
+~_(){system("pause");}
+#endif
+}_; typedef long long LL; typedef unsigned long long ULL;
+#if defined(PROB) && (!defined(LOCAL_PC) || !defined(STDIO))
+struct __{filebuf a,b;__(){cin.rdbuf(a.open("input.txt",ios::in));cout.rdbuf
+(b.open("output.txt",ios::out));}~__(){cin.rdbuf(NULL);cout.rdbuf(NULL);}}__;
+#endif
+#define FOR(i, a, b) for (long i = (a); i <= (b); ++i)
+#ifndef NDEBUG
+#define DOLOG cerr<< setw(10)<< __FUNCTION__<< ":"<< setw(3)<< __LINE__<< ": "
+#define DOVAR(x) << #x << " = " << setw(6) << left << (x) << right
+#define ENDLOG << "\n"
+#else
+#define DOLOG 0
+#define DOVAR(x)
+#define ENDLOG
+#endif
+#define LOG(x) static_cast<void>(DOLOG DOVAR(x) ENDLOG)
+#define LOG2(x,y) static_cast<void>(DOLOG DOVAR(x) DOVAR(y) ENDLOG)
+#define LOG3(x,y,z) static_cast<void>(DOLOG DOVAR(x) DOVAR(y) DOVAR(z) ENDLOG)
+/*****************************************************************************/
+
+#define LD long double
+#define EPS 1e-10
+
+LD x,y,k,t0;
+LD calc(LD a)
+{
+	LD initt = sqrt(2.0*x/a);
+	LD v0 = a*initt;
+	LD augsha = 1.0 - y*k/v0;
+	LD yt = log(augsha)/(-k);
+	return initt+yt;
+}
+int main ()
+{
+	cin >> x >> y >> k >> t0;
+	LD amin = y*y*k*k/(2.0*x)+EPS;
+	LD amax = 100.0;
+	/* assert(amin < t0);
+	assert(amax > t0); */
+	while (amax-amin > EPS) {
+		LD amid = (amin+amax)/2.0;
+		if (calc(amid) > t0) {
+			amin = amid;
+		} else {
+			amax = amid;
+		}
+	}
+	cout << fixed << setprecision(6) << amax << endl;
+}

File 2010-11-07/rvday-e.pdf

Binary file added.

File 2010-11-07/rvday-r.pdf

Binary file added.