1 Востаннє редагувалося Q-bart (11.12.2014 21:22:30)

Тема: Задача на паскалі

Доброго вечора!
В мене виникли проблеми з рішенням такої задачки

Задача

Мале Бісеня любить гострити зуби. А Зла Тітонька любить до
нього підходити і питатися: «Що, зуби гостриш?». Бісеняті таке не
дуже подобається, тому воно придумало робити наступне.
У Малого Бісеняти є N зубів. Кожен зуб має коефіцієнт
загостреності Ai. Також існує межа загостреності K. Якщо коефіцієнт
загостреності певного зуба є більшим чи рівним межі загостреності,
то такий зуб вважається загостреним.
Мале Бісеня хоче наступного разу, коли Зла Тітонька його щось
запитає, показати їй якнайбільше загострених зубів, що йдуть
підряд.
Допоможіть Малому Бісеняті дізнатися, скільки найбільше зубів
він зможе показати.

Пробував написати таке

код
program zad2;

var
  a: array [1..10000] of integer;
  b: array [1..10000] of integer;
  c: array [1..10000] of integer;
  z, j, y, i, n, k: integer;

begin
  readln(n, k);
  
  for i := 1 to n do
  begin
    read(a[i]);
    if a[i] >= k then b[i] := 1 else b[i] := 2;
  end; {До цих пір все гаразд}
  
  for i := 1 to n do 
  begin
    for j := i + 1 to n - i do 
      if i = j then c[i] := c[i] + 1
      else break;
  end;
  
  for z := 1 to n do 
    writeln(c[i]);
end.

До коментаря я шукаю який зуб загострений(позначаю 1) а який не загострений(позначаю 2).
Після коментаря я пробував записати к-сть загострених зубів підряд в масив C.
А потім вже знайти макс. значення в масиві C.
Помилки не вибиває але не рахує...
В чому проблема???

2

Re: Задача на паскалі

Надмір рухів. Вам треба знайти максимум з множини ланцюжків загострених зубів. Ну так і треба:

for i:=1 to n do begin
  read(a);
  if a > k then //якщо зуб нагострений
    len := len + 1;//довжина ланцюжка збільшується
  else
    len := 0; //інакше занулюється
  if len > lenmax then
    lenmax := len;
end;

Решту самостійно.

Подякували: Q-bart1

3

Re: Задача на паскалі

Цей код я так розумію рахує так:
якщо перший зуб загострений, то довжину збільшуємо,
якщо наступний зуб теж загострений то знову збільшуємо...
а якщо наступний зуб незагострений, то довжина анульовується..
Тобто, якщо буде так ˄∩˄˄˄∩˄ то вийде
довжина присв. 1, потім анульовується, потім присв. 3, потім анульовується, і потім знову присв. 1 Так???
І в мене виходить результат 1, а мені треба 3...

4

Re: Задача на паскалі

Q-bart, ви приймали участь у міській олімпіаді з програмування цього року?

5

Re: Задача на паскалі

Q-bart написав:

Цей код я так розумію рахує так:
якщо перший зуб загострений, то довжину збільшуємо,
якщо наступний зуб теж загострений то знову збільшуємо...
а якщо наступний зуб незагострений, то довжина анульовується..
Тобто, якщо буде так ˄∩˄˄˄∩˄ то вийде
довжина присв. 1, потім анульовується, потім присв. 3, потім анульовується, і потім знову присв. 1 Так???
І в мене виходить результат 1, а мені треба 3...

Результат це len чи lenmax?

6

Re: Задача на паскалі

Q-bart написав:

Цей код я так розумію рахує так:
якщо перший зуб загострений, то довжину збільшуємо,
якщо наступний зуб теж загострений то знову збільшуємо...
а якщо наступний зуб незагострений, то довжина анульовується..
Тобто, якщо буде так ˄∩˄˄˄∩˄ то вийде
довжина присв. 1, потім анульовується, потім присв. 3, потім анульовується, і потім знову присв. 1 Так???
І в мене виходить результат 1, а мені треба 3...

Q-bart написав:
for j := i + 1 to n - i do //ось це що таке?

Якщо n=10000, а поточне i=100, то це якийсь цикл від 101 до 9900. Що за число 9900?

