Commits

Andrey Vihrov committed 52ba836

Add 2010-10-30 solutions

  • Participants
  • Parent commits 1ba9967

Comments (0)

Files changed (6)

2010-10-30/Makefile

+###############################################################################
+#
+# Makefile for small projects, version 2.0a
+#
+# GNU Make and some POSIX utilities are required.
+#
+# Available targets:
+#   make [all]         - build all programs in debug mode
+#   make release       - build all programs in release mode
+#   make X             - build program X in debug mode
+#   make X-release     - build program X in release mode
+#   make flags         - show debug flags
+#   make flags-release - show release flags
+#   make test          - run all tests
+#   make test-X        - run all tests for program X
+#   make test-X-N      - run test N for program X
+#   make clean         - remove all generated files
+# Multiple targets can be specified on make command line.
+#
+# Copyright (C) Andrey Vihrov <andrey.vihrov@gmail.com>, 2010
+#
+# You may only use this Makefile to operate on the source code it was shipped
+# with.
+#
+
+###############################################################################
+#
+# Source configuration
+#
+
+# A list of programs to build
+PROGRAMS = a e g_fail j
+
+# Global definitions
+DEFS += -DLOCAL_PC -U_FORTIFY_SOURCE
+
+# Global libraries
+LIBS += 
+
+# For each program X the following may be specified:
+#   X_SOURCES   = <list of source files for X>; default 'X.c' or 'X.cpp',
+#                 whichever is present
+#   X_DEFS      = <additional definitions for X>; default ''
+#   X_LIBS      = <additional libraries for X>; default ''
+#   X_INPUTEXT  = input file extension for X; default '.in' via $(INPUTEXT)
+#   X_OUTPUTEXT = output file extension for X; default '.out' via $(OUTPUTEXT)
+
+
+# Extra files to clean
+EXTRA_CLEAN = 
+
+###############################################################################
+#
+# Environment and toolchain configuration
+#
+
+# Toolchain to use: 'gnu' or 'msvc' or 'default' (to use default make values)
+TOOLCHAIN ?= gnu
+
+# To override a default variable value, define it here or in Makefile.local.
+# List of some relevant variables:
+#   CC CFLAGS_BASE CFLAGS_DEBUG CFLAGS_RELEASE CXX CXXFLAGS_BASE
+#   CXXFLAGS_DEBUG CXXFLAGS_RELEASE CPPFLAGS_BASE CPPFLAGS_DEBUG
+#   CPPFLAGS_RELEASE AS ASFLAGS_BASE ASFLAGS_DEBUG ASFLAGS_RELEASE LD LD.c
+#   LD.cxx LDFLAGS_BASE LDFLAGS_DEBUG LDFLAGS_RELEASE INPUTEXT OUTPUTEXT
+
+
+###############################################################################
+###############################################################################
+#
+# Default setup
+#
+
+# First include local settings
+-include Makefile.local
+
+# Set a value if the variable has a default definition
+set-if-default = $(if $(findstring $(origin $(1)),default),$(eval $(1) = $(2)))
+
+# Determine platform
+PLATFORM := $(shell uname -s)
+
+# Name of directory for additional generated files
+BUILDDIR = .build
+
+# Directory containing tests for program $(1)
+TESTDIR = $(or $(wildcard tests-$(1)),tests)
+
+# Default input and output file extensions
+INPUTEXT ?= .in
+OUTPUTEXT ?= .out
+
+# Executable file extension
+EXT = 
+# Object file extension
+OBJEXT = .o
+
+# Select linker
+ifeq ($(origin LD),default)
+  LD.c ?= $(CC)
+  LD.cxx ?= $(CXX)
+else
+  LD.c ?= $(LD)
+  LD.cxx ?= $(LD)
+endif
+
+# Toolchain-specific values
+ifeq ($(TOOLCHAIN),gnu)
+  $(call set-if-default,CC,gcc)
+  CFLAGS_BASE ?= -Wall -Wextra -pedantic -std=c99
+  CFLAGS_DEBUG ?= -ggdb
+  CFLAGS_RELEASE ?= -O2 -march=native -fomit-frame-pointer
+
+  $(call set-if-default,CXX,g++)
+  CXXFLAGS_BASE ?= -Wall -Wextra -Wno-long-long -pedantic -std=c++98
+  CXXFLAGS_DEBUG ?= $(CFLAGS_DEBUG)
+  CXXFLAGS_RELEASE ?= $(CFLAGS_RELEASE)
+
+  CPPFLAGS_RELEASE ?= -DNDEBUG
+
+  $(call set-if-default,AS,as)
+  ASFLAGS_DEBUG ?= -g
+
+  LDFLAGS_RELEASE ?= -s -Wl,-O1,--as-needed
+
+  deptarget = $(BUILDDIR)/$(@F:%.o=%.d)
+  define depgen-wrapper
+    $(1) -MMD -MP -MT $@ -MF $(deptarget).tmp && \
+    mv $(deptarget).tmp $(deptarget)
+  endef
+  cccmd = $(call depgen-wrapper,\
+    $(CC) -c -o $@ $< $(DEFS) $(CPPFLAGS_ALL) $(CFLAGS_ALL))
+  cxxcmd = $(call depgen-wrapper,\
+    $(CXX) -c -o $@ $< $(DEFS) $(CPPFLAGS_ALL) $(CXXFLAGS_ALL))
+else ifeq ($(TOOLCHAIN),msvc)
+  # Assume we are running under MSYS
+
+  OBJEXT = .obj
+
+  $(call set-if-default,CC,cl)
+  CFLAGS_BASE ?= //nologo //Za //W4
+  CFLAGS_DEBUG ?= //Od //GS //Zi //RTCcsu
+  CFLAGS_RELEASE ?= //Ox //GF //GL
+
+  $(call set-if-default,CXX,cl)
+  CXXFLAGS_BASE ?= $(CFLAGS_BASE) //EHsc
+  CXXFLAGS_DEBUG ?= $(CFLAGS_DEBUG)
+  CXXFLAGS_RELEASE ?= $(CFLAGS_RELEASE)
+
+  CPPFLAGS_BASE ?= //D_CRT_SECURE_NO_WARNINGS
+  CPPFLAGS_RELEASE ?= //DNDEBUG
+
+  cccmd = $(CC) //c //Fo$@ //TC $< $(DEFS) $(CPPFLAGS_ALL) $(CFLAGS_ALL)
+  cxxcmd = $(CXX) //c //Fo$@ //TP $< $(DEFS) $(CPPFLAGS_ALL) $(CXXFLAGS_ALL)
+  ldcmd.c = $(LD.c) //Fe$@ $^ $(LIBS) $(CFLAGS_ALL) $(LDFLAGS_ALL)
+  ldcmd.cxx = $(LD.cxx) //Fe$@ $^ $(LIBS) $(CXXFLAGS_ALL) $(LDFLAGS_ALL)
+
+  EXTRA_CLEAN += *.ilk *.pdb
+else ifeq ($(TOOLCHAIN),default)
+  # Nothing to set
+else
+  $(error Unknown toolchain '$(TOOLCHAIN)')
+endif
+
+# Platform-specific values
+ifneq ($(findstring MINGW32,$(PLATFORM)),)
+  EXT = .exe
+  CFLAGS_RELEASE := $(filter-out -march=native,$(CFLAGS_RELEASE)) # FIXME
+endif
+
+###############################################################################
+#
+# Function definitions
+#
+
+CFLAGS_ALL = $(CFLAGS_BASE) $(CFLAGS_$(MODE)) $(CFLAGS)
+CXXFLAGS_ALL = $(CXXFLAGS_BASE) $(CXXFLAGS_$(MODE)) $(CXXFLAGS)
+CPPFLAGS_ALL = $(CPPFLAGS_BASE) $(CPPFLAGS_$(MODE)) $(CPPFLAGS)
+ASFLAGS_ALL = $(ASFLAGS_BASE) $(ASFLAGS_$(MODE)) $(ASFLAGS)
+LDFLAGS_ALL = $(LDFLAGS_BASE) $(LDFLAGS_$(MODE)) $(LDFLAGS)
+
+cccmd ?= $(CC) -c -o $@ $< $(DEFS) $(CPPFLAGS_ALL) $(CFLAGS_ALL)
+define do-cc
+  echo "  CC    $@"
+  $(cccmd)
+endef
+
+cxxcmd ?= $(CXX) -c -o $@ $< $(DEFS) $(CPPFLAGS_ALL) $(CXXFLAGS_ALL)
+define do-cxx
+  echo "  CXX   $@"
+  $(cxxcmd)
+endef
+
+ascmd ?= $(AS) -o $@ $< $(ASFLAGS_ALL)
+define do-as
+  echo "  AS    $@"
+  $(ascmd)
+endef
+
+ldcmd.c ?= $(LD.c) -o $@ $^ $(LIBS) $(CFLAGS_ALL) $(LDFLAGS_ALL)
+ldcmd.cxx ?= $(LD.cxx) -o $@ $^ $(LIBS) $(CXXFLAGS_ALL) $(LDFLAGS_ALL)
+define do-ld
+  echo "  LD    $@"
+  $(call ifcxx,$(ldcmd.cxx),$(ldcmd.c))
+endef
+
+define do-rm-base
+  echo "  RM    $(1)"
+  rm -rf $(1)
+endef
+do-rm = $(if $(wildcard $(1)),$(call do-rm-base,$(wildcard $(1))))
+
+define do-flags
+  printf "%-12s %-12s %-12s %-12s %-12s\\n" "CC=$(strip $(CC))" \
+    "CXX=$(strip $(CXX))" "AS=$(strip $(AS))" "LD.c=$(strip $(LD.c))" \
+    "LD.cxx=$(strip $(LD.cxx))"
+  echo "CFLAGS   = $(strip $(CFLAGS_ALL))"
+  echo "CXXFLAGS = $(strip $(CXXFLAGS_ALL))"
+  echo "CPPFLAGS = $(strip $(CPPFLAGS_ALL))"
+  echo "ASFLAGS  = $(strip $(ASFLAGS_ALL))"
+  echo "LDFLAGS  = $(strip $(LDFLAGS_ALL))"
+endef
+
+INFILE = $@/$(1)$($(1)_INPUTEXT)
+OUTFILE = $@/$(1)$($(1)_OUTPUTEXT)
+define do-test
+  printf "  TEST  %-11s" "$(if $(filter 1,$(words $(PROGRAMS))),,$(1):)$*"
+  if test -d $@ ; then rm -f $(OUTFILE) ; else mkdir $@ ; fi
+  cp $(2) $(INFILE)
+  if ( cd $@ && time -p ../$(1)$(EXT) ) >$@/stdout 2>$@/stderr ; then \
+    if ! test -e $(OUTFILE) ; then \
+	  echo "No output" ; \
+    elif ! diff -b $(3) $(OUTFILE) > /dev/null ; then \
+      echo "Wrong answer" ; \
+	else \
+      tail -n3 $@/stderr | head -n1 | cut -d' ' -f2 | tr -d '\n' && \
+	  echo " s" && rm -rf $@ ; \
+    fi ; \
+  else \
+    echo "Non-zero exit code $$?" ; \
+  fi
+endef
+
+# Check if this target is a C or C++ program
+ifcxx = $(if $(findstring cxx,$(TARGET_LANG)),$(1),$(2))
+
+###############################################################################
+#
+# Process targets
+#
+
+define process-target
+  $(1)_SOURCES ?= $$(wildcard $(1).c*)
+  $$(if $$(strip $$($(1)_SOURCES)),,$$(error No source files for '$(1)'))
+  $(1)_INPUTEXT ?= $$(INPUTEXT)
+  $(1)_OUTPUTEXT ?= $$(OUTPUTEXT)
+  $$(if $$(and $$($(1)_INPUTEXT),$$($(1)_OUTPUTEXT)),,\
+    $$(error Input or output file extension missing for '$(1)'))
+  $(1)_LANG = $$(if $$(filter %.cpp,$$($(1)_SOURCES)),cxx,c)
+  $(1)_OBJS = $$(addsuffix $(OBJEXT),$$(basename $$($(1)_SOURCES)))
+  OBJS += $$($(1)_OBJS)
+endef
+
+define target-rules
+  $(1)$(EXT): DEFS += $$($(1)_DEFS)
+  $(1)$(EXT): LIBS += $$($(1)_LIBS)
+  $(1)$(EXT): TARGET_LANG = $$($(1)_LANG)
+  $(1)$(EXT): $$($(1)_OBJS)
+endef
+
+OBJS =
+$(foreach target,$(PROGRAMS),$(eval $(call process-target,$(target))))
+OBJS := $(sort $(OBJS))
+
+get-test-targets = \
+  $(patsubst $(1).i%,test-$(1)-%,$(notdir $(wildcard $(TESTDIR)/$(1).i*)))
+define target-test-rules
+  .PHONY: $(get-test-targets)
+  test-$(1): $(get-test-targets)
+  $(get-test-targets): test-$(1)-%: $(1)-release \
+    $(TESTDIR)/$(1).i% $(TESTDIR)/$(1).o%
+	@$$(call do-test,$(1),$$(word 2,$$^),$$(word 3,$$^))
+endef
+
+###############################################################################
+#
+# Rules
+#
+
+MODE = DEBUG
+RELEASETARGETS = $(addsuffix -release,$(PROGRAMS))
+TESTTARGETS = $(addprefix test-,$(PROGRAMS))
+
+ifneq ($(findstring test,$(MAKECMDGOALS))$(findstring flags,$(MAKECMDGOALS)),)
+  .NOTPARALLEL:
+endif
+
+.DELETE_ON_ERROR:
+
+.PHONY: all release $(RELEASETARGETS) flags flags-release clean
+
+all: $(PROGRAMS)
+release: $(RELEASETARGETS)
+$(RELEASETARGETS) flags-release: MODE = RELEASE
+$(RELEASETARGETS): %-release: %
+
+include $(wildcard $(BUILDDIR)/*.d)
+
+$(foreach target,$(PROGRAMS),$(eval $(call target-rules,$(target))))
+
+ifneq ($(EXT),)
+  .PHONY: $(PROGRAMS)
+  $(PROGRAMS): %: %$(EXT)
+endif
+
+$(addsuffix $(EXT),$(PROGRAMS)):
+	@$(do-ld)
+
+%$(OBJEXT): %.c | $(BUILDDIR)
+	@$(do-cc)
+
+%$(OBJEXT): %.cpp | $(BUILDDIR)
+	@$(do-cxx)
+
+%$(OBJEXT): %.s
+	@$(do-as)
+
+$(BUILDDIR):
+	@mkdir $@
+
+flags flags-release:
+	@$(do-flags)
+
+clean:
+	@$(call do-rm,$(OBJS))
+	@$(call do-rm,$(addsuffix $(EXT),$(PROGRAMS)))
+	@$(call do-rm,$(EXTRA_CLEAN))
+	@$(call do-rm,$(BUILDDIR) $(PROGRAMS:%=test-%-*))
+
+.PHONY: test $(TESTTARGETS)
+
+test: $(TESTTARGETS)
+
+$(foreach target,$(PROGRAMS),$(eval $(call target-test-rules,$(target))))
+
+###############################################################################
+/*****************************************************************************
+ * 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 <cstdio>
+#include <cstdlib>
+#include <cstring>
+#include <deque>
+#include <iomanip>
+#include <iostream>
+#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; static struct _{_(){
+#if defined(PROB) && (!defined(LOCAL_PC) || !defined(STDIO))
+freopen(PROB".in","r",stdin);freopen(PROB".out","w",stdout);
+#endif
+#if defined(_WIN32) && defined(LOCAL_PC)
+}~_(){system("pause");
+#endif
+}}_; typedef long long LL; typedef unsigned long long ULL;
+#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  l = 0, h = 0, w = 0;
+	double time;
+	scanf("%lf%lf%lf", &l, &h, &w);
+
+	l /= 100;
+	h /= 100;
+
+	if(2 * h - l < 0)
+	{
+		time = 0;
+	}
+	else
+	{
+		time = sqrtl((double)(2 * h - l) / 9.81);
+	}
+
+	double angTurn = w * 6;
+	double turnedAngle = angTurn * time;
+
+	turnedAngle = fmod(turnedAngle, 360);
+
+	if(turnedAngle < 90 || turnedAngle >= 270)
+	{
+		printf("butter");
+	}
+	else
+	{
+		printf("bread");
+	}
+	
+}
+#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(LOCAL_PC)
+~_(){system("pause");}
+#endif
+}_; typedef long long LL; typedef unsigned long long ULL;
+#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
+/*************************************************************************/
+
+int main ()
+{
+	/*int n;
+	cin >> n;
+	vector<vector<vector<int> > > cubes;
+	cubes.resize(n);
+	for (int i = 0; i < n; ++i) {
+		cubes[i].resize(n);
+		for (int y = 0 ; y < n; ++y) {
+			cubes[i][y].resize(n);
+			for (int x = 0; x < n; ++x) {
+				cin >> cubes[i][y][x];
+			}
+		}
+	}*/
+	int t; cin >> t;
+	for(int i = 0; i < t; ++i) {
+		string s;
+		cin >> s; cin >> s; cin >> s;
+		string homeaway;
+		cin >> homeaway;
+		cin >> s; cin >> s;
+		int scores;
+		cin >> scores;
+		cin >> s; cin >> s; cin >> s;
+		int conc;
+		cin >> conc;
+		cin >> s;
+		// LOG(homeaway); LOG(conc);
+		//The Machinegunners played home game, scored 28 goals, and conceded 0 goals.
+
+		int mini = 1000, maxi = -1;
+		if (homeaway == "home") {
+			for (int scores2 = 0; scores2 <= 30; scores2++) {
+				bool mg_adv = false, cv_adv = false;
+				for (int conc2 = 0; conc2 <= 30; conc2++) {
+					if (scores2 + scores > conc2 + conc) {
+						mg_adv = true;
+					} else if (scores2 + scores == conc2 + conc) {
+						mg_adv |= (scores2 >= conc);
+						cv_adv |= (scores >= conc2);
+					} else {
+						cv_adv = true;
+					}
+				}
+				if (mg_adv) mini = min(mini, scores2);
+				if (cv_adv) maxi = max(maxi, scores2);
+			}
+		} else {
+			for (int scores2 = 0; scores2 <= 30; scores2++) {
+				bool mg_adv = false, cv_adv = false;
+				for (int conc2 = 0; conc2 <= 30; conc2++) {
+					if (scores2 + scores > conc2 + conc) {
+						mg_adv = true;
+					} else if (scores2 + scores == conc2 + conc) {
+						mg_adv |= (scores >= conc2);
+						cv_adv |= (scores2 >= conc);
+					} else {
+						cv_adv = true;
+					}
+				}
+				if (mg_adv) mini = min(mini, scores2);
+				if (cv_adv) maxi = max(maxi, scores2);
+			}
+		}
+		cout << mini << " " << maxi << endl;
+	}
+}

2010-10-30/g_fail.cpp

+#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(LOCAL_PC)
+~_(){system("pause");}
+#endif
+}_; typedef long long LL; typedef unsigned long long ULL;
+#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
+/*************************************************************************/
+
+/*
+int main ()
+{
+	int n;
+	cin >> n;
+	vector<vector<vector<int> > > cubes;
+	cubes.resize(n);
+	for (int i = 0; i < n; ++i) {
+		cubes[i].resize(n);
+		for (int y = 0 ; y < n; ++y) {
+			cubes[i][y].resize(n);
+			for (int x = 0; x < n; ++x) {
+				cin >> cubes[i][y][x];
+			}
+		}
+	}
+}
+*/
+
+vector<vector<pair<int, int> > > grafs; // pair(vertex, cost)
+vector<string> vertex_to_repr;
+map<string, int> repr_to_vertex;
+int main(void)
+{
+	int n;
+	cin >> n;
+	grafs.resize(n);
+	vertex_to_repr.resize(n);
+
+	vector<int> prices(10);
+	for (int i = 0; i <= 9; ++i) {
+		cin >> prices[i];
+	}
+
+	for (int i = 0; i < n; ++i) {
+		string v; cin >> v;
+		vertex_to_repr[i] = v;
+		repr_to_vertex[v] = i;
+	}
+
+	for (int i = 0; i < n; ++i) {
+		string s = vertex_to_repr[i];
+
+		for (int pos = 0; pos < 10; pos++) {
+			for (char newd = '0'; newd <= '9'; newd++) {
+				string s2 = s;
+				s2[pos] = newd;
+				if (s2 == s) continue;
+				if (repr_to_vertex.find(s2) != repr_to_vertex.end()) {
+					grafs[i].push_back(make_pair(repr_to_vertex[s2], prices[pos]));
+				}
+			}
+		}
+		for (int x = 0; x < 10; x++) {
+			for (int y = x+1; y < 10; y++) {
+				string s2 = s;
+				swap(s2[x], s2[y]);
+				if (s2 == s) continue;
+				if (repr_to_vertex.find(s2) != repr_to_vertex.end()) {
+					grafs[i].push_back(make_pair(repr_to_vertex[s2], prices[x]));
+				}
+			}
+		}
+	}
+
+	static const LL MAX = 1000000000000LL;
+	vector<LL> distances(n, MAX);
+	vector<int> prev(n, -1);
+	vector<bool> visited(n, false);
+
+	distances[0] = 0;
+
+	//priority_queue<pair<LL, int> > q;
+	set<pair<LL, int> > q;
+	//q.push(make_pair(0, 0));
+	q.insert(make_pair(0LL, 0));
+
+	while (!q.empty())
+	{
+		//pair<LL, int> t = q.top();
+		pair<LL, int> t = *q.begin();
+		// q.pop();
+		q.erase(q.begin());
+
+		if (!visited[t.second]) {
+			visited[t.second] = true;
+			for(int i = 0; i < grafs[t.second].size(); ++i) {
+				if (distances[t.second] + grafs[t.second][i].second < distances[grafs[t.second][i].first]) {
+
+					set<pair<LL, int> >::iterator it = q.find(make_pair(distances[grafs[t.second][i].first], grafs[t.second][i].first)); // pieliku
+					if (it != q.end()) q.erase(it); // pieliku
+
+					distances[grafs[t.second][i].first] = distances[t.second] + grafs[t.second][i].second;
+					prev[grafs[t.second][i].first] = t.second;
+					// q.push(make_pair(-distances[grafs[t.second][i].first], grafs[t.second][i].first));
+					q.insert(make_pair(distances[grafs[t.second][i].first], grafs[t.second][i].first));
+				}
+			}
+		}
+	}
+
+	if (prev[n-1] == -1) {
+		cout << -1 << endl;
+	} else {
+		cout << distances[n-1] << endl;
+		vector<int> path(1, n);
+		int i = prev[n-1];
+		while (i != -1) {
+			path.push_back(i+1);
+			i = prev[i];
+		}
+		cout << path.size() << endl;
+		reverse(path.begin(), path.end());
+		string s = "";
+		for (i = 0; i < path.size(); ++i) {
+			cout << s << path[i];
+			s = " ";
+		}
+		cout << endl;
+	}
+}
+#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(LOCAL_PC)
+~_(){system("pause");}
+#endif
+}_; typedef long long LL; typedef unsigned long long ULL;
+#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
+/*************************************************************************/
+
+/*int main ()
+{
+	int n;
+	cin >> n;
+	vector<vector<vector<int> > > cubes;
+	cubes.resize(n);
+	for (int i = 0; i < n; ++i) {
+		cubes[i].resize(n);
+		for (int y = 0 ; y < n; ++y) {
+			cubes[i][y].resize(n);
+			for (int x = 0; x < n; ++x) {
+				cin >> cubes[i][y][x];
+			}
+		}
+	}
+}
+*/
+
+inline int shauj(int x1, int y1, int x2, int y2) {
+	if (x1 == x2 && y1 == y2) return 0;
+	return ((x1 == x2) || (y1 == y2)) ? 1 : 0;
+}
+
+
+int pot[4][2];
+int bestval = 1000;
+int best[4][2];
+
+
+void check(int f1, int f2, int f3, int f4)
+{
+	for(int x1 = 1; x1 <= 20; ++x1)
+		for(int x2 = 1; x2 <= 20; ++x2)
+			for(int y1 = 1; y1 <= 20; ++y1)
+				for(int y2 = 1; y2 <= 20; ++y2)
+				{
+					if (!(x1 == pot[f1][0] && y1 == pot[f1][1]) && !(x1 == pot[f2][0] && y1 == pot[f2][1]) &&
+						!(x2 == pot[f1][0] && y2 == pot[f1][1]) && !(x2 == pot[f2][0] && y2 == pot[f2][1]) &&
+						!(x1 == x2 && y1 == y2)) // ja tupenji nepaarklaajas
+					{
+						int s, x, y;
+						x = x1; y = y1;
+						s = shauj(x, y, pot[f1][0], pot[f1][1]) + shauj(x, y, pot[f2][0], pot[f2][1]) + shauj(x, y, x1, y1) + shauj(x, y, x2, y2);
+						if (s != 1) continue;
+						x = x2; y = y2;
+						s = shauj(x, y, pot[f1][0], pot[f1][1]) + shauj(x, y, pot[f2][0], pot[f2][1]) + shauj(x, y, x1, y1) + shauj(x, y, x2, y2);
+						if (s != 1) continue;
+						x = pot[f1][0]; y = pot[f1][1];
+						s = shauj(x, y, pot[f1][0], pot[f1][1]) + shauj(x, y, pot[f2][0], pot[f2][1]) + shauj(x, y, x1, y1) + shauj(x, y, x2, y2);
+						if (s != 1) continue;
+						x = pot[f2][0]; y = pot[f2][1];
+						s = shauj(x, y, pot[f1][0], pot[f1][1]) + shauj(x, y, pot[f2][0], pot[f2][1]) + shauj(x, y, x1, y1) + shauj(x, y, x2, y2);
+						if (s != 1) continue;
+						
+						int mainjas = 2;
+						if (x1 == pot[f3][0] && y1 == pot[f3][1]) mainjas--;
+						if (x2 == pot[f4][0] && y2 == pot[f4][1]) mainjas--;
+						if (mainjas < bestval) {
+							best[f1][0] = pot[f1][0]; best[f1][1] = pot[f1][1];
+							best[f2][0] = pot[f2][0]; best[f2][1] = pot[f2][1];
+							best[f3][0] = x1; best[f3][1] = y1;
+							best[f4][0] = x2; best[f4][1] = y2;
+							bestval = mainjas;
+						}
+					}
+				}
+}
+
+int main(void)
+{
+	cin >> pot[0][0] >> pot[0][1];
+	cin >> pot[1][0] >> pot[1][1];
+	cin >> pot[2][0] >> pot[2][1];
+	cin >> pot[3][0] >> pot[3][1];
+	check(0, 1, 2, 3);
+	check(0, 2, 1, 3);
+	check(0, 3, 1, 2);
+	check(1, 2, 0, 3);
+	check(1, 3, 0, 2);
+	check(2, 3, 0, 1);
+	cout << best[0][0] << " " << best[0][1] << endl;
+	cout << best[1][0] << " " << best[1][1] << endl;
+	cout << best[2][0] << " " << best[2][1] << endl;
+	cout << best[3][0] << " " << best[3][1] << endl;
+	//cout << bestval << endl;
+}

2010-10-30/problems.pdf

Binary file added.