341 Востаннє редагувалося lucas-kane (21.04.2022 02:27:18)

Re: Цікаві задачі

koala написав:

Ви хотіли сказати "менший серед двох найбільших"? Бо максимальний може бути лише один. Якщо мова не про локальні максимуми.
Усе одно не зовсім розумію вашу ідею. Я б розв'язував так.
1. Обираємо дві крайні перетинки, обчислюємо, скільки там можна води налити.
2. В циклі:
2.1. Беремо нижчу з двох обраних, шукаємо першу вищу за неї (з початку - праворуч, з кінця - ліворуч). Якщо обидві однакові - шукаємо нові замість обох. Якщо немає куди далі шукати - завершуємо цикл.
2.2. Перевіряємо, скільки води тепер можна налити. Якщо більше - запам'ятовуємо.

Мушу визнати, ваш алгоритм кращий

Прихований текст
#include <stdio.h>
#include <stdlib.h>

#define MIN(x, y) (((x) < (y)) ? (x) : (y))

int main()
{
    int a[] = {2, 3, 7, 1, 2, 5, 6, 4}, t, area;

    size_t l, left = 0;
    size_t r, right = ((sizeof a / sizeof *a) - 1);

    area = MIN(a[left], a[right]) * (right - left);

    (a[left] < a[right])
        ? left++
        : right--;

    while (left <= right)
    {
        t = MIN(a[left], a[right]) * (right - left);

        if (t > area)
            area = t, l = left, r = right;

        (a[left] < a[right])
            ? left++
            : right--;
    }

    printf("a[%zu] = %d\n"
           "a[%zu] = %d\n"
           "Area = %d\n",
           l, a[l], r, a[r], area);

    return 0;
}

342 Востаннє редагувалося FakiNyan (21.04.2022 19:25:39)

Re: Цікаві задачі

Завдання таке дивне було.
Кажуть, уявіть собі 32-бітне число зі знаком. І нам треба його відзеркалити, тобто, 132 стає 231, а -1234 стає -4321. При цьому, кажуть, якшо отримане число більше 32-біт, то повернути 0.
А я ж веб-макакій, то й зробив по-своєму.

Прихований текст
function reverse(x: number): number {
  const abs = Math.abs(x);
  const sign = Math.sign(x);
  const rev = Number(abs.toString().split('').reverse().join(''));
  return rev > Math.pow(2, 31) - 1 ? 0 : sign * rev;
};

343

Re: Цікаві задачі

Ненавиджу задачі такого типу, бо завжди плутаюсь з індексами, навіть якщо загальна ідея розв'язку правильна...

Задача

Знайти довжину максимального послідовного набору унікальних значень в рядку.
Ось асерція, аби було ясно, який аргумент який результат має давати.

assert.equal(3, lengthOfLongestSubstring('123'), `123 must be of length 3`);
assert.equal(2, lengthOfLongestSubstring('12'), `12 must be of length 2`);
assert.equal(1, lengthOfLongestSubstring('11'), `11 must be of length 1`);
assert.equal(4, lengthOfLongestSubstring('1234'), `1234 must be of length 4`);
assert.equal(3, lengthOfLongestSubstring('1134'), `1134 must be of length 3`);
assert.equal(
  7,
  lengthOfLongestSubstring('11345123456712312222'),
  `11345123456712312222 must be of length 7`
);

344

Re: Цікаві задачі

Про розв'язок напишу тепер. Я вам відразу скажу, шо курс по алгоритмам і структурам даних, який я проходив пів року тому - не минув дарма, бо я відразу зрозумів, шо нам треба два курсора, один завжди був би поперед іншого.

Ідея в тім, шо у нас є геш таблиця, котрі тримає інфу про індекси символів. Також у нас є два оці курсори. Перший на 0 індексі, другий на 1.
І далі ми перевіряємо - якшо символ під правим курсором вже є в таблиці, і його індекс більший за лівий курсор - це означає, шо ми натрапили на дублікат символу, і все, шо є між попереднім значенням правого курсора і лівим курсором - унікальний рядок, в котрому символи не повторюються.
Коли ми натрапляємо на такий дубль, то нам тре зберегти довжину того унікального підрядка. Ну а потім ми збільшуємо правий курсор на 1, а лівий встановлюємо в (попередній індекс символу, котрий зустріли + 1) і перевіряємо то все заново. І ще треба не забувати заносити в геш таблицю індекси тих символів, котрі зустрічаємо.

Нехай у нас є такий рядок

123145

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

Далі у нас лівий курсор так само на 1, а правий вже на 3. Ми не бачимо 3 в таблиці, тому рухаємось далі, і заносимо інфу про цей символ в таблицю.

Тепер у нас лівий курсор на 1, а правий на 1. Ми дивимось в таблицю, і бачимо, шо ми вже зустрічали 1 під індексом 0, і наш лівий курсор як раз на нього вказує. Це означає, шо нам тепер тре відняти індекс правого курсора (3) від індексу лівого курсора (0), і нас виходе 3 - це довжина підрядка, в якому символи не повторюються.

Тепер ми рухаємо лівий курсор на (останній індекс дубльованого символу + 1, тобто 0 + 1 = 1)=, а правий курсор просто інкрементуємо.

Тепер лівий курсор на 2, а правий на 4. 4 ще не було в таблиці, тому заносимо його, і рухаємось далі.

Тепер лівий курсор так само на 2, а правий на 5. 5 так само новеньке для нас.

Тепер правий курсор дійшов кінця рядка, і ми беремо його індекс (5) і віднімаємо від нього індекс лівого курсора (1) і виходе 4. Але це не дуже правильно, бо насправді довжина підрядка - 5, а не 4. І оце проблєма індексів, яку я постійно маю. Воно працює добре для того, що йде всередині рядка, але коли ми доходимо до кінця, то одинички не вистачає, тому цей випадок я окремо обробляю, в кінці.

function lengthOfLongestSubstring(s: string): number {
  let left = 0,
    right = 1;
  const table = new Map<string, number>();
  table.set(s[left], left);
  
  let max = 0;
  while (right < s.length) {
    const check = s[right];
    if (table.has(s[right]) && table.get(s[right]) >= left) {
      max = Math.max(max, right - left);
      left = table.get(s[right]) + 1;
    }
    table.set(s[right], right);
    right++;
  }

  max = Math.max(max, s.length - left);

  return max;
}

345

Re: Цікаві задачі

Вирішив ризикнути і спробувати вирішити задачку, котра є ніби важкою, і має позначку Hard. До цього вирішував лише легкі та середні.
Завдання просте.
Нехай у нас є два відсортованих масиви, нам треба знайти медіану масиву, котрий виходе, якшо ми зіллємо ті два масиви.

Якшо є
[1,3] та [2], то результат має бути 2, бо злитий масив буде [1,2,3];
якщо є
[1,3] та [2,4], то результат має бути 2.5, бо злитий масив буде [1,2 ,3 ,4], і тут немає чіткого середнього значення, бо у нас парна кількість елементів, тому ми додаємо два середні, і множимо на їх на два, а це (2+3) / 2 = 2.5.

Я цю задачку досить швидко вирішив, при цьому навіть не використовував вбудовані функції, котрі дозволяють злити два масиви, а потім відсортувати.

Прихований текст
function findMedianSortedArrays(nums1: number[], nums2: number[]): number {
    let i1 = 0, i2 = 0, curr = 0;
    const lookingFor = Math.floor((nums1.length + nums2.length) / 2);
    let prev=0, last=0;
    
    while (curr < lookingFor+1) {
        const num1 = nums1[i1];
        const num2 = nums2[i2];
        
         prev=last;

        if (num1 > num2) {
            i2++;
            last=num2;
        } else if (num2 > num1) {
            i1++;
            last=num1;
        } else if (num1 !== undefined) {
            i1++;
            last=num1;
        } else if (num2 !== undefined) {
            i2++;
            last=num2;
        } else {
            break;
        }
        curr++;
    }
        
    if ((nums1.length + nums2.length) % 2  === 0) {
        return (prev+last)/2;
    }
    return last;
};