quez написав:

Результат це len чи lenmax?

Друге.

7

Re: Задача на паскалі

Обережно, вірний розв'язок на С++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;

    int res = 0;

    vector<int> a(n);
    vector<bool> b(n);

    for (int i = 0; i < n; ++i)
        cin >> a[i];

    for (int i = 0; i < n; ++i)
        if (a[i] >= k)
            b[i] = 1;


    int idx = 0;
    while (idx < n)
    {
        int len = 0;
        while (idx < n && b[idx++])len++;
        res = max(res, len);
    }

    cout << res << endl;
    return 0;
}

p.s. На algotest (система на якій перевіряються олімпіади) пройшов всі 10 тестів.

Подякували: Q-bart1

8

Re: Задача на паскалі

koala написав:
quez написав:

Результат це len чи lenmax?

Друге.

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

Я в курсі, задавав Q-Bart’у наводяще питання.

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

9 Востаннє редагувалося Q-bart (11.12.2014 22:46:03)

Re: Задача на паскалі

Ви маєте на увазі цей кусок  коду..?

for i := 1 to n do 
  begin
    for j := i + 1 to n - i do 
      if a[i] = a[j] then c[i] := c[i] + 1
      else break;
  end;

Пояснюю
n - це к-сть всіх зубів,
Я беру перший зуб a[і] і порівнюю з другим(j:=i+1) тобто a[j]. Якщо дорівнює, я збільшую на одну одиницю елемент в масиві C. Потім перший порівнюю з другим, третім і так далі....

Але тепер, після перерви я побачив що я тут намутив.... Зараз буду перероблювати..

10

Re: Задача на паскалі

Joker написав:

Q-bart, ви приймали участь у міській олімпіаді з програмування цього року?

Так.

11

Re: Задача на паскалі

Joker написав:
Обережно, вірний розв'язок на С++
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int n, k;
    cin >> n >> k;

    int res = 0;

    vector<int> a(n);
    vector<bool> b(n);

    for (int i = 0; i < n; ++i)
        cin >> a[i];

    for (int i = 0; i < n; ++i)
        if (a[i] >= k)
            b[i] = 1;


    int idx = 0;
    while (idx < n)
    {
        int len = 0;
        while (idx < n && b[idx++])len++;
        res = max(res, len);
    }

    cout << res << endl;
    return 0;
}

p.s. На algotest (система на якій перевіряються олімпіади) пройшов всі 10 тестів.

Дякую, але мені тре паскаль....

12

Re: Задача на паскалі

Так.

Ура.
Доречі перші три задачі були якісь надто легкі. Вони заняли лише пів години.
А от останню я зрозумів тільки частково (але думав десь 3 год). і все до чого я дійшов це перші тести і рандом.

Ви рішили четверту?
Ви пройшли далі?

13 Востаннє редагувалося Q-bart (11.12.2014 22:59:56)

Re: Задача на паскалі

Joker написав:

Так.

Ура.
Доречі перші три задачі були якісь надто легкі. Вони заняли лише пів години.
А от останню я зрозумів тільки частково (але думав десь 3 год). і все до чого я дійшов це перші тести і рандом.

Ви рішили четверту?
Ви пройшли далі?

