10 6
8
2 1
2 2
4 5
5 2
5 4
6 5
9 4
10 5

Ansver: 1366

Задача заставила подумать.
Как уже описано на форуме,  нужно научиться считать количество единиц, которые встречаются в числах от 1 до X и подбирать X бинарным поиском.

И вот мне этот подсчет долго не давался.

Итог такой.

Считать можно рекурсивно.
Для этого нужно воспользоваться тем,  что для чисел вида X=999...999 искомое количество единиц равно (log10(X)+1) *10^log10(X).
Этот факт я заметил эксперимнтально.

То есть я имею в виду
count_ones (99)=20
count_ones (999)=300
count_ones (9999)=4000
и так далее.

Отсюда и вытекает способ .

Вычисляем сначала для X с зануленными разрядами кроме самого главного,  затем прибавляем значение функции от X с зануленным главным разрядом .

Я приведу пример для небольшого числа.

Пусть X=666.

Тогда посчитаем отдельно для 0-99, умножим на 6,  прибавим к ответу; затем отдельно для 100-200, прибавим это к ответу , затем рекурсивно для 600-666 то есть просто для 0-66.

Можно считать,  что мы имеем ориентированный взвешенный граф,  у которого максимальная степень вершины равна трём .

Равна она трём потому,  что нам всегда выгодно ехать как можно дальше,  потому что мы заплатили за всю дистанцию.

То есть из какой-то станции ребра с весами C1,  C2 и C3 проводим в как можно более далёкие станции.

Тогда это получается очень сильно разреженный граф,  так как N<=1e4.

На этом графе запускаем алгоритм Дейкстры для разреженных графов.

Я использовал вариант за O(Nlog2N)  с std :: set.

Для расчёта того,  куда проводить ребра,  я использовал бинарный поиск.  И немного запорол реализацию этого поиска.

Мой поиск возвращал первую станцию, которая находится дальше,  чем разрешено.  И  возвращал  он некорректное значение,  если не было такой станции.

Это послужило причиной WA#6.

Причиной WA#2 послужило то,  что я забыл сделать обновление расстояния до пункта назначения.  Так как ребра идут жадно,  то пункт назначения проезжался и в очередь не попадал,  и расстояние соответственно никогда не обновлялось.

Does anyone know the 8th test?

Original code in your page:

string = input()
split_input = string.split()
lst = []
[lst.append(int(ndx) ** 0.5) for ndx in split_input]
[print("%.4f" % round(ndx, 4)) for ndx in lst[::-1]]

My tests in spyder:

Code:

with open('/tmp/123.txt', 'r') as f:
    string = f.read()

split_input = string.split()
lst = []
[lst.append(int(ndx) ** 0.5) for ndx in split_input]
[print("%.4f" % round(ndx, 4)) for ndx in lst[::-1]]

Answer:

runfile('/home/ant/.config/spyder-py3/temp.py', wdir='/home/ant/.config/spyder-py3')
2297.0716
936297014.1164
0.0000
37.7757

Edited by author 20.07.2017 03:14

Edited by author 20.07.2017 03:15

Is y<=x?

Рассчитывал я две величины.

(1) dp[i]  -- минимальное количество символов,  которое должен прочесть i-й человек для того,  чтобы узнать о землетрясении

(2) len[i]  -- минимальное количество символов, которое необходимо для того, чтобы ретвитнуть сообщение i-го человека.

WA#6 => check if you use module (1e9 + 9)

#include <stdio.h>

int main() {
  int a, b;

  scanf("%d %d", &a, &b);

  if (a % 2 == 0 || b % 2 != 0) {
    printf("YES");
  } else {
    printf("NO");
  }

  return 0;
}

Я написал на чистом Си и не мог ну никак пробиться через WA#4

Затем я переписал на Си++14 и получил AС

Видимо сложность Си и отсутствие привычных функций STD  меня отвлекают от сути задачи в какой-то мере

Я использовал для решения стратегию copy on write.
I have used copy on write strategy.

Когда я использовал scanf и printf,  я получал TLE#9.
When used scanf and prin
tf got TLE#9.

Когда заменил ввод на ввод через unlocked getchar и putchar,  то получил АС за менее чем  0.6 сек.
AC < 0.6 sec with _getchar_nolock and _putchar_nolock.

Ну и немного на русском про саму COW-стратегию.

Есть вектор реальных объектов клонов,  а есть вектор ссылок на эти объекты.

Новый объект в первом векторе создаётся не при клонировании,  а при попытке изменить реального клона,  на который есть больше одной ссылки.

