Advertisement
NenadKocev

[АПС] Проверка на спелување

Jan 20th, 2018
546
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5.49 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.IOException;
  3. import java.io.InputStreamReader;
  4.  
  5. class MapEntry<K extends Comparable<K>,E> implements Comparable<K> {
  6.     K key;
  7.     E value;
  8.  
  9.     public MapEntry (K key, E val) {
  10.         this.key = key;
  11.         this.value = val;
  12.     }
  13.     public int compareTo (K that) {
  14.         @SuppressWarnings("unchecked")
  15.         MapEntry<K,E> other = (MapEntry<K,E>) that;
  16.         return this.key.compareTo(other.key);
  17.     }
  18.     public String toString () {
  19.         return "(" + key + "," + value + ")";
  20.     }
  21. }
  22.  
  23.  
  24. class OBHT<K extends Comparable<K>,E> {
  25.  
  26.     private MapEntry<K,E>[] buckets;
  27.     static final int NONE = -1; // ... distinct from any bucket index.
  28.     @SuppressWarnings({ "rawtypes", "unchecked" })
  29.     private static final MapEntry former = new MapEntry(null, null);
  30.     private int occupancy = 0;
  31.  
  32.     @SuppressWarnings("unchecked")
  33.     public OBHT (int m) {
  34.         buckets = (MapEntry<K,E>[]) new MapEntry[m];
  35.     }
  36.  
  37.     private int hash (K key) {
  38.         return Math.abs(key.hashCode()) % buckets.length;
  39.     }
  40.  
  41.     public MapEntry<K,E> getBucket(int i){
  42.         return buckets[i];
  43.     }
  44.  
  45.     public int search (K targetKey) {
  46.         int b = hash(targetKey); int n_search=0;
  47.         for (;;) {
  48.             MapEntry<K,E> oldEntry = buckets[b];
  49.             if (oldEntry == null)
  50.                 return NONE;
  51.             else if (targetKey.equals(oldEntry.key))
  52.                 return b;
  53.             else{
  54.                 b = (b + 1) % buckets.length;
  55.                 n_search++;
  56.                 if(n_search==buckets.length)
  57.                     return NONE;
  58.             }
  59.         }
  60.     }
  61.  
  62.     public void insert (K key, E val) {
  63.         MapEntry<K,E> newEntry = new MapEntry<K,E>(key, val);
  64.         int b = hash(key); int n_search=0;
  65.  
  66.         for (;;) {
  67.             MapEntry<K,E> oldEntry = buckets[b];
  68.             if (oldEntry == null) {
  69.                 if (++occupancy == buckets.length) {
  70.                     System.out.println("Hash tabelata e polna!!!");
  71.                 }
  72.                 buckets[b] = newEntry;
  73.                 return;
  74.             } else if (oldEntry == former
  75.                     || key.equals(oldEntry.key)) {
  76.                 buckets[b] = newEntry;
  77.                 return;
  78.             } else{
  79.                 b = (b + 1) % buckets.length;
  80.                 n_search++;
  81.                 if(n_search==buckets.length)
  82.                     return;
  83.  
  84.             }
  85.         }
  86.     }
  87.  
  88.     @SuppressWarnings("unchecked")
  89.     public void delete (K key) {
  90.         int b = hash(key); int n_search=0;
  91.         for (;;) {
  92.             MapEntry<K,E> oldEntry = buckets[b];
  93.  
  94.             if (oldEntry == null)
  95.                 return;
  96.             else if (key.equals(oldEntry.key)) {
  97.                 buckets[b] = former;
  98.                 return;
  99.             } else{
  100.                 b = (b + 1) % buckets.length;
  101.                 n_search++;
  102.                 if(n_search==buckets.length)
  103.                     return;
  104.  
  105.             }
  106.         }
  107.     }
  108.  
  109.     public String toString () {
  110.         String temp = "";
  111.         for (int i = 0; i < buckets.length; i++) {
  112.             temp += i + ":";
  113.             if (buckets[i] == null)
  114.                 temp += "\n";
  115.             else if (buckets[i] == former)
  116.                 temp += "former\n";
  117.             else
  118.                 temp += buckets[i] + "\n";
  119.         }
  120.         return temp;
  121.     }
  122. }
  123.  
  124.  
  125. class Zbor implements Comparable<Zbor>{
  126.     String zbor;
  127.  
  128.     public Zbor(String zbor) {
  129.         if(zbor.contains(".") || zbor.contains(",") || zbor.contains("!") || zbor.contains("?"))
  130.             zbor = zbor.substring(0, zbor.length() - 1);
  131.         this.zbor = zbor.toLowerCase();
  132.     }
  133.     @Override
  134.     public boolean equals(Object obj) {
  135.         Zbor pom = (Zbor) obj;
  136.         return this.zbor.equals(pom.zbor);
  137.     }
  138.     @Override
  139.     public int hashCode(){
  140.         return zbor.hashCode();
  141.     }
  142.  
  143.     public String toString() {
  144.         return zbor;
  145.     }
  146.     @Override
  147.     public int compareTo(Zbor arg0) {
  148.         return zbor.compareTo(arg0.zbor);
  149.     }
  150. }
  151.  
  152. class Speluvanje {
  153.  
  154.     public static boolean isPrime(int m){
  155.         for(int i = 2; i < Math.sqrt(m); i++)
  156.             if (m % i == 0)
  157.                 return false;
  158.         return true;
  159.     }
  160.  
  161.     public static int findM(int n){
  162.         int m = (int)(n / 0.6);
  163.         while (!isPrime(m))
  164.             m++;
  165.         return m;
  166.     }
  167.  
  168.     public static void main(String[] args) throws IOException {
  169.         OBHT<Zbor, String> tabela;
  170.         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  171.         int N = Integer.parseInt(br.readLine());
  172.         //---Vie odluchete za goleminata na hesh tabelata----
  173.         tabela = new OBHT<Zbor,String>(findM(N));
  174.         String zbor = "";
  175.  
  176.         for(int i = 0; i < N ; i++){
  177.             zbor = br.readLine();
  178.             tabela.insert(new Zbor(zbor), zbor);
  179.         }
  180.  
  181.  
  182.         /*
  183.         *
  184.         * Vashiot kod tuka....
  185.         *
  186.         */
  187.  
  188.         String [] text = br.readLine().split("\\s+");
  189.         br.close();
  190.  
  191.         if(text[0].equals(".")){
  192.             System.out.println("Bravo");
  193.             return;
  194.         }
  195.  
  196.         boolean bravo = true;
  197.         for(int i = 0; i < text.length; i++){
  198.             if(tabela.search(new Zbor(text[i])) < 0) {
  199.                 bravo = false;
  200.                 System.out.println(new Zbor(text[i].toString()));
  201.             }
  202.         }
  203.         if(bravo)
  204.             System.out.println("Bravo");
  205.     }
  206. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement