Commits

Andrey Vihrov  committed ffd9d7f

2011/03/20 solutions

  • Participants
  • Parent commits 52ba836

Comments (0)

Files changed (5)

File 2011-03-20/Makefile

+###############################################################################
+#
+# Makefile for small projects, version 2.0b
+#
+# 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 = c f_fail h_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))))
+
+###############################################################################

File 2011-03-20/c.cpp

+/*****************************************************************************
+ * University of Latvia, team KVV                                            *
+ *****************************************************************************/
+
+#define PROB "codeforces"        /* 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)
+/*****************************************************************************/
+
+#define MAXN 100010
+#define MAXP 6
+int b[MAXN][MAXP];
+
+LL gcd(LL a, LL b) {
+	// a<b
+	if (a == 0) return b;
+	return gcd(b % a, a);
+}
+
+int main ()
+{
+	int casenum = 0;
+	while (1)
+	{
+		casenum++;
+		
+		LL n;
+		
+		cin >> n;
+		if (n == 0) break;
+		int c[MAXN];
+		for (int i=0; i<n; ++i) {
+			cin >> c[i];
+		}
+		for (int i=0; i<MAXP; ++i) {
+			b[n][i] = 0;
+		}
+		for (int i=n-1; i>0; --i) {
+			for (int p=0; p<MAXP; ++p) {
+				b[i][p] = b[i+1][p];
+			}
+			b[i][c[i]]++;
+		}
+		
+		LL numer = 0;
+		LL denum = 0;
+		
+		for (int i=0; i<n; ++i) {
+			for (int p=c[i]+1; p<MAXP; ++p) {
+				numer += b[i+1][p]*(p-c[i])*(p-c[i]);
+			}
+		}
+		
+		numer = 2*numer;
+		denum = n*(n-1);
+		
+		LL comm = gcd(numer, denum);
+		numer /= comm;
+		denum /= comm;
+		
+		if (denum > 1) {
+			cout << "Case #" << casenum << ": The contest badness is " << numer << "/" << denum << "." << endl;
+		} else
+		{
+			cout << "Case #" << casenum << ": The contest badness is " << numer << "." << endl;
+		}
+	}
+}

File 2011-03-20/f_fail.cpp

+/*****************************************************************************
+ * University of Latvia, team KVV                                            *
+ *****************************************************************************/
+
+#define PROB "ffriends"        /* 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)
+/*****************************************************************************/
+
+template<size_t n>
+struct bitset
+{
+	static const size_t nbits = 30; // 6 * 5
+
+	unsigned arr[n / nbits + 1];
+	
+	bitset()
+	{
+		memset(arr, 0, sizeof(arr));
+	}
+	
+	bool get(size_t i) const
+	{
+		return (arr[i / nbits] & (1U << (nbits - i % nbits - 1))) != 0;
+	}
+	
+	void set(size_t i)
+	{
+		arr[i / nbits] |= 1U << (nbits - i % nbits - 1);
+	}
+	
+	void clear(size_t i)
+	{
+		arr[i / nbits] &= ~(1U << (nbits - i % nbits - 1));
+	}
+	
+	void set_six(size_t i, unsigned six)
+	{
+		arr[i / nbits] |= six << (nbits - 6 - i % nbits);
+	}
+	
+	bool operator& (const bitset& other) const
+	{
+		for (size_t i = 0; i < n / nbits + 1; i++)
+		{
+			if (arr[i] & other.arr[i])
+				return true;
+		}
+		return false;
+	}
+};
+
+ostream& operator << (ostream& os, const ::bitset<1000>& b)
+{
+	for (size_t i = 0; i < 15; i++)
+		os << (b.get(i) ? '1' : '0');
+	return os;
+}
+
+inline unsigned decode(char c)
+{
+	if (c == '+')
+		return 62;
+	else if (c == '/')
+		return 63;
+	else if (c < 'A')
+		return 52 + c - '0';
+	else if (c < 'a')
+		return c - 'A';
+	else
+		return 26 + c - 'a';
+}
+
+int main ()
+{
+	int casenum = 0, n;
+		
+	cin >> n;
+	while (n)
+	{
+		casenum++;
+		
+		vector< ::bitset<1000> > sets(n);		
+		for (int i = 0; i < n; i++)
+		{
+			string s; 
+			cin >> s;
+			for (int j = 0; j <= i; j += 6)
+				sets[i].set_six(j, decode(s[j / 6]));
+		}
+		for (int i = 0; i < n - 1; i++)
+		{
+			for (int j = i + 1; j < n; j++)
+			{
+				if (sets[j].get(i))
+					sets[i].set(j);
+			}
+		}
+		for (int i = 0; i < n; i++)
+			sets[i].clear(i);
+		
+		cout << "Case #" << casenum << ": ";
+		bool found = false;
+		for (int i = 0; i < n - 1; i++)
+		{
+			for (int j = i + 1; j < n; j++)
+			{
+				if (!(sets[i] & sets[j]))
+				{
+					cout << "Members " << i + 1 << " and " << j + 1 << " have no common friends.\n";
+					found = true;
+					break;
+				}
+			}
+			if (found)
+				break;
+		}
+		if (!found)
+			cout << "Social graph is too dense.\n";			
+		
+		cin >> n;	
+	}
+}