Але навіть так в мене все вийшло досить швидко. Не розумію, чого ця задачка вважається Hard ?  *SCRATCH*

346

Re: Цікаві задачі

По діленню двох чисел без використання множення, ділення і ділення по модулю - все виявилось складніше, ніж я думав.
У мене відразу зв'явився простий алгоритм - в циклі віднімаємо від діленого дільник, і рахуємо кількість таких віднімань. Але якшо у нас буде 2147483647, що ділиться на 1, то це ж буде 2147483647 операцій в циклі.  :D   І воно не пропускає по часу.

Я довго кулупався з рішеннями, котрі самі користувачі пропонували, і через те, шо один і той самий алгоритм кожна людина може написати по-своєму, мені було складнувато допетрати, шо той код робе, але зрештою я зрозумів ідею ділення кутом, і написав код по-своєму.

function divide (dividend, divisor) {  
  const max = Math.pow(2, 31) - 1;
  const min = -Math.pow(2, 31);
  
  const dividendAbs = Math.abs(dividend);
  const divisorAbs = Math.abs(divisor);
  const dividendStr = dividendAbs.toString();
  const divisorStr = divisorAbs.toString();
  let result = [];
  let rest = 0;
     const divisorLength = divisorStr.length;
  
  for (let i = 0; i <= dividendStr.length-1; i+=divisorLength) {
      rest = Number(rest + dividendStr.slice(i, i+divisorLength));
    let multiplier = 0;

    if (rest >= divisorAbs) {
        while (rest >= divisorAbs) {
          multiplier++;
        rest -= divisorAbs;
      }
    }
    
    result.push(multiplier)
  }
  let signedResult = Number(result.join(''));
  if (dividend < 0) signedResult = -signedResult;
  if (divisor < 0) signedResult = -signedResult;
  return signedResult > max ? max : signedResult < min ? min : signedResult;
}

Ще є варіант з бітовим зсувом, але це я ще не написав, як напишу, то напишу.

347

Re: Цікаві задачі

Кілька день розбирався, як то зробити за допомогою бітового зсуву

function divide(dividend, divisor) {
  const max = Math.pow(2, 31) - 1;
  const min = -Math.pow(2, 31);
  const absDividend = Math.abs(dividend),
    absDivisor = Math.abs(divisor);
  let offset = 0;
  let tempDividend = absDividend;
  let sum = 0;
  let multiplier = 0;

  while (sum < absDividend && absDivisor <= tempDividend) {
    offset = 0;
    let offsetCalculated = absDivisor << (offset + 1);
    if (offsetCalculated <= tempDividend && offsetCalculated > 0) {
      while (offsetCalculated <= tempDividend && offsetCalculated > 0) {
        offset++;
        offsetCalculated = absDivisor << (offset + 1);
      }
      multiplier += 2 << (offset - 1);
      sum += absDivisor << offset;
      tempDividend = absDividend - sum;
    } else if (absDivisor << offset <= tempDividend) {
      sum += Math.abs(absDivisor << offset);
      multiplier += 1;
      tempDividend = absDividend - sum;
    }
  }

  const signedResult = Math.sign(dividend) * Math.sign(divisor) * multiplier;
  return signedResult > max ? max : signedResult < min ? min : signedResult;
}

Виявилось, шо той зсув робе з 32-бітними числами, і мона отримати -2147483648, якшо зробити 2147483648 << 0.

348 Востаннє редагувалося koala (22.07.2022 13:04:00)

Re: Цікаві задачі

Чорт. Мене спіймали минулого разу. Ось така задача.
Від числа n (10<=n<10000) віднімають суму його цифр. Якщо результат став від 1 до 100, беремо відповідь з масива і повертаємо, якщо ні - результат - наше нове n, повторюємо процедуру.

Масив

