P3528 [POI2011]PAT-Sticks

    • 50通过
    • 142提交
  • 题目提供者 洛谷
  • 评测方式 云端评测
  • 标签 枚举,暴力 贪心 POI 2011 Special Judge 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Little Johnny was given a birthday present by his grandparents.

    This present is a box of sticks of various lengths and colours.

    Johnny wonders if there are three sticks in the set he has been given that would form a triangle with different-coloured sides.

    Let us note that Johnny is interested in non-degenerate triangles only, i.e., those with positive area.

    给你每根木棍的长度和颜色,求一个能拼成三角形且木棍颜色互不相同的方案

    输入输出格式

    输入格式:

    In the first line of the standard input an integer $k$ ($3\le k\le 50$) is given, which is the number of different colours of sticks.

    The colours themselves are numbered from $1$ to $k$.

    The following $k$ lines contain descriptions of the sticks of particular colours.

    The line no. $i+1$ holds integers that describe the sticks of colour $i$,separated by single spaces.

    The first of these numbers, $n_i$ ($1\le n_i\le 1\ 000\ 000$), denotes the number of sticks of colour $i$.

    It is followed, in the same line, by $n_i$ integers denoting the lengths of the sticks of colour $i$.All lengths are positive and do not exceed $1\ 000\ 000\ 000$.Furthermore, the total number of all sticks does not exceed $1\ 000\ 000$.

    输出格式:

    Your program should print (on the first and only line of the standard output) either:

    six integers, separated by single spaces, that describe the construction of a triangle with different-coloured sides as follows:

    the colour and the length of the first stick, the colour and the length of the second stick, and the colour and the length of the third stick, or the word NIE (Polish for no) if no such triple of sticks exists.

    If there are multiple triples of different-coloured sticks that give rise to a triangle, your program may pick one such triple arbitrarily.

    输入输出样例

    输入样例#1: 复制
    4
    1 42
    2 6 9
    3 8 4 8
    1 12
    输出样例#1: 复制
    3 8 4 12 2 9

    说明

    给你每根木棍的长度和颜色,求一个能拼成三角形且木棍颜色互不相同的方案

    由@zhouyonglong提供SPJ

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。