File 2011-03-20/h_fail.cpp

+/*****************************************************************************
+ * University of Latvia, team KVV                                            *
+ *****************************************************************************/
+
+#define PROB "lists"        /* Comment out to use standard I/O everywhere     */
+#define STDIO            /* Uncomment to use standard I/O on our PC        */
+//#define LOCAL_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)
+/*****************************************************************************/
+
+#define MAXN 8000
+struct superset {
+	int data[MAXN];
+	int dc = 0;
+
+	void superset() {};
+	bool find(int x) {
+	}
+
+	bool 
+}
+
+int main ()
+{	
+	int cn = 0;
+	while (1) {
+		cn++;
+		int n;
+		cin >> n;
+		if (n == 0) break;
+		
+		set<unsigned int> common, newcommon;
+		bool firstrun = true;
+		
+		for (int i = 0; i < n; ++i) {
+			unsigned int x, y, a, b, m;
+			cin >> x >> y >> a >> b >> m;
+
+			newcommon.clear();
+			for (int j = 0; j < n; ++j) {
+				if (firstrun || common.find(y) != common.end()) {
+					newcommon.insert(y);
+				}
+
+				x = a*x+b;
+				if (m > 31) {
+					y++;
+				} else {
+					y = y+1+(x>>m);
+				}
+			}
+			//sort(l[i], l[i]+n);
+			firstrun = false;
+			common = newcommon;
+		}
+		cout << "Case #" << cn << ": Intersection contains " << common.size() << " integer(s).\n";
+	}
+}

File 2011-03-20/j.cpp

+/*****************************************************************************
+ * University of Latvia, team KVV                                            *
+ *****************************************************************************/
+
+#define PROB "wilson"        /* 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)
+/*****************************************************************************/
+
+bool isprime(int n) {
+	for (int k = 2; k*k<=n; k++) {
+		if (n % k == 0) return false;
+	}
+	return true;
+}
+
+int main ()
+{
+	int c = 0;
+	while (1) {
+		c++;
+		int n;
+		cin >> n;
+		if (n == 0) break;
+		int wn = (isprime(n) ? n-1 : 0);
+		if (n == 4) wn =2;
+		
+		/*int dumb = 1;
+		for (int i = 1; i<n; ++i) {
+			dumb = (dumb*i) % n;
+		}
+		*/
+		cout << "Case #" << c << ": " << n;
+		string s = "th";
+		
+		if (n % 10 == 1 && (n % 100)/10 != 1) s = "st";
+		if (n % 10 == 2 && (n % 100)/10 != 1) s = "nd";
+		if (n % 10 == 3 && (n % 100)/10 != 1) s = "rd";
+		cout << s << " Wilson number is equal to " << wn << "." << endl;
+	}
+}
+