1-kiwi
2-pear
3-kiwi
4-banana
5-melon
6-banana
7-melon
8-pineapple
9-apple
10-pineapple
11-cucumber
12-pineapple
13-cucumber
14-orange
15-grape
16-orange
17-grape
18-apple
19-grape
20-cherry
21-pear
22-cherry
23-pear
24-kiwi
25-banana
26-kiwi
27-apple
28-melon
29-banana
30-melon
31-pineapple
32-melon
33-pineapple
34-cucumber
35-orange
36-apple
37-orange
38-grape
39-orange
40-grape
41-cherry
42-pear
43-cherry
44-pear
45-apple
46-pear
47-kiwi
48-banana
49-kiwi
50-banana
51-melon
52-pineapple
53-melon
54-apple
55-cucumber
56-pineapple
57-cucumber
58-orange
59-cucumber
60-orange
61-grape
62-cherry
63-apple
64-cherry
65-pear
66-cherry
67-pear
68-kiwi
69-pear
70-kiwi
71-banana
72-apple
73-banana
74-melon
75-pineapple
76-melon
77-pineapple
78-cucumber
79-pineapple
80-cucumber
81-apple
82-grape
83-orange
84-grape
85-cherry
86-grape
87-cherry
88-pear
89-cherry
90-apple
91-kiwi
92-banana
93-kiwi
94-banana
95-melon
96-banana
97-melon
98-pineapple
99-apple
100-pineapple

Особливе попередження: треба подумати перед кодуванням.

349

Re: Цікаві задачі

koala написав:

Чорт. Мене спіймали минулого разу. Ось така задача.
Від числа n (10<=n<10000) віднімають суму його цифр. Якщо результат став від 1 до 100, беремо відповідь з масива і повертаємо, якщо ні - результат - наше нове n, повторюємо процедуру.

Масив

1-kiwi
2-pear
3-kiwi
4-banana
5-melon
6-banana
7-melon
8-pineapple
9-apple
10-pineapple
11-cucumber
12-pineapple
13-cucumber
14-orange
15-grape
16-orange
17-grape
18-apple
19-grape
20-cherry
21-pear
22-cherry
23-pear
24-kiwi
25-banana
26-kiwi
27-apple
28-melon
29-banana
30-melon
31-pineapple
32-melon
33-pineapple
34-cucumber
35-orange
36-apple
37-orange
38-grape
39-orange
40-grape
41-cherry
42-pear
43-cherry
44-pear
45-apple
46-pear
47-kiwi
48-banana
49-kiwi
50-banana
51-melon
52-pineapple
53-melon
54-apple
55-cucumber
56-pineapple
57-cucumber
58-orange
59-cucumber
60-orange
61-grape
62-cherry
63-apple
64-cherry
65-pear
66-cherry
67-pear
68-kiwi
69-pear
70-kiwi
71-banana
72-apple
73-banana
74-melon
75-pineapple
76-melon
77-pineapple
78-cucumber
79-pineapple
80-cucumber
81-apple
82-grape
83-orange
84-grape
85-cherry
86-grape
87-cherry
88-pear
89-cherry
90-apple
91-kiwi
92-banana
93-kiwi
94-banana
95-melon
96-banana
97-melon
98-pineapple
99-apple
100-pineapple

Особливе попередження: треба подумати перед кодуванням.

Думав, що не так, виходить 1, а треба повернути не kiwi, а apple.

Тоді я просто зробив отак:

public class Kata {
  public static String subtractSum (int n) {
    return "apple";
  }
}

Так собі ката, як на мене. Я люблю задачки на codewars і там траплялися набагато цікавіші.

350

Re: Цікаві задачі

Просто минулого разу я її на пайтоні писав і мені було влом думати.
А на C вже доводиться.

351

Re: Цікаві задачі

Оригінальне завдання — створити інтерпретатор Assembler'а.

Ланка

Я ще не брався, залишу тут для себе майбутнього і для зацікавленої публіки.

Подякували: leofun011

352

Re: Цікаві задачі

Там немає нічого складного, просто порядково розбираєте команди.

353

Re: Цікаві задачі

koala написав:

складного

тема написав:

Цікаві задачі

