ࡱ> 5@ bjbj22 "XX<p_p_p_p_l_ `ccccccc{}}}}}}$؄R*9ecceeccځyyye^ cc{ye{y yz||c` 3 p_r|/L0 |y4|||~LcZc@yd4PdlcccD-L3$,y L3Programming Contest Preparation Useful Libraries and Information USACO High School Programming Competition Online Tests: http://train.usaco.org/usacogate ACM: online-judge.uva.es Java Collections http://java.sun.com/docs/books/tutorial/collections/interfaces/index.html A set can only contain one of a particular element. There is also a sortedSet (treeSet) that extends set and adds an ordering. A list can contain more than one element and is sorted. A map has keys and values, like a hash table. There is also a sortedMap (treeMap) that extends a map and adds an ordering. Collections use Generics: http://java.sun.com/docs/books/tutorial/java/generics/index.html Set s = new HashSet(); Useful classes, taken from the AP CS AB handbook (http://www.collegeboard.com/prod_downloads/ap/students/compsci/52435%20APCompSci-Locked.pdf) interface java.util.List boolean add(E x) int size() E get(int index) E set(int index, E x) // replaces the element at index with x // returns the element formerly at the specified position void add(int index, E x) // inserts x at position index, sliding elements // at position index and higher to the right // (adds 1 to their indices) and adjusts size E remove(int index) // removes element from position index, sliding // elements at position index 1 1 and higher to the // left (subtracts 1 from their indices) and adjusts size // returns the element formerly at the specified position " Iterator<E> iterator() " ListIterator<E> listIterator() class ja va.util.ArrayList<E> implements java.util.List<E> class ja va.util.LinkedList implements java.util.List, java.util.Queue Methods in addition to the List methods: void addFirst(E x) void addLast(E x) E getFirst() E getLast() E removeFirst() E removeLast() interface java.util.Set boolean add(E x) boolean contains(Object x) boolean remove(Object x) int size() Iterator iterator() class ja va.util.HashSet implements java.util.Set class ja va.util.TreeSet implements java.util.Set interface java.util.Map V put(K key, V value) V get(Object key) V remove(Object key) boolean containsKey(Object key) int size() Set keySet() class ja va.util.HashMap implements java.util.Map class ja va.util.TreeMap implements java.util.Map (Use treeMap if you want a sorted Map, HashMap if you want a fast Map. Same with Set.) interface java.util.Iterator boolean hasNext() E next() void remove() interface ja va.util.ListIterator extends java.util.Iterator Methods in addition to the Iterator methods void add(E x) void set(E x) class java.util.Stack E push(E x) E pop() E peek() boolean isEmpty() interface java.util.Queue boolean add(E x) E remove() E peek() boolean isEmpty() class java.util.PriorityQueue boolean add(E x) E remove() E peek() boolean isEmpty() Java.util.Vector resizable linked listsize and capacity can vary .add(index, obj) .add(object) .get(index i) .remove(index i) isEmpty() remove(object) clear() ArrayLists are similar to Vectors. Double-ended queue Stacks combined with queues class java.util.deque extends queue - new with Java 6 Methods, from http://java.sun.com/javase/6/docs/api/java/util/Deque.html (special value functions return null or false appropriately): First Element (Head)Last Element (Tail)Throws exceptionSpecial valueThrows exceptionSpecial valueInsert HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Deque.html" \l "addFirst%28E%29" addFirst(e) HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Deque.html" \l "offerFirst%28E%29" offerFirst(e) HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Deque.html" \l "addLast%28E%29" addLast(e) HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Deque.html" \l "offerLast%28E%29" offerLast(e)Remove HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Deque.html" \l "removeFirst%28%29" removeFirst() HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Deque.html" \l "pollFirst%28%29" pollFirst() HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Deque.html" \l "removeLast%28%29" removeLast() HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Deque.html" \l "pollLast%28%29" pollLast()Examine HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Deque.html" \l "getFirst%28%29" getFirst() HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Deque.html" \l "peekFirst%28%29" peekFirst() HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Deque.html" \l "getLast%28%29" getLast() HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Deque.html" \l "peekLast%28%29" peekLast() Collections implementations and methods, from the Sun Java Collections Overview Site, http://java.sun.com/javase/6/docs/technotes/guides/collections/index.html : ImplementationsHash TableResizable ArrayBalanced TreeLinked ListHash Table + Linked ListInterfacesSet HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/HashSet.html" HashSet  HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/TreeSet.html" TreeSet   HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/LinkedHashSet.html" LinkedHashSet List  HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/ArrayList.html" ArrayList  HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/LinkedList.html" LinkedList Deque  HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/ArrayDeque.html" ArrayDeque  HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/LinkedList.html" LinkedList Map HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/HashMap.html" HashMap  HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/TreeMap.html" TreeMap  HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/LinkedHashMap.html" LinkedHashMap Collections  HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Collections.html" \l "sort%28java.util.List%29" sort(List) - Sorts a list using a merge sort algorithm, which provides average-case performance comparable to a high-quality quicksort, guaranteed O(n*log n) performance (unlike quicksort), and stability (unlike quicksort). (A stable sort is one that does not reorder equal elements.) sort(List, comparator)  HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Collections.html" \l "binarySearch%28java.util.List,%20T%29" binarySearch(List, Object) - Searches for an element in an ordered list using the binary search algorithm.  HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Collections.html" \l "reverse%28java.util.List%29" reverse(List) - Reverses the order of the elements in the a list.  HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Collections.html" \l "shuffle%28java.util.List%29" shuffle(List) - Randomly permutes the elements in a list.  HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Collections.html" \l "fill%28java.util.List,%20T%29" fill(List, Object) - Overwrites every element in a list with the specified value.  HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Collections.html" \l "copy%28java.util.List,%20java.util.List%29" copy(List dest, List src) - Copies the source list into the destination list.  HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Collections.html" \l "min%28java.util.Collection%29" min(Collection) - Returns the minimum element in a collection.  HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Collections.html" \l "max%28java.util.Collection%29" max(Collection) - Returns the maximum element in a collection.  HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Collections.html" \l "rotate%28java.util.List,%20int%29" rotate(List list, int distance) - Rotates all of the elements in the list by the specified distance.  HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Collections.html" \l "replaceAll%28java.util.List,%20T,%20T%29" replaceAll(List list, Object oldVal, Object newVal) - Replaces all occurrences of one specified value with another.  HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Collections.html" \l "indexOfSubList%28java.util.List,%20java.util.List%29" indexOfSubList(List source, List target) - Returns the index of the first sublist of source that is equal to target.  HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Collections.html" \l "lastIndexOfSubList%28java.util.List,%20java.util.List%29" lastIndexOfSubList(List source, List target) - Returns the index of the last sublist of source that is equal to target.  HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Collections.html" \l "swap%28java.util.List,%20int,%20int%29" swap(List, int, int) - Swaps the elements at the specified positions in the specified list.  HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Collections.html" \l "frequency%28java.util.Collection,%20java.lang.Object%29" frequency(Collection, Object) - Counts the number of times the specified element occurs in the specified collection.  HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Collections.html" \l "disjoint%28java.util.Collection,%20java.util.Collection%29" disjoint(Collection, Collection) - Determines whether two collections are disjoint, in other words, whether they contain no elements in common.  HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Collections.html" \l "addAll%28java.util.Collection,%20T...%29" addAll(Collection, T...) - Adds all of the elements in the specified array to the specified collection.  HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Collections.html" \l "newSetFromMap%28java.util.Map%29" newSetFromMap(Map) - Creates a general purpose Set implementation from a general purpose Map implementation.  HYPERLINK "http://java.sun.com/javase/6/docs/api/java/util/Collections.html" \l "asLifoQueue%28java.util.Deque%29" asLifoQueue(Deque) - Returns a view of a Deque as a Last-in-first-out (Lifo) Queue. Range-view operations on a sorted set dictionary.subSet("f", "g").clear(); .subSet(f,g).size() dictionary.headSet(object n) up to n, exclusive dictionary.tailSet(Object n) .first() last() For each-loops java.sun.com/j2se/1.5.0/docs/guide/language/foreach.html Instead of void cancelAll(Collection c) { for (Iterator i = c.iterator(); i.hasNext(); ) i.next().cancel(); } we can use void cancelAll(Collection c) { for (TimerTask t : c) t.cancel(); } // a is an array of integers for (int i : a) result += i; Does not work for collections if youre removing elements Example with a map: for (KeyType key : m.keySet()) System.out.println(key); and with an iterator: // Filter a map based on some property of its keys. for (Iterator it = m.keySet().iterator(); it.hasNext(); ) if (it.next().isBogus()) it.remove(); Sorting an array (code taken from http://www.exampledepot.com/egs/java.util/pkg.html , Java Developers Almanac) Arrays.sort(strArray, String.CASE_INSENSITIVE_ORDER); // [a, C, z] // Reverse-order sort Arrays.sort(strArray, Collections.reverseOrder()); Convert an array to a Collection // Fixed-size list List list = Arrays.asList(array); // Growable list list = new LinkedList(Arrays.asList(array)); // Duplicate elements are discarded Set set = new HashSet(Arrays.asList(array)); Converting a Collection to an Array .toArray() returns an array of Objects. If you want an array of a particular kind, you have to cast it as follows. // Create an array containing the elements in a list Object[] objectArray = list.toArray(); MyClass[] array = (MyClass[])list.toArray(new MyClass[list.size()]); // Create an array containing the elements in a set objectArray = set.toArray(); array = (MyClass[])set.toArray(new MyClass[set.size()]); // Create an array containing the keys in a map objectArray = map.keySet().toArray(); array = (MyClass[])map.keySet().toArray(new MyClass[set.size()]); // Create an array containing the values in a map objectArray = map.values().toArray(); array = (MyClass[])map.values().toArray(new MyClass[set.size()]); Subarrays with Java 6 int[] newArray = Arrays.copyOf(a, newLength); public static int[] copyOfRange(int[]original, intfrom, intto) Math.Random() Random.nextInt(int) returns [0,int) float  HYPERLINK "http://java.sun.com/j2se/1.4.2/docs/api/java/util/Random.html" \l "nextFloat%28%29" nextFloat() [0.0,1.0] Strings, Characters, and I/O Use the Scanner class for reading input. .nextInt() nextLine() hasNext() nextFloat(); new Scanner(new File(prob.in)); String substring(int from, int to) // returns the substring beginning at from // and ending at to-1 String charAt(char) StringBuffer buffer = new StringBuffer(128); New String(StringBuffer); yourStringBuffer.append(string); String.toLowerCase() toUpperCase() equals() Can use C A + a to convert to lower caseor Character.toLowerCase Can also use character codes as above to index an array of characters instead of intsbe creative! .startsWith(string) trim() .indexOf(char) .indexOf(string) NumberFormatcan use for output NumberFormat nf = new NumberFormat(); nf.setMinimumFractionDigits( 3 ); nf.setMaximumFractionDigits( 3 ); nf.setMinimumIntegerDigits( 1 ); nf.setMaximumIntegerDigits( 10 ); string = nf.format(int); Easy toString: concatenate starting with a string, Or an empty string: + yourint no toString needed Of course youre familiar with Integer.parseInt(String) and related classes. Character.isDigit() .isLetterOrDigit() .isLetter() isSpace() String [] = yourString.split() instead of tokenizer uses regular expressions You can use .split() on the nextLine() from a Scanner. Split(\\s) splits with spaces as separators \s stands for spaces, \\ is so the backslash is recognized \S all but whitespace java.sun.com/javase/6/docs/api/java/util/regex/Pattern.html [abc] only characters a,b,c ^ negation [a-zA-Z] inclusive range union ACM/Programming Contest Judge Feedback Accepted (AC) Presentation Error (PE) The I/O is off. Theyre picky with thisbe careful. Accepted (PE) Accepted with presentation error, like extra blank at end of line Wrong Answer(WA) Be sure to look at boundary cases and ensure youre solving the right problem. You wont be able to know what the judges input is to test. Compile Error (CE) Runtime Error (RE) Time Limit Exceeded (TL) You probably wont have to worry about this for the contest. Make sure youre outputting to System.out. Memory Limit Exceed (ML) Output Limit Exceeded (OL) For this and the two above, watch out for infinite loops. Restricted Function (RF) In the real contest, some functions may be restricted, like BigInteger. Check with the judges for details. Submission Error (SE) You gave an incorrect user ID or problem numberthe automated system we use takes care of this.  ABz  D W Y u w $ @ H J V ] n q }    ' ѻѻܜzzzzzzzzzzzzzzz h?h=<CJOJQJ^JaJ h?h=<CJOJQJ^JaJ&h?h=<5CJOJQJ\^JaJh?hVCJaJh?h CJaJh?hdCJaJh?hCJaJh?h=<CJaJh?h?5CJaJh?h=<5CJaJ. ABz  D E _ W X u !!!!!!!!!!!!!!!!!!!!!!!!!!! 7$8$H$gd=<gdVgdVgd=<$a$gd=< " = n  ,FP{0!!!!!!!!!!!!!!!!!!!!!!!!!!!! 7$8$H$gd=<,2FJPmr}02KMXZq+-BDdfqsͼͼͼͼͫͼͼͼͼͼͼ͗ͼͼͼͼ͗ͼͼͼͼͼ͗h?h=<CJaJ&h?h=<5CJOJQJ\^JaJ h?h=<CJOJQJ^JaJ h?h=<CJOJQJ^JaJ h?h=<CJOJQJ^JaJ h?h=<CJOJQJ^JaJ h?h=<CJOJQJ^JaJ50KXq+BdqTUu!!!!!!!!!!!!!!!!!!!!!!!!!!!!gd 7$8$H$gd=<3RTUuw %'6OQ]_girt%'02CDE±±±±±h?h=<CJaJ h?h=<CJOJQJ^JaJ h?h=<CJOJQJ^JaJ h?h=<CJOJQJ^JaJ&h?h=<5CJOJQJ\^JaJ&h?h 5CJOJQJ\^JaJh?hVCJaJh?h CJaJ1%56O]gr%0DE!!!!!!!!!!!!!!!!!!!!!!!!!!!gdVgd=< 7$8$H$gd=<  ;t%!!!!!!!!!!!"H $$Ifa$$Ifgd=<gdV :bdst$'78EFVWdflmn9:GHIJ "()*ꪗꪗꪗꪗꪗ$h?hGy0J>*B*CJaJphjh?hGyCJUaJh?hGy0JCJaJh?hGy5CJ\aJh?hVCJaJh?h=<CJaJh?hGyCJaJh?h?CJaJ;%&'8FWea["RRRR $$Ifa$$Ifkd$$If-FeX'06    34-ab pefmI-'"''$Ifkd$$If-ret X'0634-abp2I!")'"kd$$If-ret X'0634-abp2$If)s$IfdeqrstCDNOPQ"#$%34GHҹҹjh?h&`CJUaJh?h&`5CJ\aJh?h&`CJaJh?hVCJaJh?hGy5CJ\aJh?hGyCJaJ$h?hGy0J>*B*CJaJphjh?hGyCJUaJ6P-'"''$Ifkd$$If-ret X'0634-abp2$'kd$$If-ret X'0634-abp2$If247GHIT!!!!E a[$Ifkd$$IfT44    00(0    634abpT $$Ifa$gdVgd=< Tdr~ $$Ifa$ I=kd$$IfT44    ֈ0# (0    634abp<TUX {~B E F G K FfFf Ff-$If $$Ifa$JKRSXY !noyz5 6 @ A F K L L!M!Z![!k!l!!!Ӵh?h&`0JCJaJ!jh?h&`0JCJUaJh?h&`5CJ\aJh?h&`CJaJjh?h&`CJUaJ$h?h&`0J>*B*CJaJphAK \!]!^!_!"##$Y% &&'X(6)**++3, -.3/&0 1!!!!!!!!!!!!!!!!!!!!X & Fdd[$\$gd&`gd=<FfM$If!!!"""########g$h$u$v$$$%%*%+%Y%Z%%%%% &!&&&&&&&b'c'r's'''((&('(X(Y(((((6)7)))))**+*****++,+++Լ߯߯߯߯߯߯߯߯߯߯߯h?h&`0JCJaJh?hdCJaJh?h&`0JCJaJh?h&`CJaJ!jh?h&`0JCJUaJh?h&`0J5CJ\aJE+++3,4,,,,, ------......3/4/////&0'000000000 1 111111111122222ԺԺԺԺԯh?hGyCJaJh?hCJaJh?hdCJaJh?h CJaJh?h&`0JCJaJh?h&`0JCJaJh?h&`CJaJ!jh?h&`0JCJUaJh?h&`0J5CJ\aJ4 1111#2;2k22222223V3q3s3~3333333 44!X!!!!!!!!!!!!!!!!!!!!!!!!gdgdGygd gd=< & Fdd[$\$gd&`2222!3T3^3f33333334$4]4^444m5n5555555566$7)77곥ߖߋ~shhVV#h?h6B*CJ]aJphfh?h?CJaJh?hVCJaJh?h 0JCJaJh?h CJaJh?hB* CJaJphh?hGy5CJ\aJh?h5CJ\aJh?hGyB* CJaJphh?hGyB*CJaJphh?hCJaJh?hGyCJaJh?h=<CJaJ!4$4^4_4s44444:5W5l5m5o5556,616K666666666!!!!!!!X!!!!!!!!!!!!!!!!!!!gd gd gd=<gd6-727Z7777#8$8]88889/9l9q999::P:z::::;;!!!!!!!!!!!!!!!!!!!!!!!!!!!gdGygd=<gdVgd77#8$8x8|88888888888 9#9<9C9F9I9V9]9^9a99999999:: :b:e::::::::::::;%;;;;;;;̨̳h?h&`0JCJaJh?h&`CJaJh?hGy5CJ\aJh?h=<CJaJh?hGyCJaJh?hVCJaJh?hCJaJ#h?h6B*CJ]aJphf8;6;`;;;;;;;<=<Z<<<<<<!=7=K=x=====)>>>!!!!!!!X!X!!!!!!!!!!!!!!!!!gd&` 7$8$H$gdGy$a$gdVgd=<gdGy;;#<$<-<.<0<;<<<=<Z<<<<<<<<=$=2=7=J=K=x==븭ttcRcRcGh?hdCJaJ h?hGyCJOJQJ^JaJ h?hGyCJOJQJ^JaJh?h CJaJh?hGyCJaJh?hV5CJaJh?h&`5CJaJh?hVCJaJh?h&`CJaJh?h&`0JCJaJ*h?h&`0J5CJOJQJ\^JaJh?h&`0J5CJ\aJ'jh?h&`0J5CJU\aJ==>>>>>????+?,?-?/?0?1?2?4?5?M?N?O?Q?R?S?U?W?X?o?p?q?s?t?u?v?x?y???????????@ɼɈ{ɼɈ{ɼɈ{ɼɈ{h?h 0JCJaJh?h 0JCJaJh?h 0JCJaJh?h 0JCJaJh?h 0JCJaJh?h 0JCJaJh?h CJaJh?hVCJaJh?h&`CJaJh?hdCJaJh?h2CJaJ0>>>>>?2?T?U?v?????@@j@@@@.A\AAAABB0B!!!!!!!!!!!!!!!!!!!!!!!!!!!gddgd gd=<gd&`@@@i@@@@@ A-A.AA0B1B2BXBYBEɾ골ɨUh?h2CJaJh?hCJaJh?h CJaJh?hGyCJaJh?hz#CJaJh?h&`CJaJh?hVCJaJh?hdCJaJ0B2BYBgBBCCCCPDiDDFEEE!!!!!!!!!!!!!!gd=<You can have more than one problem with your program and only have one error message reported to youtheres a hierarchy. Youll get a PE before a WA, for example. 1h/ =!"#$%$$If!vh555#v#v#v:V -06,5/ 34-p$$If!vh55 5 5g5n#v#v #vg#vn:V -06,5/ 34-p2$$If!vh55 5 5g5n#v#v #vg#vn:V -06,5/ 34-p2$$If!vh55 5 5g5n#v#v #vg#vn:V -06,5/ 34-p2$$If!vh55 5 5g5n#v#v #vg#vn:V -06,5/ 34-p2$$If!vh5l5 #vl#v :V 440    6+,5/ 34pT.$$If!vh5l55555#vl#v#v#v#v#v:V 440    6+,5/ 34p<TF$$If!vh55U55555#v#vU#v#v#v#v#v:V 440    6+,5/ 34pFTkd$$IfT44    ֞0# (0    634abpFTF$$If!vh55U55555#v#vU#v#v#v#v#v:V 440    6+,5/ 34pFTkdE $$IfT44    ֞0# (0    634abpFTF$$If!vh55U55555#v#vU#v#v#v#v#v:V 440    6+,5/ 34pFTkd $$IfT44    ֞0# (0    634abpFTF$$If!vh55U55555#v#vU#v#v#v#v#v:V 440    6+,5/ 34pFTkd$$IfT44    ֞0# (0    634abpFT@@@ NormalCJ_HaJmH sH tH N@2N  Heading 3dd@&[$\$5CJ\aJDA@D Default Paragraph FontRi@R  Table Normal4 l4a (k@(No Liste@ HTML Preformatted7 2( Px 4 #\'*.25@9CJOJQJ^JaJ6U@6  Hyperlink >*B*phB^@B Gy Normal (Web)dd[$\$.X@!. GyEmphasis6]Bb@1B Gy HTML CodeCJOJPJQJ^JaJNg@AN 0HTML TypewriterCJOJPJQJ^JaJ*W@Q* &`Strong5\ oa jvar(oq( operator&o& jmethod$o$ fence1:o: numericliterallow*o* semicolon:o: commentslashslash< !z z z z z z z z z! z z z*  X!7*+/i2$7^8<W#4 7  ABzDE_WXu"=nC}-L}-@]x,DXo ) *  B R b c |   2 E R ] q r   6 7 h ( ) > R S T e s vNOV2  }Q_adtuv),JMorstx%(%<$McW X!`":#>$`%S&8'((+(P(h(((((())E)))))))***#*7*L*Q*******'+g+++++ ,,H,Y,^,x,,,,,,--)-Z-_-----P.Q..../;/\/////B0G0}000012131c1111111h2j222223#3N3d3x33333 4V4444445=5_55555556H6I6666$7[7777838>8]8_888849999}:::s;;;<00p0p0p00p0p0000p0p000000000p0p0p00 00 0 00 0 000 00 0 00 0 00 0 00 0000 0 0 0 080 0p0p0p0p0p0p00p0p0p000p0p0p0p00000 00 00p00 0 00 0 00 0000 0 0 0 00000 00 0 0@0p0p0p0p00@0p@0p@0p@0p@0p@0p@000000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00p0@000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0  0 00 0 0p 0p 0p 0p 0p 0p 0 00 0 00 00 00 00p0000 00 0 00 0 0p0p0p0p0p0p0p00000p0p0p0p0p0p0p0000000000 00 00 00 00 0(00(0 00 0000 0 0 0 0p0p0p0p0p0p0p000p0p00p0p0000p0p0p00000000p0p000 000 0p0 000 0p0 000p0000 000000 0p00000000000000p00 00000000000000ABzDE_WXu"=nC}-L}-@]x,DXo ) *  B R b c |   2 E R ] q r  7 h ( ) > R S T e s vNOV2  }Q_adtuv),JMorstx%(%<$McW X!`":#>$`%S&8'((+(P(h(((((())E)))))))***#*7*L*Q*******'+g+++++ ,,H,Y,^,x,,,,,,--)-Z-_-----Q..../;/\/////B0G0}000012131c1111111h2j223#3N3d3x33333 4V4444445=5_55555556H6666$7[7777838>8]8_888849999}:::s;;;<000000M9000000M90 0M90 0O900@0-.@0-.@0@00000000000000000000000000000000000000000000000000000000000000000000000000000000000000O90g@0@0@0@0@0@0@0@000O90i00000000000000000000000000000000Oy00@00000 000000000000000 00000000 00000000 0000000000 0 0 0 0 0 0 0 0 0 0  0  0  0  0  0 0 0 0 000000000000000000000000000000000000000000000000000000000*0*00-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.O90?1My00My00My00Oy00My000-.0-.0-.0-.0-.0-.0-.0-.O90L1M90L1M90L1M90L10-.M90Q1M90Q10-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.0-.!+27;=@#'),18:;=@BCE 0%eI)TK 146;>0B$&(*+-./02345679<>?ADF% ftv?LV$02p{}EOQ',w>HMbmx#(y<$IW MCSc W !X!!"`""":###>$$$`%%&S&&&8'''1P2Z2<XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX0lY1lk#2l\3lܷ4lX5l"BBH<GSS<=*urn:schemas-microsoft-com:office:smarttags PlaceType=*urn:schemas-microsoft-com:office:smarttags PlaceName9*urn:schemas-microsoft-com:office:smarttagsState8*urn:schemas-microsoft-com:office:smarttagsCity9*urn:schemas-microsoft-com:office:smarttagsplace U^`gcqw~-0 )356HWejy)/6BI_fz} &qxy  # / 6 Q X  1 9 i x    . 4 ; _ f g n r   n } gq@I%.qyFM 'x?Hcm#z   ,!3!!!4";"""""%%&&''''''''+(<(Q(W(Y(^(h(z((( )))5)>)N)V)W)`)b)c)f)p)t)}))))))))))),*/*0*1*I*J*********,+4+@+H+K+S+W+a+o+v+y++++,,,&,(,E,|,,,,,,,,,--#-8-B-C-P---------..............?/J/M/X/i/p/s/~/////////// 0000 0'0,03040<000000000000000000011 111"1&1/1A1D1G1R1S1V11111111111Q2Z222222222223333k3q3x333333333334@4U444444444455#5$5&5-595=5X5_5z55555555555+62686@6i6y6666666666667@7H77788,818A8C8p:z:D;N;<Ybw~$(-2LV/6BI_fz}04HL\cqx  q D H T X c h    4 ; I Q V \ _ f   h m  JRDH !!""##$$%%&&''+(=(Q(X(h({((((())I)L))))))))))*'***?*E*******'+*+k+m+++++,,|,,,---1-----X.^..... //?/J/`/e/////00N0T000001131911111111111222233k3r3333333334444-5:5=5Y5_5{5555555i6z666661777[7a78858=8:9A9<::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::::@J K S g <<< Rose NestorYu6 ?^`CJOJQJo(^`CJOJQJo(opp^p`CJOJ QJ o(@ @ ^@ `CJOJ QJ o(^`CJOJ QJ o(^`CJOJ QJ o(^`CJOJ QJ o(^`CJOJ QJ o(PP^P`CJOJ QJ o(Yu69h:#*Ldd] {7f Udd R S T e s vNOV2  }Qadtuv),JMorstx%(<@i22l۝22 4--;<@ @ @Unknown Gz Times New Roman5Symbol3& z ArialGCourierStd-Bold]CenturyOldStyleStd-Regular=CourierStd[Universal-GreekwithMathPiESerifaStd-Bold?5 z Courier New;Wingdings"qh˷f˷f 3 m 3 m!>4r<r<3QH)?=<Programming Contest Preparation Rose Nestor Rose Nestor Oh+'0  , H T `lt| Programming Contest Preparationrog Rose Nestoroseose Normal.dot Rose Nestor2seMicrosoft Word 10.0@F#@@  3՜.+,D՜.+,L hp|   rmr<  Programming Contest Preparation Title# 8@ _PID_HLINKSAt#ixx>http://java.sun.com/j2se/1.4.2/docs/api/java/util/Random.htmlnextFloat%28%29 uAhttp://java.sun.com/javase/6/docs/api/java/util/Collections.html!asLifoQueue%28java.util.Deque%29 rAhttp://java.sun.com/javase/6/docs/api/java/util/Collections.html!newSetFromMap%28java.util.Map%29KoAhttp://java.sun.com/javase/6/docs/api/java/util/Collections.html)addAll%28java.util.Collection,%20T...%29ajlAhttp://java.sun.com/javase/6/docs/api/java/util/Collections.html;disjoint%28java.util.Collection,%20java.util.Collection%29,qiAhttp://java.sun.com/javase/6/docs/api/java/util/Collections.html8frequency%28java.util.Collection,%20java.lang.Object%29' fAhttp://java.sun.com/javase/6/docs/api/java/util/Collections.html'swap%28java.util.List,%20int,%20int%29 cAhttp://java.sun.com/javase/6/docs/api/java/util/Collections.html9lastIndexOfSubList%28java.util.List,%20java.util.List%29`Ahttp://java.sun.com/javase/6/docs/api/java/util/Collections.html5indexOfSubList%28java.util.List,%20java.util.List%29XG]Ahttp://java.sun.com/javase/6/docs/api/java/util/Collections.html)replaceAll%28java.util.List,%20T,%20T%29SZAhttp://java.sun.com/javase/6/docs/api/java/util/Collections.html"rotate%28java.util.List,%20int%29_WAhttp://java.sun.com/javase/6/docs/api/java/util/Collections.htmlmax%28java.util.Collection%29WTAhttp://java.sun.com/javase/6/docs/api/java/util/Collections.htmlmin%28java.util.Collection%29dbQAhttp://java.sun.com/javase/6/docs/api/java/util/Collections.html+copy%28java.util.List,%20java.util.List%29ENAhttp://java.sun.com/javase/6/docs/api/java/util/Collections.htmlfill%28java.util.List,%20T%29j&KAhttp://java.sun.com/javase/6/docs/api/java/util/Collections.htmlshuffle%28java.util.List%29|7HAhttp://java.sun.com/javase/6/docs/api/java/util/Collections.htmlreverse%28java.util.List%29@EAhttp://java.sun.com/javase/6/docs/api/java/util/Collections.html&binarySearch%28java.util.List,%20T%29LDBAhttp://java.sun.com/javase/6/docs/api/java/util/Collections.htmlsort%28java.util.List%29.-?Chttp://java.sun.com/javase/6/docs/api/java/util/LinkedHashMap.htmlCU<=http://java.sun.com/javase/6/docs/api/java/util/TreeMap.htmlIK9=http://java.sun.com/javase/6/docs/api/java/util/HashMap.htmlhk6@http://java.sun.com/javase/6/docs/api/java/util/LinkedList.htmljs3@http://java.sun.com/javase/6/docs/api/java/util/ArrayDeque.htmlhk0@http://java.sun.com/javase/6/docs/api/java/util/LinkedList.html8/-?http://java.sun.com/javase/6/docs/api/java/util/ArrayList.html4)*Chttp://java.sun.com/javase/6/docs/api/java/util/LinkedHashSet.htmlYQ'=http://java.sun.com/javase/6/docs/api/java/util/TreeSet.htmlSO$=http://java.sun.com/javase/6/docs/api/java/util/HashSet.html!;http://java.sun.com/javase/6/docs/api/java/util/Deque.htmlpeekLast%28%29.f;http://java.sun.com/javase/6/docs/api/java/util/Deque.htmlgetLast%28%29];http://java.sun.com/javase/6/docs/api/java/util/Deque.htmlpeekFirst%28%29;http://java.sun.com/javase/6/docs/api/java/util/Deque.htmlgetFirst%28%29 ;http://java.sun.com/javase/6/docs/api/java/util/Deque.htmlpollLast%28%29fg;http://java.sun.com/javase/6/docs/api/java/util/Deque.htmlremoveLast%28%29T;http://java.sun.com/javase/6/docs/api/java/util/Deque.htmlpollFirst%28%29!i ;http://java.sun.com/javase/6/docs/api/java/util/Deque.htmlremoveFirst%28%294. ;http://java.sun.com/javase/6/docs/api/java/util/Deque.htmlofferLast%28E%29JI;http://java.sun.com/javase/6/docs/api/java/util/Deque.htmladdLast%28E%29f5;http://java.sun.com/javase/6/docs/api/java/util/Deque.htmlofferFirst%28E%29R;http://java.sun.com/javase/6/docs/api/java/util/Deque.htmladdFirst%28E%29  !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIKLMNOPQRSTVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~Root Entry F@$Data Je1TableU·WordDocument"SummaryInformation(DocumentSummaryInformation8%CompObjj  FMicrosoft Word Document MSWordDocWord.Document.89q