Во втором же векторе новые объекты создаются, напротив,  только при клонировании.

import java.util.Scanner;


public class T2012 {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner sc=new Scanner(System.in);
        int f=sc.nextInt();
        int r=12-f;
        int time=r*45;
        if(time<=240)
            System.out.println("YES");
        else
            System.out.println("NO");

    }

}

[code deleted]

===
Return "Fail (checker)", why?

Edited by moderator 20.11.2019 00:01

Есть наверно несколько решений этой задачи.
Я использовал стек пар. first это было верхняя грань пары, second нижняя.
Как только я считал число, я посмотрел на первый элемент в стеке на его верхнюю грань, если она совпадала, то я понижал грань на -1, если в стеке еще и грани местами менялись то есть first<second, то удалял элемент.
Если же элемент который я считал был меньше чем верхняя грань первого элемента в стеке, то выводил фразу читер!!!!
Если стек оказывался пустым или элмент считывания оказывался больше чем верхняя грань первого элемента, то создавал новую пару и ее грани first присваивал считанное значение, а second присваивал значение h. h это число которое в начале было равно 1 а после добавления нового элемента в стек становилось считанное число +1. Оно менялось у меня только когда добавлял что-то.
Потом проверял если новый элемент стека верхняя и нижняя грань совпадает то удалял его, иначе понижал нверхнюю границу на -1.
Если в конце чтения стек становился пустым, то значит выводим фразу Not a proof.
К сожалению нельзя кидать код программ...
Но могу поделиться парой тестов:

5
3
2
5
4
1
Not a proof

5
3
5
2
4
1
Cheater

4
3
4
1
2
Cheater

Просто по длине слова определяем,  какой у нас случай.
(Замена,  удаление или вставка).

Затем для каждой позиции пытаемся внести изменения и смотрим,  получается у нас выполнение условия или нет.

Удобно завести массив постфиксных сумм для того чтобы быстро пересчитать сумму позиций единиц.

Так как сумма всех элементов последовательности равна (S+N),  то сумма всех элементов последовательности,  в которой каждый элемент уменьшен на единицу,  равна просто N.

Тогда если мы найдём в такой последовательности с уменьшенными членами отрезок с максимальной суммой и сравним сумму на нем с числом N,  то мы узнаем ответ на задачу.

А именно,  если эта сумма превосходит N,  то ответ "NO".
В противном случае, ответ "YES".

Отрезок с максимальной суммой ищется за O(n)  методом кумулятивных сумм.

All the test cases given in this forum are working.But giving WA 1

my code is:
#include <stdio.h>
#include <string.h>
 int len[910][8110];
 int dig[910][8110];
 int num[110];

 int main(){
  int t,s1,s2,k,pt,i,j,l,temp;
  memset(len,0,sizeof(len));
  for(i=1;i<=900;i++){
      for(j=1;j<=8100;j++){
          for(k=1;k<=9;k++){
              if((i-k)<0||(j-k*k)<0)
                  break;
              else if((i-k)==0&&(j-k*k)==0){
                  len[i][j] = 1;
                  dig[i][j] = k;
              }
              else if(len[i-k][j-k*k]>0){
                  if(len[i-k][j-k*k]+1<len[i][j]||len[i][j]==0){
                      len[i][j] = len[i-k][j-k*k]+1;
                      dig[i][j] = k;
                  }
              }
              else
                  continue;
          }
      }
  }
  scanf("%d",&t);
  while(t--){
  scanf("%d %d",&s1,&s2);
  pt = 0;
  if(len[s1][s2]==0||len[s1][s2]>100)
      printf("No Solution");
  else{
        i=s1;
        j=s2;
      while((len[i][j]>=1)&&i>=1&&j>=1){
          l = dig[i][j];
          num[pt++] = l;
          i = i-l;
          l = l*l;
          j-=l;
      }
      for(i=0;i<pt;i++){
        for(j=i+1;j<pt;j++){
            if(num[i]>num[j]){
             temp=num[i];
             num[i]=num[j];
             num[j] = temp;
            }
        }
      }
      for(i=0;i<pt;i++)
          printf("%d",num[i]);
  }
  printf("\n");
  }
  return 0;
 }

To read IP address /subnet mask
I recommend you to use the following template


unsigned int read_mask(){
    unsigned int a, b, c, d;
    scanf("%u.%u.%u.%u", &a, &b, &c, &d);
    return (a<<24) + (b<<16) + (c<<8) + d;
}

You can just sort edges in non-increasing order and add them sequentially until there are two or more connectivity components...

who knows the Test2 ??