354 Востаннє редагувалося koala (11.11.2022 12:10:12)

Re: Цікаві задачі

Python
def get_value(arg, registers):
    try:
        return int(arg)
    except ValueError:
        return registers[arg]

def simple_assembler(program):
    registers = {}
    ip = 0
    while 0<=ip<len(program):
        parts = program[ip].split()
        if parts[0]=="inc":
            registers[parts[1]] += 1
        elif parts[0]=="dec":
            registers[parts[1]] -= 1
        elif parts[0]=="mov":
            registers[parts[1]] = get_value(parts[2], registers)
        elif parts[0]=="jnz":
            if get_value(parts[1], registers)!=0:
                ip += get_value(parts[2], registers)
                continue
        else:
            raise ValueError("Wrong instruction: " + program[ip])
        ip += 1
    return registers

Проглянув інші рішення - є ж талановиті люди...

Подякували: leofun011

355

Re: Цікаві задачі

Rust
use std::collections::HashMap;

fn value(registers:&HashMap<String, i64>, s: &str) -> i64 {
    registers.get(s)
             .copied()
             .unwrap_or_else(||s.parse().unwrap())
}

fn simple_assembler(program: Vec<&str>) -> HashMap<String, i64> {   
    let mut registers = HashMap::new();
    let mut ip = 0i64;
    
    while ip < program.len() as i64 {
        let mut instruction = program[ip as usize].split_whitespace();
        match instruction.next().unwrap() {
            "mov" => {
                registers.insert(instruction.next().unwrap().to_string(), value(&registers, instruction.next().unwrap()));
            },
            "inc" => {
                *registers.get_mut(instruction.next().unwrap()).unwrap() += 1;
            },
            "dec" => {
                *registers.get_mut(instruction.next().unwrap()).unwrap() -= 1;
            },
            "jnz" => if value(&registers, instruction.next().unwrap())!=0 {
                ip += value(&registers, instruction.next().unwrap());
                continue;
            },
            _ => panic!("Wrong instruction {}", program[ip as usize]),
        }
        ip += 1;
    }
    
    registers
}
Подякували: leofun011

356

Re: Цікаві задачі

Довго промучився, пробуючи рекурсію як за каноном у Scala, проте на «складних програмах» воно сипалося. І ніяк не придумав, де втулити хвостову рекурсію з теґом @tailrec.

Прихований текст
object SimpleAssembler {
  def interpret(program: List[String]): Map[String, Int] = {
    val result = new HashMap[String, Int]

    def loop(list: List[String]): Unit = breakable {
      for (command <- list) {
        val args = command.split(' ')
        args(0) match {
          case "mov" => 
            result.put(args(1), result.get(args(2)).getOrElse(args(2).toInt))
          case "inc" => 
            result.put(args(1), result.get(args(1)).get + 1)
          case "dec" => 
            result.put(args(1), result.get(args(1)).get - 1)
          case "jnz" =>
            val switcher = 
                result.get(args(2)).getOrElse(args(2).toInt)
            if (result.get(args(1)).getOrElse(args(1).toInt) != 0) {
              val startPosition = program.indexOf(command) + switcher
              loop(program.slice(startPosition, program.length))
              break()
            }
        }
      }
    }
    loop(program)
    result.toMap
  }
}

Зрештою закинув до готових цей процедурний стандарт як у koala:

Прихований текст
object SimpleAssembler {
  def interpret(program: List[String]): Map[String, Int] = {
    val result = new HashMap[String, Int]
    var iter = 0
    

    while (iter < program.length) {
      breakable {
        val args = program(iter).split(' ')
        args(0) match {
          case "mov" => 
            result.put(args(1), result.get(args(2)).getOrElse(args(2).toInt))
          case "inc" => 
            result.put(args(1), result.get(args(1)).get + 1)
          case "dec" => 
            result.put(args(1), result.get(args(1)).get - 1)
          case "jnz" =>
            val switcher = 
                result.get(args(2)).getOrElse(args(2).toInt)
            if (result.get(args(1)).getOrElse(args(1).toInt) != 0) {
              iter = iter + switcher
              break()
            }
        }
        iter = iter + 1
      }
    }
    result.toMap
  }
}

