精進

勉強したこととか

Codeforces 235 Division2

AとCが通った.Bは終了直前まで正しく問題文理解できてなくて間に合わなかった.

A - Vanya and Cards

http://codeforces.com/contest/401/problem/A

概要

1000以下の正整数nとx,絶対値がx以下の整数がn個与えられる.
そのn個の数の和に絶対値がx以下の整数を加えて0にしようとするとき,最小で何個の整数を加えれば良いか求めよ.

解法

入力の合計値の絶対値をxで何回引くと0以下になるか数えた.
単にxで割ったのを切り上げれば良いのに終了後に気づいた.

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <functional>
#include <set>

using namespace std;

int main()
{
	int n,x,sum;
	cin>>n>>x;
	sum=0;

	for(int i=0;i<n;i++){
		int tmp;
		cin>>tmp;
		sum+=tmp;
	}

	sum=abs(sum);
	int res=0;

	while(sum>0){
		sum-=x;
		res++;
	}

	cout<<res<<endl;

	return 0;
}

C - Team

http://codeforces.com/contest/401/problem/C

概要

n個の0とm個の1を用いて,0は2つ以上並ばず,1は3つ以上並ばない数列を作れるか.
作れるならばそれを,作れないならば-1を出力せよ.

解法

数列中に現れる"0"の数,"1"の数,"11"の数について連立方程式を立て,全てが正の解が得られれば,"0","1","11"を適切に並べたものが解となる.
解のパターンとしては,

  • "0"で始まり"0"で終わる
  • "0"で始まり"1"か"11"で終わる("1"か"11"で始まり"0"で終わる)
  • "1"か"11"で始まり"1"か"11"で終わる.

が考えられるので,全てのパターンでダメならば-1を出力する.
提出したコードだと落ちるケースがあるような気がするけど通った.

#include <iostream>
#include <string>
#include <vector>
#include <cmath>
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <cstdio>
#include <functional>
#include <set>

using namespace std;

int main()
{
	long long zero,one;
	cin>>zero>>one;

	long long a,b;
	if(one-zero>=0 && 2*zero-one>=0){
		a=2*zero-one; b=one-zero;

//		cout<<"case1"<<endl;

		for(long long i=0;i<a;i++) cout<<0<<1;
		for(long long i=0;i<b;i++) cout<<0<<11;
		cout<<endl;
	}
	else if(one-zero+1>=0 && 2*zero-one-2>=0){
		a=2*zero-one-2; b=one-zero+1;

//		cout<<"case2"<<endl;

		for(long long i=0;i<a;i++) cout<<0<<1;
		for(long long i=0;i<b;i++) cout<<0<<11;
		cout<<0<<endl;
	}
	else if(one-zero-1>=0 && 2*zero-one+2>=0){
		a=2*zero-one+2; b=one-zero-1;

//		cout<<"case3"<<endl;

/*
提出時(AC)
		if(a>zero){
			for(long long i=0;i<a-1;i++) cout<<1<<0;
			for(long long i=0;i<b;i++) cout<<11<<0;
			cout<<1<<endl;
		}else{
			for(long long i=0;i<a;i++) cout<<1<<0;
			for(long long i=0;i<b-1;i++) cout<<11<<0;
			cout<<11<<endl;
		}
*/

		for(long long i=0;i<a-1;i++) cout<<1<<0;
		for(long long i=0;i<b-1;i++) cout<<11<<0;

		if(a==0) cout<<11<<endl;
		else if(b==0) cout<<1<<endl;
		else cout<<1101<<endl;

	}
	else{
		cout<<-1<<endl;
	}
	return 0;
}

結果

oxo-- = 1404pts, 1102nd/2691,
Rating:1341->1382(+41)