Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

RGB7470 - Ижил хос

Модны зангилаан дээр байх (a,b) хосыг дараах нөхцөл хангаж байвал ижил хос гэе.

 1. a зангилаа нь b зангилааны өвөг дээдэс

 2. abs(a - b) <= k.

Зангилаанууд нь 1,2,. . .,n гэсэн зүүлттэй модон дахь ижил хосын тоог олно уу.

Зурагт өгөгдсөн модны хувьд:

image

дараах өвөг дээдэс болон үр удмын хосууд гарна.

Pair             abs(a-b)                       Pair             abs(a-b)

1,2              1                                      3,4              1

1,3              2                                      3,5              2

1,4              3                                      3,6              3

1,5              4

1,6              5

Хэрэв k=3 гэж өгвөл abs(a-b) <= 3 нөхцөл хангах ижил хос 6 гарах нь.

Фунцийн тодорхойлолт

Доорх редакторын цонхонд similarPair функцийг гүйцээн бичнэ үү. Энэ функц шалгуурт нийцэж буй хосын тоог илэрхийлэх ганц бүхэл тоог буцаана.

similarPair дараах параметрүүдтэй.

n: зангилааны тоог илэрхийлэх бүхэл тоо

k: өгсөн бүхэл тоо

edges: хоорондоо холбогдсон зангилааны зүүлтийг илэрхийлдэг хоёр бүхэл тооноос бүрдэх элемент бүхий хоёр хэмжээст массив.

Оролтын хэлбэр

Эхний мөрөнд зайгаар тусгаарлагдсан n ба k хоёр бүхэл тоо өгөгдөнө. Энд n нь зангилааны тоо, k нь ижил хосын босго юм.

Дараагийн n-1 мөрд хос тоонууд зайгаар тусгаарлан өгөгдөнө. Энэ нь p[i], c[i] ирмэгтэй гэдгийг илэрхийлэх бөгөөд

p[i] нь эцэг зангилааны зүүлт бол c[i]  нь хүү зангилааны зүүлт юм.

Зааглалт

  • 1 <= n <= 10^5
  • 1 <= k <= n
  • 1 <= p[i] ,c[i] <= n

Гаралтын хэлбэр

Ижил хосын тоог илэрхийлэх ганц бүхэл тоо байна.

Жишээ

Оролт

 5 2

3 2

3 1

1 4

1 5

Гаралт

4

Тайлбар

image

Нөхцөл хангах ижил хосууд (3,2), (3,1), (3,4), (3,5) байх учраас хариулт 4 юм.

(1,4), (1,5) хосууд байгаа боловч abs(a-b) <= k нөхцөлийг k=2 үед хангахгүй.


Орчуулсан : Р.Мижиддорж МУБИС, доктор


Нэмсэн:Bataa
Огноо:2020-04-14
Хугацааны хязгаарлалт:1s
Эх кодын хэмжээний хязгаарлалт:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Програмчлалын хэлүүд:ADA95 ASM32 ASM64 BASH BF C NCSHARP CSHARP C++ 4.3.2 CPP C99 CLPS LISP sbcl LISP clisp D ERL FORTRAN HASK ICON ICK JAVA JS-RHINO JULIA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON PYPY3 PYTHON3 RUBY SCALA SCM guile ST TCL WHITESPACE
Эх сурвалж:https://www.hackerrank.com/challenges/similarpair/problem

hide comments
2024-05-08 10:38:03
amarhan ymaa
2024-03-06 03:37:55
import pygame
import time
import random

pygame.init()

# Define colors
white = (255, 255, 255)
yellow = (255, 255, 102)
black = (0, 0, 0)
red = (213, 50, 80)
green = (0, 255, 0)
blue = (50, 153, 213)

# Set display dimensions
dis_width = 800
dis_height = 600

# Define size of snake block and speed
snake_block = 10
snake_speed = 30

# Create display
dis = pygame.display.set_mode((dis_width, dis_height))
pygame.display.set_caption('Snake Game')

clock = pygame.time.Clock()

font_style = pygame.font.SysFont(None, 50)


def message(msg, color):
mesg = font_style.render(msg, True, color)
dis.blit(mesg, [dis_width / 6, dis_height / 3])


def gameLoop():
game_over = False
game_close = False

x1 = dis_width / 2
y1 = dis_height / 2

x1_change = 0
y1_change = 0

snake_list = []
length_of_snake = 1

foodx = round(random.randrange(0, dis_width - snake_block) / 10.0) * 10.0
foody = round(random.randrange(0, dis_height - snake_block) / 10.0) * 10.0

while not game_over:

while game_close == True:
dis.fill(blue)
message("You Lost! Press Q-Quit or C-Play Again", red)
pygame.display.update()

for event in pygame.event.get():
if event.type == pygame.KEYDOWN:
if event.key == pygame.K_q:
game_over = True
game_close = False
if event.key == pygame.K_c:
gameLoop()

for event in pygame.event.get():
if event.type == pygame.QUIT:
game_over = True
if event.type == pygame.KEYDOWN:
if event.key == pygame.K_LEFT:
x1_change = -snake_block
y1_change = 0
elif event.key == pygame.K_RIGHT:
x1_change = snake_block
y1_change = 0
elif event.key == pygame.K_UP:
y1_change = -snake_block
x1_change = 0
elif event.key == pygame.K_DOWN:
y1_change = snake_block
x1_change = 0

if x1 >= dis_width or x1 < 0 or y1 >= dis_height or y1 < 0:
game_close = True
x1 += x1_change
y1 += y1_change
dis.fill(blue)
pygame.draw.rect(dis, green, [foodx, foody, snake_block, snake_block])
snake_head = []
snake_head.append(x1)
snake_head.append(y1)
snake_list.append(snake_head)
if len(snake_list) > length_of_snake:
del snake_list[0]

for x in snake_list[:-1]:
if x == snake_head:
game_close = True

for segment in snake_list:
pygame.draw.rect(dis, black, [segment[0], segment[1], snake_block, snake_block])

pygame.display.update()

if x1 == foodx and y1 == foody:
foodx = round(random.randrange(0, dis_width - snake_block) / 10.0) * 10.0
foody = round(random.randrange(0, dis_height - snake_block) / 10.0) * 10.0
length_of_snake += 1

clock.tick(snake_speed)

pygame.quit()
quit()


gameLoop()
2023-10-28 06:33:30
gay

Last edit: 2023-10-28 06:33:40
2023-10-28 06:33:30
wtf
2023-03-26 14:42:19
#include <iostream>
#include <unordered_map>
#include <vector>
#include <cmath>

using namespace std;

int k;
int counter = 0;

void getPairCount(unordered_map<int, vector<int>>);
void recurse(unordered_map<int, vector<int>>, int, int);

int main() {
int n;
unordered_map<int, vector<int>> nodeMap;

cin >> n >> k;

for (int i = 0; i < n - 1; i++) {
int key;
int child;
cin >> key >> child;

nodeMap[key].push_back(child);
}

getPairCount(nodeMap);

cout << counter;
}

void getPairCount(unordered_map<int, vector<int>> nodeMap) {
for(auto pair : nodeMap) {
recurse(nodeMap, pair.first, pair.first);
}
}

void recurse(unordered_map<int, vector<int>> nodeMap, int ancestor, int parent) {
for(auto value : nodeMap[parent]) {
if(abs(ancestor - value) <= k)
counter++;
recurse(nodeMap, ancestor, value);
}
}

Source code by JacKeR*
2022-12-05 04:13:17
bro wtf is dis shi
2022-03-30 10:24:55
oke
2020-11-26 13:01:24
EZEZ
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.