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

Правила проведения олимпиады, условия задач и комментарии к ним, результаты олимпиады и апелляции.
Руководители: к.ф-м.н., профессор Пирогов Владислав Юрьевич, ник - Vladislav_133; к.п.н, доцент Слинкин Дмитрий Анатольевич, ник - xdsl

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

Сообщение Vladislav_133 04 апр 2015, 10:24

Задача, действительно, простая. Меня просто заинтересовала такая последовательность. Последовательность я придумал сам, но, я думаю, что где-то она все равно упоминается. Оказалось, что она периодическая с периодом 6. Это позволяет, в случае оперирования большим количеством членов ускорить обработку. Но в нашем случае можно было бы и не заморачиваться существованием периода.
Последний раз редактировалось Vladislav_133 04 апр 2015, 12:22, всего редактировалось 2 раз(а).
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

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

Сообщение Vladislav_133 04 апр 2015, 12:14

Подсветка синтаксиса: [ Загрузить ] [ Скрыть ]
Подсветка синтаксиса языка 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;
}

 
Последний раз редактировалось Vladislav_133 04 апр 2015, 18:29, всего редактировалось 3 раз(а).
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

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

Сообщение Vladislav_133 04 апр 2015, 12:21

В программе, которую я привел, определение начальных значений последовательности осуществляется с учетом периодичности, а суммирование происходит по обычной схеме.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.

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

Сообщение hardcore_test 05 апр 2015, 00:35

Мое решение было в лоб. Сначала нашли значение всех элементов до 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();
   }

}

Кому удобнее с подсветкой кода тык сюда
hardcore_test
 
Сообщения: 102
Зарегистрирован: 06 мар 2015, 16:10
Полное имя: Владислав Андреевич Быков

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

Сообщение xdsl 06 апр 2015, 11:21

Можете пользоваться встроенной подсветкой на нашем сайте. Для этого достаточно вместо тега [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.  
xdsl
 
Сообщения: 1236
Зарегистрирован: 09 дек 2008, 05:16
Откуда: ВЦ ШГПИ
Полное имя: Слинкин Д.А.

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

Сообщение [DD] 08 апр 2015, 19:50

Ну собственно вот мое решение первой задачи)
Подсветка синтаксиса: (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);
мы рождены чтоб сказку сделать кодом
[DD]
Elite
 
Сообщения: 163
Зарегистрирован: 18 мар 2009, 22:18
Откуда: from HELL
Полное имя: Зыков Д.А.

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

Сообщение [DD] 09 апр 2015, 09:21

Владислав Юрьевич, в Вашем решении есть одна не точность. По условию задачи ни одно число не может превышать значение int32, но ни где не сказано, что их сумма не может его превышать.
для последовательности:
Код: Выделить всё
2147483646 2147483647 1

сумма первых двух или трех элементов вычисляется не корректно.
мы рождены чтоб сказку сделать кодом
[DD]
Elite
 
Сообщения: 163
Зарегистрирован: 18 мар 2009, 22:18
Откуда: from HELL
Полное имя: Зыков Д.А.

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

Сообщение Vladislav_133 09 апр 2015, 13:14

Конечно, Дмитрий, теоретически, такая ситуация возможна.
Но такие уточнения, в принципе, можно делать и по другим задачам. Например, про квадраты.
Просто строить логически полные формулировки не имеет особого смысла, хотя и хочется иногда.
Обычно такие уточнения делают, когда это входит в смысл задания.
С другой стороны, на некоторых олимпиадах, такая вот формулировка могла бы как раз и означать,
что сумма может превышать указанные пределы.
Аватара пользователя
Vladislav_133
Elite
 
Сообщения: 1386
Зарегистрирован: 13 дек 2008, 18:08
Полное имя: П.В.Ю.


Вернуться в Олимпиада по программированию

Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 1

cron