Страница 1 из 1

Задача 1 (Интересная последовательность)

СообщениеДобавлено: 04 апр 2015, 10:24
Vladislav_133
Задача, действительно, простая. Меня просто заинтересовала такая последовательность. Последовательность я придумал сам, но, я думаю, что где-то она все равно упоминается. Оказалось, что она периодическая с периодом 6. Это позволяет, в случае оперирования большим количеством членов ускорить обработку. Но в нашем случае можно было бы и не заморачиваться существованием периода.

Re: Задача 1 (Интересная последовательность)

СообщениеДобавлено: 04 апр 2015, 12:14
Vladislav_133
Подсветка синтаксиса: [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка cpp
#include <stdio.h>
int main(){
    int d,j1,j2,n,a,s,m;
    if(scanf("%d",&j1)==EOF)return 0;
    if(scanf("%d",&j2)==EOF)return 0;
    if(scanf("%d",&n)==EOF)return 0;
    if(scanf("%d",&m)==EOF)return 0;
    if(m<=0||n<=0)return 0;    
    while(1){
        a=j1;
        if(((n%6)*6)==n)   break;
        n--; j1=j1-j2; j2=a;
    }
//summing
    a=2;
    if(m==1){
      printf("%d\n",j1);       
      return 0;    
    }
    s=j1+j2;
    while(1){
        if(a==m)break;
        d=j2-j1; j1=j2; j2=d;
        s=s+d; a++;
    }
    printf("%d\n",s);
    return 0;
}

 

Re: Задача 1 (Интересная последовательность)

СообщениеДобавлено: 04 апр 2015, 12:21
Vladislav_133
В программе, которую я привел, определение начальных значений последовательности осуществляется с учетом периодичности, а суммирование происходит по обычной схеме.

Re: Задача 1 (Интересная последовательность)

СообщениеДобавлено: 05 апр 2015, 00:35
hardcore_test
Мое решение было в лоб. Сначала нашли значение всех элементов до K, потом от K до Н
Код: Выделить всё
// задача №1 "интересная последовательность"

import java.util.Scanner;


public class zadaca1 {

   public static void main(String[] args) {
      Scanner sc=new Scanner(System.in);
      int a1=sc.nextInt();
      int a2=sc.nextInt();
      int k=sc.nextInt();
      int n=sc.nextInt();
      int d=0;
      if (n>k) d=n; //определяем, что больше
      else d=k;
      int mas[]=new int[d+2]; //берем размер с запасом
      mas[k]=a1;
         mas[k+1]=a2;
      if (k-1>=0){ // проверка, не равно ли к 0
         mas[k-1]=mas[k]-mas[k+1];
      }
      for (int i=k-1;i>0;i--){ // высчитываем значение от 0 до k
         mas[i-1]=mas[i]-mas[i+1];
      }
      for (int i=k+2;i<n;i++){ //высчитываем значение от k+2 до n
         mas[i]=mas[i-1]-mas[i-2];
      }
      int sum=0;
      for (int i=0;i<n;i++){
         sum+=mas[i];
      }
      System.out.println(sum);
      sc.close();
   }

}

Кому удобнее с подсветкой кода тык сюда

Re: Задача 1 (Интересная последовательность)

СообщениеДобавлено: 06 апр 2015, 11:21
xdsl
Можете пользоваться встроенной подсветкой на нашем сайте. Для этого достаточно вместо тега [code] использовать тег [java]. Нумерацию строк обеспечит атрибут lines=n, возможность загрузки файлов - атрибут file=имя_файла. Итого: [java lines=n file=1.java]. Результат будет примерно такой:

Подсветка синтаксиса: (1.java) [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка java
  1. // задача №1 "интересная последовательность"
  2.  
  3. import java.util.Scanner;
  4.  
  5.  
  6. public class zadaca1 {
  7.  
  8.         public static void main(String[] args) {
  9.                 Scanner sc=new Scanner(System.in);
  10.                 int a1=sc.nextInt();
  11.                 int a2=sc.nextInt();
  12.                 int k=sc.nextInt();
  13.                 int n=sc.nextInt();
  14.                 int d=0;
  15.                 if (n>k) d=n; //определяем, что больше
  16.                 else d=k;
  17.                 int mas[]=new int[d+2]; //берем размер с запасом
  18.                 mas[k]=a1;
  19.                         mas[k+1]=a2;
  20.                 if (k-1>=0){ // проверка, не равно ли к 0
  21.                         mas[k-1]=mas[k]-mas[k+1];
  22.                 }
  23.                 for (int i=k-1;i>0;i--){ // высчитываем значение от 0 до k
  24.                         mas[i-1]=mas[i]-mas[i+1];
  25.                 }
  26.                 for (int i=k+2;i<n;i++){ //высчитываем значение от k+2 до n
  27.                         mas[i]=mas[i-1]-mas[i-2];
  28.                 }
  29.                 int sum=0;
  30.                 for (int i=0;i<n;i++){
  31.                         sum+=mas[i];
  32.                 }
  33.                 System.out.println(sum);
  34.                 sc.close();
  35.         }
  36.  
  37. }
  38.  

Re: Задача 1 (Интересная последовательность)

СообщениеДобавлено: 08 апр 2015, 19:50
[DD]
Ну собственно вот мое решение первой задачи)
Подсветка синтаксиса: (1.php) [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка php
  1. <?php
  2. /**
  3. Сразу раскажу к каким выводам я пришел написав на листочке такую последовательность
  4. 1 4 3 -1 -4 -3 1 4 3 -1 -4 -3:
  5. 1. последовательность циклична. повторяются значения шестерками
  6. 2. значения во второй тройке идут такие же как и в первой, но с противоположным знаком
  7.  2.1 сумма каждых шести элементов последовательности ровняется нулю следовательно
  8.     число n как токовое не интересно, а интересен остаток от деления на 6.
  9.     Такая же ситуация с числом k
  10.  2.2 сумма двух чисел с индексами различющимися на 3 равна нулю следовательно
  11.     для вычисления суммы нужно знать только первые три элемента
  12. опираесь на эти выводы получил такое вот решение
  13. */
  14. $keys = [0,1,2,0,1,2];//мапинг индексов в массиве(нужно ведь заполнить только перве три)
  15. $sum_map = [[], [0], [0,1], [0,1,2], [1,2], [2]];//маппинг индексов участвующих в вычислени суммы
  16. $tmp = [];
  17. list($tmp[0], $tmp[1], $k, $n) = preg_split("/\s+/", file_get_contents("./input.txt"), NULL, PREG_SPLIT_NO_EMPTY);//считываем входящие данные
  18. $tmp[2] = $tmp[1] - $tmp[0];//вычисляем третий элемент последовательности
  19. $k %= 6;
  20. $n %= 6;
  21. $data = [];
  22. for($i = 0; $i <3; $i++){//заполняем массив
  23.     $key = ($k + $i) % 6;//получаем реальный индекс(от 0 до 5)
  24.     $idx = $keys[$key];//получаем индекс в результате(от 0 до 2)
  25.     /**
  26.         так как числа повторяются в тройках но с другим знаком - то при
  27.         заполнении если реальный индекс больше 2 записать нужно число с другим знаком
  28.     */
  29.     $data[$idx] = ($key > 2) ? -$tmp[$i]: $tmp[$i];
  30. }
  31. $s = 0;
  32. foreach($sum_map[$n] as $idx){//ну а тут просто считаем сумму
  33.     $s += $data[$idx];
  34. }
  35. file_put_contents("./output.txt", $s);

Re: Задача 1 (Интересная последовательность)

СообщениеДобавлено: 09 апр 2015, 09:21
[DD]
Владислав Юрьевич, в Вашем решении есть одна не точность. По условию задачи ни одно число не может превышать значение int32, но ни где не сказано, что их сумма не может его превышать.
для последовательности:
Код: Выделить всё
2147483646 2147483647 1

сумма первых двух или трех элементов вычисляется не корректно.

Re: Задача 1 (Интересная последовательность)

СообщениеДобавлено: 09 апр 2015, 13:14
Vladislav_133
Конечно, Дмитрий, теоретически, такая ситуация возможна.
Но такие уточнения, в принципе, можно делать и по другим задачам. Например, про квадраты.
Просто строить логически полные формулировки не имеет особого смысла, хотя и хочется иногда.
Обычно такие уточнения делают, когда это входит в смысл задания.
С другой стороны, на некоторых олимпиадах, такая вот формулировка могла бы как раз и означать,
что сумма может превышать указанные пределы.