Відтак мені відкрилися рішення інших людей, котрі знають Скалу і ФП ліпше за мене і хвостову ресурсію звісно ж реалізували — є чого повчитися.

357

Re: Цікаві задачі

Що ж, рекурсію мені таки втулити вдалося, навіть @tailrec не знадобився.

Прихований текст
object SimpleAssembler {
  def interpret(program: List[String]): Map[String, Int] = {
    val getNumericValue = (
      hashMap: HashMap[String, Int], 
      value: String
    ) => 
      hashMap.get(value).getOrElse(value.toInt)
    
    def loop(list: List[String], currentIndex: Int, result: HashMap[String, Int]): Map[String, Int] = {
      if (currentIndex >= list.length) result.toMap
      else {
        val args = list(currentIndex).split(' ')
        val switcher: Int = args(0) match {
          case "mov" =>
            result.put(args(1), getNumericValue(result, args(2)))
            1
          case "inc" =>
            result.put(args(1), result.get(args(1)).get + 1)
            1
          case "dec" =>
            result.put(args(1), result.get(args(1)).get - 1)
            1
          case "jnz" =>
            if (getNumericValue(result, args(1)) != 0) {
              getNumericValue(result, args(2))
            } else {
              1
            }
        }
        loop(program, currentIndex + switcher, result)
      }
    }
    loop(program, 0, new HashMap[String, Int])
  }
}

358

Re: Цікаві задачі

Ок, можна ще так, щоб зовсім без зайвини. І на цьому мої ідеї сьодні вичерпались.

Прихований текст
object SimpleAssembler {
  def interpret(program: List[String], 
                currentIndex: Int = 0, 
                result: HashMap[String, Int] = new HashMap[String, Int]
                ): Map[String, Int] = {
    if (currentIndex >= program.length) result.toMap
    else {
      lazy val getNumericValue = (
        hashMap: HashMap[String, Int], 
        value: String
      ) => 
        hashMap.get(value).getOrElse(value.toInt)
      val args = program(currentIndex).split(' ')
      val switcher: Int = args(0) match {
        case "mov" =>
          result.put(args(1), getNumericValue(result, args(2)))
          1
        case "inc" =>
          result.put(args(1), result.get(args(1)).get + 1)
          1
        case "dec" =>
          result.put(args(1), result.get(args(1)).get - 1)
          1
        case "jnz" =>
          if (getNumericValue(result, args(1)) != 0) {
            getNumericValue(result, args(2))
          } else {
            1
          }
      }
      interpret(program, currentIndex + switcher, result)
    }
  }
}
Подякували: koala1

359 Востаннє редагувалося leofun01 (19.02.2023 22:58:07)

Re: Цікаві задачі

Завершилося змаганя в Алґотестер, а я все ще не маю рішеня, яке би проходило всі тести для задачі E (pdf).

Дано: n, a[k] (k=1..n)
, де a[k] - кількість інверсій префікса довжиною k.
Знайти: p[k] - перестановку, для якої всі префікси мають задану кількість інверсій (a[k]).

Приклад даних
stdin написав:

5
0 1 2 4 7

stdout написав:

5 1 4 3 2

Всі мої ідеї виявились до сраки. Може ви знаєте як рішати подібні задачі ?

360

Re: Цікаві задачі

leofun01 написав:
Прихований текст

Завершилося змаганя в Алґотестер, а я все ще не маю рішеня, яке би проходило всі тести для задачі E (pdf).

Дано: n, a[k] (k=1..n)
, де a[k] - кількість інверсій префікса довжиною k.
Знайти: p[k] - перестановку, для якої всі префікси мають задану кількість інверсій (a[k]).

Приклад даних
stdin написав:

5
0 1 2 4 7

stdout написав:

5 1 4 3 2

Всі мої ідеї виявились до сраки. Може ви знаєте як рішати подібні задачі ?

Цей алгоритм?

Подякували: leofun011