Ну може вам, так як вже давно вчите C++  і перші три дуже легкі але в нас в районі навіть з одинадцятого класу лише 1 чи 2 учні(не пам'ятаю) зробили другу повністю, з всіма тестами(!)
Я зробив лише 1 для всіх тестів, і по 2 бали за інші...
Проте я пройшов на ІІІ етап... Тепер готуюсь, щойно почались канікули... Вже хотів покинути паскаль, але ж нема часу вчити другу мову...

14

Re: Задача на паскалі

Q-bart написав:
Joker написав:

Так.

Ура.
Доречі перші три задачі були якісь надто легкі. Вони заняли лише пів години.
А от останню я зрозумів тільки частково (але думав десь 3 год). і все до чого я дійшов це перші тести і рандом.

Ви рішили четверту?
Ви пройшли далі?

Ну може вам, так як вже давно вчите C++  і перші три дуже легкі але в нас в районі навіть з одинадцятого класу лише 1 чи 2 учні(не пам'ятаю) зробили другу повністю, з всіма тестами(!)
Я зробив лише 1 для всіх тестів, і по 2 бали за інші...
Проте я пройшов на ІІІ етап... Тепер готуюсь, щойно почались канікули... Вже хотів покинути паскаль, але ж нема часу вчити другу мову...

Тобто ми зустрінемося у Львові, тільки у різних категоріях? :)

15

Re: Задача на паскалі

Joker написав:
Q-bart написав:
Joker написав:

Ура.
Доречі перші три задачі були якісь надто легкі. Вони заняли лише пів години.
А от останню я зрозумів тільки частково (але думав десь 3 год). і все до чого я дійшов це перші тести і рандом.

Ви рішили четверту?
Ви пройшли далі?

Ну може вам, так як вже давно вчите C++  і перші три дуже легкі але в нас в районі навіть з одинадцятого класу лише 1 чи 2 учні(не пам'ятаю) зробили другу повністю, з всіма тестами(!)
Я зробив лише 1 для всіх тестів, і по 2 бали за інші...
Проте я пройшов на ІІІ етап... Тепер готуюсь, щойно почались канікули... Вже хотів покинути паскаль, але ж нема часу вчити другу мову...

Тобто ми зустрінемося у Львові, тільки у різних категоріях? :)

Виходить, так...

16

Re: Задача на паскалі

koala написав:

Надмір рухів. Вам треба знайти максимум з множини ланцюжків загострених зубів. Ну так і треба:

for i:=1 to n do begin
  read(a);
  if a > k then //якщо зуб нагострений
    len := len + 1;//довжина ланцюжка збільшується
  else
    len := 0; //інакше занулюється
  if len > lenmax then
    lenmax := len;
end;

Решту самостійно.

Я ще раз перечитав, вдумався і зрозумів.. Надалі запам'ятаю.
Дуже-дуже дякую!!!

17

Re: Задача на паскалі

Q-bart написав:
Joker написав:
Q-bart написав:

Ну може вам, так як вже давно вчите C++  і перші три дуже легкі але в нас в районі навіть з одинадцятого класу лише 1 чи 2 учні(не пам'ятаю) зробили другу повністю, з всіма тестами(!)
Я зробив лише 1 для всіх тестів, і по 2 бали за інші...
Проте я пройшов на ІІІ етап... Тепер готуюсь, щойно почались канікули... Вже хотів покинути паскаль, але ж нема часу вчити другу мову...

Тобто ми зустрінемося у Львові, тільки у різних категоріях? :)

Виходить, так...

Круто!!!
От тільки, що важкого у тих задачах?
1) перевірка на парні і непарні числа.
2) просто на реалізацію
3) чиста геометрія, знати одун формулу відстані на площині
4) от тут я сам нічо мудрого не придумав.

18

Re: Задача на паскалі

1) зробив.
2) реалізація - те чого не вистачає
3) чисто геометрично я її легко зробив би, але та ж реалізація...
4) не знаю.. але я чув (від вчителів) що на олімпіадах, часто дають щось про "теорію графів", в неті пробував гуглити - толком нічого не зрозумів, щось про площину.. Може воно тут теж до чогось..

2, 3 - Ви вже просто вивчили повністю C++ і цієї реалізації достатньо повністю.. А коли я з паскалем(який поглиблено почав вчити тільки на початку цього року) ... Ця ж третя - легка здається коли числа, - а коли змусити комп'ютер рахувати за тебе це вже треба тих навичок в мові програмування...

19 Востаннє редагувалося Joker (11.12.2014 23:35:05)

Re: Задача на паскалі

Ну буває багато на що.
Я якраз вчу графи.
Перед тим вивчив довгу арифметику, префіксні суми, динаміку.

Все це часто буває, вітаю бро :)

Можливо знадобиться:
http://codeforces.ru
http://www.e-olimp.com

Подякували: Q-bart, Torbins, leofun013

20

Re: Задача на паскалі

Ну і звісно ж алгоритми:
http://e-maxx.ru/algo/

Ще є одна дуже крута книжка, але я загубив десь її (

Подякували: Q-bart, Torbins, leofun013