dima and guards

简介: dima and guards


 

 

A - Dima and Guards

Time Limit:1000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u

Submit Status

Description

Nothing has changed since the last round. Dima and Inna still love each other and want to be together. They've made a deal with Seryozha and now they need to make a deal with the dorm guards...

There are four guardposts in Dima's dorm. Each post contains two guards (in Russia they are usually elderly women). You can bribe a guard by a chocolate bar or a box of juice. For each guard you know the minimum price of the chocolate bar she can accept as a gift and the minimum price of the box of juice she can accept as a gift. If a chocolate bar for some guard costs less than the minimum chocolate bar price for this guard is, or if a box of juice for some guard costs less than the minimum box of juice price for this guard is, then the guard doesn't accept such a gift.

In order to pass through a guardpost, one needs to bribe both guards.

The shop has an unlimited amount of juice and chocolate of any price starting with 1. Dima wants to choose some guardpost, buy one gift for each guard from the guardpost and spend exactlyn rubles on it.

Help him choose a post through which he can safely sneak Inna or otherwise say that this is impossible. Mind you, Inna would be very sorry to hear that!

Input

The first line of the input contains integer n (1 ≤ n ≤ 105) — the money Dima wants to spend. Then follow four lines describing the guardposts. Each line contains four integers a, b, c, d (1 ≤ a, b, c, d ≤ 105) — the minimum price of the chocolate and the minimum price of the juice for the first guard and the minimum price of the chocolate and the minimum price of the juice for the second guard, correspondingly.

Output

In a single line of the output print three space-separated integers: the number of the guardpost, the cost of the first present and the cost of the second present. If there is no guardpost Dima can sneak Inna through at such conditions, print -1 in a single line.

The guardposts are numbered from 1 to 4 according to the order given in the input.

If there are multiple solutions, you can print any of them.

Sample Input

Input

10
5 6 5 6
6 6 7 7
5 8 6 6
9 9 9 9

Output

1 5 5

Input

10
6 6 6 6
7 7 7 7
4 4 4 4
8 8 8 8

Output

3 4 6

Input

5
3 3 3 3
3 3 3 3
3 3 3 3
3 3 3 3

Output

-1

Hint

Explanation of the first example.

The only way to spend 10 rubles to buy the gifts that won't be less than the minimum prices is to buy two 5 ruble chocolates to both guards from the first guardpost.

Explanation of the second example.

Dima needs 12 rubles for the first guardpost, 14 for the second one, 16 for the fourth one. So the only guardpost we can sneak through is the third one. So, Dima can buy 4 ruble chocolate for the first guard and 6 ruble juice of the second guard.

 

 

 

 

题目分析:意思是第一行  n是dima愿意花费的钱

接下来有四个门,每个门有两个守卫,每个守卫分别接收的贿赂最低价是xx(巧克力)和xx(果汁)

你的任务是按顺序找出第一个能贿赂过关的门卫,输出是几个,和第一个门卫需要花的钱和第二个门卫需要花的钱(第二个门卫的钱就是中钱减去第一个花的)。如果没有成功输出-1

 

 

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iostream>
#define INF 0x3f3f3f3f
using namespace std;
int main()
{
  int money;
  int a[5][5];
  while(~scanf("%d",&money))
  {
    for(int i=1;i<=4;i++)
      for(int j=1;j<=4;j++)
        scanf("%d",&a[i][j]);
    int first,second;
    int ans=0;
    for(int i=1;i<=4;i++)
    {
        first=min(a[i][1],a[i][2]);
        second=min(a[i][3],a[i][4]);
        if(first+second<=money)
        {
          ans=i;
          break;
        } 
    }
    if(ans)
      printf("%d %d %d\n",ans,first,money-first);
    else printf("-1\n");  
  }
  return 0;
 }  

 

 

 

 

 

 

 

目录
相关文章
|
人工智能 搜索推荐 调度
AI与教育的发展趋势
【8月更文挑战第4天】AI与教育的发展趋势
258 3
|
Oracle Java 关系型数据库
Java官网下载JDK21版本详细教程(下载、安装、环境变量配置)
Java官网下载JDK21版本详细教程(下载、安装、环境变量配置)
|
Java Apache Spring
Java发送Http请求(HttpClient)
Java发送Http请求(HttpClient)
12279 2
|
算法 Oracle Java
一文详解|从JDK8飞升到JDK17,再到未来的JDK21
本文深入浅出地解析了从JDK8到JDK17版本升级的新特性,并展望后续将会更新的JDK21.
10986 8
|
监控 网络协议 数据安全/隐私保护
运用自定义协议设计与实现“跨网络计算器”
运用自定义协议设计与实现“跨网络计算器”
121 3
|
Oracle 安全 Java
JDK收费的各个版本(记录一下)
JDK收费的各个版本(记录一下)
12677 1
|
人工智能 运维 Cloud Native
智库观察|企业全生命周期数字化路径追探
数智化不仅仅是技术,它还为企业进行组织、生产、贸易和创新提供了新的途径,驱动企业生产方式、组织架构和商业模式发生深刻变革。企业正在经历一次全生命周期的数智跃迁。
866 0
智库观察|企业全生命周期数字化路径追探
|
存储 人工智能 安全
阿里云oss简介和如何对接使用
阿里云对象存储服务(Alibaba Cloud Object Storage Service,简称OSS)是阿里云提供的一种安全、稳定、高效的对象存储服务。它支持多元数据存储、持久化存储和共享访问,并且具有无限的扩展性和备份恢复能力。阿里云OSS适用于各类场景,如云计算、大数据分析、人工智能等,并且具备高可用性、高可扩展性和低成本等优势。
13378 2
|
Java Windows
JDK17 || JDK 8 完美 卸载 教程 (Windows版) 完整指南:卸载JDK17和JDK8,并安装新版JDK
JDK17 || JDK 8 完美 卸载 教程 (Windows版) 完整指南:卸载JDK17和JDK8,并安装新版JDK
4249 0
|
分布式计算 Hadoop Linux
Docker 上部署一主两从Hadoop集群 | [Centos7](上)
写在前面 配置前须知 集群规划 step0 可能会遇到的问题及解决方式 step1 开启docker拉取镜像 step2 创建容器 step3 免密登录配置 1. ip查看 2. 设置主机名 3. 主机名与ip地址映射 4. 免密登录 5. 免密登录效果 ***bug fix1.0 /etc/hosts修改完成后重
760 0
Docker 上部署一主两从Hadoop集群 | [Centos7](上)