Stran 1 od 1

Prepogosto

Objavljeno: Če Jun 08, 2017 1:42 pm
Napisal/-a lukazlatecan
Podan imamo seznam N števil, v katerem se nekatera števila pojavijo večkrat. Obdržali bi radi samo zadnjih K pojavitev (gledano od leve proti desni) istega števila, ostale pa želimo izbrisati. Napisati morate program, ki bo učinkovito izračunal, kakšen je novonastali seznam.

Naloga
Začetni seznam je zelo dolg, zato je podan v obliki generatorja seznama. Podani sta prvo in drugo število v seznamu (tj. števili [math]) ter pravilo za izračun naslednjih členov seznama: [math].

Napišite program, ki se bo znebil prepogostih števil in izpisal preostanek seznama od mest A do B.

Opozorila:
Bodite pozorni na količino (razpoložljivega) pomnilnika!

Omejitve
Čas: 10 s
Spomin: 512 MB


Vhodni podatki
V prvi vrstici se nahajata celi števili N in K. V drugi vrstici so podani parametri za generiranje seznama: [math] X, Y in M. Tretja vrstica pa vsebuje števili A in B, ki definirata izpis.

Omejitve vhodnih podatkov
1≤N≤70000000
1≤K,M≤1000000
0≤[math]<M
1≤A≤B
V seznamu bo ostalo najmanj B števil.
0≤B−A≤100

Izhodni podatki
Izpišite s presledki ločena števila, ki se v končnem seznamu nahajajo od mesta A do B.

Primer vhoda

Koda: Izberi vse

20 2
6 1 4 7 13
2 6


Pripadajoč izhod

Koda: Izberi vse

0 7 7 11 1


Komentar
Seznam števil opisan v testnem primeru je [6, 1, 5, 0, 7, 10, 7, 11, 1, 12, 10, 1, 8, 8, 10, 11, 0, 5, 9, 5]. Če obdržimo samo zadnje prepogoste pojavitve števil, dobimo seznam [6, 0, 7, 7, 11, 1, 12, 10, 1, 8, 8, 10, 11, 0, 5, 9, 5]. Ko izpišemo elemente od 2. do 6. mesta, dobimo iskan rezultat.

Re: Prepogosto

Objavljeno: Ne Jun 25, 2017 11:35 am
Napisal/-a hinkopihpih

Koda: Izberi vse

import java.util.*;
import java.io.*;

public class Prepogosto
{
   public static void main(String[]args)
   {
      Scanner skan;
      File vhod;

      try
      {
         vhod = new File("prepogosto.txt");
         skan = new Scanner(vhod);
      }
      catch(FileNotFoundException e)
      {
         skan = new Scanner(System.in);
      }

      int n = skan.nextInt();
      int k = skan.nextInt();
      int s2 = skan.nextInt();
      int s1 = skan.nextInt();
      int x = skan.nextInt();
      int y = skan.nextInt();
      int m = skan.nextInt();
      int a = skan.nextInt();
      int b = skan.nextInt();

      for(int i = 0; i < n - 2; i++)
      {
         int temp = s1;
         s1 = function1(s1,s2,x,y,m);
         s2 = temp;
      }

      int[] repeated = new int[m];
      repeated[s1]++;
      repeated[s2]++;
      List<Integer> sequence = new ArrayList<Integer>();

      if(s1 == s2 && k == 1)
      {
         sequence.add(s1);
      }   
      else
      {
         sequence.add(s1);
         sequence.add(s2);
      }   

      for(int i = 0; i < n - 2; i++)
      {
         int temp = s2;
         s2 = function2(s1,s2,x,y,m);
         s1 = temp;

         if(s2 < 0)
         {
            s2 += m;
         }   

         repeated[s2]++;

         if(repeated[s2] <= k)
         {
            sequence.add(s2);
         }   
      }

      for(int i = sequence.size() - a; i >= sequence.size() - b; i--)
      {
         System.out.print(sequence.get(i) + " ");
      }   
   }
   public static int function1(int s1, int s2, int x, int y, int m)
   {
      return (s2 * x + s1 * y) % m;
   }
   public static int function2(int s1, int s2, int x, int y, int m)
   {
      return ((int)(Math.pow(x,euler(m) - 1)) * (s1 - s2 * y)) % m;
   }
   public static int euler(int m)
   {
      int result = 0;

      for(int i = 1; i < m; i++)
      {
         if(gcd(i,m) == 1)
         {
            result++;
         }   
      }

      return result;
   }
   public static int gcd(int a, int b)
   {   
       while(b != 0)
       {   
             int temp = b;
             b = a % b;
             a = temp;
       }   

       return a;
    }
}